Honey, I sped up the associated array

[Lionello Lunesu]

Some claim, so numbers first:

As a benchmark, I've used my implementation of the program mentioned in 
the thread "Lisp vs. C++ (not off-topic)", in a critical-priority 
thread. Results are averaged over 8 runs. System: AMD X2 4600+, Windows 
Vista RC1 x64, 1GB.

Old AA: 563ms
New AA: 445ms

The only difference is the indexing. The old AA uses "index = hash % 
prime" whereas the new AA uses "index = (hash * MAGICNUMBER) >>> shift" 
(MAGICNUMBER being a uint constant, 0x9E3779B9 == (sqrt(5) - 1)*(2^31), 
aka golden ration [1]).

The performance of the AA depends also on the size of the underlying 
array, and since the sizes of the two implementations are never the same 
(the old one uses primes, the new one powers of 2) it's impossible to 
find a benchmark that covers all usage cases. But, when comparing only 
the changed lines of codes, the one involving the multiplication and 
shift is twice as fast as the one with the modulo (=division).

Attached, the new src/phobos/internal/aaA.d. To try it out, simply 
overwrite the file and rebuild phobos (make -fwin32.mak). Don't forget 
to copy phobos.lib to the lib folder.

L.

[1] Art of Computer Programming, Donald E. Knuth
-------------- next part --------------
A non-text attachment was scrubbed...
Name: aa_no_mod.zip
Type: application/octet-stream
Size: 5315 bytes
Desc: not available
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20061012/1ab655fe/attachment.obj>