Fun project - faster associative array algorithm

Andrei Alexandrescu via Digitalmars-d digitalmars-d at puremagic.com
Tue Apr 7 15:14:46 PDT 2015


On 4/7/15 10:24 AM, 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.

Arrays would need to move data. Current hashtables rely on values 
staying put. -- Andrei



More information about the Digitalmars-d mailing list