why allocators are not discussed here

[H. S. Teoh]

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