maintenance of hash tables.
mohangupta13
This may sound pretty basic but still I have this doubt.
It is know that to maintain the constant time operations in a hash
table the number of elements in the table should be proportional to
the slots in the table.
But I have seen in a lot many places that to maintain this, whenever
the number of elements in a hash table reach half the table size ,the
size of the table is doubled.
Why this factor of 2 (only) is chosen most of the time??
I believe it must have to do something relating to statistics but can
I get a solid theoretical explanation for the same.
Thanks a lot
Mohan Gupta
Pascal J. Bourguignon
> hello everyone,
> This may sound pretty basic but still I have this doubt.
> It is know that to maintain the constant time operations in a hash
> table the number of elements in the table should be proportional to
> the slots in the table.
> But I have seen in a lot many places that to maintain this, whenever
> the number of elements in a hash table reach half the table size ,the
> size of the table is doubled.
>
> Why this factor of 2 (only) is chosen most of the time??
The numerical value of the factor doesn't import much. What import is
that it be a _factor_. That is that the increasing or decreasing of
the size of the hash table be geometrical. This way, the _amortized_
complexity can remain proportional to the number of elements.
> I believe it must have to do something relating to statistics but can
> I get a solid theoretical explanation for the same.
Imagine you have a vector, and you keep inserting elements, from slot
0 up. When you reach the end of the vector, you allocate a new vector
twice the size, therefore you have to copy all the old elements before
inserting the new element. Count the number of copies you have to do
to fill a vector of N elements when you start from a vector of size 1:
size insert allocate new vector copies total copies
1 slot 0 no 0 0
1 slot 1 yes 1 1
2 slot 2 yes 2 3
4 slot 3 no 0 3
4 slot 4 yes 4 7
8 slot 5 no 0 7
8 slot 6 no 0 7
8 slot 7 no 0 7
8 slot 8 yes 8 15
16 slot 9 no 0 15
16 slot 10 no 0 15
16 slot 11 no 0 15
16 slot 12 no 0 15
16 slot 13 no 0 15
16 slot 14 no 0 15
16 slot 15 no 0 15
16 slot 16 yes 16 31
32 slot 17 no 0 31
32 slot 18 no 0 31
...
32 slot 31 no 0 31
32 slot 32 yes 32 63
64 slot 33 no 0 63
...
64 slot 63 no 0 63
So you can see that to insert 64 elements, from slot 0 to slot 63, you
need to make only 63 copies (and of course, 64 initial insertions):
inserting is O(N).
You can get the same result if you _multiply_ the size by 1.5, or 3 or
any other factor.
On the other hand, notice how much copying is done while the size of
the vector is less than 8. That's the reason why it's often take as
the minimum size for extensible vectors or hash-tables.
--
__Pascal Bourguignon__
Andrew Tomazos
wrote:
> So you can see that to insert 64 elements, from slot 0 to slot 63, you
> need to make only 63 copies (and of course, 64 initial insertions):
> inserting is O(N).
You mean O(1), not O(N).
-Andrew.
Andrew Tomazos
> hello everyone,
> This may sound pretty basic but still I have this doubt.
> It is know that to maintain the constant time operations in a hash
> table the number of elements in the table should be proportional to
> the slots in the table.
> But I have seen in a lot many places that to maintain this, whenever
> the number of elements in a hash table reach half the table size ,the
> size of the table is doubled.
>
> Why this factor of 2 (only) is chosen most of the time??
Look at this diagram:
-A
-BB
-
-CCCC
-
-
-
-DDDDDDDD
-
-
-
-
-
-
-
Now look what happens when I let the towers hang down:
-A
-B
-B
-C
-C
-C
-C
-D
-D
-D
-D
-D
-D
-D
-D
Enjoy,
Andrew.
Pascal J. Bourguignon
Yes of course. Sorry for the typo.
--
__Pascal Bourguignon__
cr88192
"mohangupta13" <mohang...@gmail.com> wrote in message
news:fc625db7-f59c-4fca...@g23g2000vbr.googlegroups.com...
well, it has to do a lot with the expected growth rate...
2 is a very simple expansion, and with a power-of-2 sized table, can keep
the size a power of 2. this can likely allow the use of a mask to keep the
hash-index in the range of the table (vs a more expensive modulo).
however, more often for table expansions, ... I use a factor of 1.5, since
as I see it, this is more often a much closer fit to the natural growth
pattern.
it may also depend a lot on whose code one is looking at...
mohangupta13
wrote:
Well , thank you for such a nice explanation .
> You can get the same result if you _multiply_ the size by 1.5, or 3 or
> any other factor.
>
so why don't we instead use 1.5 as a preferred factor as it may waste
little space as compared to a case using factor 2.
mohangupta13
> "mohangupta13" <mohangupt...@gmail.com> wrote in message
>
> news:fc625db7-f59c-4fca...@g23g2000vbr.googlegroups.com...
>
> > hello everyone,
> > This may sound pretty basic but still I have this doubt.
> > It is know that to maintain the constant time operations in a hash
> > table the number of elements in the table should be proportional to
> > the slots in the table.
> > But I have seen in a lot many places that to maintain this, whenever
> > the number of elements in a hash table reach half the table size ,the
> > size of the table is doubled.
>
> > Why this factor of 2 (only) is chosen most of the time??
>
> > I believe it must have to do something relating to statistics but can
> > I get a solid theoretical explanation for the same.
>
> well, it has to do a lot with the expected growth rate...
>
> 2 is a very simple expansion, and with a power-of-2 sized table, can keep
> the size a power of 2. this can likely allow the use of a mask to keep the
> hash-index in the range of the table (vs a more expensive modulo).
>
mask-ing method to calculate hash-table index values.(As i always use
the so called more expensive modulo )
Pascal J. Bourguignon
>> You can get the same result if you _multiply_ the size by 1.5, or 3 or
>> any other factor.
>>
> so why don't we instead use 1.5 as a preferred factor as it may waste
> little space as compared to a case using factor 2.
In binary computers, it's easier to multiply by 2 or to divide/modulo
by 2, since you only need to shift bits or mask them out.
On the other hand, using a factor less than 2 would allow you to
better fill the memory.
--
__Pascal Bourguignon__
Andrew Tomazos
> > 2 is a very simple expansion, and with a power-of-2 sized table, can keep
> > the size a power of 2. this can likely allow the use of a mask to keep the
> > hash-index in the range of the table (vs a more expensive modulo).
>
> Can you please elaborate a bit more on what you actually mean by the
> mask-ing method to calculate hash-table index values.(As i always use
> the so called more expensive modulo )
One way to calculate x mod 2^k is:
int modp2_slow(int x, int k)
{
return x % pow(2,k);
}
A faster way is:
int modp2_fast(int x, int k)
{
return x & ((1 << k) - 1);
}
Here we create a bit mask with the k low bits on, and then use them to
mask (binary AND) the part of the integer that is less than 2^k.
This optimization only works for powers of 2.
-Andrew.
cr88192
"Pascal J. Bourguignon" <p...@informatimago.com> wrote in message
news:87ws6ut...@galatea.local...
yep.
in practice, although divides or modulo operators are a bit more expensive
than masks, typically they are not a significant portion of the overall
performance, so the cost is often reasonable.
> --
> __Pascal Bourguignon__
Andrew Tomazos
> in practice, although divides or modulo operators are a bit more expensive
> than masks, typically they are not a significant portion of the overall
> performance, so the cost is often reasonable.
If we use x86 as an example than a binary and (AND) is approximately
50-100 times faster than a modulus (IDIV). [*]
If the keys are easily hashed (such as numeric types) than a modulus
will be a significant cost associated with the hash function.
-Andrew.
[*] See Intel 64 and IA-32 Architectures Optimization Reference
Manual, Appendix C
cr88192
"Andrew Tomazos" <and...@tomazos.com> wrote in message
news:e2a2fff7-b993-4ddc...@x5g2000yqk.googlegroups.com...
ok...
well, this operation is weighted against:
hashing the string (if a string is used);
various other costs (checking if the spot is free, calculating the next
permutation, ...);
...
so, mod is slow, but in many cases, this can be glossed over some (which is
why I said 'typically'...).
in some cases, there are "faster" ways to approximate division and modulo,
but I am not sure of any that are particularly appropriate in this case. I
may have to check compiler output, and see if it finds some way to optimize
away the idiv...
but, yes, if speed is critical (and/or one is using a highly optimized hash
table), then a power-of-2 size is better...
Pascal J. Bourguignon
In lisp, the default for hash-table is to use the identity of the key
[:test (function eql)]. In this situation, there's no lengthy hash to
compute, just the modulo on the address (or object in case of fixnums
and characters). The way they're specified, it is intended that CL
hash-table do not use collision lists, but have always more slots in a
vector than entries in the hash, so collisions are handled by storing
the colliding entries in adjacent slots. This means that in the worse
case, there's a small number of additionnal EQL comparisons made. As
soon as the hash-table becomes too filled, the vector is extended to
render it sparse again.
So we are comparing: SHIFT + MOD + s AREF + s EQL + CONS + 3 STORE + ADD
vs. DIV + s AREF + s EQL + CONS + 3 STORE + ADD
Basically, all the operations but the firsts are sum up to 5+2s
The default rehash threshold is
#+clisp (hash-table-rehash-threshold (make-hash-table)) -> 0.75s0
so in clisp, s = 4
s = ceiling( 1 + ( rehash-threshold / ( 1 - rehash-threshold ) ) )
so we get 13 steps for them, and we would be comparing 15 steps
vs. 113 steps, about an order of magnitude, for the most used hash
tables.
Unfortunately (or happily), doing Q&D benchmarks on sbcl and clisp on
ix86 dual core, I observe a much smaller ratio between TRUNCATE and +
on fixnums... (about 1.3 in sbcl, and 17 in clisp).
(let ((a (random most-positive-fixnum))
(b (random most-positive-fixnum))
(r 10000000))
(macrolet ((test (expression)
`(funcall (compile nil (lambda ()
(print ',expression)
#+clisp (ext:gc) #+sbcl (SB-EXT:GC)
(time (loop repeat r do ,expression)))))))
(list
(test (progn))
(test (truncate a b))
(test (+ a b)))))
--
__Pascal Bourguignon__
cr88192
<snip>
I am not sure how this is directly related, or what exactly is trying to be
argued here...
but, I guess it can be noted that LISP is its own set of issues...
but, I guess the core issue is that, yes, mod (and div) are a bit slower
than shifts or masks, but in many cases, it is not noticable (the weight of
everything else often compensates enough that there is not as much worry
over the number of clock cycles taken for particular instructions...).
of course, a mod is often slower than a conditional, which says something...
however, given a typical hash operation may involve several conditionals in
a row (is spot empty? is spot the wanted value? is the loop finished? ...),
the mod is no longer the big killer (especially if the value check is a
'strcmp'...).
but, alas, if we are looking up based on a pointer-address or integer (no
strcmp, ...), this mod may be significant, and it may well be worthwhile to
use a power-of 2 table...
of course, as a matter of practice I tend to keep all fixed-size tables as
powers of 2, as after all, it is not useful to waste time unnecessarily...
or such...
Ira Baxter
"cr88192" <cr8...@hotmail.com> wrote in message
news:h2jr05$vmv$1...@news.albasani.net...
>
> "Andrew Tomazos" <and...@tomazos.com> wrote in message
> news:e2a2fff7-b993-4ddc...@x5g2000yqk.googlegroups.com...
> On Jun 30, 5:10 pm, "cr88192" <cr88...@hotmail.com> wrote:
>> in practice, although divides or modulo operators are a bit more
>> expensive
>> than masks, typically they are not a significant portion of the overall
>> performance, so the cost is often reasonable.
>
> <
> If we use x86 as an example than a binary and (AND) is approximately
> 50-100 times faster than a modulus (IDIV). [*]
>
> If the keys are easily hashed (such as numeric types) than a modulus
> will be a significant cost associated with the hash function.
> -Andrew.
>
> [*] See Intel 64 and IA-32 Architectures Optimization Reference
> Manual, Appendix C
You can choose pretty much any constant modulus you want and still get
the remainder quickly by multiplying by the appropriately scaled
reciprocal of the constant. I think the IA-32/64 manuals describe how
how to do this. The multiply can often be implemented by (astonishing)
sequences of
shift, add, subtract and LEA used to multiply by 3,5 or 9 and add.
We do this in a compiled symbolic language and it is quite fast.
-- IDB
Andrew Tomazos
> > If we use x86 as an example than a binary and (AND) is approximately
> > 50-100 times faster than a modulus (IDIV). [*]
>
> > If the keys are easily hashed (such as numeric types) than a modulus
> > will be a significant cost associated with the hash function.
> > -Andrew.
>
> > [*] See Intel 64 and IA-32 Architectures Optimization Reference
> > Manual, Appendix C
>
> You can choose pretty much any constant modulus you want and still get
> the remainder quickly by multiplying by the appropriately scaled
> reciprocal of the constant. I think the IA-32/64 manuals describe how
> how to do this. The multiply can often be implemented by (astonishing)
> sequences of shift, add, subtract and LEA used to multiply by 3,5 or 9 and add.
> We do this in a compiled symbolic language and it is quite fast.
I am skeptical about your claim because even in optimized code (gcc,
msvc) an IDIV is generated to implement modulus. If there exists some
faster technique for moding by an arbitrary constant, than why
wouldn't this be used in the CPU or in the optimizing compiler?
Can you provide example code of the technique you describe?, or a link
to it?, or provide a reference to which of the IA-32/64 manuals/
chapter this technique is described in?
Thanks,
Andrew.
Andrew Tomazos
...here is GCC -O2 of the following:
int m(int x, int y)
{
return x % y;
}
compiles to:
...
sarl $31, %edx
idivl 12(%ebp) // see, IDIV is used
...
You claim to have a faster implementation of this function? No
offense, but I find that hard to believe.
-Andrew.
Ben Bacarisse
>> On Jul 3, 9:56 pm, "Ira Baxter" <idbax...@semdesigns.com> wrote:
>> > > If we use x86 as an example than a binary and (AND) is approximately
>> > > 50-100 times faster than a modulus (IDIV). [*]
>>
>> > > If the keys are easily hashed (such as numeric types) than a modulus
>> > > will be a significant cost associated with the hash function.
>> > > -Andrew.
>>
>> > > [*] See Intel 64 and IA-32 Architectures Optimization Reference
>> > > Manual, Appendix C
>>
>> > You can choose pretty much any constant modulus you want and
Note "constant".
>> > still get the remainder quickly by multiplying by the
>> > appropriately scaled reciprocal of the constant. I think the
>> > IA-32/64 manuals describe how how to do this. The multiply can
>> > often be implemented by (astonishing) sequences of shift, add,
>> > subtract and LEA used to multiply by 3,5 or 9 and add. We do
>> > this in a compiled symbolic language and it is quite fast.
>>
>> I am skeptical about your claim because even in optimized code (gcc,
>> msvc) an IDIV is generated to implement modulus. If there exists some
>> faster technique for moding by an arbitrary constant, than why
>> wouldn't this be used in the CPU or in the optimizing compiler?
>>
>> Can you provide example code of the technique you describe?, or a link
>> to it?, or provide a reference to which of the IA-32/64 manuals/
>> chapter this technique is described in?
>
> ...here is GCC -O2 of the following:
>
> int m(int x, int y)
> {
> return x % y;
> }
>
> compiles to:
>
> ...
> sarl $31, %edx
> idivl 12(%ebp) // see, IDIV is used
> ...
>
> You claim to have a faster implementation of this function? No
> offense, but I find that hard to believe.
gcc does do all sorts of gyrations rather than an idiv if the modulus
is constant.
--
Ben.
dj3v...@csclub.uwaterloo.ca.invalid
Andrew Tomazos <and...@tomazos.com> wrote:
>> On Jul 3, 9:56 pm, "Ira Baxter" <idbax...@semdesigns.com> wrote:
>> > You can choose pretty much any constant modulus you want and still get
^^^^^^^^
>> > the remainder quickly by multiplying by the appropriately scaled
>> > reciprocal of the constant.
^^^^^^^^
>> I am skeptical about your claim because even in optimized code (gcc,
>> msvc) an IDIV is generated to implement modulus. If there exists some
>> faster technique for moding by an arbitrary constant, than why
>> wouldn't this be used in the CPU or in the optimizing compiler?
>>
>> Can you provide example code of the technique you describe?, or a link
>> to it?, or provide a reference to which of the IA-32/64 manuals/
>> chapter this technique is described in?
>
>...here is GCC -O2 of the following:
>
> int m(int x, int y)
> {
> return x % y;
> }
>
>compiles to:
>
> ...
> sarl $31, %edx
> idivl 12(%ebp) // see, IDIV is used
> ...
>
>You claim to have a faster implementation of this function? No
>offense, but I find that hard to believe.
It might help if you actually used a constant. A single division at
runtime tends to be faster than a modular-inverse followed by a
multiplication.
Any odd number has a unique multiplicative inverse in the ring of
integers mod 2^N. If the number you're dividing/modding by is known at
compile time, that inverse can be calculated at compile time, and then
you can use a multiplication instead of a division at run time.
(Even numbers are an easy extension of this, since they're the product
of an odd number and a power of two, and multiplication/division by
powers of two is just shifting.)
gcc -O2 compiles this:
--------
int foo(int x)
{
return x%17;
}
--------
into this:
--------
;...get x from stack into esi...
movl $2021161081, %edx
movl %esi, %eax
imull %edx
sarl $3, %edx
movl %esi, %ecx
sarl $31, %ecx
subl %ecx, %edx
movl %edx, %ecx
sall $4, %ecx
addl %edx, %ecx
subl %ecx, %esi
;...get result from esi into eax to return...
--------
I don't see any divisons there.
dave
--
Dave Vandervies dj3vande at eskimo dot com
Naturally. Whilst I don't claim to be perfect, I am quite accustomed
to being correct. You should try it.
--infobahn in comp.lang.c
Richard Harter
Just as a note, a factor 1.5 doesn't require a divide. In C it is
a one liner, size += (size/2); (If one has a truly archaic
compiler replace the divide by a shift.) At the machine level this
translates into a copy, a shift, and an add. It's more expensive
than doubling, but only slightly.
In linear hashing doubling is preferred and natural; however one
can arrange the code to use an intermediate step of N*1.5. Whether
this is worth doing is open to question.
Richard Harter, c...@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
If I do not see as far as others, it is because
I stand in the footprints of giants.
Andrew Tomazos
> >You claim to have a faster implementation of this function? No
> >offense, but I find that hard to believe.
>
> It might help if you actually used a constant. A single division at
> runtime tends to be faster than a modular-inverse followed by a
> multiplication.
Yes, granted, but the base is not constant. We were talking about
dynamic hash tables where we need mod pow(constant,k):
For the case of 2^k we have:
int modp2_slow(int x, int k)
{
return x % pow(2,k);
}
int modp2_fast(int x, int k)
{
return x & ((1 << k) - 1);
}
For the case of some other base we need:
#define CONSTANT 17
int modpc_slow(int x, int k)
{
return x % pow(CONSTANT,k);
}
int modpc_fast(int x, int k)
{
return ???; // <-- What goes here?
}
Is there a way to implement modpc_fast without using IDIV?
-Andrew.
Andrew Tomazos
> >On the other hand, using a factor less than 2 would allow you to
> >better fill the memory.
>
> Just as a note, a factor 1.5 doesn't require a divide.
Calculating the next size up is not the problem, what I don't
understand is how to mod the hash key by it without using a divide.
-Andrew.
dj3v...@csclub.uwaterloo.ca.invalid
Andrew Tomazos <and...@tomazos.com> wrote:
>On Jul 3, 11:59 pm, dj3va...@csclub.uwaterloo.ca.invalid wrote:
>> >You claim to have a faster implementation of this function? No
>> >offense, but I find that hard to believe.
>>
>> It might help if you actually used a constant. A single division at
>> runtime tends to be faster than a modular-inverse followed by a
>> multiplication.
>
>Yes, granted, but the base is not constant. We were talking about
>dynamic hash tables where we need mod pow(constant,k):
[...]
>For the case of some other base we need:
>
> #define CONSTANT 17
>
> int modpc_slow(int x, int k)
> {
> return x % pow(CONSTANT,k);
> }
>
> int modpc_fast(int x, int k)
> {
> return ???; // <-- What goes here?
> }
>
>Is there a way to implement modpc_fast without using IDIV?
I think so. Precalculate the multiplicative inverses (mod UINT_MAX)
for all the values of k you expect to use (at compile time if
possible), and then you can replace the division with a table lookup
and multiplication.
If CONSTANT and the bounds on k are known at compile time and you don't
mind making the code ugly, you might be able to get the compiler to do
the hard work for you:
--------
int modpc_fast(int x,int k)
{
assert(k>0 && k<5);
switch(k)
{
case 1: return x%CONSTANT;
case 2: return x%(CONSTANT*CONSTANT);
case 3: return x%(CONSTANT*CONSTANT*CONSTANT);
case 4: return x%(CONSTANT*CONSTANT*CONSTANT*CONSTANT);
}
/*not reached*/
abort();
}
--------
You can get a bit more flexibility, at the expense of having to do the
modular inversion at runtime, by recomputing and storing the inverse
when the modulus changes:
--------
static unsigned mod,inv;
void set_mod(unsigned newmod)
{
mod=newmod;
inv=/*compute mod^-1 (mod UINT_MAX)*/;
}
int modpc_fast(unsigned x)
{
unsigned t=x*inv;
return x-(t*mod);
}
--------
Both of these are taking advantage of the fact that you're re-using the
same modulus most of the time, and amortize the cost of the more
expensive setup over the operations that it speeds up. If the modulus
is changing often, you're probably better off just doing an IDIV.
dave
--
Dave Vandervies dj3vande at eskimo dot com
>Are you certified for hazmat?
No official certifications there, so I probably don't want to get anywhere
near spammer remains. --Shmuel Metz and Anthony de Boer in the SDM
Pascal J. Bourguignon
(a mod b) = a - ((a div b) * b)
But in languages such as C, you don't use normal arithmetic, but
arithmetic modulo 2^w, for some bitsize w of your ints (eg. 32).
There exist some q in [0... 2^w-1] such as:
1 = q*b [2^w]
and
a div b = (a * q) [2^w]
For example, for w = 32 and b = 91 we find q = 3539808211
3539808211 * 91 = 1 [ 2^32 ]
So instead of dividing by 91, we can multiply by 3539808211 (modulo
2^32) and we get the same bits, the same result.
--
__Pascal Bourguignon__
Andrew Tomazos
wrote:
Yes, okay, this is true - however we still need to use a lookup table
or a switch (for 1.5^k, about 50 different cases) and use an IMUL (20
times slower than AND).
It is clear that simply using the 2^k optimization of (x & ((1 << k) -
1)) is much more efficient than any of these other methods - hence the
original question of why we use 2^k, and not some other base, is
answered.
-Andrew.
James Dow Allen
$1...@rumours.uwaterloo.ca:
> In article <fba71655-19e0-4d3d-8fdf-7038ab198f84@
24g2000yqm.googlegroups.com>,
> Andrew Tomazos <and...@tomazos.com> wrote:
>>Is there a way to implement modpc_fast without using IDIV?
>
> I think so. Precalculate the multiplicative inverses (mod UINT_MAX)
> for all the values of k you expect to use...
Integer division speed seems important; I just did some
tests whose times are reproduced below (last digit not
significant). This is with gcc version 4.1.2 at 1.87 Ghz.
I tried two divisors: 11 and 3299717 (and a few more
divisors for the code cases of real interest.)
Often, *both* quotient and remainder are needed;
options 3, 7, 15 below deliver both. (Functions like
div(), ldiv() are provided, presumably to get both quotient
and remainder "for the price of one", but gcc version 4.1.2
seems to do that optimization only if you *don't* invoke
div(), ldiv() !).
For my hash tables I *do* need both quotient and remainder,
so -O3S 3 & 7 are the relevant entries in the following table,
which (with some additional divisor values) are
DIVISOR=11 1.78 3.85
DIVISOR=773 1.77 2.97
DIVISOR=77137 1.79 2.17
DIVISOR=771389 1.94 2.15
DIVISOR=3299717 1.90 2.14
Once the divisor is largish, the win from the constant divisor
is smallish, so I guess I won't bother special-casing each
table size (even though I could get by with just several
dozen sizes).
Comments: The constant divisor was converted to
use multiply at any optimization level; every level
except -O0 knew how to get the remainder easily after
getting quotient. -O3 saw that "variable" divisors
were really constants; -O3S is the result when I
separated the source into two modules to circumvent that.
---- constant -- ---- variable --
Div Mod D&M Div Mod D&M div()
1 2 3 5 6 7 15
---------------------------------------------------
DIVISOR=11
-O0 1.81 2.73 3.35 4.14 3.82 7.82 6.41
-O1 1.07 1.40 1.79 3.82 3.82 3.82 5.05
-O2 1.03 1.40 1.79 3.82 3.82 3.82 5.14
-O3S 1.01 1.33 1.78 3.85 3.86 3.85 5.05
-O3 0.53 0.73 1.05 0.53 0.73 1.05 4.11
DIVISOR=3299717
-O0 2.32 2.99 3.95 2.15 2.15 4.61 5.20
-O1 1.27 1.54 1.91 2.16 2.13 2.55 4.32
-O2 1.31 1.48 1.89 2.10 2.17 2.17 4.31
-O3S 1.30 1.49 1.90 2.13 2.19 2.14 4.26
-O3 0.69 0.85 1.20 0.68 0.85 1.20 3.41
James Dow Allen
/****************************************/
#include <stdlib.h>
#include <stdio.h>
#ifndef DIVISOR
#define DIVISOR 11
#endif
long long Dtot, Mtot;
void divmodgen(unsigned int x, unsigned int y)
{ Dtot += x / y; Mtot += x % y; }
void divgen(unsigned int x, unsigned int y)
{ Dtot += x / y; }
void modgen(unsigned int x, unsigned int y)
{ Mtot += x % y; }
void divmodkkk(unsigned int x)
{ Dtot += x / DIVISOR; Mtot += x % DIVISOR; }
void divkkk(unsigned int x)
{ Dtot += x / DIVISOR; }
void modkkk(unsigned int x)
{ Mtot += x % DIVISOR; }
void usediv(unsigned int x, unsigned int y)
{
div_t dt = div(x, y);
Dtot += dt.quot;
Mtot += dt.rem;
}
/* Usage: bit 1 for div, bit 2 for mod, bit 4 for variable */
int main(int argc, char **argv)
{
unsigned int i;
#define LOOP for (i = 0; i < 200000000; i++)
switch (atoi(argv[1])) {
case 1: LOOP divkkk(i); break;
case 2: LOOP modkkk(i); break;
case 3: LOOP divmodkkk(i); break;
case 5: LOOP divgen(i, DIVISOR); break;
case 6: LOOP modgen(i, DIVISOR); break;
case 7: LOOP divmodgen(i, DIVISOR); break;
case 15: LOOP usediv(i, DIVISOR); break;
}
printf("%Ld %Ld\n", Dtot, Mtot);
exit(0);
}
/****************************************/
Andrew Tomazos
wrote:
> dj3va...@csclub.uwaterloo.ca.invalid might have writ, in news:h2m6vm$1ep
> $...@rumours.uwaterloo.ca:
Your posted source is missing the harness script that executes the
application for each case, times them and then presents the tabulated
results. Could you please post that part too so we can reproduce your
results. Thanks, Andrew.
James Dow Allen
ba68-4e81-8fc...@a36g2000yqc.googlegroups.com:
> On Jul 6, 12:40�pm, James Dow Allen <gm...@jamesdowallen.nospam>
> wrote:
>> For my hash tables I *do* need both quotient and remainder,
>> so -O3S 3 & 7 are the relevant entries in the following table,
>> which (with some additional divisor values) are
>> � DIVISOR=11 � � � � 1.78 � �3.85
>> � DIVISOR=773 � � � �1.77 � �2.97
>> � DIVISOR=77137 � � �1.79 � �2.17
>> � DIVISOR=771389 � � 1.94 � �2.15
>> � DIVISOR=3299717 � �1.90 � �2.14
>>
>> Once the divisor is largish, the win from the constant divisor
>> is smallish, so I guess I won't bother special-casing each
>> table size (even though I could get by with just several
>> dozen sizes).
>
> Your posted source is missing the harness script that executes the
> application for each case, times them and then presents the tabulated
> results. Could you please post that part too so we can reproduce your
> results. Thanks, Andrew.
I didn't bother with a script for this once-only test but something
like the following should work, though untested. Sorry: I use csh.
foreach d ( 11 3299717 )
foreach o ( 0 1 2 3 )
cc -DDIVISOR=$d -O$o whatever.c
foreach t ( 1 2 3 5 6 7 15 )
time a.out $t
end
end
end
exit
> and then presents the tabulated results.
It was this that led me to wonder if yours is some sort of sarcasm.
The above script doesn't handle the (important) "-O3S" case.
Assuming you are sincere; just split the
source into two modules.
Jamesd
Andrew Tomazos
wrote:
> > and then presents the tabulated results.
>
> It was this that led me to wonder if yours is some sort of sarcasm.
>
> The above script doesn't handle the (important) "-O3S" case.
> Assuming you are sincere; just split the
> source into two modules.
I am not sure what caused you to think I was being sarcastic. By
"tabulated results", I just meant the table of results you included in
your post. Clearly you didn't execute each case individually and
write up each entry yourself.
To post a csh script you just need to prepend:
#!/bin/csh
Ideally, it would be nice to be able to copy and paste the source code
into two files and then go.
-Andrew.