Am 23.09.2013 01:49, schrieb Andrei Alexandrescu:
> Hello,
>
>
> 2. Untyped allocator - traffics exclusively in ubyte[].
>

Why "ubyte[]" and not "void[]"?


-- 
Kind Regards
Benjamin Thaut

On 9/22/2013 9:19 PM, Manu wrote:
> Following this train of thought, I can imagine a really nice end goal would be
> that the existing GC is effectively plugged in as a library, and people can
> easily substitute it for their own GC if they want/need to.

It already is, and has been from the beginning. Rainer, for example, uses a different GC for VisualD.

dmd knows naught about the GC.

On Monday, 23 September 2013 at 04:19:34 UTC, Manu wrote:
> You've just described C++ verbatim.
> And you've previously agreed that C++'s approach totally failed. Can you
> explain how this is different from C++, and how it solves the issues that
> defeated that design?
>
> One possibility I'm keeping in mind is that of defining a dynamic interface

Once you have static allocator you can go dynamic easily:

interface DynamicAllocator // isAllocator==true
{
    // whatever the interface is
}

struct StaticAllocator // isAllocator==true
{
}

struct Container(ALLOCATOR = DynamicAllocator) if (isAllocator!ALLOCATOR)
{
    this(ALLOCATOR a){}

}

class DynamicAllocatorWrapper(T) : DynamicAllocator if (is(T) == struct)
{
    // wraps any static allocator to be callable using dynamic interface
}

With that boilerplate you can easily create allocator agnostic containers:

auto c = Container(new DynamicAllocatorWrapper!(StaticAllocator)())

and you can create specialized version if you need speed very much:

auto c = Container!(StaticAllocator)(StaticAllocator());

On 2013-09-23 01:49, Andrei Alexandrescu wrote:

> I am making good progress on the design of std.allocator, and I am
> optimistic about the way it turns out. D's introspection capabilities
> really shine through, and in places the design does feel really
> archetypal - e.g. "this is the essence of a freelist allocator". It's a
> very good feeling. The overall inspiration comes from Berger's
> HeapLayers, but D's introspection takes that pattern to a whole new level.

I agree with Manu here. I thought the whole point was to come up with a design and API how the allocators are supposed to be used. How they integrate with user code.

Here's a quick idea:

I can think of at least four different usage patterns how an allocator can be set. Hopefully this will be backwards compatible as well.

1. Globally - The same allocator is used in the whole application by all threads

2. Thread local - The allocator is set per thread. Different threads can used different allocators

3. Function local - This is the most intrusive. Sets the allocator for a given function call

4. Block local - The allocator is used during a given block

This will require some interaction with the runtime and library and probably use OOP. We define two module variables in some module in druntime, say rt.allocator:

module rt.allocator:

shared Allocator globalAllocator;
Allocator allocator;

shared this ()
{
    globalAllocator = GCAllocator.allocator;
}

The global allocator is, by default, a GC allocator (the GC we're currently using). For each thread we set the thread local allocator to be the same as the global allocator:

allocator = globalAllocator;

By default all code will use "new" to allocate memory. druntime will have three functions which the "new" keyword is lowered to. They could look something like this:

extern (C) ubyte[] _d_tl_new (size_t size)
{
    return _d_new(size, rt.allocator.allocator);
}

extern (C) ubyte[] _d_global_new (size_t size)
{
    return _d_new(size, rt.allocator.globalAllocator);
}

extern (C) ubyte[] _d_new (size_t size, Allocator allocator)
{
    if (memory = allocator.allocate(size))
        return memory;

    onOutOfMemoryError();
}

By default "new" is lowered to a call to "_d_tl_new", which will allocate using the thread local allocator, which is by default the same as the global allocator, that is, the GC. In this way we maintain the current method of allocating memory.

When using "new shared", it's lowered to a function call to "_d_global_new", which uses the global allocator.

For block local allocator an ideal syntax would be:

allocator (GCAllocator.allocator)
{
    // explicitly use the GC allocator within this block.
}

If that's not possibly we can define a function look like this:

useAllocator (alias allocator, alias block) ()
{
    auto currentAllocator = core.allocator.allocator;
    scope (exit)
        core.allocator.allocator = currentAllocator;

    block();
}

Which is used, something like this:

useAllocator!(GCAllocator.allocator, {
    // explicitly use the GC allocator within this block.
});

Or alternately, using a struct:

struct UseAllocator
{
    private Allocator currentAlloctor;

    this (Allocator allocator)
    {
        currentAlloctor = core.allocator.allocator;
    }

    ~this ()
    {
        rt.allocator.allocator = currentAlloctor;
    }
}

UseAllocator useAllocator (Allocator allocator)
{
    return UseAllocator(allocator);
}


{
    auto _ = useAllocator(GCAllocator.allocator);
    // explicitly use the GC allocator within this block.
}

Of curse it's also possible to explicitly set the thread local or global allocator for a more fine grained control. The above functions are just for convenience and to make sure the allocator is restored.

Function local allocator would just be a function taking an allocator as a parameter, example:

void process (Allocator) (int a, Allocator allocator = core.allocator.allocator)
{
    auto _ = useAllocator(allocator);
    // use the given allocator throughout the rest of this function scope
}

Some bikeshedding:

> struct NullAllocator
> {
>      enum alignment = real.alignof;
>      enum size_t available = 0;
>      ubyte[] allocate(size_t s) shared { return null; }
>      bool expand(ref ubyte[] b, size_t minDelta, size_t maxDelta) shared
>      { assert(b is null); return false; }
>      bool reallocate(ref ubyte[] b, size_t) shared
>      { assert(b is null); return false; }
>      void deallocate(ubyte[] b) shared { assert(b is null); }
>      void collect() shared { }
>      void deallocateAll() shared { }
>      static shared NullAllocator it;
> }

I would put the asserts in an "in" block.

> * "it" is an interesting artifact. Allocators may or may not hold
> per-instance state. Those that don't are required to define a global
> shared or thread-local singleton called "it" that will be used for all
> calls related to allocation. Of course, it is preferred for maximum
> flexibility that "it" is shared so as to clarify that the allocator is
> safe to use among different threads. In the case of the NullAllocator,
> this is obviously true, but non-trivial examples are the malloc-based
> allocator and the global garbage collector, both of which implement
> thread-safe allocation (at great effort no less).

You have to come up with a better name than "it". If it's some kind of singleton instance then the standard name is usually "instance". Another suggested would be "allocator".

-- 
/Jacob Carlborg

On Sunday, 22 September 2013 at 23:49:56 UTC, Andrei Alexandrescu wrote:
> ...

In general I like it though I do agree with concerns mentioned that without speculation about high-level API and usage examples it is rather hard to evaluate its practical applicability. For example, you have mentioned somewhere in comments that it is planned to embed allocator as part of template site like in C++ and it does not really sound a good idea.

On Monday, 23 September 2013 at 07:31:46 UTC, Jacob Carlborg wrote:
> On 2013-09-23 01:49, Andrei Alexandrescu wrote:
>
>> I am making good progress on the design of std.allocator, and I am
>> optimistic about the way it turns out. D's introspection capabilities
>> really shine through, and in places the design does feel really
>> archetypal - e.g. "this is the essence of a freelist allocator". It's a
>> very good feeling. The overall inspiration comes from Berger's
>> HeapLayers, but D's introspection takes that pattern to a whole new level.
>
> I agree with Manu here. I thought the whole point was to come up with a design and API how the allocators are supposed to be used. How they integrate with user code.
>
> Here's a quick idea:
>
> I can think of at least four different usage patterns how an allocator can be set. Hopefully this will be backwards compatible as well.
>
> 1. Globally - The same allocator is used in the whole application by all threads
>
> 2. Thread local - The allocator is set per thread. Different threads can used different allocators
>
> 3. Function local - This is the most intrusive. Sets the allocator for a given function call
>
> 4. Block local - The allocator is used during a given block

5. Class local - The allocator is used for specific types (e.g. ASTNode in a compiler)

6. Class-hierarchy - The allocator is used for a specific type hierarchy (e.g. ASTNode might have sub classes Statement,BinOp,etc)

7. Container local - The C++ way which binds allocation to a wrapping container

8. Task local - like Thread local but for std.parallelism.Task

That's it for now.

This is quite a long list, which means it is probably exhaustive. There should be a generic approach which encompasses at least those cases.

On 23 September 2013 15:37, Walter Bright <newshound2@digitalmars.com>wrote:

> On 9/22/2013 9:19 PM, Manu wrote:
>
>> Following this train of thought, I can imagine a really nice end goal
>> would be
>> that the existing GC is effectively plugged in as a library, and people
>> can
>> easily substitute it for their own GC if they want/need to.
>>
>
> It already is, and has been from the beginning. Rainer, for example, uses a different GC for VisualD.
>
> dmd knows naught about the GC.
>

Sure, true. But little things like separate it into its own lib, so you can
easily link a different one, or not link one at all.
Also, what about language support? How much language support is there
currently?
I don't think I could currently write the ref-counting GC that I'd like
without extensive language support.
inc/dec ref calls would need to be inserted all over the place by he
compiler, and optimiser would need to know how to remove redundant inc/dec
sequences.

On 9/23/13, Benjamin Thaut <code@benjamin-thaut.de> wrote:
> Why "ubyte[]" and not "void[]"?

Probably to make the GC avoid scanning into the array.

On 2013-09-23 11:31, qznc wrote:

> 5. Class local - The allocator is used for specific types (e.g. ASTNode
> in a compiler)
>
> 6. Class-hierarchy - The allocator is used for a specific type hierarchy
> (e.g. ASTNode might have sub classes Statement,BinOp,etc)
>
> 7. Container local - The C++ way which binds allocation to a wrapping
> container
>
> 8. Task local - like Thread local but for std.parallelism.Task
>
> That's it for now.
>
> This is quite a long list, which means it is probably exhaustive. There
> should be a generic approach which encompasses at least those cases.

That's a good addition to the list.

-- 
/Jacob Carlborg

On 9/22/13 9:03 PM, Manu wrote:
> On 23 September 2013 12:28, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org <mailto:SeeWebsiteForEmail@erdani.org>>
> wrote:
>     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?

For some definition of "system" and "API", yes :o).

> 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.

Great. Do you have a couple of nontrivial allocators (heap, buddy system etc) that could be adapted to the described API?

>     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?

Some higher level design will come later. I'm not sure whether or not you'll find it satisfying, for reasons I'll expand on below.

> 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.

Again, if you already have many allocators, please let me know if you can share some.

std.allocator will prescribe a standard for defining allocators, with which the rest of std will work, same as std.range prescribes a standard for defining ranges, with which std.algorithm, std.format, and other modules work. Clearly one could come back with "but I already have my own ranges that use first/done/next instead of front/empty/popFront, so I'm not sure what we're gaining here".

>     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.

I think a disconnect here is that you think "it" where I think "them". It's natural for an application to use one allocator that's not provided by the standard library, and it's often the case that an application defines and uses _several_ allocators for different parts of it. Then the natural question arises, how to deal with these allocators, pass them around, etc. etc.

> 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)

If the author forgets and hardcodes a library to use malloc(), I have no way around that.

> 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...

The library wouldn't need to worry as there would be the notion of a default allocator (probably backed by the existing GC).

> And does that mean that applications+libraries are required to ALWAYS
> allocate through given allocator objects?

Yes, they should.

> That effectively makes the new keyword redundant.

new will still be used to tap into the global shared GC. std.allocator will provide other means of allocating memory.

> And what about the GC?

The current global GC is unaffected for the time being.

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

Then you'd need to wait a little bit.

>         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?

Yes, they'd be distinct. Imagine an allocator that requests 4 MB from the GC as NO_SCAN memory, and then does its own management inside that block. User-level code allocates and frees e.g. strings or whatever from that block, without the global GC intervening.

> Is it possible to create a tracing allocator without language support?

I think it is possible.

> Does the current language insert any runtime calls to support the GC?

Aside from operator new, I don't think so.

> 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.

Unfortunately that's a chymera I had to abandon, at least at this level. The problem is that installing an allocator does not get to define what a pointer is and what a reference is. These are notions hardwired into the language, so the notion of turning a switch and replacing the global GC with a reference counting scheme is impossible at the level of a library API.

(As an aside, you still need tracing for collecting cycles in a transparent reference counting scheme, so it's not all roses.)

What I do hope to get to is to have allocators define their own pointers and reference types. User code that uses those will be guaranteed certain allocation behaviors.

> 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.

It doesn't. As long as the standard prescribes ONE specific API for defining untyped allocators, if you define your own to satisfy that API, then you'll be able to use your allocator with e.g. std.container, just the same as defining your own range as std.range requires allows you to tap into std.algorithm.

> 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;

What is 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.

Do you mean s/range/region/?

> 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?

If you meant region, then yes that's boilerplate that hopefully will be reasonably automated by std.allocator. (What I discussed so far predates that stage of the design.)

>         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.

This is not a flaw as much as an engineering choice with advantages and disadvantages on the relative merits of which reasonable people may disagree.

There are two _fundamental_ flaws of the C++ allocator design, in the sense that they are very difficult to argue in favor of and relatively easy to argue against:

1. Allocators are parameterized by type; instead, individual allocations should be parameterized by type.

2. There is no appropriate handling for allocators with state.

The proposed std.allocator design deals with (2) with care, and will deal with (1) when it gets to typed allocators.

> 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?

At this point collect() is only implemented by the global GC. It is possible I'll drop it from the final design. However, it's also possible that collect() will be properly defined as "collect all objects allocated within this particular allocator that are not referred from any objects also allocated within this allocator". I think that's a useful definition.

> 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?

Language support would be needed for things like scanning the stack and the globals. But one can gainfully use a heap with semantics as described just above, which requires no 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.

The D language has no idea what a range is. The notion is completely defined in std.range.

> 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.

I guess that's to be seen.

> 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.

I think it's understood that if a library chooses its own ways to allocate memory, there's no way around that. The point of std.allocator is that it defines a common interface that user code can work with.


Andrei