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.
