std.allocator ready for some abuse

[Andrei Alexandrescu]

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