std.tempalloc

TempAlloc is a memory allocator based on a thread-local segmented stack. 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.

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

1. Pointers to memory allocated on the TempAlloc stack are still valid when the function they were allocated from returns. Functions can be written to create and return data structures on the TempAlloc stack.

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

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

It has thet 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 TempAlloc 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 TempAlloc 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.

Note:
The first segment of the TempAlloc stack is allocated lazily, so no space is allocated in any thread that does not use TempAlloc.

Synopsis:

// Initialize a new TempAlloc frame.
TempAlloc.frameInit();

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

// Release all memory allocated on TempAlloc since the last call to
// TempAlloc.frameInit().
TempAlloc.frameFree();

Author:
David Simcha

License:
Boost License 1.0

struct TempAlloc;

This struct functions as a namespace for all of the core TempAlloc functions. All of its member functions are static.

static void frameInit();

Pushes the current stack position onto an internal bookkeeping stack. A call to frameFree frees all memory allocated since the last call to frameInit.

static void frameFree();

Frees all memory allocated by TempAlloc since the last call to frameInit. This can be used to free all TempAlloc memory allocated within a function upon returning from that function.

Examples:

    void useFrameInit() {
        // Mark the current position.
        TempAlloc.frameInit();

        // Free all memory allocated by this function on exit.
        scope(exit) TempAlloc.frameFree();

        // All of these will be freed when useFrameInit() exits.
        auto ptr1 = TempAlloc.malloc(3);
        auto ptr2 = TempAlloc.malloc(1);
        auto ptr3 = TempAlloc.malloc(4);
    }

static void* malloc(size_t nbytes);

Allocates nbytes bytes on the TempAlloc stack. The last block allocated in the current thread can be freed by calling TempAlloc.free. The memory returned by this function is not scanned for pointers by the garbage collector unless GC.addRange is called.

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

Allocates an array of type T on the TempAlloc stack. For performance reasons, the returned array is not initialized. It is not scanned for pointers by the garbage collector unless GC.addRange is called. 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:

    double[] arr = TempAlloc.newArray!(double[])(100);
    assert(arr.length == 100);

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

static void free();

Frees the last block of memory allocated in the current thread by TempAlloc. Since all memory must be allocated and freed in last in first out order within a thread, there's no need to pass a pointer to the block being freed. This bookkeeping is handled internally.

static @property size_t segmentSlack();

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

CommonType!(staticMap!(ElementType,T))[] stackCat(T...)(T data);

Concatenates any number of arrays of the same type, placing results on the TempAlloc stack. The returned array is not scanned for pointers by the garbage collector unless GC.addRange is called.

Examples:

auto a = [1, 2, 3];
auto b = [4, 5, 6];
auto c = [7, 8, 9];

auto d = stackCat(a, b, c);
assert(d == [1, 2, 3, 4, 5, 6, 7, 8, 9]);

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

Copies range to an array. The array will be located on the TempAlloc stack and not scanned for pointers by the garbage collector under either of the following conditions:

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

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

If neither condition is met, the array is returned on the C heap and GC.addRange is called. In either case, TempAlloc.free or TempAlloc.frameFree will free the array as if it had been allocated on the TempAlloc stack.

Rationale:
The most common reason to call tempArray on an 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.

Examples:

auto arr = tempArray(iota(5));
assert(arr == [0, 1, 2, 3, 4]);

immutable string newFrame;

A convenience mixin, equivalent to:

TempAlloc.frameInit();  scope(exit) TempAlloc.frameFree();

Example:

void* useNewFrame() {
    // This will not be freed when useNewFrame() exits.
    auto ptr1 = TempAlloc.malloc(8);

    mixin(newFrame);

    // All of these will be freed when useNewFrame() exits.
    auto ptr2 = TempAlloc.malloc(3);
    auto ptr3 = TempAlloc.malloc(1);
    auto ptr4 = TempAlloc.malloc(4);

    // ptr1 is still valid after useNewFrame() exits.
    return ptr1;
}