rust-obstack

A fast segmented stack allocator, supporting multiple objects of any type.

A type of arena allocator, obstacks deallocate memory all at once, when the Obstack itself is destroyed. The benefit is extremely fast allocation: just a pointer bump. Unlike a typed arena, a single Obstack can contain values with any number of different types.

For Copy types pushing a value to an Obstack returns a standard mutable reference:

let r: &mut u8 = stack.push_copy(42);
assert_eq!(*r, 42);

As Copy types can't implement Drop, nothing needs to be done to deallocate the value beyond deallocating the memory itself, which is done en-mass when the Obstack itself is dropped. push_copy() is thus limited to types that implement Copy.

Types that do not implement Copy may implement Drop. As Rust's type system doesn't have a negative !Drop trait, Obstack has a second method - push() - that is not restricted to Copy types. This method returns the wrapper type Ref<T>, that wraps the underlying mutable reference. This wrapper owns the value on the stack, and ensures that drop is called when the wrapper goes out of scope. Essentially Ref is the equivalent of Box, but using an Obstack rather than the heap.

In practice even when the Ref wrapper is used, if the underlying type doesn't actually implement a meaningful drop method, the Rust compiler is able to optimize away all calls to drop, resulting in the same performance as for Copy types; the actual Ref::drop() method is [inline(always)] to aid this process. This is important as not all non-drop types can implement Copy - notably mutable references can't.

Obstack allocates memory as a segmented stack consisting of one or more segments of contiguous memory. Each time the top segment becomes full, a new segment is allocated from the heap. To ensure the total number of allocations remains small, segments are allocated in a powers-of-two fashion, with each segment being twice the size of the previous one.

Once a segment has been allocated it's stable for the life of the Obstack, allowing the values contained in that segment to be referenced directly; Rust lifetimes ensure that the references are valid for the lifetime of the Obstack.

Benchmarks

Some preliminary benchmarks can be run with:

cargo bench

tl;dr: Approximately 10x faster to allocate and deallocate a linked-list.