www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - why allocators are not discussed here

reply "cybervadim" <vadim.goryunov gmail.com> writes:
I know Andrey mentioned he was going to work on Allocators a year 
ago. In DConf 2013 he described the problems he needs to solve 
with Allocators. But I wonder if I am missing the discussion 
around that - I tried searching this forum, found a few threads 
that was not actually a brain storm for Allocators design.

Please point me in the right direction
or
is there a reason it is not discussed
or
should we open the discussion?


The easiest approach for Allocators design I can imagine would be 
to let user specify which Allocator operator new should get the 
memory from (introducing a new keyword allocator). This gives a 
total control, but assumes user knows what he is doing.

Example:

CustomAllocator ca;
allocator(ca) {
   auto a = new A; // operator new will use 
ScopeAllocator::malloc()
   auto b = new B;

   free(a); // that should call ScopeAllocator::free()
   // if free() is missing for allocated area, it is a user 
responsibility to make sure custom Allocator can handle that
}

By default allocator is the druntime using GC, free(a) does 
nothing for it.


if some library defines its allocator (e.g. specialized 
container), there should be ability to:
1. override allocator
2. get access to the allocator used

I understand that I spent 5 mins thinking about the way 
Allocators may look.
My point is - if somebody is working on it, can you please share 
your ideas?
Jun 25 2013
next sibling parent reply "Adam D. Ruppe" <destructionator gmail.com> writes:
On Tuesday, 25 June 2013 at 22:22:09 UTC, cybervadim wrote:
 (introducing a new keyword allocator)

It would be easier to just pass an allocator object that provides the necessary methods and don't use new at all. (I kinda wish new wasn't in the language. It'd make this a little more consistent.) The allocator's create function could also return wrapped types, like RefCounted!T or NotNull!T depending on what it does. Though the devil is in the details here and I don't think I can say more without trying to actually do it.
Jun 25 2013
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
26-Jun-2013 14:03, Robert Schadek пишет:
 On 06/26/2013 12:50 AM, Adam D. Ruppe wrote:
 On Tuesday, 25 June 2013 at 22:22:09 UTC, cybervadim wrote:
 (introducing a new keyword allocator)

It would be easier to just pass an allocator object that provides the necessary methods and don't use new at all. (I kinda wish new wasn't in the language. It'd make this a little more consistent.)

I did think about this as well, but than I came up with something that IMHO is even simpler. Imagine we have two delegates: void* delegate(size_t); // this one allocs void delegate(void*); // this one frees you pass both to a function that constructs you object. The first is used for allocation the memory, the second gets attached to the TypeInfo and is used by the gc to free the object.

Then it's just GC but with an extra complication.
 This would be completely transparent to the user.

 The use in a container is similar. Just use the alloc delegate to
 construct the objects and
 attach the free delegate to the typeinfo. You could even mix allocator
 strategies in the middle
 of the lifetime of the container.

-- Dmitry Olshansky
Jun 26 2013
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Jun 26, 2013 at 12:22:04AM +0200, cybervadim wrote:
 I know Andrey mentioned he was going to work on Allocators a year
 ago. In DConf 2013 he described the problems he needs to solve with
 Allocators. But I wonder if I am missing the discussion around that
 - I tried searching this forum, found a few threads that was not
 actually a brain storm for Allocators design.
 
 Please point me in the right direction
 or
 is there a reason it is not discussed
 or
 should we open the discussion?

That would be nice to get things going. :) Ever since I found D and subscribed to this mailing list, I've been hearing rumors of allocators, but they seem to be rather lacking in the department of concrete evidence. They're like the Big Foot or Swamp Ape of D. Maybe it's time we got out into the field and produced some real evidence of these mythical beasts. :-P
 The easiest approach for Allocators design I can imagine would be to
 let user specify which Allocator operator new should get the memory
 from (introducing a new keyword allocator). This gives a total
 control, but assumes user knows what he is doing.
 
 Example:
 
 CustomAllocator ca;
 allocator(ca) {
   auto a = new A; // operator new will use ScopeAllocator::malloc()
   auto b = new B;
 
   free(a); // that should call ScopeAllocator::free()
   // if free() is missing for allocated area, it is a user
 responsibility to make sure custom Allocator can handle that
 }
 
 By default allocator is the druntime using GC, free(a) does nothing
 for it.

I believe the current direction is to avoid needing new language features / syntax. So the above probably won't happen.
 if some library defines its allocator (e.g. specialized container),
 there should be ability to:
 1. override allocator
 2. get access to the allocator used
 
 I understand that I spent 5 mins thinking about the way Allocators
 may look.
 My point is - if somebody is working on it, can you please share
 your ideas?

Well, thanks for getting the ball rolling. Maybe Andrei can pipe up about any experimental designs he's currently considering. But barring that, I'm thinking about how allocators would be used in user code. I think it's pretty much a given that the C++ way of sticking it to the end of template arguments doesn't really fly: it's just too much of a hassle to keep having to worry about passing allocators around template arguments, that people just don't bother. So coming back to square one, how would allocators be used? 1) Usually, the user would just be content with the GC, and not ever have to worry about allocators. So this means that whatever allocator design we adopt, it should be practically invisible to ordinary users unless they're specifically looking to change how memory is allocated. 2) Furthermore, it's unlikely that in the same piece of code, you'd want to use 3 or 4 different allocators for different objects; while such cases may exist, it seems to me to be more likely that you want either (a) a very specific object (say a class instance or container) to use a particular allocator, or (b) you want to transitively block off an entire section of code (which may be the entire program in some cases) to use a particular allocator. As a first stab at it, I'd say (a) can be implemented by a static class member reference to an allocator, that can be set from user code. And maybe (b) can be implemented by making gc_alloc / gc_free overridable function pointers? Then we can override their values and use scope guards to revert them back to the values they were before. This allows us to use the runtime stack to manage which allocator is currently active. This lets *all* memory allocations be rerouted through the custom allocator without needing to hand-edit every call to new down the call graph. This is just a very crude first stab at the problem, though. In particular, (a) isn't very satisfactory. And also the interaction of allocated objects with the call stack: if any custom-allocated objects in (b) survive past the containing function which sets/resets the function pointers, there could be problems: if a member function of such an object needs to allocate memory, it will pick up the ambient allocator instead of the custom allocator in effect when the object was first created. Also, we may have the problem of the wrong allocator being used to free the object. Anyone has better ideas? T -- All problems are easy in retrospect.
Jun 25 2013
next sibling parent Jacob Carlborg <doob me.com> writes:
On 2013-06-26 01:16, Adam D. Ruppe wrote:

 You'd want it to be RAII or delegate based, so the scope is clear.

 with_allocator(my_alloc, {
       do whatever here
 });


 or

 {
     ChangeAllocator!my_alloc dummy;

     do whatever here
 } // dummy's destructor ends the allocator scope


 I think the former is a bit nicer, since the dummy variable is a bit
 silly. We'd hope that delegate can be inlined.

It won't be inlined. You would need to make it a template parameter to have it inlined. -- /Jacob Carlborg
Jun 26 2013
prev sibling next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
26-Jun-2013 03:16, Adam D. Ruppe пишет:
 On Tuesday, 25 June 2013 at 22:50:55 UTC, H. S. Teoh wrote:
 And maybe (b) can be implemented by making gc_alloc / gc_free
 overridable function pointers? Then we can override their values and
 use scope guards to revert them back to the values they were before.

Yea, I was thinking this might be a way to go. You'd have a global (well, thread-local) allocator instance that can be set and reset through stack calls. You'd want it to be RAII or delegate based, so the scope is clear. with_allocator(my_alloc, { do whatever here }); or { ChangeAllocator!my_alloc dummy; do whatever here } // dummy's destructor ends the allocator scope

Both suffer from a) being totally unsafe and in fact bug prone since all references obtained in there are now dangling (and there is no indication where they came from) b) imagine you need to use an allocator for a stateful object. Say forward range of some other ranges (e.g. std.regex) both scoped/stacked to allocate its internal stuff. 2nd one may handle it but not the 1st one. c) transfer of objects allocated differently up the call graph (scope graph?), is pretty much neglected I see. I kind of wondering how our knowledgeable community has come to this. (must have been starving w/o allocators way too long)
 {
     malloced_string str;
     auto got = to!string(10, str);
 } // str is out of scope, so it gets free()'d. unsafe though: if you
 stored a copy of got somewhere, it is now a pointer to freed memory. I'd
 kinda like language support of some sort to help mitigate that though,
 like being a borrowed pointer that isn't allowed to be stored, but
 that's another discussion.

be still customizable. IMHO the only place for allocators is in containers other kinds of code may just ignore allocators completely. std.algorithm and friends should imho be customized on 2 things only: a) containers to use (instead of array) b) optionally a memory source (or allocator) f container is temporary(scoped) to tie its life-time to smth. Want temporary stuff? Use temporary arrays, hashmaps and whatnot i.e. types tailored for a particular use case (e.g. with a temporary/scoped allocator in mind). These would all be unsafe though. Alternative is ref-counting pointers to an allocator. With word on street about ARC it could be nice direction to pursue. Allocators (as Andrei points out in his video) have many kinds: a) persistence: infinite, manual, scoped b) size: unlimited vs fixed c) block-size: any, fixed, or *any* up to some maximum size Most of these ARE NOT interchangeable! Yet some are composable however I'd argue that allocators are not composable but have some reusable parts that in turn are composable. Code would have to cutter for specific flavors of allocators still so we'd better reduce this problem to the selection of containers. -- Dmitry Olshansky
Jun 26 2013
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
26-Jun-2013 21:23, H. S. Teoh пишет:

 Both suffer from
 a) being totally unsafe and in fact bug prone since all references
 obtained in there are now dangling (and there is no indication where
 they came from)

How is this different from using malloc() and free() manually? You have no indication of where a void* came from either, and the danger of dangling references is very real, as any C/C++ coder knows. And I assume that *some* people will want to be defining custom allocators that wrap around malloc/free (e.g. the game engine guys who want total control).

Why the heck you people think I purpose to use malloc directly as alternative to whatever hackish allocator stack proposed? Use the darn container. For starters I'd make allocation strategy a parameter of each containers. At least they do OWN memory. Then refactor out common pieces into a framework of allocation helpers. I'd personally in the end would separate concerns into 3 entities: 1. Memory area objects - think as allocators but without the circuitry to do the allocation, e.g. a chunk of memory returned by malloc/alloca can be wrapped into a memory area object. 2. Allocators (Policies) - a potentially nested combination of such "circuitry" that makes use of memory areas. Free-lists, pools, stacks etc. Safe ones have ref-counting on memory areas, unsafe once don't. (Though safety largely depends on the way you got that chunk of memory) 3. Containers/Warppers as above objects that handle life-cycle of objects and make use of allocators. In fact allocators are part of type but not memory area objects.
 b) imagine you need to use an allocator for a stateful object. Say
 forward range of some other ranges (e.g. std.regex) both
 scoped/stacked to allocate its internal stuff. 2nd one may handle it
 but not the 1st one.

Yeah this is a complicated area. A container basically needs to know how to allocate its elements. So somehow that information has to be somewhere.
 c) transfer of objects allocated differently up the call graph
 (scope graph?), is pretty much neglected I see.

They're incompatible. You can't safely make a linked list that contains both GC-allocated nodes and malloc() nodes.

What I mean is that if types are the same as built-ins it would be a horrible mistake. If not then we are talking about containers anyway. And if these have a ref-counted pointer to their allocator then the whole thing is safe albeit at the cost of performance. Sadly alias this to some built-in (=e.g. slice) allows squirreling away underlying reference too easily. As such I don't believe in any of the 2 *lies*: a) built-ins can be refurbished to use custom allocators b) we can add opSlice/alias this or whatever to our custom type to get access to the underlying built-ins safely and transparently Both are just nuclear bombs waiting a good time to explode. That's just a bomb waiting
 to explode in your face. So in that sense, Adam's idea of using a
 different type for differently-allocated objects makes sense.

Yes, but one should be careful here as not to have exponential explosion in the code size. So some allocators have to be compatible and if there is a way to transfer ownership it'd be bonus points (and a large pot of these mind you).
 A
 container has to declare what kind of allocation its members are using;
 any other way is asking for trouble.

Hence my thoughts to move this piece of "circuitry" to containers proper. The whole idea that by swapping malloc with myMalloc you can translate to a wildly different allocation scheme doesn't quite hold. I think it may be interesting to try and put a "wall" in different place namely in between allocation strategy and memory areas it works on.
 I kind of wondering how our knowledgeable community has come to this.
 (must have been starving w/o allocators way too long)

We're just trying to provoke Andrei into responding. ;-)

care of.
 [...]
 IMHO the only place for allocators is in containers other kinds of
 code may just ignore allocators completely.

But some people clamoring for allocators are doing so because they're bothered by Phobos using ~ for string concatenation, which implicitly uses the GC. I don't think we can just ignore that.

~= would work with any sensible array-like contianer. ~ is sadly only a convenience for scripts and/or non-performance (determinism) critical apps unfortunately.
 std.algorithm and friends should imho be customized on 2 things only:

 a) containers to use (instead of array)
 b) optionally a memory source (or allocator) f container is
 temporary(scoped) to tie its life-time to smth.

 Want temporary stuff? Use temporary arrays, hashmaps and whatnot
 i.e. types tailored for a particular use case (e.g. with a
 temporary/scoped allocator in mind).
 These would all be unsafe though. Alternative is ref-counting
 pointers to an allocator. With word on street about ARC it could be
 nice direction to pursue.

Ref-counting is not fool-proof, though. There's always cycles to mess things up.

You surely shouldn't have allocators reference each other cyclically? Then I see this as a DAG with allocator at the bottom and objects referencing it.
 Allocators (as Andrei points out in his video) have many kinds:
 a) persistence: infinite, manual, scoped
 b) size: unlimited vs fixed
 c) block-size: any, fixed, or *any* up to some maximum size

 Most of these ARE NOT interchangeable!
 Yet some are composable however I'd argue that allocators are not
 composable but have some reusable parts that in turn are composable.

I was listening to Andrei's talk this morning, but I didn't quite understand what he means by composable allocators. Is he talking about nesting, say, a GC inside a region allocated by a region allocator?

I'd say something like: fixed size region allocator with GC as fallback. Or pool for small allocations + malloc/free with a free-list for bigger allocations etc. And the stuff should be as easily composable as I just listed.
 Code would have to cutter for specific flavors of allocators still
 so we'd better reduce this problem to the selection of containers.

Hmm. Sounds like we have two conflicting things going on here: 1) En massé replacement of gc_alloc/gc_free in a certain block of code (which may be the entire program), e.g., for the avoidance of GC in game engines, etc.. Basically, the code is allocator-agnostic, but at some higher level we want to control which allocator is being used.

There is no allocator agnostic code that allocates. It either happens to call free/dispose/destroy manually (implicitly with ref-counts) or it does not. It either escapes references to who knows where or doesn't.
 2) Specific customization of containers, etc., as to which allocator(s)
 should be used, with (hopefully) some kind of support from the type
 system to prevent mistakes like dangling pointers, escaping references,
 etc.. Here, the code is NOT allocator-agnostic; it has to be written
 with the specific allocation model in mind. You can't just replace the
 allocator with another one without introducing bugs or problems.

With another one of the same _kind_ I'd say.
 These two may interact in complex ways... e.g., you might want to use
 malloc to allocate a pool, then use a custom gc_alloc/gc_free to
 allocate from this pool in order to support language built-ins like ~
 and ~= without needing to rewrite every function that uses strings.

I guess we have to re-write them. Or don't allocate in string functions.
 Maybe we should stop conflating these two things so that we stop
 confusing ourselves, and hopefully it will be easier to analyse
 afterwards.

-- Dmitry Olshansky
Jun 26 2013
prev sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
26-Jun-2013 05:24, Adam D. Ruppe пишет:
 I was just quickly skimming some criticism of C++ allocators, since my
 thought here is similar to what they do. On one hand, maybe D can do it
 right by tweaking C++'s design rather than discarding it.

Criticisms are: A) Was defined to not have any state (as noted in the standard) B) Parametrized on type (T) yet a container that is parametrized on it may need to allocate something else completely (a node with T). C) Containers are parametrized on allocators so say 2 lists with different allocators are incompatible in a sense that e.g. you can't splice pieces of them together. Of the above IMHO we can deduce that a) Should support stateful allocators but we have to make sure we don't pay storage space for state-less ones (global ones e.g. mallocator). b) Should preferably be typeless and let container define what they allocate c) Hardly solvable unless we require a way to reassign objects between allocators (at least of similar kinds)
 Anyway, bottom line is I don't think that criticism necessarily applies
 to D. But there's surely many others and I'm more or less a n00b re
 c++'s allocators so idk yet.

-- Dmitry Olshansky
Jun 26 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Jun 26, 2013 at 12:50:36AM +0200, Adam D. Ruppe wrote:
 On Tuesday, 25 June 2013 at 22:22:09 UTC, cybervadim wrote:
(introducing a new keyword allocator)

It would be easier to just pass an allocator object that provides the necessary methods and don't use new at all. (I kinda wish new wasn't in the language. It'd make this a little more consistent.)

It's not too late to introduce a default allocator object that maps to built-in GC primitives. Maybe something like: struct DefaultAllocator { T* alloc(T, A...)(A args) { return new T(args); } void free(T)(T* ref) { // no-op } } We can then change Phobos to always use allocator.alloc and allocator.free, which it gets from user code somehow, and in the default case it would do the Right Thing.
 The allocator's create function could also return wrapped types,
 like RefCounted!T or NotNull!T depending on what it does.

So maybe something like: struct RefCountedAllocator { RefCounted!T alloc(T, A...)(A args) { return allocRefCounted(args); } void free(T)(RefCounted!T ref) { dotDotDotMagic(ref); } } etc..
 Though the devil is in the details here and I don't think I can say
 more without trying to actually do it.

The main issue I see is how *not* to get stuck in C++'s situation where you have to specify allocator objects everywhere, which is highly inconvenient and liable for people to avoid using, which defeats the purpose of having allocators. It would be nice, IMO, if we can somehow let the user specify a custom allocator for, say, the whole of Phobos, so that people who care about this sorta thing can just replace the GC wholesale and then use Phobos to their hearts' content without having to manually specify allocator objects everywhere and risk forgetting a single case that eventually leads to memory leakage. T -- Computers shouldn't beep through the keyhole.
Jun 25 2013
prev sibling next sibling parent "cybervadim" <vadim.goryunov gmail.com> writes:
On Tuesday, 25 June 2013 at 22:50:55 UTC, H. S. Teoh wrote:
 On Wed, Jun 26, 2013 at 12:22:04AM +0200, cybervadim wrote:

 That would be nice to get things going. :)

 Ever since I found D and subscribed to this mailing list, I've 
 been
 hearing rumors of allocators, but they seem to be rather 
 lacking in the
 department of concrete evidence. They're like the Big Foot or 
 Swamp Ape
 of D. Maybe it's time we got out into the field and produced 
 some real
 evidence of these mythical beasts. :-P

 Well, thanks for getting the ball rolling. Maybe Andrei can 
 pipe up
 about any experimental designs he's currently considering.

 But barring that, I'm thinking about how allocators would be 
 used in
 user code. I think it's pretty much a given that the C++ way of 
 sticking
 it to the end of template arguments doesn't really fly: it's 
 just too
 much of a hassle to keep having to worry about passing 
 allocators around
 template arguments, that people just don't bother. So coming 
 back to
 square one, how would allocators be used?

 1) Usually, the user would just be content with the GC, and not 
 ever
 have to worry about allocators. So this means that whatever 
 allocator
 design we adopt, it should be practically invisible to ordinary 
 users
 unless they're specifically looking to change how memory is 
 allocated.

 2) Furthermore, it's unlikely that in the same piece of code, 
 you'd want
 to use 3 or 4 different allocators for different objects; while 
 such
 cases may exist, it seems to me to be more likely that you want 
 either
 (a) a very specific object (say a class instance or container) 
 to use a
 particular allocator, or (b) you want to transitively block off 
 an
 entire section of code (which may be the entire program in some 
 cases)
 to use a particular allocator.

 As a first stab at it, I'd say (a) can be implemented by a 
 static class
 member reference to an allocator, that can be set from user 
 code.

 And maybe (b) can be implemented by making gc_alloc / gc_free
 overridable function pointers? Then we can override their 
 values and use
 scope guards to revert them back to the values they were 
 before. This
 allows us to use the runtime stack to manage which allocator is
 currently active. This lets *all* memory allocations be 
 rerouted through
 the custom allocator without needing to hand-edit every call to 
 new down
 the call graph.

 This is just a very crude first stab at the problem, though. In
 particular, (a) isn't very satisfactory. And also the 
 interaction of
 allocated objects with the call stack: if any custom-allocated 
 objects
 in (b) survive past the containing function which sets/resets 
 the
 function pointers, there could be problems: if a member 
 function of such
 an object needs to allocate memory, it will pick up the ambient
 allocator instead of the custom allocator in effect when the 
 object was
 first created. Also, we may have the problem of the wrong 
 allocator
 being used to free the object.

 Anyone has better ideas?


 T

From my experience all objects may be divided into 2 categories 1. temporaries. Program usually have some kind of event loop. During one iteration of this loop some temporary objects are created and then discarded. The ideal case for stack (or ranged or area) allocator, where you define allocator at the beginning of the loop cycle, use it for all temporaries, then free all the memory in one go at the end of iteration. 2. containers. Program receives an event from the outside and puts some data into container OR update the data if the record already exists. The important thing here is - when updating the data in container, you may want to resize the existing area. If you are working with temporary which should be placed into container, a copy can be made (with corresponding memory allocation from container allocator). Not sure if there is anything better than stack/area allocator for the first class. For the second class user should be able to choose default GC or more precise memory handling (e.g. explicit malloc/free for resizing). Anything I am missing in this categorization? So even if we get allocators that lets us deal with temporaries, that will be a huge benefit.
Jun 25 2013
prev sibling next sibling parent "Adam D. Ruppe" <destructionator gmail.com> writes:
On Tuesday, 25 June 2013 at 22:50:55 UTC, H. S. Teoh wrote:
 And maybe (b) can be implemented by making gc_alloc / gc_free
 overridable function pointers? Then we can override their 
 values and use scope guards to revert them back to the values 
 they were before.

Yea, I was thinking this might be a way to go. You'd have a global (well, thread-local) allocator instance that can be set and reset through stack calls. You'd want it to be RAII or delegate based, so the scope is clear. with_allocator(my_alloc, { do whatever here }); or { ChangeAllocator!my_alloc dummy; do whatever here } // dummy's destructor ends the allocator scope I think the former is a bit nicer, since the dummy variable is a bit silly. We'd hope that delegate can be inlined. But, the template still has a big advantage: you can change the type. And I think that is potentially enormously useful. Another question is how to tie into output ranges. Take std.conv.to. auto s = to!string(10); // currently, this hits the gc What if I want it to go on a stack buffer? One option would be to rewrite it to use an output range, and then call it like: char[20] buffer; auto s = to!string(10, buffer); // it returns the slice of the buffer it actually used (and we can do overloads so to!string(10, radix) still works, as well as to!string(10, radix, buffer). Hassle, I know...) Naturally, the default argument is to use the 'global' allocator, whatever that is, which does nothing special. The fun part is the output range works for that, and could also work for something like this: struct malloced_string { char* ptr; size_t length; size_t capacity; void put(char c) { if(length >= capacity) ptr = realloc(ptr, capacity*2); ptr[length++] = c; } char[] slice() { return ptr[0 .. length]; } alias slice this; mixin RefCounted!this; // pretend this works } { malloced_string str; auto got = to!string(10, str); } // str is out of scope, so it gets free()'d. unsafe though: if you stored a copy of got somewhere, it is now a pointer to freed memory. I'd kinda like language support of some sort to help mitigate that though, like being a borrowed pointer that isn't allowed to be stored, but that's another discussion. And that should work. So then what we might do is provide these little output range wrappers for various allocators, and use them on many functions. So we'd write: import std.allocators; import std.range; // mallocator is provided in std.allocators and offers the goods OutputRange!(char, mallocator) str; auto got = to!string(10, str); What's nice here is the output range is useful for more than just allocators. You could also to!string(10, my_file) or a delegate, blah blah blah. So it isn't too much of a burden, it is something you might naturally use anyway.
 Also, we may have the problem of the wrong allocator
 being used to free the object.

Another reason why encoding the allocator into the type is so nice. For the minimal D I've been playing with, the idea I'm running with is all allocated memory has some kind of special type, and then naked pointers are always assumed to be borrowed, so you should never store or free them. auto foo = HeapArray!char(capacity); void bar(char[] lol){} bar(foo); // allowed, foo has an alias this on slice // but.... struct A { char[] lol; // not allowed, because you don't know when lol is going to be freed } foo frees itself with refcounting.
Jun 25 2013
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
cybervadim:

 From my experience all objects may be divided into 2 categories
 1. temporaries. Program usually have some kind of event loop. 
 During one iteration of this loop some temporary objects are 
 created and then discarded. The ideal case for stack (or ranged 
 or area) allocator, where you define allocator at the beginning 
 of the loop cycle, use it for all temporaries, then free all 
 the memory in one go at the end of iteration.
 2. containers. Program receives an event from the outside and 
 puts some data into container OR update the data if the record 
 already exists.
 The important thing here is - when updating the data in 
 container, you may want to resize the existing area.

Many garbage collectors use the same idea (and manage it automatically), with two or three different generations: http://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29#Generational_GC_.28ephemeral_GC.29 Bye, bearophile
Jun 25 2013
prev sibling next sibling parent "cybervadim" <vadim.goryunov gmail.com> writes:
 Many garbage collectors use the same idea (and manage it 
 automatically), with two or three different generations:

 http://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29#Generational_GC_.28ephemeral_GC.29

 Bye,
 bearophile

The problem with GC is that it doesn't know which is temporary and which is not, so it has to traverse tree to determine that. Allocators in my opinion should let user specify explicitly the temporaries.
Jun 25 2013
prev sibling next sibling parent "Adam D. Ruppe" <destructionator gmail.com> writes:
I was just quickly skimming some criticism of C++ allocators, 
since my thought here is similar to what they do. On one hand, 
maybe D can do it right by tweaking C++'s design rather than 
discarding it.

On the other hand, with all the C++ I've done, I have never 
actually used STL allocators, which could say something about me 
or could say something about them.


One thing I saw said making the differently allocated object a 
different type sucks. ...but must it? The complaint there was "so 
much for just doing a function that takes a std::string". But, 
the way I'd want to do it in D is the function would take a 
char[] instead, and our special allocated type provides that via 
opSlice and/or alias this.

So you'd only have to worry about the different type if you 
intend to take ownership of the container yourself. Which we 
already kinda think about in D: if you store a char[], someone 
else could overwrite it, so we prefer to store an 
immutable(char)[] aka string. If you're given a char[] and want 
to store it, you might idup. So I don't think doing a private 
copy with some other allocation scheme is any more of a hassle.

(BTW immutable objects IMO should *always* be garbage collected, 
because part of immutability is infinite lifetime. So we might 
want to be careful with implicit conversions to immutable based 
on allocation method, which I believe we can protect through 
member functions.)


Anyway, bottom line is I don't think that criticism necessarily 
applies to D. But there's surely many others and I'm more or less 
a n00b re c++'s allocators so idk yet.
Jun 25 2013
prev sibling next sibling parent Robert Schadek <realburner gmx.de> writes:
On 06/26/2013 12:50 AM, Adam D. Ruppe wrote:
 On Tuesday, 25 June 2013 at 22:22:09 UTC, cybervadim wrote:
 (introducing a new keyword allocator)

It would be easier to just pass an allocator object that provides the necessary methods and don't use new at all. (I kinda wish new wasn't in the language. It'd make this a little more consistent.)

I did think about this as well, but than I came up with something that IMHO is even simpler. Imagine we have two delegates: void* delegate(size_t); // this one allocs void delegate(void*); // this one frees you pass both to a function that constructs you object. The first is used for allocation the memory, the second gets attached to the TypeInfo and is used by the gc to free the object. This would be completely transparent to the user. The use in a container is similar. Just use the alloc delegate to construct the objects and attach the free delegate to the typeinfo. You could even mix allocator strategies in the middle of the lifetime of the container.
Jun 26 2013
prev sibling next sibling parent "Jason House" <jason.james.house gmail.com> writes:
Bloomberg released an STL alternative called BSL which contains 
an alternate allocator model. In a nutshell object supporting 
custom allocators can optionally take an allocator pointer as an 
argument. Containers will save the pointer and use it for all 
their allocations. It seems simple enough and does not embed the 
allocator in the type.

https://github.com/bloomberg/bsl/wiki/BDE-Allocator-model

On Tuesday, 25 June 2013 at 22:22:09 UTC, cybervadim wrote:
 I know Andrey mentioned he was going to work on Allocators a 
 year ago. In DConf 2013 he described the problems he needs to 
 solve with Allocators. But I wonder if I am missing the 
 discussion around that - I tried searching this forum, found a 
 few threads that was not actually a brain storm for Allocators 
 design.

 Please point me in the right direction
 or
 is there a reason it is not discussed
 or
 should we open the discussion?


 The easiest approach for Allocators design I can imagine would 
 be to let user specify which Allocator operator new should get 
 the memory from (introducing a new keyword allocator). This 
 gives a total control, but assumes user knows what he is doing.

 Example:

 CustomAllocator ca;
 allocator(ca) {
   auto a = new A; // operator new will use 
 ScopeAllocator::malloc()
   auto b = new B;

   free(a); // that should call ScopeAllocator::free()
   // if free() is missing for allocated area, it is a user 
 responsibility to make sure custom Allocator can handle that
 }

 By default allocator is the druntime using GC, free(a) does 
 nothing for it.


 if some library defines its allocator (e.g. specialized 
 container), there should be ability to:
 1. override allocator
 2. get access to the allocator used

 I understand that I spent 5 mins thinking about the way 
 Allocators may look.
 My point is - if somebody is working on it, can you please 
 share your ideas?

Jun 26 2013
prev sibling next sibling parent "cybervadim" <vadim.goryunov gmail.com> writes:
On Wednesday, 26 June 2013 at 13:16:25 UTC, Jason House wrote:
 Bloomberg released an STL alternative called BSL which contains 
 an alternate allocator model. In a nutshell object supporting 
 custom allocators can optionally take an allocator pointer as 
 an argument. Containers will save the pointer and use it for 
 all their allocations. It seems simple enough and does not 
 embed the allocator in the type.

 https://github.com/bloomberg/bsl/wiki/BDE-Allocator-model

I think the problem with such approach is that you have to maniacally add support for custom allocator to every class if you want them to be on a custom allocator. If we simply able to say - all memory allocated in this area {} should use my custom allocator, that would simplify the code and no need to change std lib. The next step is to notify allocator when the memory should be released. But for the stack based allocator that is not required. More over, if we introduce access to different GCs (e.g. mark-n-sweep, semi-copy, ref counted), we should be able to say this {} piece of code is my temporary, so use semi-copy GC, the other code is long lived and not much objects created, so use ref counted. That is, it is all runtime support and no need changing the library code.
Jun 26 2013
prev sibling next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
26-Jun-2013 02:22, cybervadim пишет:
 I know Andrey mentioned he was going to work on Allocators a year ago.
 In DConf 2013 he described the problems he needs to solve with
 Allocators. But I wonder if I am missing the discussion around that - I
 tried searching this forum, found a few threads that was not actually a
 brain storm for Allocators design.

 Please point me in the right direction
 or
 is there a reason it is not discussed
 or
 should we open the discussion?


 The easiest approach for Allocators design I can imagine would be to let
 user specify which Allocator operator new should get the memory from
 (introducing a new keyword allocator). This gives a total control, but
 assumes user knows what he is doing.

 Example:

 CustomAllocator ca;
 allocator(ca) {
    auto a = new A; // operator new will use ScopeAllocator::malloc()
    auto b = new B;

    free(a); // that should call ScopeAllocator::free()
    // if free() is missing for allocated area, it is a user
 responsibility to make sure custom Allocator can handle that
 }

Awful. What that extra syntax had brought you? Except that now new is unsafe by design? Other questions involve how does this allocation scope goes inside of functions, what is the mechanism of passing it up and down of call-stack. Last but not least I fail to see how scoped allocators alone (as presented) solve even half of the problem. -- Dmitry Olshansky
Jun 26 2013
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
26-Jun-2013 18:27, cybervadim пишет:
 On Wednesday, 26 June 2013 at 14:17:03 UTC, Dmitry Olshansky wrote:
 Awful. What that extra syntax had brought you? Except that now new is
 unsafe by design?
 Other questions involve how does this allocation scope goes inside of
 functions, what is the mechanism of passing it up and down of call-stack.

 Last but not least I fail to see how scoped allocators alone (as
 presented) solve even half of the problem.

Extra syntax allows me not touching the existing code. Imagine you have a stateless event processing. That is event comes, you do some calculation, prepare the answer and send it back. It will look like: void onEvent(Event event) { process(); } Because it is stateless, you know all the memory allocated during processing will not be required afterwards.

Here is a chief problem - the assumption that is required to make it magically work. Now what I see is: T arr[];//TLS //somewhere down the line arr = ... ; else{ ... alloctor(myAlloc){ arr = array(filter!....); } ... } return arr; Having an unsafe magic wand that may transmogrify some code to switch allocation strategy I consider naive and dangerous. Who ever told you process does return before allocating a few Gigs of RAM (and hoping on GC collection)? Right, nobody. Maybe it's an event loop that may run forever. What is missing is that code up to date assumes new == GC and works _like that_.
 So the syntax I suggested
 requires a very little change in code. process() may be implemented
 using std lib, doing several news and resizing.

 With new syntax:


 void onEvent(Event event)
 {
     ScopedAllocator alloc;
     allocator(alloc) {
       process();
     }
 }

 So now you do not use GC for all that is created inside the process().
 ScopedAllocator is a simple stack that will free all memory in one go.

 It is up to the runtime implementation to make sure all memory that is
 allocated inside allocator{} scope is actually allocated using
 ScopedAllocator and not GC.

 Does it make sense?

Yes, but it's horribly broken. -- Dmitry Olshansky
Jun 26 2013
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
26-Jun-2013 23:04, cybervadim пишет:
 On Wednesday, 26 June 2013 at 14:59:41 UTC, Dmitry Olshansky wrote:

 Having an unsafe magic wand that may transmogrify some code to switch
 allocation strategy I consider naive and dangerous.

 Who ever told you process does return before allocating a few Gigs of
 RAM (and hoping on GC collection)? Right, nobody. Maybe it's an event
 loop that may run forever.

 What is missing is that code up to date assumes new == GC and works
 _like that_.

Not magic, but the tool which is quite powerful and thus it may shoot your leg.

I know what kind of thing you are talking about. It's ain't powerful it's just a hack that doesn't quite do what advertised.
 This is unsafe, but if you want it safe, don't use allocators, stay with
 GC.

BTW you were talking changing allocation of the code you didn't write. There is not even single fact that makes the thing safe. It's all working by chance or because the thing was designed to work with scoped allocator to begin with. I believe the 2nd case (design to use scoped allocation) is a) The behavior is guaranteed (determinism vs GC etc) b) Safety is assured be the designer not pure luck (and reasonable assumption that may not hold)
 In the example above, you get first arr freed by GC, second arr may
 point to nothing if myAlloc was implemented to free it before. Or you
 may get a proper arr reference if myAlloc used malloc and didn't free
 it.

Yeah I know, hence I showed it. BTW forget about malloc I'm not talking about explicit malloc being an alternative to you scheme.
 The fact that you may write bad code does not make the language (or
 concept) bad.

It does. Because it introduces easy unreliable and bug prone usage. -- Dmitry Olshansky
Jun 26 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Jun 26, 2013 at 04:10:49PM +0200, cybervadim wrote:
 On Wednesday, 26 June 2013 at 13:16:25 UTC, Jason House wrote:
Bloomberg released an STL alternative called BSL which contains an
alternate allocator model. In a nutshell object supporting custom
allocators can optionally take an allocator pointer as an
argument. Containers will save the pointer and use it for all
their allocations. It seems simple enough and does not embed the
allocator in the type.

https://github.com/bloomberg/bsl/wiki/BDE-Allocator-model

I think the problem with such approach is that you have to maniacally add support for custom allocator to every class if you want them to be on a custom allocator.

Yeah, that's a major inconvenience with the C++ allocator model. There's no way to say "switch to allocator A within this block of code"; if you're given a binary-only library that doesn't support allocators, you're out of luck. And even if you have the source code, you have to manually modify every single line of code that performs allocation to take an additional parameter -- not a very feasible approach.
 If we simply able to say - all memory allocated in this area {}
 should use my custom allocator, that would simplify the code and no
 need to change std lib.
 The next step is to notify allocator when the memory should be
 released. But for the stack based allocator that is not required.
 More over, if we introduce access to different GCs (e.g.
 mark-n-sweep, semi-copy, ref counted), we should be able to say this
 {} piece of code is my temporary, so use semi-copy GC, the other
 code is long lived and not much objects created, so use ref counted.
 That is, it is all runtime support and no need changing the library
 code.

Yeah, I think the best approach would be one that doesn't require changing a whole mass of code to support. Also, one that doesn't require language changes would be far more likely to be accepted, as the core D devs are leery of adding yet more complications to the language. That's why I proposed that gc_alloc and gc_free be made into thread-global function pointers, that can be swapped with a custom allocator's version. This doesn't have to be visible to user code; it can just be an implementation detail in std.allocator, for example. It allows us to implement custom allocators across a block of code that doesn't know (and doesn't need to know) what allocator will be used. T -- Fact is stranger than fiction.
Jun 26 2013
prev sibling next sibling parent "cybervadim" <vadim.goryunov gmail.com> writes:
On Wednesday, 26 June 2013 at 14:17:03 UTC, Dmitry Olshansky 
wrote:
 Awful. What that extra syntax had brought you? Except that now 
 new is unsafe by design?
 Other questions involve how does this allocation scope goes 
 inside of functions, what is the mechanism of passing it up and 
 down of call-stack.

 Last but not least I fail to see how scoped allocators alone 
 (as presented) solve even half of the problem.

Extra syntax allows me not touching the existing code. Imagine you have a stateless event processing. That is event comes, you do some calculation, prepare the answer and send it back. It will look like: void onEvent(Event event) { process(); } Because it is stateless, you know all the memory allocated during processing will not be required afterwards. So the syntax I suggested requires a very little change in code. process() may be implemented using std lib, doing several news and resizing. With new syntax: void onEvent(Event event) { ScopedAllocator alloc; allocator(alloc) { process(); } } So now you do not use GC for all that is created inside the process(). ScopedAllocator is a simple stack that will free all memory in one go. It is up to the runtime implementation to make sure all memory that is allocated inside allocator{} scope is actually allocated using ScopedAllocator and not GC. Does it make sense?
Jun 26 2013
prev sibling next sibling parent Robert Schadek <realburner gmx.de> writes:
 Imagine we have two delegates:

 void* delegate(size_t);  // this one allocs
 void delegate(void*);    // this one frees

 you pass both to a function that constructs you object. The first is
 used for allocation the
 memory, the second gets attached to the TypeInfo and is used by the gc
 to free
 the object.

Then it's just GC but with an extra complication.

the GC, or at least not directly. The GC algorithm would see that there is a "free delegate" attached to the object and would use this to free the memory. The same should hold true for calling GC.free. Or are you talking about ref counting and such?
Jun 26 2013
prev sibling next sibling parent "cybervadim" <vadim.goryunov gmail.com> writes:
On Wednesday, 26 June 2013 at 14:26:03 UTC, H. S. Teoh wrote:
 Yeah, I think the best approach would be one that doesn't 
 require
 changing a whole mass of code to support. Also, one that 
 doesn't require
 language changes would be far more likely to be accepted, as 
 the core D
 devs are leery of adding yet more complications to the language.

 That's why I proposed that gc_alloc and gc_free be made into
 thread-global function pointers, that can be swapped with a 
 custom
 allocator's version. This doesn't have to be visible to user 
 code; it
 can just be an implementation detail in std.allocator, for 
 example. It
 allows us to implement custom allocators across a block of code 
 that
 doesn't know (and doesn't need to know) what allocator will be 
 used.

Yes, being able to change gc_alloc, gc_free would do the work. If runtime remembers the stack of gc_alloc/gc_free functions like pushd, popd, that would simplify its usage. I think this is a very nice and simple solution to the problem.
Jun 26 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Jun 26, 2013 at 04:31:40PM +0200, cybervadim wrote:
 On Wednesday, 26 June 2013 at 14:26:03 UTC, H. S. Teoh wrote:
Yeah, I think the best approach would be one that doesn't require
changing a whole mass of code to support. Also, one that doesn't
require language changes would be far more likely to be accepted, as
the core D devs are leery of adding yet more complications to the
language.

That's why I proposed that gc_alloc and gc_free be made into
thread-global function pointers, that can be swapped with a custom
allocator's version. This doesn't have to be visible to user code; it
can just be an implementation detail in std.allocator, for example.
It allows us to implement custom allocators across a block of code
that doesn't know (and doesn't need to know) what allocator will be
used.

Yes, being able to change gc_alloc, gc_free would do the work. If runtime remembers the stack of gc_alloc/gc_free functions like pushd, popd, that would simplify its usage. I think this is a very nice and simple solution to the problem.

Adam's idea does this: tie each replacement of gc_alloc/gc_free to some stack-based object, that automatically cleans up in the dtor. So something along these lines: struct CustomAlloc(A) { void* function(size_t size) old_alloc; void function(void* ptr) old_free; this(A alloc) { old_alloc = gc_alloc; old_free = gc_free; gc_alloc = &A.alloc; gc_free = &A.free; } ~this() { gc_alloc = old_alloc; gc_free = old_free; // Cleans up, e.g., region allocator deletes the // region A.cleanup(); } } class C {} void main() { auto c = new C(); // allocates using default allocator (GC) { CustomAlloc!MyAllocator _; // Everything from here on until end of block // uses MyAllocator auto d = new C(); // allocates using MyAllocator { CustomAlloc!AnotherAllocator _; auto e = new C(); // allocates using AnotherAllocator // End of scope: auto cleanup, gc_alloc and // gc_free reverts back to MyAllocator } auto f = new C(); // allocates using MyAllocator // End of scope: auto cleanup, gc_alloc and // gc_free reverts back to default values } auto g = new C(); // allocates using default allocator } So you effectively have an allocator stack, and user code never has to directly manipulate gc_alloc/gc_free (which would be dangerous). T -- Almost all proofs have bugs, but almost all theorems are true. -- Paul Pedersen
Jun 26 2013
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
Some type system help is required to guarantee that references to 
such scope-allocated data won't escape.
Jun 26 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Jun 26, 2013 at 06:51:54PM +0400, Dmitry Olshansky wrote:
 26-Jun-2013 03:16, Adam D. Ruppe пишет:
On Tuesday, 25 June 2013 at 22:50:55 UTC, H. S. Teoh wrote:
And maybe (b) can be implemented by making gc_alloc / gc_free
overridable function pointers? Then we can override their values and
use scope guards to revert them back to the values they were before.

Yea, I was thinking this might be a way to go. You'd have a global (well, thread-local) allocator instance that can be set and reset through stack calls. You'd want it to be RAII or delegate based, so the scope is clear. with_allocator(my_alloc, { do whatever here }); or { ChangeAllocator!my_alloc dummy; do whatever here } // dummy's destructor ends the allocator scope

Both suffer from a) being totally unsafe and in fact bug prone since all references obtained in there are now dangling (and there is no indication where they came from)

How is this different from using malloc() and free() manually? You have no indication of where a void* came from either, and the danger of dangling references is very real, as any C/C++ coder knows. And I assume that *some* people will want to be defining custom allocators that wrap around malloc/free (e.g. the game engine guys who want total control).
 b) imagine you need to use an allocator for a stateful object. Say
 forward range of some other ranges (e.g. std.regex) both
 scoped/stacked to allocate its internal stuff. 2nd one may handle it
 but not the 1st one.

Yeah this is a complicated area. A container basically needs to know how to allocate its elements. So somehow that information has to be somewhere.
 c) transfer of objects allocated differently up the call graph
 (scope graph?), is pretty much neglected I see.

They're incompatible. You can't safely make a linked list that contains both GC-allocated nodes and malloc() nodes. That's just a bomb waiting to explode in your face. So in that sense, Adam's idea of using a different type for differently-allocated objects makes sense. A container has to declare what kind of allocation its members are using; any other way is asking for trouble.
 I kind of wondering how our knowledgeable community has come to this.
 (must have been starving w/o allocators way too long)

We're just trying to provoke Andrei into responding. ;-) [...]
 IMHO the only place for allocators is in containers other kinds of
 code may just ignore allocators completely.

But some people clamoring for allocators are doing so because they're bothered by Phobos using ~ for string concatenation, which implicitly uses the GC. I don't think we can just ignore that.
 std.algorithm and friends should imho be customized on 2 things only:
 
 a) containers to use (instead of array)
 b) optionally a memory source (or allocator) f container is
 temporary(scoped) to tie its life-time to smth.
 
 Want temporary stuff? Use temporary arrays, hashmaps and whatnot
 i.e. types tailored for a particular use case (e.g. with a
 temporary/scoped allocator in mind).
 These would all be unsafe though. Alternative is ref-counting
 pointers to an allocator. With word on street about ARC it could be
 nice direction to pursue.

Ref-counting is not fool-proof, though. There's always cycles to mess things up.
 Allocators (as Andrei points out in his video) have many kinds:
 a) persistence: infinite, manual, scoped
 b) size: unlimited vs fixed
 c) block-size: any, fixed, or *any* up to some maximum size
 
 Most of these ARE NOT interchangeable!
 Yet some are composable however I'd argue that allocators are not
 composable but have some reusable parts that in turn are composable.

I was listening to Andrei's talk this morning, but I didn't quite understand what he means by composable allocators. Is he talking about nesting, say, a GC inside a region allocated by a region allocator?
 Code would have to cutter for specific flavors of allocators still
 so we'd better reduce this problem to the selection of containers.

Hmm. Sounds like we have two conflicting things going on here: 1) En massé replacement of gc_alloc/gc_free in a certain block of code (which may be the entire program), e.g., for the avoidance of GC in game engines, etc.. Basically, the code is allocator-agnostic, but at some higher level we want to control which allocator is being used. 2) Specific customization of containers, etc., as to which allocator(s) should be used, with (hopefully) some kind of support from the type system to prevent mistakes like dangling pointers, escaping references, etc.. Here, the code is NOT allocator-agnostic; it has to be written with the specific allocation model in mind. You can't just replace the allocator with another one without introducing bugs or problems. These two may interact in complex ways... e.g., you might want to use malloc to allocate a pool, then use a custom gc_alloc/gc_free to allocate from this pool in order to support language built-ins like ~ and ~= without needing to rewrite every function that uses strings. Maybe we should stop conflating these two things so that we stop confusing ourselves, and hopefully it will be easier to analyse afterwards. T -- You have to expect the unexpected. -- RL
Jun 26 2013
prev sibling next sibling parent reply "Dicebot" <public dicebot.lv> writes:
By the way, while this topic gets some attention, I want to make 
a notice that there are actually two orthogonal entities that 
arise when speaking about configurable allocation - allocators 
itself and global allocation policies. I think good design should 
address both of those.

For example, changing global allocator for custom one has limited 
usability - you are anyway limited by the language design that 
makes only GC or ref-counting viable general options. However, 
some way to prohibit automatic allocations at runtime while still 
allowing manual ones may be useful - and it does not matter what 
allocator is actually used to get that memory. Once such API is 
designed, tighter classification and control may be added with 
time.
Jun 26 2013
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
26-Jun-2013 21:35, Dicebot пишет:
 By the way, while this topic gets some attention, I want to make a
 notice that there are actually two orthogonal entities that arise when
 speaking about configurable allocation - allocators itself and global
 allocation policies. I think good design should address both of those.

Sadly I believe that global allocators would still have to be compatible with GC (to not break code in hard to track ways) thus basically being a GC. Hence we can easily stop talking about them ;) -- Dmitry Olshansky
Jun 26 2013
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
27-Jun-2013 00:53, Dicebot пишет:
 On Wednesday, 26 June 2013 at 19:40:54 UTC, Dmitry Olshansky wrote:
 Sadly I believe that global allocators would still have to be
 compatible with GC (to not break code in hard to track ways) thus
 basically being a GC. Hence we can easily stop talking about them ;)

Nice way to say "we don't really need that embedded, kernel and gamedev guys". GC as a safe an obvious approach should be the default but druntime needs to provide means for tight and dangerous control upon explicit request.

Just don't use certain built-ins. Stub them out in run-time if you like. The only problematic point I see is closures allocated on heap. Frankly I see embedded, kernel and gamedev guys using ref-counting and custom data structures all the time. They all want that level of control and determinism anyway or are so resource constrained that GC is too much code space or run-time overhead anyway. Needless to say that custom run-time for the first 2 categories is required anyway so just hack the druntime. It would be nice to have hooks readily available (and documented?) to do so but hardly beyond that. -- Dmitry Olshansky
Jun 26 2013
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
27-Jun-2013 01:05, Adam D. Ruppe пишет:
 On Wednesday, 26 June 2013 at 21:00:54 UTC, Dmitry Olshansky wrote:
 Just don't use certain built-ins. Stub them out in run-time if you
 like. The only problematic point I see is closures allocated on heap.

Actually, I was kinda sorta able to solve this in my minimal d. // this would be used for automatic heap closures, but there's no way to free it...

[snip a cool hack] Yeah, I suspected something like this might work. Basically defining your own ref-count closure type and forging delegate keyword in your codebase (except in the file that defines heap closure). That still leaves chasing code like auto dg = (...){ ... } though. Maybe having it as a template Closure!(ret-type, arg types...) and instantiator function called simply closure could be more ecstatically pleasing (this is IMHO).
 It worked in my toy tests. The trick would be though to never store or
 use a non-scope builtin delegate. Using RTInfo, I believe I can
 statically verify you don't do this in the whole program,  but haven't
 actually tried yet.


 I also left built in append unimplemented, but did custom types with ~=
 that are pretty convenient. Binary ~ is a loss though, too easy to lose
 pointers with that.

-- Dmitry Olshansky
Jun 26 2013
prev sibling next sibling parent "Brian Rogoff" <brogoff gmail.com> writes:
On Wednesday, 26 June 2013 at 17:25:24 UTC, H. S. Teoh wrote:
 I was listening to Andrei's talk this morning, but I didn't 
 quite
 understand what he means by composable allocators. Is he 
 talking about
 nesting, say, a GC inside a region allocated by a region 
 allocator?

Maybe he was talking about a freelist allocator over a reap, as described by the HeapLayers project http://heaplayers.org/ in the paper from 2001 titled 'Composing High-Performance Memory Allocators'. I'm pretty sure that web site was referenced in the talk. A few publications there are from Andrei. I agree that D should support programming without a GC, with different GCs than the default one, and custom allocators, and that features which demand a GC will be troublesome. -- Brian
Jun 26 2013
prev sibling next sibling parent "Adam D. Ruppe" <destructionator gmail.com> writes:
On Wednesday, 26 June 2013 at 17:25:24 UTC, H. S. Teoh wrote:
 malloc to allocate a pool, then use a custom gc_alloc/gc_free to
 allocate from this pool in order to support language built-ins 
 like ~ and ~= without needing to rewrite every function that 
 uses strings.

Blargh, I forgot about operator ~ on built ins. For custom types it is easy enough to manage, just overload it. You can even do ~= on types that aren't allowed to allocate, if they have a certain capacity set up ahead of time (like a stack buffer) But for built ins, blargh, I don't even think we can hint on them to the gc. Maybe we should just go ahead and make the gc generational. (If you aren't using gc, I say leave binary ~ unimplemented in all cases. Use ~= on a temporary instead whenever you would do that. It is easier to follow the lifetime if you explicitly declare your temporary.)
Jun 26 2013
prev sibling next sibling parent "cybervadim" <vadim.goryunov gmail.com> writes:
On Wednesday, 26 June 2013 at 14:59:41 UTC, Dmitry Olshansky 
wrote:
 Here is a chief problem - the assumption that is required to 
 make it magically work.

 Now what I see is:

 T arr[];//TLS

 //somewhere down the line
 arr = ... ;
 else{
 ...
 alloctor(myAlloc){
 	arr = array(filter!....);
 }
 ...
 }
 return arr;

 Having an unsafe magic wand that may transmogrify some code to 
 switch allocation strategy I consider naive and dangerous.

 Who ever told you process does return before allocating a few 
 Gigs of RAM (and hoping on GC collection)? Right, nobody. Maybe 
 it's an event loop that may run forever.

 What is missing is that code up to date assumes new == GC and 
 works _like that_.

Not magic, but the tool which is quite powerful and thus it may shoot your leg. This is unsafe, but if you want it safe, don't use allocators, stay with GC. In the example above, you get first arr freed by GC, second arr may point to nothing if myAlloc was implemented to free it before. Or you may get a proper arr reference if myAlloc used malloc and didn't free it. The fact that you may write bad code does not make the language (or concept) bad.
Jun 26 2013
prev sibling next sibling parent Marco Leise <Marco.Leise gmx.de> writes:
Am Wed, 26 Jun 2013 16:30:50 +0200
schrieb Robert Schadek <realburner gmx.de>:

 
 Imagine we have two delegates:

 void* delegate(size_t);  // this one allocs
 void delegate(void*);    // this one frees

 you pass both to a function that constructs you object. The first is
 used for allocation the
 memory, the second gets attached to the TypeInfo and is used by the gc
 to free
 the object.



Does it mean 16 extra bytes for every allocation ? -- Marco
Jun 26 2013
prev sibling next sibling parent Robert Schadek <realburner gmx.de> writes:
On 06/26/2013 10:06 PM, Marco Leise wrote:
 Does it mean 16 extra bytes for every allocation ?

save it somewhere
Jun 26 2013
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Wednesday, 26 June 2013 at 19:40:54 UTC, Dmitry Olshansky 
wrote:
 Sadly I believe that global allocators would still have to be 
 compatible with GC (to not break code in hard to track ways) 
 thus basically being a GC. Hence we can easily stop talking 
 about them ;)

Nice way to say "we don't really need that embedded, kernel and gamedev guys". GC as a safe an obvious approach should be the default but druntime needs to provide means for tight and dangerous control upon explicit request.
Jun 26 2013
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Wednesday, 26 June 2013 at 21:00:54 UTC, Dmitry Olshansky 
wrote:
 Needless to say that custom run-time for the first 2 categories 
 is required anyway so just hack the druntime. It would be nice 
 to have hooks readily available (and documented?) to do so but 
 hardly beyond that.

It is an API issue. Hacking druntime is, unfortunately, inevitable but keeping ability to swap those two with no code changes simplifies development process and makes less tempting too forget about this use case when doing std lib / runtime stuff - it has been a second-class citizen for rather long time.
Jun 26 2013
prev sibling next sibling parent "Adam D. Ruppe" <destructionator gmail.com> writes:
On Wednesday, 26 June 2013 at 21:00:54 UTC, Dmitry Olshansky 
wrote:
 Just don't use certain built-ins. Stub them out in run-time if 
 you like. The only problematic point I see is closures 
 allocated on heap.

Actually, I was kinda sorta able to solve this in my minimal d. // this would be used for automatic heap closures, but there's no way to free it... ///* extern(C) void* _d_allocmemory(size_t bytes) { auto ptr = manual_malloc(bytes); debug(allocations) { char[16] buffer; write("warning: automatic memory allocation ", intToString(cast(size_t) ptr, buffer)); } return ptr; } struct HeapClosure(T) if(is(T == delegate)) { mixin SimpleRefCounting!(T, q{ char[16] buffer; write("\nfreeing closure ", intToString(cast(size_t) payload.ptr, buffer),"\n"); manual_free(payload.ptr); }); } HeapClosure!T makeHeapClosure(T)(T t) { // if(__traits(isNested, T)) { return HeapClosure!T(t); } void closureTest2(HeapClosure!(void delegate()) test) { write("\nptr is ", cast(size_t) test.ptr, "\n"); test(); auto b = test; } void closureTest() { string a = "whoa"; scope(exit) write("\n\nexit\n\n"); //throw new Exception("test"); closureTest2( makeHeapClosure({ write(a); }) ); } It worked in my toy tests. The trick would be though to never store or use a non-scope builtin delegate. Using RTInfo, I believe I can statically verify you don't do this in the whole program, but haven't actually tried yet. I also left built in append unimplemented, but did custom types with ~= that are pretty convenient. Binary ~ is a loss though, too easy to lose pointers with that.
Jun 26 2013
prev sibling next sibling parent "Adam D. Ruppe" <destructionator gmail.com> writes:
So to try some ideas, I started implementing a simple container 
with replaceable allocators: a singly linked list.

All was going kinda well until I realized the forward range it 
offers to iterate its contents makes it possible to escape a 
reference to a freed node.

auto range = list.range;
auto range2 = range;
range.removeFront();

range2 now refers to a freed node. Maybe the nodes could be 
refcounted, though a downside there is even the range won't be 
sharable, it would be a different type based on allocation 
method. (I was hoping to make the range be a sharable component, 
even as the list itself changed type with allocators.)

I guess we could  disable copy construction, and make it a 
forward range instead of an input one, but that takes some of the 
legitimate usefulness away.

Interestingly though, opApply would be ok here, since all it 
would expose is the payload.

(though if the payload is a reference type, does the container 
take ownership of it? How do we indicate that? Perhaps more 
interestingly, how do we indicate the /lack/ of ownership at the 
transfer point?)



This is all fairly easy if we just decide "we're going to do this 
with GC" or "we're going to do this C style" and do the whole 
program like that, libraries and all. But trying to mix and match 
just gets more complicated the more I think about it :( It makes 
the question of "allocators" look trivial.
Jun 26 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Jun 27, 2013 at 12:43:54AM +0200, Adam D. Ruppe wrote:
 So to try some ideas, I started implementing a simple container with
 replaceable allocators: a singly linked list.
 
 All was going kinda well until I realized the forward range it
 offers to iterate its contents makes it possible to escape a
 reference to a freed node.

 (though if the payload is a reference type, does the container take
 ownership of it? How do we indicate that? Perhaps more interestingly,
 how do we indicate the /lack/ of ownership at the transfer point?)

Maybe a type distinction akin to C++'s auto_ptr might help? Say we introduce OwnedRef!T vs. plain old T*. So something returning OwnedRef!T will need to assume ownership of the object, whereas something returning T* would just be returning a reference, but the container continues to hold ownership over the object.
 This is all fairly easy if we just decide "we're going to do this
 with GC" or "we're going to do this C style" and do the whole
 program like that, libraries and all. But trying to mix and match
 just gets more complicated the more I think about it :( It makes the
 question of "allocators" look trivial.

Heh. Yeah, I'm started to wonder if it even makes sense to try to mix-n-match GC-based and non-GC-based allocators. It seems that maybe we just have to settle for the fact of life that a GC-based object is fundamentally incompatible with a pool-allocated object, and both are also fundamentally incompatible with malloc-allocated objects, 'cos you need the code to be aware in each instance of what needs to be done to cleanup, etc.. T -- GEEK = Gatherer of Extremely Enlightening Knowledge
Jun 26 2013
prev sibling next sibling parent "Adam D. Ruppe" <destructionator gmail.com> writes:
On Wednesday, 26 June 2013 at 23:02:47 UTC, H. S. Teoh wrote:
 Maybe a type distinction akin to C++'s auto_ptr might help?

Yeah, that's what I'm thinking, but I don't really like it. Perhaps I'm trying too hard to cover everything, and should be happier with just doing what C++ does. Full memory safety is prolly out the window anyway. In std.typecons, there's a Unique!T, but it doesn't look complete. A lot of the code is commented out, maybe it was started back in the days of bug city.
 Yeah, I'm started to wonder if it even makes sense to try to 
 mix-n-match GC-based and non-GC-based allocators.

It might not be so bad if we modified D to add a lent storage class, or something, similar to some discussions about scope in the past. These would be values you may work with, but never keep; assigning them to anything is not allowed and you may only pass them to a function or return them from a function if that is also marked lent. Any regular reference would be implicitly usable as lent. int* ptr; void bar(int* a) { foo(a); // ok } int* foo(lent int* a) { bar(a); // error, cannot call bar with lent pointer ptr = a; // error, cannot assign lent value to non-lent field foo2(a); // ok foo(foo2(a)); // ok return a; // error, cannot return a lent value } lent int* foo2(lent int* a) { return a; // ok } foo(ptr); // ok (if foo actually compiled) And finally, if you take the address of a lent reference, that itself is lent; &(lent int*) == lent int**. Then, if possible, it would be cool if: lent int* a; { int* b; a = b; } That was an error, because a outlived b. But since you can't store a anywhere, the only time this would happen would be something like here. And hell maybe we could hammer around that by making lent variables head const and say they must be initialized at declaration, so "lent int* a;" is illegal as well as "a = b;". But we wouldn't want it transitively const, because then: void fillBuffer(lent char[] buffer) {} would be disallowed and that is something I would definitely want. Part of me thinks pure might help with this too.... but eh maybe not because even a pure function could in theory escape a reference via its other parameters. But with this kind of thing, we could do a nicer pointer type that does: lent T getThis() { return _this; } alias getThis this; and thus implicitly convert our inner pointer to something we can use on the outside world with some confidence that they won't sneak away any references to it. If combined with disabling the address of operator on the container itself, we could really lock down ownership.
Jun 26 2013
prev sibling next sibling parent "BLM768" <blm768 gmail.com> writes:
On Wednesday, 26 June 2013 at 23:59:01 UTC, Adam D. Ruppe wrote:
 On Wednesday, 26 June 2013 at 23:02:47 UTC, H. S. Teoh wrote:
 Maybe a type distinction akin to C++'s auto_ptr might help?

It might not be so bad if we modified D to add a lent storage class, or something, similar to some discussions about scope in the past. These would be values you may work with, but never keep; assigning them to anything is not allowed and you may only pass them to a function or return them from a function if that is also marked lent. Any regular reference would be implicitly usable as lent.

Something along those lines would probably be a good solution. It seems that we're working with three types of objects: 1. Objects that are "owned" by a scope (can be stack-allocated) 2. Objects that are "owned" by a another object (C/C++-like memory management) 3. Objects that have no single "owner" (GC memory management) The first two would probably operate under semantics like "lent" or "scope", although I'd like to propose an extension to the rules: it should be possible to store a weak reference to these types (or at least to #2) once we have weak reference support. The third type seems to be pretty much solved, seeing as we have a (mostly) working GC. Something like this might be a nice way to implement it: class Thing {} void doSomething(scope Thing t); //Takes #1, #2, or #3 by reference void doSomethingElse(owned Thing t); //Takes only #2 or #3 void main() { scope Thing t1; //stack-allocated doSomething(t1); owned Thing t2 = new Thing; //heap-allocated but freed at end of scope doSomething(t2); }
Jun 27 2013
prev sibling next sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Tuesday, 25 June 2013 at 22:22:09 UTC, cybervadim wrote:
 I know Andrey mentioned he was going to work on Allocators a 
 year ago. In DConf 2013 he described the problems he needs to 
 solve with Allocators. But I wonder if I am missing the 
 discussion around that - I tried searching this forum, found a 
 few threads that was not actually a brain storm for Allocators 
 design.

 Please point me in the right direction
 or
 is there a reason it is not discussed
 or
 should we open the discussion?


 The easiest approach for Allocators design I can imagine would 
 be to let user specify which Allocator operator new should get 
 the memory from (introducing a new keyword allocator). This 
 gives a total control, but assumes user knows what he is doing.

 Example:

 CustomAllocator ca;
 allocator(ca) {
   auto a = new A; // operator new will use 
 ScopeAllocator::malloc()
   auto b = new B;

   free(a); // that should call ScopeAllocator::free()
   // if free() is missing for allocated area, it is a user 
 responsibility to make sure custom Allocator can handle that
 }

 By default allocator is the druntime using GC, free(a) does 
 nothing for it.


 if some library defines its allocator (e.g. specialized 
 container), there should be ability to:
 1. override allocator
 2. get access to the allocator used

 I understand that I spent 5 mins thinking about the way 
 Allocators may look.
 My point is - if somebody is working on it, can you please 
 share your ideas?

Old but perhaps relevant? http://www.linkedin.com/news?viewArticle=&articleID=-1&gid=86782&type=member&item=253295471&articleURL=http%3A%2F%2Fwww%2Eallendowney%2Ecom%2Fss08%2Fhandouts%2Fberger02reconsidering%2Epdf&urlhash=96TJ&goback=%2Egmr_86782%2Egde_86782_member_253295471 (It's an academic article about memory allocation from 2002)
Jun 27 2013
prev sibling next sibling parent Marco Leise <Marco.Leise gmx.de> writes:
Am Thu, 27 Jun 2013 01:59:00 +0200
schrieb "Adam D. Ruppe" <destructionator gmail.com>:

 void fillBuffer(lent char[] buffer) {}
 
 would be disallowed and that is something I would definitely want.

Isn't that what scope is for? -- Marco
Jun 28 2013
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Friday, 28 June 2013 at 07:07:39 UTC, Marco Leise wrote:
 Am Thu, 27 Jun 2013 01:59:00 +0200
 schrieb "Adam D. Ruppe" <destructionator gmail.com>:

 void fillBuffer(lent char[] buffer) {}
 
 would be disallowed and that is something I would definitely 
 want.

Isn't that what scope is for?

Reading dlang.org makes you guess so but official position is that 'scope' does not exist, so it is hard to say what it is really for.
Jun 28 2013
prev sibling next sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Thursday, 27 June 2013 at 22:50:47 UTC, John Colvin wrote:
 Old but perhaps relevant?

 http://www.linkedin.com/news?viewArticle=&articleID=-1&gid=86782&type=member&item=253295471&articleURL=http%3A%2F%2Fwww%2Eallendowney%2Ecom%2Fss08%2Fhandouts%2Fberger02reconsidering%2Epdf&urlhash=96TJ&goback=%2Egmr_86782%2Egde_86782_member_253295471

 (It's an academic article about memory allocation from 2002)

Interesting paper. Still concurrency isn't really addressed, which is a problem to be future proof.
Jun 28 2013
prev sibling next sibling parent "Adam D. Ruppe" <destructionator gmail.com> writes:
On Friday, 28 June 2013 at 07:07:39 UTC, Marco Leise wrote:
 Isn't that what scope is for?

I don't really know. In practice, it does something else (usually nothing, but suppresses heap closure allocation on delegates). The DIPs relating to it all talk about returning refs from functions and I'm not sure if they relate to the built ins or not- I don't think it would quite work for what I have in mind.
Jun 28 2013
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Friday, 28 June 2013 at 11:55:46 UTC, Adam D. Ruppe wrote:
 On Friday, 28 June 2013 at 07:07:39 UTC, Marco Leise wrote:
 Isn't that what scope is for?

I don't really know. In practice, it does something else (usually nothing, but suppresses heap closure allocation on delegates). The DIPs relating to it all talk about returning refs from functions and I'm not sure if they relate to the built ins or not- I don't think it would quite work for what I have in mind.

It is no-op keyword in current implementation for everything but delegates. DIP speculation was based on http://dlang.org/attribute.html#scope and "Parameter Storage Classes" in http://dlang.org/function.html but that info is obviously outdated.
Jun 28 2013
prev sibling next sibling parent "Brian Rogoff" <brogoff gmail.com> writes:
On Friday, 28 June 2013 at 10:57:45 UTC, deadalnix wrote:
 On Thursday, 27 June 2013 at 22:50:47 UTC, John Colvin wrote:
 Old but perhaps relevant?

 http://www.linkedin.com/news?viewArticle=&articleID=-1&gid=86782&type=member&item=253295471&articleURL=http%3A%2F%2Fwww%2Eallendowney%2Ecom%2Fss08%2Fhandouts%2Fberger02reconsidering%2Epdf&urlhash=96TJ&goback=%2Egmr_86782%2Egde_86782_member_253295471

 (It's an academic article about memory allocation from 2002)

Interesting paper. Still concurrency isn't really addressed, which is a problem to be future proof.

http://en.wikipedia.org/wiki/Hoard_memory_allocator
Jun 28 2013
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Friday, June 28, 2013 13:55:45 Adam D. Ruppe wrote:
 On Friday, 28 June 2013 at 07:07:39 UTC, Marco Leise wrote:
 Isn't that what scope is for?

I don't really know. In practice, it does something else (usually nothing, but suppresses heap closure allocation on delegates). The DIPs relating to it all talk about returning refs from functions and I'm not sure if they relate to the built ins or not- I don't think it would quite work for what I have in mind.

Per the spec, all scope is supposed to do is prevent references in a parameter to be escaped. To be specific, it says ------- ref­er­ences in the pa­ra­me­ter can­not be es­caped (e.g. as­signed to a global vari­able) ------- So, in theory, if you had something like auto foo(scope int[] i) {...} it would prevent i or anything refering to it from being returned or assigned to any variable which will outlive the function call. However, scope currently does _nothing_ for anything other than delegates - which is why I think that using the in attribute is such an incredibly bad idea. Using either in or scope on anything other than delegates could result in all kinds of code breakage if/when scope is ever implemented for types other than delegates. For delegates, it has the advantage of telling the compiler that it doesn't need to allocate a closure (since the delegate won't be used passed the point when it's calling scope will exist as could occur if the delegate escaped the function it was passed to), but I'm not sure that even that works 100% correctly right now. We really should sort out exactly what we're going to do with scope one of these days soon. But the stuff that some of the DIPS do with scope (e.g. returning with scope - which is completely against the spec at this point) are suggestions and not at all how it currently works. - Jonathan M Davis
Jun 28 2013
prev sibling next sibling parent "Adam D. Ruppe" <destructionator gmail.com> writes:
On Friday, 28 June 2013 at 17:43:21 UTC, Jonathan M Davis wrote:
 it would prevent i or anything refering to it from being 
 returned or assigned to any variable which will outlive the
 function call. However,

That's fairly close to what I'd want. But there's two cases I'm not sure it would cover: 1: struct Unique(T) { scope T borrow(); } If the unique pointer decides to let its reference slip, it wouldn't want it going somewhere else and escaping, since that breaks the unique need. This is important for a few cases. Here's one: int* foo; { Unique!(int*) bar; foo = bar.borrow; int* ok = bar.borrow; // this should be ok, because this never exists outside the same scope as the Unique } // foo now talks to a freed *bar, so that shouldn't be allowed Similarly, if bar were reassigned, this could cause trouble, but what we might do is just disallow such reassignments, but maybe it could work if it always goes down in scope. I'd have to think about that. (I'm thinking my borrowed thing might have to be a type constructor rather than a storage class. Otherwise, you could get around it by: int* bar(scope int* foo) { int* b = foo; return b; } Unless the compiler is very smart about following where it goes.) But if scope works on the return value too, it might be ok. maybe 2: void bar(scope int* foo, int** bar) { *bar = foo; } Actually, I'm reasonably clear the spec's scope words would work for this one. But we'd need to be sure - this is one case where pure wouldn't help (pure generally would help, since it disallows assignments to the outside world, but there's enough holes that you could leak a reference). To be memory safe, these would all have to be guaranteed.
Jun 28 2013
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Friday, June 28, 2013 19:56:44 Adam D. Ruppe wrote:
 struct Unique(T) {
 scope T borrow();
 }

Per the current spec, this would not be a valid use of scope, as scope is specifically a parameter storage class and can only be used on function parameters (just like in, out, ref, and lazy). scope seems to be specifically intended for guaranteeing that an argument passed to a function does not escape that function. - Jonathan M Davis
Jun 28 2013
prev sibling parent "Brad Anderson" <eco gnuk.net> writes:
On Wednesday, 26 June 2013 at 13:16:25 UTC, Jason House wrote:
 Bloomberg released an STL alternative called BSL which contains 
 an alternate allocator model. In a nutshell object supporting 
 custom allocators can optionally take an allocator pointer as 
 an argument. Containers will save the pointer and use it for 
 all their allocations. It seems simple enough and does not 
 embed the allocator in the type.

 https://github.com/bloomberg/bsl/wiki/BDE-Allocator-model

There is also EASTL's (Electronic Arts version of STL for gamedev) take on allocators. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html#eastl_allocator
Jun 28 2013