A faster bump allocator for rust

Say hello to stumpalo.

Stumpalo is a bump allocator.

Stumpalo has scoped stack support.

Stumpalo is extremely fast.

Stumpalo has a logo, created very hastily.

Stumpalo’s logo is stumpy:

# Speed

You’re probably using a bump allocator because you want raw allocation throughput.

Let’s see how fast stumpalo is, compared to other libraries.

Benchmark machine: AMD Ryzen 3900x, Arch Linux, kernel 7.0.3

# Where does the speed come from

In an arena allocator, the fast path is everything. The fast path has to check whether there’s room in the current chunk, if so, allocate the value in the current chunk, and if not, jump to the slow path.

# Using more information

Rustc / LLVM is able to erase if/else statements whose conditions are expressions known at compile-time.

Different types have different information available at compile-time. Think alignment and size. When this information is available, stumpalo uses it, as well as information about the hardware you’re running on, to avoid overflow/underflow checks, when overflow/underflow couldn’t possibly occur anyway.

Generally, stumpalo’s fast-paths contain a single conditional branch, and as few as six instructions.

# Less indirection

A stumpalo arena contains pointers to the top and bottom of the chunk. Other libraries contain a pointer to a chunk, whose header contains pointers to their top. Stumpalo goes through one less layer of indirection to read the top.

# Example

The following function:

fn alloc_u32(a: &Arena, n: u32) -> &mut u32 {
    a.alloc(n)
}

Compiles down to this fast path:

alloc_u32:
  mov     rcx, qword ptr [rdi]
  and     rcx, -4
  lea     rax, [rcx - 4]
  cmp     rax, qword ptr [rdi + 8]
  jb      example::ArenaRef::alloc_slow_with::h903e68372b5b408b
  mov     dword ptr [rcx - 4], esi
  mov     qword ptr [rdi], rax
  ret

That’s:

1. Load the top pointer
2. Round top down to a multiple of alignment (4)
3. Subtract size (4) from top
4. Compare top against bottom
5. If less, tail call to the slow path
6. Write the value to the chunk
7. Store the new top
8. Return

If there are multiple allocations in a row, then the first instruction, loading the top, is avoided. The stub for the slow path is expanded to update the register.

This is a fairly simple example, but stumpalo produces tiny, fast code across the board.

# Scoped stacks

Scoped stacks let you use the arena temporarily, and revert it to a previous state once you’re done.

This can be useful as a sort of scratch area. Using the arena after it’s been used as a scratch area will reuse allocations made for the scratch area.

If you’re using a bump allocator, you probably like amortizing allocations. How about amortizing the allocations across uses of your allocation amortizer? I’m dizzy.

let mut arena = Arena::new();

// This is necessary if you need to keep references alive from
// the outer scope, after the inner scope returns.
// Otherwise, just call `with_scope` on the arena directly.
let arena = arena.as_arena_ref_mut();

let a = arena.alloc(1u32);

arena.with_scope(|scope: &mut ArenaRef| {
    let temporary = scope.alloc(2u32);
    scope.with_scope(|scope: &mut ArenaRef| {
        // Wow, you can have nested scopes.
        // That might be useful... I guess...
    });
});
// After a scope returns, the arena is reset to its previous position.
// Any chunks allocated for the inner scope are added to a free list for reuse.

// 'a' is still accessible
assert_eq!(*a, 1);

A lot of effort went into coming up with a safe API for scoped stacks. There are tests that various misuses of scopes fail to compile in the ui tests directory.

Thanks for reading, and thank you to bumpalo, a fantastic bump allocator I’ve been using for years.