Allocators in Phobos

[Steven Schveighoffer]

On Fri, 19 Aug 2011 23:33:27 -0400, David Simcha <dsimcha at yahoo.com> wrote:

> I've massively improved my RegionAllocator (formerly TempAlloc) module  
> thanks
> to the excellent suggestions from Andrei and from Dimitri Olshansky (the  
> GSoC
> student working on regexes).
>
> For the curious:
>
> http://cis.jhu.edu/~dsimcha/d/phobos/std_regionallocator.html
> https://github.com/dsimcha/TempAlloc/blob/master/regionallocator.d
>
> The main point of this massive overhaul was Andrei's suggestion that
> TempAlloc/RegionAllocator be converted from something fairly ad-hoc to an
> implementation of the more general allocator interface that he  
> proposed.  I
> also think that three high-level functions were missing from Andrei's
> proposal.  All of these will be included in RegionAllocator even if we  
> decide
> they're not "standard" allocator functions:
>
> newArray:  Creates a new array.  Can be syntactic sugar for (cast(T*)
> allocate(T.sizeof * nElements))[0..nElements] or can do something more
> complicated based on knowing what type T is.
>
> uninitializedArray:  Same as newArray but doesn't initialize elements.

According to your syntactic sugar description, newArray does not  
initialize elements, is this not the case?

I'm assuming so, otherwise, why the extra function :)

>
> array:  Converts a range into an array.
>
> While I'm waiting in the review queue, I'm thinking of broadening the
> allocator proposal to include a few more low-hanging fruit allocators:
>
> GCAllocator:  An allocator wrapper over the garbage collector.  Question:
> Should GCAllocator.free() call core.memory.GC.free() or be a no-op?

I'm mixed on this.  In a world where the GC does a good job of freeing  
unused memory automatically, I'd say this is a no-op.  But we don't yet  
live in that world for D.

I'd say call core.memory.GC.free for now.

>
> CAllocator:  An allocator wrapper over C's malloc and free.
>
> FreeListAllocator:  A meta-allocator that allocates blocks of some fixed,
> user-specified size off of some other base allocator and makes them  
> available
> via the allocate() function.  All allocation requests larger than the  
> block
> size throw.  All allocations smaller than the blolck size use whatever
> fraction of a block they need and waste the rest.  Freeing memory via  
> free()
> puts it on a free list maintained by the FreeListAllocator object.
> FreeListAllocator attempts to satisfy allocation requests from its free  
> list
> before allocating off the base allocator.  I'd probably make each
> FreeListAllocator instance reference counted, and when the the last copy  
> of an
> instance goes out of scope, all blocks on the free list get freed.

Take a look at dcollections' chunk allocator, which is under boost  
license.  It implements a free list + efficient allocation/deallocation by  
dividing up a large block.  It might be a fit for this, or at least a  
starting point.

One difference from this allocator vs. the generic ones you are  
implementing is that it's templated on the type being allocated.  It's  
intended to be used for a collection, which only allocates one type (a  
node).  Does this kind of thinking belong in phobos?  I'm not sure.  But I  
think we can at least reuse the free list implementation.

http://www.dsource.org/projects/dcollections/browser/branches/d2/dcollections/DefaultAllocator.d#L41

-Steve