Pools, slabs, and arenas

The object pool

An object pool is a fixed number of slots for values of one type, allocated at startup, with a record of which are empty. Taking a slot replaces Box::new, returning it replaces the drop, and neither calls the allocator. It serves values that come and go in no fixed order, as orders do between the strategy’s decision and the venue’s last word.

use std::mem::MaybeUninit;

pub struct Pool<T> {
    slots: Vec<MaybeUninit<T>>, // room for n values, allocated once
    free: Vec<u32>,             // a stack of the indices of empty slots
    live: Vec<bool>,            // live[i]: slot i holds a value
}

impl<T> Pool<T> {
    pub fn with_capacity(n: usize) -> Self {
        assert!(n <= u32::MAX as usize);
        let mut slots = Vec::with_capacity(n);
        slots.resize_with(n, MaybeUninit::uninit);
        let free = (0..n as u32).rev().collect(); // slot 0 on top
        Pool { slots, free, live: vec![false; n] }
    }

    /// A slot for `v`, or `None` when all n are in use: the pool never grows.
    pub fn alloc(&mut self, v: T) -> Option<u32> {
        let i = self.free.pop()?;
        self.slots[i as usize].write(v);
        self.live[i as usize] = true;
        Some(i)
    }

    pub fn get(&self, i: u32) -> &T {
        assert!(self.live[i as usize], "slot {i} is empty");
        // SAFETY: live[i] is true only while slot i holds a value from alloc.
        unsafe { self.slots[i as usize].assume_init_ref() }
    }

    pub fn free(&mut self, i: u32) {
        assert!(self.live[i as usize], "slot {i} freed twice");
        self.live[i as usize] = false;
        // SAFETY: as in get; the flag is cleared first, so this runs once.
        unsafe { self.slots[i as usize].assume_init_drop() };
        self.free.push(i); // never more than n indices: never reallocates
    }
}

MaybeUninit<T> is room for a T that the compiler does not assume holds one, since reading it before a write is undefined behaviour, which the compiler may assume never happens. The free field is a stack of indices: alloc pops one and the free method pushes it back, and since it never holds more than n it never reallocates. The live flags let get take any index safely; without them, get on a freed slot would read a value that is not there.

The caller keeps the index, a 4-byte handle where a pointer takes 8. A pointer kept after its box was dropped points into memory the allocator may have handed on; an index always points into the pool, so a stale one is a panic or, if the slot was reused, the wrong order: a logic bug, never a corrupted heap. A generation counter per slot, carried in the handle, catches the second case, as a tag protects a lock-free free list from ABA, a value that left and came back looking untouched. Chapter 3’s FreeList is this stack made safe for several threads with a compare-and-swap on its head; a pool owned by one thread, as the gateway owns its orders, needs only a Vec. Like the thread cache, the stack hands back the most recently freed slot, the likeliest to be in L1.

The slab

A slab is a pool of one type, and the name is the kernel’s. Jeff Bonwick’s slab allocator, built for Sun’s Solaris kernel and published in 1994, keeps a cache per kind of object the kernel makes many of, each carved from slabs, runs of pages divided into equal slots, and keeps freed objects initialised so that a reused one skips its constructor. Linux’s kernel allocators descend from it, and sudo slabtop lists their caches by type. One type per pool is what makes it cheap: every slot is the same size, so slot i sits at the base plus i times that size, no slot needs a header, nothing is split or merged, and the free structure is a list of indices. A Pool<T> is a slab of one cache.

The arena

An arena, or bump allocator, is one block of memory and an offset into it. Allocating rounds the offset up to the value’s alignment, hands out that address and adds the size: a compare, an add and a store, 1–2 ns. No single value can be freed; the arena is reset at a boundary, its offset set to zero, and everything in it is gone in one store. Here the boundary is the batch: what the strategy makes for one batch, and has finished with at its end, lives in the arena. For that lifetime an arena beats a pool: no record of what is free, values of any type side by side on shared lines, and one store at the end instead of a push per value. bumpalo is the crate to read; here the arena holds each batch’s Intents, the orders the strategy has decided to send:

use bumpalo::Bump;

pub fn run(batches: &[Vec<Update>], mut send: impl FnMut(&[Intent])) {
    let mut arena = Bump::with_capacity(64 * 1024); // one 64 KB block, at startup
    for batch in batches {
        // Values whose lives end with the batch: each allocation bumps the offset.
        let intents = arena.alloc_slice_fill_iter(batch.iter().map(Intent::from));
        send(intents);
        arena.reset(); // all gone at once; the block is kept
    }
}

The catch is that nothing in the arena may outlive the reset, since a reference kept past it points at bytes the next batch overwrites. In bumpalo Rust’s lifetimes enforce this: every reference alloc returns borrows the arena, and reset takes &mut self, so while one is alive the compiler refuses the reset with error E0502. reset runs no destructors, so a value owning a String leaks it, and a batch larger than the block quietly takes another chunk from the global allocator unless set_allocation_limit forbids it.