Fun project - faster associative array algorithm

[Dejan Lekic via Digitalmars-d]

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.