Change AAs to pow of 2 tables

This is a performance tweak for aav.c.

Citing the commit message:

Brings in somewhere in the area of 1-2% increase in speed as measured by
dmd -unittest -c std\algorithm.d
on Linux x64

This closely follows the original prime sizes by using next pow-2 of primes
and reproducing roughly the same grow factor (=4).

Takes into account that key are aligned pointers to strings
and thus need a fair bit-shake to get a decent distribution.


And lastly my measurements with avgtime, see https://github.com/jmcabo/avgtime (neat tool written in D!).
This is on linux x64. Command line is: 
avgtime -d -r 30 dmd -unittest -c std/algorithm.d

dmd_E2 
The current pull, power of 2 tables with extra hashing of keys.

------------------------
Total time (ms): 203185
Repetitions    : 30
Sample mode    : 6750 (6 ocurrences)
Median time    : 6760.67
Avg time       : 6772.83
Std dev.       : 61.7325
Minimum        : 6622.79
Maximum        : 6899.12
95% conf.int.  : [6651.83, 6893.82]  e = 120.994
99% conf.int.  : [6613.81, 6931.84]  e = 159.013
EstimatedAvg95%: [6750.74, 6794.92]  e = 22.0903
EstimatedAvg99%: [6743.79, 6801.86]  e = 29.0316

------------------------
dmd_P3 
Original with primes, but a fix for small tables of 4 items to use better index then 2 lower bits 
or it'd be just a linked list! 
Hardly helps though, could it be that tables of 4 slots ain't that common by the time the storm of lookups comes?

------------------------

Total time (ms): 204673
Repetitions    : 30
Sample mode    : 6810 (5 ocurrences)
Median time    : 6816.01
Avg time       : 6822.43
Std dev.       : 58.3656
Minimum        : 6645.7
Maximum        : 6919.68
95% conf.int.  : [6708.03, 6936.82]  e = 114.394
99% conf.int.  : [6672.09, 6972.77]  e = 150.34
EstimatedAvg95%: [6801.54, 6843.31]  e = 20.8855
EstimatedAvg99%: [6794.98, 6849.88]  e = 27.4482

------------------------
dmd 
Vanila original

------------------------
Total time (ms): 204676
Repetitions    : 30
Sample mode    : 6770 (5 ocurrences)
Median time    : 6826.8
Avg time       : 6822.55
Std dev.       : 61.4625
Minimum        : 6663.03
Maximum        : 6936.67
95% conf.int.  : [6702.08, 6943.01]  e = 120.464
99% conf.int.  : [6664.23, 6980.86]  e = 158.317
EstimatedAvg95%: [6800.55, 6844.54]  e = 21.9937
EstimatedAvg99%: [6793.64, 6851.45]  e = 28.9046

------------------------
> 
> 25 îêò. 2014 ã., â 17:25, Martin Nowak <notifications@github.com> íàïèñàë(à):
> 
> In src/root/aav.c:
> 
> > -static const size_t prime_list[] = {
> > -              31UL,
> > -              97UL,            389UL,
> > -            1543UL,           6151UL,
> > -           24593UL,          98317UL,
> > -          393241UL,        1572869UL,
> > -         6291469UL,       25165843UL,
> > -       100663319UL,      402653189UL,
> > -      1610612741UL,     4294967291UL,
> > -};
> > +
> > +inline size_t hash(size_t a)
> > +{
> > +    a ^= (a >> 20) ^ (a >> 12);
> > +    return a ^ (a >> 7) ^ (a >> 4);
> > +}
> Where does that mix function come from?
> 
Was stolen from some article on what OpenJDK does in its hash map. The trick is since DMD hashes only pointers and thus least significant bits are always zero. Second trick is to mix upper bits with lower bits, since most hash tables are small.

In the same manner Java hashes references.

I can probably dig up original source if needed.

> —
> Reply to this email directly or view it on GitHub.