• David Simcha (35/35) Aug 19 2011 I've massively improved my RegionAllocator (formerly TempAlloc) module t...
• bearophile (5/8) Aug 19 2011 I'd like a hierarchical allocator. A C example:
• Steven Schveighoffer (19/60) Aug 22 2011 According to your syntactic sugar description, newArray does not
• dsimcha (6/25) Aug 22 2011 Hmm, your chunk allocator looks like a generalization of
• Steven Schveighoffer (6/24) Aug 22 2011 Well, I think the GC already uses free lists... What would be the point...
• Steven Schveighoffer (9/33) Aug 22 2011 I didn't fully read your FreeListAllocator proposal, I lost that it was ...
• Andrei Alexandrescu (3/42) Aug 22 2011 Sorry for writing my answer before reading this.
• dsimcha (7/32) Aug 22 2011 They'd be thread-local, that's the main advantage. W.r.t. your other po...
• Andrei Alexandrescu (4/29) Aug 22 2011 Because you can create free lists on top of other allocators than the GC...
• Andrei Alexandrescu (4/7) Aug 22 2011 We need to have a classic heap allocator that we can combine with
• dsimcha (13/22) Aug 22 2011 I've read up on reaps a little. It sounds like a pretty interesting

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?

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

"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

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.

"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

"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

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

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.



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

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.

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

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

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.