https://issues.dlang.org/show_bug.cgi?id=2504: reserve for associative arrays

[Steven Schveighoffer via Digitalmars-d]

On 11/1/16 11:36 PM, Andrei Alexandrescu wrote:
> Our student Alex has been looking at this and I wanted to open the floor
> for a bit of discussion before we embark on an implementation.
>
> Last time I looked our associative arrays were arrays of singly-linked
> lists. It follows that in order to implement reserve() we'd need a
> freelist allocator approach, which preallocates a bunch of nodes in a
> single contiguous block of memory.

They have changed. Collisions are now handled via finding the next 
available slot in the array. However, elements of the array are still 
pointers to entries.

So technically, the freelist is still needed. But I'm not sure 
preallocating into a contiguous block is the best approach. People don't 
expect a hashtable to hold onto all the memory it has used in the past 
when you remove most of the elements.

In dcollections, I let the allocator take care of the details of 
allocation. I think the best thing to do is to preallocate the array at 
least (so no rehashing occurs during additions of nodes), and then move 
towards a templated solution that can use a custom allocator for tuning 
the performance/memory usage tradeoff.

-Steve