std.regionallocator

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 increments the stack pointer and returns. If not, a new segment is allocated. When memory is freed, the stack pointer is decremented. If the last segment is no longer in use, it may be returned to where it was allocated from or retained for future use.

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

1. Pointers to memory allocated on a RegionAllocator stack are still valid when the function they were allocated from returns, unless the last instance of the RegionAllocator object they were allocated from goes out of scope. Functions can be written to create and return data structures on the RegionAllocator stack.

2. It's possible to have more than one stack per thread.

3. Since it is a segmented stack, large allocations can be performed with no danger of stack overflow errors.

4. It guarantees 16-byte alignment of all allocated objects.

It has the following disadvantages:

1. The extra checks due to stack segmentation make allocation slightly slower and prevent simultanelous deallocation of several objects from being a single decrement of the stack pointer.

2. Memory allocated on RegionAllocator is accessed through an extra layer of pointer indirection compared to memory on the call stack.

It has the following advantages compared to heap allocation:

1. Both allocation and deallocation are extremely fast. Most allocations consist of verifying enough space is available, incrementing a pointer and a performing a few cheap bookkeeping operations. Most deallocations consist decrementing a pointer and performing a few cheap bookkeeping operations.

2. The segmented stack is thread-local, so synchronization is only needed when a segment needs to be allocated or freed.

3. Fragmentation is not an issue when allocating memory on the RegionAllocator stack, though it can be an issue when trying to allocate a new segment.

It has the following disadvantages compared to heap allocation:

1. The requirement that memory be freed in last in, first out order.

2. No automatic garbage collection.

A segmented stack may be created manually. Alternatively, a default thread-local stack that is automatically created lazily on the first attempt to use it may be used.

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

Author:
David Simcha

License:
Boost License 1.0

class RegionAllocatorException: object.Exception;

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

enum GCScan;

This flag determines whether a given RegionAllocatorStack 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

struct RegionAllocatorStack;

This object represents a segmented stack. Memory can be allocated from this stack using a std.regionallocator RegionAllocator.regionallocator RegionAllocator object. Multiple RegionAllocator objects may be created per RegionAllocatorStack but each RegionAllocator uses a single RegionAllocatorStack.

For most use cases it's convenient to use the default thread-local instance of RegionAllocatorStack, which is lazily instantiated on the first call to the global function std.regionallocator.newRegionAllocator. Occasionally it may be useful to have multiple independent stacks in one thread, in which case a RegionAllocatorStack can be created manually.

RegionAllocatorStack is reference counted and has reference semantics. When the last copy of a given instance goes out of scope, the memory held by the RegionAllocatorStack instance is released back to the heap. This cannot happen before memory allocated to a RegionAllocator instance is released back to the stack, because a RegionAllocator holds a copy of the RegionAllocatorStack instance it uses.

Examples:

import std.regionallocator;

void main() {
    fun1();
}

void fun1() {
    auto stack = RegionAllocatorStack(1_048_576, GCScan.no);
    fun2(stack);

    // At the end of fun1, the last copy of the RegionAllocatorStack
    // instance pointed to by stack goes out of scope.  The memory
    // held by stack is released back to the heap.
}

void fun2(RegionAllocatorStack stack) {
    auto alloc = stack.newRegionAllocator();
    auto arr = alloc.newArray!(double[])(1_024);

    // At the end of fun2, the last copy of the RegionAllocator instance
    // pointed to by alloc goes out of scope.  The memory used by arr
    // is released back to stack.
}

this(size_t segmentSize, GCScan shouldScan);: Create a new RegionAllocatorStack with a given segment size in bytes.
RegionAllocator newRegionAllocator();: Creates a new RegionAllocator region using this stack.
const pure nothrow @property @safe bool gcScanned();: Whether this stack is 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 RegionAllocatorStack instance. The default size is 4 megabytes. The setter is only effective before the global function 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 RegionAllocatorException.

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

These properties determine whether the default thread-local RegionAllocatorStack instance 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 std.regionallocator.GCScan for details.)

The setter is only effective before the global function 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 an Exception.

struct RegionAllocator;

This struct provides an interface to the RegionAllocator functionality and enforces scoped deletion. A new instance using the thread-local RegionAllocatorStack instance is created using the global newRegionAllocator function. A new instance using an explicitly created RegionAllocatorStack is created using RegionAllocatorStack.newRegionAllocator.

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 using a given RegionAllocatorStack may be used to allocate and free memory at any given time. Deviations from this model result in a RegionAllocatorException 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 RegionAllocatorException being thrown.

Examples:

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

    // The last instance of the region allocator 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 = newRegionAllocator();
    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.
    // An instance 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 RegionAllocatorStack objects.
    auto alloc = newRegionAllocator();
    auto ptr1 = alloc.allocate(42);

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

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

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

    // 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.
}

void* allocate(size_t nBytes);

Allocates nBytes bytes on the RegionAllocatorStack used by this RegionAllocator instance. 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.

void freeLast();

Frees the last block of memory allocated by the current RegionAllocator. Throws a RegionAllocatorException if this RegionAllocator is not the most recently created still-existing RegionAllocator using its RegionAllocatorStack instance.

void free(void* ptr);

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

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

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

auto newArray(T, I...)(I sizes);

Allocates an array of type T. T may be a multidimensional array. In this case sizes may be specified for any number of dimensions from 1 to the number in T.

Examples:

    auto alloc = newRegionAllocator();
    double[] arr = alloc.newArray!(double[])(100);
    assert(arr.length == 100);

    double[][] matrix = alloc.newArray!(double[][])(42, 31);
    assert(matrix.length == 42);
    assert(matrix[0].length == 31);

auto uninitializedArray(T, I...)(I sizes);

Same as newArray, except skips initialization of elements for performance reasons.

static bool resize(void* p, size_t newSize);

Dummy implementation for compatibility with allocator interface. Always returns false.

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 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 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 RegionAllocatorStack instance 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]);

RegionAllocator newRegionAllocator();

Returns a new RegionAllocator that uses the default thread-local RegionAllocatorStack instance.

std

etc

core

std.regionallocator