Fun project - faster associative array algorithm

[Walter Bright via Digitalmars-d]

The current D associative array algorithm

     https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d

uses an array of buckets with a linked list attached to the buckets to resolve 
collisions.

Linked lists are perhaps the worst (i.e. slowest) data structure possible on 
modern CPUs with memory caches.

A possible cache-friendly replacement would be an array of buckets with local 
probing to resolve collisions. D programs are often heavily dependent on 
associative arrays, so this could be a big win for us.

And it's a fun project, too. Any takers?



Interestingly,

 
https://github.com/D-Programming-Language/dmd/blob/master/src/root/stringtable.c

uses quadratic probing instead of linked lists, but this is not cache friendly, 
either.