Hello,


I know it's been a long wait. Hopefully it was worth it. The alpha release of untyped allocators is ready for tire-kicking and a test drive.

Code: https://github.com/andralex/phobos/blob/allocator/std/allocator.d

Dox: http://erdani.com/d/phobos-prerelease/std_allocator.html

Warning: this is alpha quality. Unit tests are thin, and there are no benchmarks. Both would be appreciated, particularly benchmarks to validate the gains (which I speculate can be very sizable) of custom-built, special-purpose allocators compared to traditional allocators.

I acknowledge I'm clearly in no position to evaluate this design. I have been knocking around it for long enough to have no idea how easy it is to get into it from the outside, or how good it is. By all signs I could gather this feels like good design, and one of the best I've ever put together. The allocators defined have an archetypal feeling, are flexible both statically and dynamically, and morph and combine in infinite ways.

CAllocator and CAllocatorImpl make the link between the static and dynamic worlds. Once an allocator is assembled out of pieces and finely tuned, wrapping it in a dynamic API is a snap.

Please destroy! I've literally sweat as I'm sending this :o).


Andrei

Andrei Alexandrescu:

> and morph and combine in infinite ways.

Yes, those combination capabilities look very nice :-)

I presume this module is not in "core" because it's meant to be used from normal D code.

- Could some new/extra D language/compiler support/features help this module usage safety, efficiency, expressibility or usage syntax (beside Issue 11331)?
- Can you create an hierarchical allocator with those?
- Are some operating system memory functions (below C malloc) used/supported/addable/useful for those allocators? (Including awareness of virtual memory management from the OS).

Bye,
bearophile

On 10/24/2013 12:54 PM, Andrei Alexandrescu wrote:
> I know it's been a long wait. Hopefully it was worth it. The alpha release of
> untyped allocators is ready for tire-kicking and a test drive.
>
> Code: https://github.com/andralex/phobos/blob/allocator/std/allocator.d
>
> Dox: http://erdani.com/d/phobos-prerelease/std_allocator.html

I'm impressed. I looked for 3 or 4 must haves, and they were there! It covers all the cases I've written custom allocators for.

The design looks great. Easy to grasp and covers almost all imaginable use cases.

'Almost' because it would be nice to also have ScopeAllocator!N ~ FallbackAllocator!(InsituRegion!N, Mallocator) which would automatically deallocate all heap-allocated blocks when exiting the scope (i.e. no deallocate method, array of pointers to be freed is kept on a C heap).

On 10/24/13 1:46 PM, bearophile wrote:
> Andrei Alexandrescu:
>
>> and morph and combine in infinite ways.
>
> Yes, those combination capabilities look very nice :-)
>
> I presume this module is not in "core" because it's meant to be used
> from normal D code.

Interesting - moving to core is a possibility if we find it necessary.

> - Could some new/extra D language/compiler support/features help this
> module usage safety, efficiency, expressibility or usage syntax (beside
> Issue 11331)?

I thought about that a lot, too, while I was working on the design. Kinda analyzing my own going. It's generally been a pleasant experience - i.e. whenever I'd find myself in a bind there was some nice way out of it. One thing that I found myself wishing is uniformly aliasing something to something else. There's plenty of code like:

static if (staticallyKnownAlignment!Primary
        && staticallyKnownAlignment!Fallback)
    enum uint alignment = min(Primary.alignment, Fallback.alignment);
else
    uint alignment()
    {
        return min(primary.alignment, fallback.alignment);
    }

This is aimed at making the alignment either a statically-known constant or a dynamic property, depending on two type parameters. There's not a lot of duplication but it's quite annoying to have to write this. Would be great if I could just write e.g.

alias alignment = min(primary.alignment, fallback.alignment);

and have the thing just automagically do the right thing.

There have been some good idioms I used gainfully, i.e. I think the use of unbounded and chooseAtRuntime could become quite common.

"Turtles all the way" are awesome because they allow me to get work done without having to pop up and down. Consider for example:

    bool reallocate(ref void[] b, size_t newSize)
    {
        bool crossAllocatorMove(From, To)(ref From from, ref To to)
        {
            auto b1 = to.allocate(newSize);
            if (!b1) return false;
            if (b.length < newSize) b1[0 .. b.length] = b[];
            else b1[] = b[0 .. newSize];
            static if (hasMember!(From, "deallocate"))
                from.deallocate(b);
            b = b1;
            return true;
        }

        if (primary.owns(b))
        {
            if (primary.reallocate(b, newSize)) return true;
            // Move from primary to fallback
            return crossAllocatorMove(primary, fallback);
        }
        if (fallback.reallocate(b, newSize)) return true;
        // Interesting. Move from fallback to primary.
        return crossAllocatorMove(fallback, primary);
    }

This is code that moves memory across two allocators, in either directions. The original version duplicated the actual work. Then I considered a version that would define crossAllocatorMove as a private method. Then I tried the above, which just worked awesomely nice.

But above all there's the property of Things Just Working (tm). Compared to e.g. the time when I designed ranges, there's a lot less toil for a lot more effect. Consider e.g. the Segregator with multiple arguments:

template Segregator(Args...) if (Args.length > 3)
{
    // Binary search
    private enum cutPoint = ((Args.length - 2) / 4) * 2;
    static if (cutPoint >= 2)
    {
        alias Segregator = .Segregator!(
            Args[cutPoint],
            .Segregator!(Args[0 .. cutPoint], Args[cutPoint + 1]),
            .Segregator!(Args[cutPoint + 2 .. $])
        );
    }
    else
    {
        // Favor small sizes
        alias Segregator = .Segregator!(
            Args[0],
            Args[1],
            .Segregator!(Args[2 .. $])
        );
    }

    // Linear search
    //alias Segregator = .Segregator!(
    //    Args[0], Args[1],
    //    .Segregator!(Args[2 .. $])
    //);
}

Granted, it's not easy to get into, but can't be made much easier because it does something highly non-trivial: a left-leaning binary search through a subset of the template arguments. That's in order to find the best size class to allocate. (Linear version shown in comment, probably we should enable that with a policy.) Such code would have been much harder to get going in the past because of random bugs and limitations in the compiler and inscrutable error messages.

The entire code base stands at 4000 lines, documentation and all, yet allows for a lot of allocator designs.

> - Can you create an hierarchical allocator with those?

Not sure what that means (I recall the phrase has been discussed but forgot what it means).

> - Are some operating system memory functions (below C malloc)
> used/supported/addable/useful for those allocators? (Including awareness
> of virtual memory management from the OS).

Definitely!

* http://stackoverflow.com/questions/3839922/aligned-malloc-in-gcc comes to mind.

* http://en.wikipedia.org/wiki/Sbrk

* http://en.wikipedia.org/wiki/Mmap

These would be implemented as top allocators (a la Mallocator). On top thereof, nice block allocators etc. can be easily defined.

Also the final version should define a few convenience types that are pre-assembled allocators that are known to be useful: heaps, reaps, freelist batteries come to mind.


Andrei

On 10/24/13 2:08 PM, Walter Bright wrote:
> On 10/24/2013 12:54 PM, Andrei Alexandrescu wrote:
>> I know it's been a long wait. Hopefully it was worth it. The alpha
>> release of
>> untyped allocators is ready for tire-kicking and a test drive.
>>
>> Code: https://github.com/andralex/phobos/blob/allocator/std/allocator.d
>>
>> Dox: http://erdani.com/d/phobos-prerelease/std_allocator.html
>
> I'm impressed. I looked for 3 or 4 must haves, and they were there! It
> covers all the cases I've written custom allocators for.

<big sigh of relief>


Andrei

On 10/24/13 2:16 PM, Artem Tarasov wrote:
> The design looks great. Easy to grasp and covers almost all imaginable
> use cases.
>
> 'Almost' because it would be nice to also have ScopeAllocator!N ~
> FallbackAllocator!(InsituRegion!N, Mallocator) which would automatically
> deallocate all heap-allocated blocks when exiting the scope (i.e. no
> deallocate method, array of pointers to be freed is kept on a C heap).

Great point, clearly you cut to the chase :o). Yes, I hope to integrate that, and I'm a bit pained I didn't have the time to do that.

The way I see that could be done is by defining a ScopedAllocator that uses internally an AffixAllocator with a doubly-linked list tracking all allocations. In the destructor, ScopedAllocator would walk the list and deallocate everything allocated since its construction.

Andrei

On Thursday, 24 October 2013 at 21:20:02 UTC, Andrei Alexandrescu wrote:
> The way I see that could be done is by defining a ScopedAllocator that uses internally an AffixAllocator with a doubly-linked list tracking all allocations. In the destructor, ScopedAllocator would walk the list and deallocate everything allocated since its construction.

Can this be generalized as a proxy allocator which simply implements deallocateAll, on top of its parent allocator's primitives?

The list can be singly-linked if random deallocation is not needed.

Awesome! Will Appender get an option to use a suitable allocator?

On Thursday, 24 October 2013 at 21:31:42 UTC, Namespace wrote:
> Awesome! Will Appender get an option to use a suitable allocator?

A dream of me, that will probably never come true, would be also something like this:
----
with (Mallocator) {
    int[] arr;
    arr ~= 42; /// will use Mallocator.it.allocate internal
}
----