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

[Andrei Alexandrescu via Digitalmars-d]

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.

Each hashtable would have its own freelist, or alternatively all 
hashtables of the same types share the same freelist.

So should we get into this? Pros:

* It provides a nice primitive to use with built-in hashtables

* Accelerates without much effort a variety of codes using hashtables

Cons:

* Built-in hashtables are a convenience facility more than a 
high-performance one, so providing an efficiency-oriented primitive 
seems a bit odd.

* We're considering a number of improvements and refactorings to 
built-in hashtables, which may obviate the freelist implementation or 
need extra effort to implement it. Basically defining reserve() limits 
our future implementation freedom.

* Implementation effort is nontrivial.

* The time needed to initialize the freelist in one contiguous block of 
memory is still O(n) (although the constant is small and special 
implementation techniques may make it O(1)).

* The implementation cannot use Phobos' allocator because it's in druntime.

Please share your thoughts.


Thanks,

Andrei