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.
Every now and then I think how nice it would be for Phobos to be
just a bunch of "module interfaces" along with default
implementations of them. Unfortunately, or fortunately, D does
not have module interfaces like, say, Modula-3. It would make
things much easier for someone who wants to work on a different
implementation of a certain module (or even whole package)
implementation.
I wonder what other people think about this.
