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
