www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Allocators in Phobos

reply David Simcha <dsimcha yahoo.com> writes:
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.

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?

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.

Are there any other allocators that might be useful and could reasonably be
implemented as Phobos modules without major modifications to druntime or the
compiler?
Aug 19 2011
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
David Simcha:

 Are there any other allocators that might be useful and could reasonably be
 implemented as Phobos modules without major modifications to druntime or the
 compiler?

I'd like a hierarchical allocator. A C example: http://swapped.cc/halloc/ Bye, bearophile
Aug 19 2011
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 19 Aug 2011 23:33:27 -0400, David Simcha <dsimcha 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
Aug 22 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
On 8/22/2011 7:07 AM, Steven Schveighoffer wrote:
 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 :)

Yes, newArray does initialize elements. My mistake.
 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

Hmm, your chunk allocator looks like a generalization of FreeListAllocator. If I get around to implementing FreeListAllocator, I'll add support for allocating chunks instead of one element per heap allocation.
Aug 22 2011
next sibling parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Steven Schveighoffer (schveiguy yahoo.com)'s article
 On Mon, 22 Aug 2011 09:02:02 -0400, dsimcha <dsimcha yahoo.com> wrote:
 On 8/22/2011 7:07 AM, Steven Schveighoffer wrote:
 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.




Hmm, your chunk allocator looks like a generalization of FreeListAllocator. If I get around to implementing FreeListAllocator, I'll add support for allocating chunks instead of one element per heap allocation.

of one on top of that, especially if the "block size" is constant? https://github.com/D-Programming-Language/druntime/blob/master/src/gc/gcx.d#L505 https://github.com/D-Programming-Language/druntime/blob/master/src/gc/gcx.d#L927 -Steve

They'd be thread-local, that's the main advantage. W.r.t. your other post, it would make sense to do it on top of the GC, because the free lists would be completely thread-local. Allocating would never require any synchronization as long as there's a node on the free list and freeing would never require require synchronization, period.
Aug 22 2011
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 8/22/11 8:21 AM, Steven Schveighoffer wrote:
 On Mon, 22 Aug 2011 09:02:02 -0400, dsimcha <dsimcha yahoo.com> wrote:

 On 8/22/2011 7:07 AM, Steven Schveighoffer wrote:
 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

Hmm, your chunk allocator looks like a generalization of FreeListAllocator. If I get around to implementing FreeListAllocator, I'll add support for allocating chunks instead of one element per heap allocation.

Well, I think the GC already uses free lists... What would be the point of one on top of that, especially if the "block size" is constant? https://github.com/D-Programming-Language/druntime/blob/master/src/gc/gcx.d#L505 https://github.com/D-Programming-Language/druntime/blob/master/src/gc/gcx.d#L927

Because you can create free lists on top of other allocators than the GC one. Andrei
Aug 22 2011
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 8/22/11 8:36 AM, Steven Schveighoffer wrote:
 On Mon, 22 Aug 2011 09:21:43 -0400, Steven Schveighoffer
 <schveiguy yahoo.com> wrote:

 On Mon, 22 Aug 2011 09:02:02 -0400, dsimcha <dsimcha yahoo.com> wrote:

 On 8/22/2011 7:07 AM, Steven Schveighoffer wrote:
 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

Hmm, your chunk allocator looks like a generalization of FreeListAllocator. If I get around to implementing FreeListAllocator, I'll add support for allocating chunks instead of one element per heap allocation.

Well, I think the GC already uses free lists... What would be the point of one on top of that, especially if the "block size" is constant? https://github.com/D-Programming-Language/druntime/blob/master/src/gc/gcx.d#L505 https://github.com/D-Programming-Language/druntime/blob/master/src/gc/gcx.d#L927

I didn't fully read your FreeListAllocator proposal, I lost that it was on *top of* another allocator. So obviously, it wouldn't make much sense to do it on top of the GC, but it could make sense on top of a different allocator (say the C malloc allocator). In that case, I agree the chunk allocator could be an option for the free list allocator. -Steve

Sorry for writing my answer before reading this. Andrei
Aug 22 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 22 Aug 2011 09:02:02 -0400, dsimcha <dsimcha yahoo.com> wrote:

 On 8/22/2011 7:07 AM, Steven Schveighoffer wrote:
 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

Hmm, your chunk allocator looks like a generalization of FreeListAllocator. If I get around to implementing FreeListAllocator, I'll add support for allocating chunks instead of one element per heap allocation.

Well, I think the GC already uses free lists... What would be the point of one on top of that, especially if the "block size" is constant? https://github.com/D-Programming-Language/druntime/blob/master/src/gc/gcx.d#L505 https://github.com/D-Programming-Language/druntime/blob/master/src/gc/gcx.d#L927 -Steve
Aug 22 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 22 Aug 2011 09:21:43 -0400, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:

 On Mon, 22 Aug 2011 09:02:02 -0400, dsimcha <dsimcha yahoo.com> wrote:

 On 8/22/2011 7:07 AM, Steven Schveighoffer wrote:
 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

Hmm, your chunk allocator looks like a generalization of FreeListAllocator. If I get around to implementing FreeListAllocator, I'll add support for allocating chunks instead of one element per heap allocation.

Well, I think the GC already uses free lists... What would be the point of one on top of that, especially if the "block size" is constant? https://github.com/D-Programming-Language/druntime/blob/master/src/gc/gcx.d#L505 https://github.com/D-Programming-Language/druntime/blob/master/src/gc/gcx.d#L927

I didn't fully read your FreeListAllocator proposal, I lost that it was on *top of* another allocator. So obviously, it wouldn't make much sense to do it on top of the GC, but it could make sense on top of a different allocator (say the C malloc allocator). In that case, I agree the chunk allocator could be an option for the free list allocator. -Steve
Aug 22 2011
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 8/19/11 10:33 PM, David Simcha wrote:
 Are there any other allocators that might be useful and could reasonably be
 implemented as Phobos modules without major modifications to druntime or the
 compiler?

We need to have a classic heap allocator that we can combine with regions. See Emery Berger's HeapLayers and reap data structure. Andrei
Aug 22 2011
parent dsimcha <dsimcha yahoo.com> writes:
On 8/22/2011 4:21 PM, Andrei Alexandrescu wrote:
 On 8/19/11 10:33 PM, David Simcha wrote:
 Are there any other allocators that might be useful and could
 reasonably be
 implemented as Phobos modules without major modifications to druntime
 or the
 compiler?

We need to have a classic heap allocator that we can combine with regions. See Emery Berger's HeapLayers and reap data structure. Andrei

I've read up on reaps a little. It sounds like a pretty interesting concept. Since I'm hoping RegionAllocator will get its turn in the review queue soon and implementing a good heap is fairly involved, a reap isn't going to be part of my initial proposal. (Dimity's and Cristi's GSoC projects are both Phobos candidates and both already depend on RegionAllocator, so we should probably get it in Phobos soon. As a short term solution, both are just keeping a copy of it in their source trees.) However, when RegionAllocator is reviewed, we should make sure there are no bad design decisions that would make implementing a reap on top of it unnecessarily difficult. Bottom like: Longer term, a reap definitely does belong in Phobos and we should plan accordingly, but it should be a separate, later proposal.
Aug 22 2011