[phobos] Sealed Hash Tables

[David Simcha]

  On 10/23/2010 11:48 AM, Andrei Alexandrescu wrote:
> Then I think that's a good addition to std.container. Before that, we 
> should discuss in more depth allocators. This is because some use 
> cases will prefer malloc and others will prefer the GC heap.
>
> For example, a class that has a sealed container as member wouldn't 
> want the container to hold on to some mallocated chunks until the next 
> GC cycle.
>
>
> Andrei

Ok.  First, I'll start off by stating that I don't have much knowledge 
of how custom allocators work in C++.  I know that they're template 
parameters to STL containers, but that's about it.  I don't know many 
details.

I guess the first question on the list is, do we want to make allocator 
choice parametric (i.e. any allocator that meets some compile-time 
interface can be used) or ad-hoc (i.e. we support only a small, limited 
set of allocators, such as malloc and core.memory)?  This is basically a 
tradeoff between simplicity and flexibility.

Secondly, assuming we go with parametric (which is my vote), what would 
be the API?  The most simple and obvious answer is an alias parameter 
for a malloc() function and another alias paramter for a free() 
function.  The free() function may be a dummy/no-op function if malloc'd 
blocks are GC'd.  On the other hand, while I know C++ makes the 
allocator a compile-time/template parameter, I don't see what's gained 
in exchange for losing runtime flexibility in this case.  It makes a lot 
more sense to me that it should be changeable at runtime and be either 
an object or a pair of function pointers/delegates (one for malloc(), 
one for free()).

Third, how about things like stack allocators that might only be able to 
free memory in LIFO order or mark-release allocators that might only be 
able to free whole chunks of memory at once?  I'd assume we can't 
support these, at least not well.  In terms of my personal experience, I 
actually wrote a hash table implementation for a stack allocator at one 
point as a performance optimization.  It worked well for its intended 
use cases, but required a substantial amount of awareness of the 
underlying allocator in the implementation and some in the API.  For 
example, you had to specify in advance the approximate size of the 
table, and removed entries were kept on an internal free list since 
otherwise that memory would go to waste.