Honey, I sped up the associated array

[Dave]

Lionello Lunesu wrote:
> 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
> 

There were 4 Shootout Benchmark tests using hash tables - one is still active:

http://shootout.alioth.debian.org/gp4/benchmark.php?test=knucleotide&lang=dlang&id=2

Old AA: 1.85
New AA: 1.85

For the three older tests:

hash Old: 2.55
      New: 3.02

hash2 Old: 3.36
       New: 2.88

wordfreq Old: 0.178
          New: 0.170

(These were run as they are/were on the Shootout)

So it's kind-of 6 of one and 1/2 dozen of another for those tests, but your new version sure seems
more elegant!

Based on this and looking at the code for hash.d where the new version doesn't perform as well, it 
looks like the new version has more collisions.. If the getHash() in std/typeinfo/ti_Aa.d could be 
changed to provide a more unique hash w/o being made a lot slower, then I'd think your new version 
would be faster in the general case (at least for char[] AA keys).


> 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