std.allocator needs your help

[Dmitry Olshansky]

24-Sep-2013 19:56, Andrei Alexandrescu пишет:
> On 9/24/13 1:46 AM, Dmitry Olshansky wrote:
>> 23-Sep-2013 03:49, Andrei Alexandrescu пишет:
>> Do you imagine Typed allocators as something more then adapters that
>> simplify a common pattern of allocate + emplace / destroy + deallocate?
>> (create!T/destroy!T)
>
> Well as a simple matter tracing allocators will have to store dynamic
> type information (just like the current GC does).
>
> Also, I hope we'll be able to allow allocators to define Pointer(T),
> Ref(T) etc. that supplant replacements for the built-in notions of
> pointer, reference etc. Then, user code that uses these notions instead
> of the built-in ones will be guaranteed some nice properties (e.g.
> automatic reference counting). Unfortunately I don't see a way for an
> allocator to enforce that its users don't do illegal things such as
> escaping addresses etc. So it would be a discipline-backed scheme.
> Notable beneficiaries will be containers.

Indeed I thought of Ref!T and Pointer!T for ARC. And just like you said 
I do not see a way of avoiding any potential abuse. But it is some power 
to desire.

>> First things first - can't allocator return alignment as run-time value
>> - a property (just like 'available' does)? The implementation contract
>> is that it must be O(1) vanila syscall-free function. (Read this as
>> consult system info exactly once, at construction).
>
> It could, but as I mentioned to Manu - at this level any cost is
> significant. Even changing from a compile-time constant to a global
> static dynamically-initialized constant has a cost. Making alignment an
> instance variable turns stateless allocators into stateful ones.

Hm most could just get away with an enum. Am I missing something?

>> Thinking more of it - it also may be immutable size_t? Then it gets
>> proper value at construction and then is never changed.
>
> I'm hoping to get away with a static function "static uint alignment()"
> that (a) is CTFEable for most allocators/platforms, (b) uses a
> dynamically-initialized static constant for a few. Then derived
> allocators will inherit CTFEability.

A check for CTFE-ablity might do the trick. The run-time dependent ones 
usually would immediately hit a wall that is a sys-call or WinAPI.

> Would a per-allocator-type alignment suffice?

I see alignment as an inherent property of the way an allocator acquires 
memory. Sad but true one can't determine the actual alignment of some 
important ones at CTFE. Even worse adapters would in turn depend on 
these system-specific run-time values such as half a page, 2 cache lines 
etc.

auto my2PageAligner = AligningAllocator(page_size*2, rootAllocator)

where page_size is calculated elsewhere.


>>> * deallocate(b) deallocates the memory allocated for b. b must have been
>>> previously allocated by the same allocator. This method is usually
>>> unsafe (but there are notable implementations that may offer safety,
>>> such as unbounded freelists.) This method is optional.
>>
>> Does the following implication hold "have a deallocate" --> must be
>> manually managed? Otherwise how would one reliably work with it and not
>> leak? This brings us to traits that allocators may (should) have
>> a-la automatic? free-all on termination? Zeros on allocate (more common
>> then one would think)? etc.
>
> The global GC does offer manual deallocation. It's the presence of
> collect() that indicates tracing abilities. If deallocateAll() is
> present, user code must assume it will be called during destruction.
>

I was looking into how some library would have to tweak its code based 
on presence/absence of some methods. For instance if there is collect, 
it doesn't have to call deallocate (even if present). If not then it has 
to call deallocate (again if present). Ditto with deallocateAll  with or 
without explicit deallocate.

> That said, I've also been thinking of adding a variety of Boolean
> telling properties. "Zeros on allocate" has an important relationship
> with safety of higher-level objects - zeros offer "not really
> initialized but without forged pointers so memory-safe" objects.

Great.

>>> * deallocateAll() deallocates in one shot all memory previously
>>> allocated by this allocator. This method is optional, and when present
>>> is almost always unsafe (I see no meaningful @safe implementation.)
>>> Region allocators are notable examples of allocators that define this
>>> method.
>>
>> Okay.. I presume region "mark" works by spiting off a subinstance of
>> allocator and "release" by deallocateAll().
>
> Nice, didn't think of this.

I made it up 'cause I thought you did thought of this ;)

[snip]

>> To the point - we have address space and optionally memory committed in
>> there, leading us to a 3-state of an  _address range_:
>> available, reserved, committed. The ranges of 2nd state are dirt cheap
>> (abundant on 64bit) and could be easily flipped to committed and back.
>>
>> So I have a pattern I want to try to fit in your design. At present it
>> is a datastructure + allocation logic. What I would want is clean and
>> nice composition for ultimate reuse.
> [snip]
>
> Interesting. I'll be looking forward to what you come up with. Yes, for
> large, coarse-granularity allocations, tapping into OS' paging
> capabilities is the best way to go.
>

Would love to do just that.. once we figure out some minor details.

>> Now how to fit this monster into the current API...
>> Plainly I need a way to tell hey Mr. Allocator RESERVE me a 1Gb of RAM
>> but don't chew on, it please. In other words - allocate needs something
>> like a "guaranteed capacity of the block". By default it could be ==
>> size.
>>
>> struct Allocator
>> {
>> ...
>> //allocate size bytes with a block of with no less then capacity bytes.
>> void[] allocate(size_t size, size_t capacity=size);
>> ...
>> }
>>
>> Or maybe somehow add a reserve method explicitly...
>
> Assuming you have an optional two-argument allocate() primitive, once
> you get the initial allocation, how do you commit it? By calling
> expand() I assume? Would that be enough?

expand should do the trick. I think that nicely saves on primitives 
count. But we may have to add a 'shrink' if you are so bent on never 
decreasing size in expand :)
And ... reallocate doesn't cut it as long as there is no big red tape 
on it that says - if decreasing the size reallocation it is ALWAYS 
in-place (it might not be true for some allocators - e.g. realloc 
doesn't guarantee even this IIRC).

>
> In the reserve()-based API - how would that work? Does reserve returns a
> void[] with size zero and then you expand() it?

In the reserve curiously one has to return a pointer to where the block 
is reserver _and_ a size of reserved range. Yes, one can't touch said 
memory range yet. So said 0 actual size is assumed implicitly.

void[] reserve(size_t maxSize);

Usage is like this:

auto range = reserve(1024*1024*1024);
auto memory = range[0..0];
auto capacity = range.length;
expand(memory, someSize, someSize);
...

Other option is to be "honest" and return a tuple of (pointer,capacity) 
and not a slice. It's still a bit hairy as it may as well be.

-- 
Dmitry Olshansky