731 Fundamental

731-tiered-memory-strategy — Tiered Memory Strategy

Functional Programming

Tutorial

The Problem

Real-time systems — game engines, audio DSP, embedded firmware — cannot afford to call the global allocator in hot paths because it may block or cause fragmentation. The solution is a tiered strategy: trivially small data lives on the stack (Tier 1), medium-lived working data uses a fast bump arena with a fixed slab (Tier 2), and only large or long-lived data falls back to the heap (Tier 3). This mirrors the design of modern memory allocators like jemalloc and mimalloc, which maintain thread-local arenas before escalating to the global heap.

🎯 Learning Outcomes

• Implement a bump allocator (BumpArena) backed by a stack slab with Cell<usize> offset

• Understand why bump allocation is O(1) and lock-free: just increment a pointer

• Use Rust's lifetime system to tie arena-allocated slices to the arena's lifetime

• Model the three tiers as an enum (Stack, Arena, Heap) with a unified as_slice interface

• Recognize when to reset an arena (O(1), no destructors) vs. drop it

Code Example

#![allow(clippy::all)]
/// 731: Tiered Memory — Stack → Arena Pool → Heap
use std::cell::Cell;

// ── Tier 2: Bump Arena ────────────────────────────────────────────────────────

/// A simple bump allocator backed by a fixed-size stack slab.
/// All allocations are `u8` slices with `'arena` lifetime.
struct BumpArena<const CAP: usize> {
    slab: [u8; CAP],
    offset: Cell<usize>,
}

impl<const CAP: usize> BumpArena<CAP> {
    const fn new() -> Self {
        BumpArena {
            slab: [0u8; CAP],
            offset: Cell::new(0),
        }
    }

    /// Allocate `n` bytes from the arena. Returns `None` if full.
    fn alloc(&self, n: usize) -> Option<&mut [u8]> {
        let start = self.offset.get();
        let end = start.checked_add(n)?;
        if end > CAP {
            return None;
        }
        self.offset.set(end);
        // SAFETY: we've verified bounds; slab lives as long as &self
        let ptr = unsafe { (self.slab.as_ptr() as *mut u8).add(start) };
        Some(unsafe { std::slice::from_raw_parts_mut(ptr, n) })
    }

    /// Reset the arena — O(1), no destructors called.
    fn reset(&self) {
        self.offset.set(0);
    }

    fn used(&self) -> usize {
        self.offset.get()
    }
    fn remaining(&self) -> usize {
        CAP - self.used()
    }
}

// ── Tier 3: Heap fallback ─────────────────────────────────────────────────────

enum Allocation<'a> {
    Stack(u8),           // Tier 1: trivial value
    Arena(&'a mut [u8]), // Tier 2: pool
    Heap(Box<[u8]>),     // Tier 3: heap
}

impl<'a> Allocation<'a> {
    fn as_slice(&self) -> &[u8] {
        match self {
            Allocation::Stack(v) => std::slice::from_ref(v),
            Allocation::Arena(s) => s,
            Allocation::Heap(b) => b,
        }
    }
}

fn tier_alloc<'a, const CAP: usize>(arena: &'a BumpArena<CAP>, size: usize) -> Allocation<'a> {
    if size == 1 {
        return Allocation::Stack(0);
    }
    if let Some(slice) = arena.alloc(size) {
        return Allocation::Arena(slice);
    }
    Allocation::Heap(vec![0u8; size].into_boxed_slice())
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn arena_alloc_and_use() {
        let arena: BumpArena<128> = BumpArena::new();
        let slice = arena.alloc(10).unwrap();
        slice[0] = 7;
        assert_eq!(slice[0], 7);
        assert_eq!(arena.used(), 10);
    }

    #[test]
    fn arena_full_returns_none() {
        let arena: BumpArena<8> = BumpArena::new();
        assert!(arena.alloc(8).is_some());
        assert!(arena.alloc(1).is_none());
    }

    #[test]
    fn arena_reset_reclaims_space() {
        let arena: BumpArena<16> = BumpArena::new();
        arena.alloc(16).unwrap();
        assert_eq!(arena.remaining(), 0);
        arena.reset();
        assert_eq!(arena.remaining(), 16);
        assert!(arena.alloc(16).is_some());
    }

    #[test]
    fn tier_alloc_heap_fallback() {
        let arena: BumpArena<4> = BumpArena::new();
        let alloc = tier_alloc(&arena, 100);
        assert_eq!(alloc.as_slice().len(), 100);
    }

    #[test]
    fn tier_alloc_uses_arena_when_space() {
        let arena: BumpArena<512> = BumpArena::new();
        let _a1 = tier_alloc(&arena, 10);
        assert_eq!(arena.used(), 10);
    }
}

(* 731: Tiered Memory — OCaml arena simulation
   OCaml's GC is already generational (young/old heap), but we can
   simulate arena semantics with a Bigarray slab. *)

let () =
  (* Tier 1: Stack-equivalent — OCaml native int/float are unboxed *)
  let x : int = 42 in
  let y : float = 3.14 in
  Printf.printf "Stack-like: %d %.2f\n" x y;

  (* Tier 2: Pool/arena — reuse a Bytes buffer *)
  let arena = Bytes.make 1024 '\x00' in
  let arena_ptr = ref 0 in

  let arena_alloc size =
    let start = !arena_ptr in
    if start + size > Bytes.length arena then failwith "Arena full";
    arena_ptr := start + size;
    (arena, start, size)
  in

  let arena_reset () = arena_ptr := 0 in

  let (buf, off, _sz) = arena_alloc 16 in
  Bytes.blit_string "hello arena" 0 buf off 11;
  Printf.printf "Arena allocation: '%s'\n"
    (Bytes.sub_string buf off 11);

  arena_reset ();
  Printf.printf "Arena reset, ptr=%d\n" !arena_ptr;

  (* Tier 3: Heap — normal OCaml allocation *)
  let heap_data = Array.make 10000 0 in
  heap_data.(0) <- 99;
  Printf.printf "Heap: heap_data[0]=%d len=%d\n"
    heap_data.(0) (Array.length heap_data)

Key Differences

Control: Rust gives complete control over which tier is used; OCaml's GC decides placement automatically.

Lifetime safety: Rust's borrow checker ensures arena-allocated slices cannot outlive the arena; OCaml relies on the GC to prevent dangling references.

Reset cost: Rust's bump arena resets in O(1) with no GC involvement; an OCaml equivalent would just let the GC collect freed values on the next cycle.

Embedded use: Rust's no_std bump arenas are used in embedded firmware; OCaml's GC requires a runtime that is too large for most microcontrollers.

OCaml Approach

OCaml provides no manual memory tiers; all allocation goes through the GC. However, Bigarray provides C-backed flat buffers outside the GC heap for FFI and BLAS workloads. The Owl scientific library uses Bigarray for matrix data to avoid GC pressure. For arena-style patterns, OCaml programmers sometimes use the slab or region libraries from the opam ecosystem.

Full Source

#![allow(clippy::all)]
/// 731: Tiered Memory — Stack → Arena Pool → Heap
use std::cell::Cell;

// ── Tier 2: Bump Arena ────────────────────────────────────────────────────────

/// A simple bump allocator backed by a fixed-size stack slab.
/// All allocations are `u8` slices with `'arena` lifetime.
struct BumpArena<const CAP: usize> {
    slab: [u8; CAP],
    offset: Cell<usize>,
}

impl<const CAP: usize> BumpArena<CAP> {
    const fn new() -> Self {
        BumpArena {
            slab: [0u8; CAP],
            offset: Cell::new(0),
        }
    }

    /// Allocate `n` bytes from the arena. Returns `None` if full.
    fn alloc(&self, n: usize) -> Option<&mut [u8]> {
        let start = self.offset.get();
        let end = start.checked_add(n)?;
        if end > CAP {
            return None;
        }
        self.offset.set(end);
        // SAFETY: we've verified bounds; slab lives as long as &self
        let ptr = unsafe { (self.slab.as_ptr() as *mut u8).add(start) };
        Some(unsafe { std::slice::from_raw_parts_mut(ptr, n) })
    }

    /// Reset the arena — O(1), no destructors called.
    fn reset(&self) {
        self.offset.set(0);
    }

    fn used(&self) -> usize {
        self.offset.get()
    }
    fn remaining(&self) -> usize {
        CAP - self.used()
    }
}

// ── Tier 3: Heap fallback ─────────────────────────────────────────────────────

enum Allocation<'a> {
    Stack(u8),           // Tier 1: trivial value
    Arena(&'a mut [u8]), // Tier 2: pool
    Heap(Box<[u8]>),     // Tier 3: heap
}

impl<'a> Allocation<'a> {
    fn as_slice(&self) -> &[u8] {
        match self {
            Allocation::Stack(v) => std::slice::from_ref(v),
            Allocation::Arena(s) => s,
            Allocation::Heap(b) => b,
        }
    }
}

fn tier_alloc<'a, const CAP: usize>(arena: &'a BumpArena<CAP>, size: usize) -> Allocation<'a> {
    if size == 1 {
        return Allocation::Stack(0);
    }
    if let Some(slice) = arena.alloc(size) {
        return Allocation::Arena(slice);
    }
    Allocation::Heap(vec![0u8; size].into_boxed_slice())
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn arena_alloc_and_use() {
        let arena: BumpArena<128> = BumpArena::new();
        let slice = arena.alloc(10).unwrap();
        slice[0] = 7;
        assert_eq!(slice[0], 7);
        assert_eq!(arena.used(), 10);
    }

    #[test]
    fn arena_full_returns_none() {
        let arena: BumpArena<8> = BumpArena::new();
        assert!(arena.alloc(8).is_some());
        assert!(arena.alloc(1).is_none());
    }

    #[test]
    fn arena_reset_reclaims_space() {
        let arena: BumpArena<16> = BumpArena::new();
        arena.alloc(16).unwrap();
        assert_eq!(arena.remaining(), 0);
        arena.reset();
        assert_eq!(arena.remaining(), 16);
        assert!(arena.alloc(16).is_some());
    }

    #[test]
    fn tier_alloc_heap_fallback() {
        let arena: BumpArena<4> = BumpArena::new();
        let alloc = tier_alloc(&arena, 100);
        assert_eq!(alloc.as_slice().len(), 100);
    }

    #[test]
    fn tier_alloc_uses_arena_when_space() {
        let arena: BumpArena<512> = BumpArena::new();
        let _a1 = tier_alloc(&arena, 10);
        assert_eq!(arena.used(), 10);
    }
}

(* 731: Tiered Memory — OCaml arena simulation
   OCaml's GC is already generational (young/old heap), but we can
   simulate arena semantics with a Bigarray slab. *)

let () =
  (* Tier 1: Stack-equivalent — OCaml native int/float are unboxed *)
  let x : int = 42 in
  let y : float = 3.14 in
  Printf.printf "Stack-like: %d %.2f\n" x y;

  (* Tier 2: Pool/arena — reuse a Bytes buffer *)
  let arena = Bytes.make 1024 '\x00' in
  let arena_ptr = ref 0 in

  let arena_alloc size =
    let start = !arena_ptr in
    if start + size > Bytes.length arena then failwith "Arena full";
    arena_ptr := start + size;
    (arena, start, size)
  in

  let arena_reset () = arena_ptr := 0 in

  let (buf, off, _sz) = arena_alloc 16 in
  Bytes.blit_string "hello arena" 0 buf off 11;
  Printf.printf "Arena allocation: '%s'\n"
    (Bytes.sub_string buf off 11);

  arena_reset ();
  Printf.printf "Arena reset, ptr=%d\n" !arena_ptr;

  (* Tier 3: Heap — normal OCaml allocation *)
  let heap_data = Array.make 10000 0 in
  heap_data.(0) <- 99;
  Printf.printf "Heap: heap_data[0]=%d len=%d\n"
    heap_data.(0) (Array.length heap_data)

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn arena_alloc_and_use() {
        let arena: BumpArena<128> = BumpArena::new();
        let slice = arena.alloc(10).unwrap();
        slice[0] = 7;
        assert_eq!(slice[0], 7);
        assert_eq!(arena.used(), 10);
    }

    #[test]
    fn arena_full_returns_none() {
        let arena: BumpArena<8> = BumpArena::new();
        assert!(arena.alloc(8).is_some());
        assert!(arena.alloc(1).is_none());
    }

    #[test]
    fn arena_reset_reclaims_space() {
        let arena: BumpArena<16> = BumpArena::new();
        arena.alloc(16).unwrap();
        assert_eq!(arena.remaining(), 0);
        arena.reset();
        assert_eq!(arena.remaining(), 16);
        assert!(arena.alloc(16).is_some());
    }

    #[test]
    fn tier_alloc_heap_fallback() {
        let arena: BumpArena<4> = BumpArena::new();
        let alloc = tier_alloc(&arena, 100);
        assert_eq!(alloc.as_slice().len(), 100);
    }

    #[test]
    fn tier_alloc_uses_arena_when_space() {
        let arena: BumpArena<512> = BumpArena::new();
        let _a1 = tier_alloc(&arena, 10);
        assert_eq!(arena.used(), 10);
    }
}

Exercises

Add a BumpArena::alloc_aligned method that pads the offset to the requested alignment before returning a slice.

Implement a reset_to_checkpoint feature: save the offset before a batch operation and restore it on error, freeing all intermediate allocations at once.

Write a benchmark comparing BumpArena allocation throughput against Vec::new() for 10 000 small slices. Measure total allocation time and cache miss rate.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust