std.allocator needs your help

[Andrei Alexandrescu]

On 9/23/13 1:37 PM, Peter Alexander wrote:
> What if, for example, I wanted to allocate a 4096 byte aligned block
> from the GC allocator? Do I have to create a new allocator backed by the
> GC allocator?

I've been thinking a good library component would be AlignmentAllocator 
that would work like this:

struct AlignmentAllocator(Allocator, size_t desiredAlignment)
if (Allocator.alignment < desiredAlignment)
{
     enum alignment = desiredAlignment;
     ...
}

That allocator would allocate more memory (I suspect there's a gcd 
calculation somewhere :o)) and then adjust the starting pointer of the 
allocated block to reach the requested alignment.

I'm just off the phone with Walter discussing this and related issue. 
It's an interesting problem space.

> What if the alignment is not known at compile time (e.g. hard disk page
> size or CPU cache line size)?

The proposed design assumes compile-time allocation sizes. A trick 
similar to the one above (overallocate and adjust pointer) should work.

I'd need a handful of good examples where the alignment must be known at 
runtime. Can you link to some?

> Might be better to pass the desired alignment in the allocate method.

The thing is in 99%+ of the cases you don't need it. Then perhaps in 
99%+ of the remaining cases the alignment is known during compilation. 
Nevertheless it's a change worth investigating.

>> * available is a property that returns how many total (not necessarily
>> contiguous) bytes are available for allocation. The NullAllocator
>> knows statically it has 0 bytes available so it implements it as an
>> enum. Generally allocators will implement it as a @property. This
>> property is optional.
>
> It would be useful to know the maximum available contiguous block size
> too, so that you can find out if an allocation will succeed without
> calling allocate.

I think the best way is to just go ahead and attempt an allocation, 
especially if the allocator is shared (races!). (There's some 
flexibility with expand() there, which has a minimum size and a desired 
size.) But clearly the information of the largest contiguous block is 
currently missing, and is reasonable to be considered for addition.

> It's also useful for diagnosing fragmentation issues
> e.g. "allocation failed, free memory = X, max contiguous = Y". If X is
> high and Y is low then you are highly fragmented.
>
> Of course, this should be optional.

Makes sense.

>> * allocate(s) returns a ubyte[] with length at least s, or null. (It
>> does not throw on out-of-memory because that would hurt composability;
>> it turns out many elemental allocators do naturally run out of
>> memory.) This method is required for all allocators. In most
>> allocators this method should be @safe.
>
> What are the semantics of allocate(0)? malloc(0) is implementation defined.

I defined Mallocator to return whatever malloc returns on allocate(0), 
but decided realloc() is too messed up and special-cased reallocate(0) 
to free memory and place null in the buffer. Probably I'll work the same 
logic in Mallocator.allocate(0) to eliminate platform dependencies.


Andrei