std.allocators.region

RegionAllocator is a memory allocator based on segmented stacks. A segmented stack is similar to a regular stack in that memory is allocated and freed in last in, first out order. When memory is requested from a segmented stack, it first checks whether enough space is available in the current segment, and if so bumps the stack pointer and returns. If not, a new segment is allocated. When memory is freed, the stack pointer is bumped down, and multiple allocations can be freed in a single operation. If the last segment is no longer in use, it may be returned to where it was allocated from or retained for future use.

Synopsis:

void fun() {
    // Create a new RegionAllocator using the default thread-local stack.
    auto alloc = newRegionAllocator();

    // Allocate a temporary array on the RegionAllocator stack.
    auto arr = alloc.uninitializedArray!(double[][][])(8, 6, 7);
    assert(arr.length == 8);
    assert(arr[0].length == 6);
    assert(arr[0][0].length == 7);

    // When alloc goes out of scope, all memory allocated by it is freed.
    // If alloc has been copied, then the memory is freed when all copies
    // have gone out of scope.
}

A segmented stack may be created manually using the two-argument overload of newRegionAllocator. Alternatively, a default thread-local stack may be automatically lazily created using the zero-argument overload of this function.

RegionAllocator has the following advantages compared to allocation on the call stack:

RegionAllocator

It has the following disadvantages:

It has the following advantages compared to heap allocation:

RegionAllocator

It has the following disadvantages compared to heap allocation:

Author:
David Simcha

License:
Boost License 1.0

struct RegionAllocator;

This struct provides an interface to the RegionAllocator functionality and enforces scoped deletion. A new instance is created using the newRegionAllocator function or the RegionAllocator.nested function. An instance of a RegionAllocator is defined as a RegionAllocator created by calling one of these functions and all copies of this initial object.

Each instance has reference semantics in that any copy will allocate from the same memory. When the last copy of an instance goes out of scope, all memory allocated via that instance is freed. Only the most recently created still-existing RegionAllocator instance using a given stack may be used to allocate and free memory at any given time. Deviations from this model result in a RegionAllocatorError being thrown.

An uninitialized RegionAllocator (for example RegionAllocator.init) has semantics similar to a null pointer. It may be assigned to or passed to a function. However, any attempt to call a method will result in a RegionAllocatorError being thrown.

Examples:

void foo() {
    auto alloc = newRegionAllocator();
    auto ptr1 = bar(alloc);
    auto ptr2 = alloc.allocate(42);

    // The last copy of the RegionAllocator object used to allocate ptr1
    // and ptr2 is going out of scope here.  The memory pointed to by
    // both ptr1 and ptr2 will be freed.
}

void* bar(RegionAllocator alloc) {
    auto ret = alloc.allocate(42);

    auto alloc2 = alloc.nested();
    auto ptr3 = alloc2.allocate(42);

    // ptr3 was allocated using alloc2, which is going out of scope.
    // Its memory will therefore be freed.  ret was allocated using alloc.
    // A copy of this RegionAllocator is still alive in foo() after
    // bar() executes.  Therefore, ret will not be freed on returning and
    // is still valid after bar() returns.

    return ret;
}

void* thisIsSafe() {
    // This is safe because the two RegionAllocator objects being used
    // are using two different stacks.
    auto alloc = newRegionAllocator();
    auto ptr1 = alloc.allocate(42);

    auto alloc2 = newRegionAllocator(1_048_576, GCScan.no);

    auto ptr2 = alloc2.allocate(42);
    auto ptr3 = alloc.allocate(42);
}

void* dontDoThis() {
    auto alloc = newRegionAllocator();
    auto ptr1 = alloc.allocate(42);
    auto alloc2 = alloc.nested();

    // Error:  Allocating from a RegionAllocator instance other than the
    // most recently created one that's still alive from a given stack.
    auto ptr = alloc.allocate(42);
}

void uninitialized() {
    RegionAllocator alloc;
    auto ptr = alloc.allocate(42);  // Error:  alloc is not initialized.
    auto alloc2 = alloc;  // Ok.  Both alloc, alloc2 are uninitialized.

    alloc2 = newRegionAllocator();
    auto ptr2 = alloc2.allocate(42);  // Ok.
    auto ptr3 = alloc.allocate(42);  // Error:  alloc is still uninitialized.

    alloc = alloc2;
    auto ptr4 = alloc.allocate(42);  // Ok.
}

Note:
Allocations larger than this.segmentSize are handled as a special case and fall back to allocating directly from the C heap. These large allocations are freed as if they were allocated normally when free or freeLast is called or the last copy of a RegionAllocator instance goes out of scope. However, due to the extra bookkeeping required, destroying a region (as happens when the last copy of a RegionAllocator instance goes out of scope) will require time linear instead of constant in the number of allocations for regions where these large allocations are present.

BUGS:
Finalizers/destuctors are never called on freeing objects allocated with create, newArray, uninitializedArray or array, as this would create an unacceptable amount of bookkeeping overhead and prevent O(1) freeing of regions.

RegionAllocator nested();

Creates a new RegionAllocator instance using the same stack as this. Memory can be allocated and freed from the returned instance, but cannot be allocated and freed from this until the last copy of the returned instance is destroyed.

Examples:

    void fun()
    {
        auto alloc = newRegionAllocator(1_024 * 1_024, GCScan.no);
        auto ptr1 = alloc.allocate(42);

        foreach(i; 0..10)
        {
            auto alloc2 = alloc.nested();
            auto ptr2 = alloc.allocate(42);   // Error.
            auto ptr3 = alloc2.allocate(42);  // Works.

            // ptr3 is freed on exiting this scope, since the last copy
            // of alloc2 is destroyed.
        }

        auto ptr4 = alloc.allocate(42);  // Works.  alloc2 no longer exists.

        // ptr4 is freed on exiting this scope, since the last copy of
        // alloc is destroyed.
    }

void* allocate(size_t nBytes);

Allocates nBytes bytes. The last block allocated from this RegionAllocator instance can be freed by calling RegionAllocator.free or RegionAllocator.freeLast or will be automatically freed when the last copy of this RegionAllocator instance goes out of scope.

Allocation requests larger than segmentSize are allocated directly on the C heap, are scanned by the GC iff gcScanned is true.

void freeLast();

Frees the last block of memory allocated by the current RegionAllocator. Throws a RegionAllocatorError if this RegionAllocator is not the most recently created still-existing RegionAllocator on the stack it uses.

void free(void* ptr);

Checks that ptr is a pointer to the block that would be freed by freeLast then calls freeLast. Throws a RegionAllocatorError if the pointer does not point to the block that would be freed by freeLast.

bool resize(const(void)* ptr, size_t newSize);

Attempts to resize a previously allocated block of memory in place. This is possible only if ptr points to the beginning of the last block allocated by this RegionAllocator instance and, in the case where newSize is greater than the old size, there is additional space in the segment that ptr was allocated from. Additionally, blocks larger than this RegionAllocator's segment size cannot be grown or shrunk.

Returns:
True if the block was successfully resized, false otherwise.

const pure nothrow @property @safe bool gcScanned();

Returns whether the stack used by this RegionAllocator instance is scanned by the garbage collector.

static size_t alignBytes(size_t nBytes);

Returns the number of bytes to which an allocation of size nBytes is guaranteed to be aligned.

static pure nothrow size_t allocSize(size_t nBytes);

Returns the number of bytes used to satisfy an allocation request of nBytes. Will return a value greater than or equal to nBytes to account for alignment overhead.

bool isAutomatic;

False because memory allocated by this allocator is not automatically reclaimed by the garbage collector.

bool isScoped;

True because, when the last last copy of a instance goes out of scope, the memory it references is automatically freed.

bool freeIsChecked;

True because if memory is freed via free() instead of freeLast() then the pointer is checked for validity.

@property size_t segmentSize();

Returns the segment size of the stack used by this RegionAllocator.

@property size_t segmentSlack();

Returns the maximum number of bytes that may be allocated in the current segment.

Unqual!(ElementType!(R))[] array(R)(R range);

Copies range, which must be a finite input range, to an array. The array will be located on the RegionAllocator stack if any of the following conditions apply:

1. std.traits.hasIndirections!(ElementType!R) is false.

2. R is a builtin array. In this case range maintains pointers to all elements at least until array returns, preventing the elements from being freed by the garbage collector. A similar assumption cannot be made for ranges other than builtin arrays.

3. The stack used by this RegionAllocator is scanned by the garbage collector.

If none of these conditions is met, the array is returned on the C heap and GC.addRange is called. In either case, RegionAllocator.free, RegionAllocator.freeLast, or the last copy of this RegionAllocator instance going out of scope will free the array as if it had been allocated on the RegionAllocator stack.

Rationale:
The most common reason to call array on a builtin array is to modify its contents inside a function without affecting the caller's view. In this case range is not modified and prevents the elements from being freed by the garbage collector. Furthermore, if the copy returned does need to be scanned, the client can call GC.addRange before modifying the original array.

Examples:

    auto alloc = newRegionAllocator();
    auto arr = alloc.array(iota(5));
    assert(arr == [0, 1, 2, 3, 4]);

@property DynamicAllocator dynamicAllocator();

Returns an instance of the std.allocators.allocator.DynamicAllocator interface encapsulating this RegionAllocator instance. The DynamicAllocator instance returned does not prevent the freeing of memory allocated on this RegionAllocator instance. The memory is freed when the last copy of this RegionAllocator instance goes out of scope, even if a DynamicAllocator instance referencing this RegionAllocator instance is still alive. Use of the DynamicAllocator after the last copy of this RegionAllocator instance has gone out of scope will result in undefined behavior.

Examples:

    // The following is an example of what **not** to do:
    import std.allocators.region;

    void main()
    {
        auto dyn = returnDynamic();
    }

    DynamicAllocator returnDynamic()
    {
        auto alloc = newRegionAllocator();
        auto dyn = alloc.dynamicAllocator;

        // The last copy of alloc is going out of scope.  When dyn is
        // returned, it will no longer be valid.  Calling methods on it
        // from main() will result in undefined behavior.
    }

RegionAllocator newRegionAllocator();

Returns a new RegionAllocator that uses the default thread-local stack. If this is called when a RegionAllocator using this stack is already in existence, the semantics will be identical to calling the nested method on the most recently created RegionAllocator instance using this stack.

Examples:

void fun()
{
    auto alloc = newRegionAllocator();
    auto ptr1 = alloc.allocate(42);
    fun2();

    // ptr1 freed on exit because last copy of alloc is going out of scope.
}

void fun2()
{
    auto alloc2 = newRegionAllocator();  // Same as calling alloc.nested().
    auto ptr2 = alloc2.allocate(42);     // Works.

    // ptr2 freed on exit because last copy of alloc2 is going out of scope.
}

enum GCScan;

This flag determines whether a given RegionAllocator created using a new stack is scanned for pointers by the garbage collector (GC). If yes, the entire stack is scanned, not just the part currently in use, since there is currently no efficient way to modify the bounds of a GC region. The stack is scanned conservatively, meaning that any bit pattern that would point to GC-allocated memory if interpreted as a pointer is considered to be a pointer. This can result in GC-allocated memory being retained when it should be freed. Due to these caveats, it is recommended that any stack scanned by the GC be small and/or short-lived.

no
yes

RegionAllocator newRegionAllocator(size_t segmentSize, GCScan shouldScan);

Returns a new RegionAllocator that uses a newly created stack. The underlying stack space is freed when the last RegionAllocator using this stack goes out of scope.

Parameters:

size_t segmentSize	The size of each segment of the stack.
GCScan shouldScan	Whether the stack should be scanned by the garbage collector.

nothrow @property @safe size_t threadLocalSegmentSize(); @property @safe size_t threadLocalSegmentSize(size_t newSize);

These properties get and set the segment size of the default thread-local stack. The default size is 4 megabytes. The setter is only effective before the zero-argument overload of newRegionAllocator has been called for the first time in the current thread. Attempts to set this property after the first call to this function from the current thread throw a RegionAllocatorError.

nothrow @property @safe bool threadLocalStackIsScannable(); @property @safe bool threadLocalStackIsScannable(bool shouldScan);

These properties determine whether the default thread-local stack is scanned by the garbage collector. The default is no. In most cases, scanning a stack this long-lived is not recommended, as it will cause too many false pointers. (See GCScan for details.)

The setter is only effective before the zero-argument overload of newRegionAllocator has been called for the first time in the current thread. Attempts to set this property after the first call to this function from the current thread throw a RegionAllocatorError.

class RegionAllocatorError: object.Error;

The exception that is thrown on invalid use of . This exception is not thrown on out of memory. An OutOfMemoryError is thrown instead.

std

etc

core

std.allocators.region