std.allocator needs your help

[Manu]

On 23 September 2013 12:28, Andrei Alexandrescu <
SeeWebsiteForEmail at erdani.org> wrote:

> On 9/22/13 6:35 PM, Manu wrote:
>
>> Well it looks like a good start, but the thing I'm left wondering after
>> reading this is still... how is it actually used?
>> I think the greatest challenge is finding a simple, clean
>>
>
> Oxford comma please :o)
>
>
>  and correct
>> way to actually specify which allocator should be used for making
>> allocations throughout your code, and perhaps more troublesome; within
>> generic code, and then layers of generic code.
>>
>
> My design makes it very easy to experiment by allowing one to define
> complex allocators out of a few simple building blocks. It is not a
> general-purpose allocator, but it allows one to define any number of such.


Oh okay, so this isn't really intended as a system then, so much a
suggested API?
That makes almost all my questions redundant. I'm interested in the system,
not the API of a single allocator (although your API looks fine to me).
I already have allocators I use in my own code. Naturally, they don't
inter-operate with anything, and that's what I thought std.allocator was
meant to address.

 Are you intending to be able to associate a particular allocator with a
>> class declaration?
>>
>
> No, or at least not at this level.
>
>
>  What about a struct declaration?
>>
>
> Same answer.
>
>
>  What about a region of code (ie, a call tree/branch).
>> What if the given allocator should be used for most of the tree, except
>> for a couple of things beneath that always want to use their explicit
>> allocator?
>>
>
> The proposed design makes it easy to create allocator objects. How they
> are used and combined is left to the application.


Is that the intended limit of std.allocator's responsibility, or will
patterns come later?

Leaving the usage up to the application means we've gained nothing.
I already have more than enough allocators which I use throughout my code.
The problem is that they don't inter-operate, and certainly not with
foreign code/libraries.
This is what I hoped std.allocator would address.

 What if I want to associate an allocator instance, not just an allocator
>> type (ie, I don't want multiple instances of the same type(/s) of
>> allocators in my code, how are they shared?
>>
>
> An allocator instance is a variable like any other. So you use the classic
> techniques (shared globals, thread-local globals, passing around as
> parameter) for using the same allocator object from multiple places.


Okay, that's fine... but this sort of manual management implies that I'm
using it explicitly. That's where it all falls down for me.

Eg, I want to use a library, it's allocation patterns are incompatible with
my application; I need to provide it with an allocator.
What now? Is every library responsible for presenting the user with a
mechanism for providing allocators? What if the author forgets? (a problem
I've frequently had to chase up in the past when dealing with 3rd party
libraries)

Once a library is designed to expect a user to supply an allocator, what
happens if the user doesn't? Fall-back logic/boilerplate exists in every
library I guess...
And does that mean that applications+libraries are required to ALWAYS
allocate through given allocator objects?
That effectively makes the new keyword redundant. And what about the GC?

I can't really consider std.allocator intil it presents some usage patterns.

 It wasn't clear to me from your demonstration, but 'collect()' implies
>> that GC becomes allocator-aware; how does that work?
>>
>
> No, each allocator has its own means of dealing with memory. One could
> define a tracing allocator independent of the global GC.


I'm not sure what this means. Other than I gather that the GC and
allocators are fundamentally separate?
Is it possible to create a tracing allocator without language support? Does
the current language insert any runtime calls to support the GC?

I want a ref-counting GC for instance to replace the existing GC, but it's
impossible to implement one of them nicely without support from the
language, to insert implicit inc/dec ref calls all over the place, and to
optimise away redundant inc/dec sequences.

 deallocateAll() and collect() may each free a whole lot of memory, but
>> it seems to me that they may not actually be aware of the individual
>> allocations they are freeing; how do the appropriate destructors for the
>> sub-allocations get called?
>>
>
> No destructors are called at this level. Again, all these allocators
> understand is ubyte[].


Fair enough. That's a problem for another time then.

 I have a suspicion you're going to answer most of these questions with
>> the concept of allocator layering, but I just don't completely see it.
>>
>
> No, it's just that at this level some of these questions don't even have
> an appropriate answer - like we discuss atoms and molecules and you ask
> about building floors and beams and pillars.


Yep, fair enough.
I just saw "I am making good progress on the design of std.allocator" and
presumed you had some thoughts about actual usage semantics of the system.
I can easily define an allocator to use in my own code if it's entirely up
to me how I use it, but that completely defeats the purpose of this
exercise.
Until there aren't standard usage patterns, practises, conventions that ALL
code follows, then we have nothing. I was hoping to hear your thoughts
about those details.

 It's quite an additional burden of resources and management to manage
>> the individual allocations with a range allocator above what is supposed
>> to be a performance critical allocator to begin with.
>>
>
> I don't understand this.


It's irrelevant here.
But fwiw, in relation to the prior point about block-freeing a range
allocation; there will be many *typed* allocations within these ranges, but
a typical range allocator doesn't keep track of the allocations within.
This seems like a common problem that may or may not want to be addressed
in std.allocator.
If the answer is simply "your range allocator should keep track of the
offsets of allocations, and their types", then fine. But that seems like
boilerplate that could be automated, or maybe there is a different/separate
system for such tracking?

 C++'s design seems reasonable in some ways, but history has demonstrated
>> that it's a total failure, which is almost never actually used (I've
>> certainly never seen anyone use it).
>>
>
> Agreed. I've seen some uses of it that quite fall within the notion of the
> proverbial exception that prove the rule.


I think the main fail of C++'s design is that it mangles the type.
I don't think a type should be defined by the way it's memory is allocated,
especially since that could change from application to application, or even
call to call. For my money, that's the fundamental flaw in C++'s design.

 Some allocators that I use regularly to think about:
>>
>> A ring-buffer:
>>    * Like a region allocator I guess, but the circular nature adds some
>> minor details, and requires the user to mark the heap from time to time,
>> freeing all allocations between the old mark and the new mark.
>>
>> A pool:
>>    * Same as a free-list, but with a maximum size, ie, finite pool of
>> objects pre-allocated and pre-populating the freelist.
>>
>
> I implemented the finite size for a freelist.
>
>
>  A pool-group:
>>    * Allocate from a group of pools allocating differently sized
>> objects. (this is a good test for allocator layering, supporting a group
>> of pools above, and fallback to the malloc heap for large objects)
>>
>
> I implemented that as well, it's one of the best designs I've defined in
> my life.


Well as an atom, as you say, it seems like a good first step.
I can't see any obvious issues, although I don't think I quite understand
the collect() function if it has no relation to the GC. What is it's
purpose?
If the idea is that you might implement some sort of tracking heap which is
able to perform a collect, how is that actually practical without language
support?

I had imagined going into this that, like the range interface which the
_language_ understands and interacts with, the allocator interface would be
the same, ie, the language would understand this API and integrate it with
'new', and the GC... somehow.
If allocators are just an object like in C++ that people may or may not
use, I don't think it'll succeed as a system. I reckon it needs deep
language integration to be truly useful.

The key problem to solve is the friction between different libraries, and
different moments within a single application its self.
I feel almost like the 'current' allocator needs to be managed as some sort
of state-machine. Passing them manually down the callstack is no good. And
'hard' binding objects to their allocators like C++ is no good either.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20130923/37b5f975/attachment-0001.html>