Memory Arena

A bump allocation arena (BumpArena) pre-allocates contiguous heap chunks and satisfies individual allocations by advancing a cursor pointer forward (offset aligned up to align_of::<T>()), reducing per-object allocation overhead to a few CPU instructions and freeing all objects simultaneously when the arena is dropped or reset.

Bump Allocation and Chunk Growth

Current Chunk (4096 bytes)
+-----------------+----+----------------------+------------------------+
| Object A (24 B) |Pad | Object B (16 B)      | Free Space --->        |
+-----------------+----+----------------------+------------------------+
^                      ^                      ^                        ^
base                   aligned_offset         cursor                   capacity

Shared Allocation: alloc(&self, val: T) -> &mut T
  Because moving the vector of retired chunks does NOT move the heap buffers
   inside each Box<[MaybeUninit<u8>]>, shared `&self` can hand out `&mut T`
  references tied to the lifetime `'a` of the arena borrow.

Complete Byte Bump Arena and Typed Arena Implementation

use std::alloc::Layout;
use std::cell::{Cell, RefCell};
use std::mem::MaybeUninit;
use std::ptr;

pub struct BumpArena {
    chunk_size: usize,
    cursor: Cell<usize>,
    chunks: RefCell<Vec<Box<[MaybeUninit<u8>]>>>,
}

impl BumpArena {
    pub fn with_chunk_size(chunk_size: usize) -> Self {
        let size = chunk_size.max(256).next_power_of_two();
        let initial = Self::make_chunk(size);
        Self {
            chunk_size: size,
            cursor: Cell::new(0),
            chunks: RefCell::new(vec![initial]),
        }
    }

    fn make_chunk(size: usize) -> Box<[MaybeUninit<u8>]> {
        let mut v = Vec::with_capacity(size);
        // SAFETY: Elements are `MaybeUninit<u8>`, which do not require initialization.
        unsafe {
            v.set_len(size);
        }
        v.into_boxed_slice()
    }

    pub fn alloc<T: Copy>(&self, value: T) -> &mut T {
        let layout = Layout::new::<T>();
        let raw = self.alloc_layout(layout) as *mut T;
        // SAFETY: `raw` is properly aligned for `T`, non-null, and uniquely owned for `'self`.
        unsafe {
            ptr::write(raw, value);
            &mut *raw
        }
    }

    pub fn alloc_str(&self, s: &str) -> &str {
        let layout = Layout::from_size_align(s.len().max(1), 1).unwrap();
        let dst = self.alloc_layout(layout);
        // SAFETY: `dst` has at least `s.len()` valid bytes in the arena chunk.
        unsafe {
            ptr::copy_nonoverlapping(s.as_ptr(), dst, s.len());
            let bytes = std::slice::from_raw_parts(dst, s.len());
            std::str::from_utf8_unchecked(bytes)
        }
    }

    fn alloc_layout(&self, layout: Layout) -> *mut u8 {
        let size = layout.size().max(1);
        let align = layout.align();

        loop {
            let current = self.cursor.get();
            let aligned = (current + align - 1) & !(align - 1);
            let new_cursor = aligned + size;

            let active_cap = self.chunks.borrow().last().unwrap().len();
            if new_cursor <= active_cap {
                self.cursor.set(new_cursor);
                let mut chunks = self.chunks.borrow_mut();
                let active = chunks.last_mut().unwrap();
                // SAFETY: `aligned..new_cursor` is disjoint from all previous allocations.
                return unsafe { (active.as_mut_ptr() as *mut u8).add(aligned) };
            }

            let next_size = (self.chunk_size * 2).max(size + align);
            self.chunks.borrow_mut().push(Self::make_chunk(next_size));
            self.cursor.set(0);
        }
    }

    pub fn chunk_count(&self) -> usize {
        self.chunks.borrow().len()
    }

    pub fn total_allocated_capacity(&self) -> usize {
        self.chunks.borrow().iter().map(|c| c.len()).sum()
    }
}

#[derive(Debug, Clone, Copy)]
enum AstExpr<'a> {
    Number(i64),
    Ident(&'a str),
    Add(&'a AstExpr<'a>, &'a AstExpr<'a>),
    Mul(&'a AstExpr<'a>, &'a AstExpr<'a>),
}

impl<'a> AstExpr<'a> {
    fn eval(&self, env: &[(&str, i64)]) -> i64 {
        match *self {
            AstExpr::Number(n) => n,
            AstExpr::Ident(name) => env
                .iter()
                .find(|(k, _)| *k == name)
                .map(|(_, v)| *v)
                .unwrap_or(0),
            AstExpr::Add(lhs, rhs) => lhs.eval(env) + rhs.eval(env),
            AstExpr::Mul(lhs, rhs) => lhs.eval(env) * rhs.eval(env),
        }
    }
}

fn main() {
    let arena = BumpArena::with_chunk_size(256);

    // Allocate AST nodes and interned identifier strings directly inside the bump arena
    let var_x = arena.alloc_str("base_price");
    let var_tax = arena.alloc_str("tax_multiplier");

    let n_x = arena.alloc(AstExpr::Ident(var_x));
    let n_bonus = arena.alloc(AstExpr::Number(25));
    let subtotal = arena.alloc(AstExpr::Add(n_x, n_bonus));
    let n_tax = arena.alloc(AstExpr::Ident(var_tax));
    let root = arena.alloc(AstExpr::Mul(subtotal, n_tax));

    let env = [("base_price", 100), ("tax_multiplier", 3)];
    println!("AST Root: {:?}", root);
    println!("Evaluated result: {}", root.eval(&env));
    println!(
        "Arena stats: {} chunk(s), {} bytes capacity",
        arena.chunk_count(),
        arena.total_allocated_capacity()
    );
}

AST Root: Mul(Add(Ident("base_price"), Number(25)), Ident("tax_multiplier"))
Evaluated result: 375
Arena stats: 1 chunk(s), 256 bytes capacity