On Tuesday, 7 April 2015 at 17:25:00 UTC, Walter Bright wrote:
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.
I have already been experimenting with this myself actually. My
hashmap now uses a bucket array with quadratic probing. I was
just following Martin Nowak's advice. My code for it is here.
https://github.com/w0rp/dstruct/blob/master/source/dstruct/map.d
I have a benchmark program available in my repository for testing
it against the druntime version. It doesn't amaze me at the
moment, as it's slightly faster for integers, and slightly slower
for strings at the moment. I would appreciate any advice on it.
I'm sure someone will look at my code and say, "Noo! Don't do
that!"
