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
