Hello,


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.

Several details are still in flux, but at the top level it seems most natural to divide things in two tiers:

1. Typed allocator, i.e. every request for allocation comes with the exact type requested;

2. Untyped allocator - traffics exclusively in ubyte[].

Initially I thought it's impossible to separate the two, but it turns out there are profound generic realities about untyped allocators that make them the perfect foundation for typed allocators, without considerable abstraction costs.

I need to prove that before I'm sure, because so far I only have an archetype of untyped allocators, with typed allocators to follow. There's always the possibility that some hitch shows itself only when actually trying to implement various typed allocators.

Anyhow, here's the general interface of an untyped allocator. In fact I'll showcase the simplest allocator - the NullAllocator, which has zero memory to offer. (In spite of its do-absolutely-nothing stance, the NullAllocator is surprisingly useful as a "terminator" for certain layered allocators.) Anyhow, here it is (explanations follow):

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

Primitives:

* alignment is a compile-time constant yielding the alignment of allocated data. Many allocators offer the maximum alignment of the platform (for which I used real.alignof above). This constant is required for all allocators.

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

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

* expand(b, minDelta, maxDelta) grows b's length by at least minDelta (and on a best-effort basis by at least maxDelta) and returns true, or does nothing and returns false. In most allocators this should be @safe. (One key insight is that expand() can be made @safe whereas shrink() or realloc() are most often not; such mini-epiphanies are very exciting because they put the design on a beam guide with few principles and many consequences.) The precondition is that b is null or has been previously returned by allocate(). This method is optional.

* reallocate(b, s) reallocates (like C's realloc) b to at least s bytes and returns true, or does nothing and returns false. It is possible that the memory is moved. This method is optional, and usually unsafe. (This was mostly introduced to accommodate C's realloc() within the allocator design.)

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

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

* collect() frees unused memory that had been allocated with this allocator. This optional method is implemented by tracing collectors and is usually @safe.

* "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).

There are quite a few more things to define more precisely, but this part of the design has become quite stable. To validate the design, I've defined some simple allocators (Mallocator, GCAllocator, Freelist, StackRegion, Region etc) but not the more involved ones, such as coalescing heaps, buddy system etc.

If you have an interest in memory allocators and would like to design (or have around) an allocator that fits the API above, please post it. For layering purposes, don't call malloc() or sbrk() for getting large blocks of memory from the system; instead, use another Allocator as your parent allocator in a pattern as follows:

struct MyAllocator(Allocator)
{
    static if (is(typeof(Allocator.it))) alias Allocator.it _parent;
    else Allocator _parent;
    ... use _parent for getting memory ...
}

This allows MyAllocator to use stateful and stateless allocators transparently by just referring to _parent. Of course, your allocator may take other generic parameters in addition to Allocator, or take none at all if it's a "root" allocator (sbrk() or Mallocator would be examples).

Destroy!