[phobos] Sealed Hash Tables

[Andrei Alexandrescu]

On 10/23/10 18:38 CDT, David Simcha wrote:
> 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.

Probably you're better off making good judgments than I am; I know about 
STL allocators, I also know they are wrong, but I can't figure why.

> 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.

Well it also imposes certain constraints. If parametric, you can 
implement swap(). If not, you can't, or swap() could fail. (You can't 
swap two objects leaving memory for one being freed by another allocator.)

> 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()).

Often an object would need to figure out statically if they need to 
explicitly free everything; depending on that, the object may opt for 
different designs (e.g. refcounted vs. not).

> 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.

We don't have the type system chops to support region-based allocation 
statically. The most we could is to define an interface for region 
allocation (e.g. allocate() and freeAll() but not free() for individual 
elements) that allows containers to statically figure out they're 
dealing with regions and tailor code appropriately.


Andrei