Fun project - faster associative array algorithm

w0rp via Digitalmars-d digitalmars-d at puremagic.com
Tue Apr 7 11:04:57 PDT 2015


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!"


More information about the Digitalmars-d mailing list