Rust Performance Engineering

Stack vs. Heap Allocation

Memory for local variables and data structures in a running Rust program comes from two primary regions: the thread stack (an ultra-fast LIFO region managed directly by the CPU's stack pointer register rsp/sp) and the heap (a dynamic memory pool shared across the process and managed by the global memory allocator).

Thread Stack (LIFO, ~0-1 CPU cycle):           Process Heap (Dynamic, ~15-100+ CPU cycles):
+-----------------------------------+          +------------------------------------------+
| Frame `main()`:                   |          | Global Allocator (`System`/`mimalloc`):  |
|   `arr: [u64; 4]` (32B inline)    |          |   - Searches free lists / size classes   |
|   `vec: Vec<u64>` (24B header) ---+--------->|   - Allocates `[u64; cap]` block         |
+-----------------------------------+          |   - Requires pointer indirection to read |
| Stack Pointer (`sp`) moves down/up|          +------------------------------------------+

Comparing Stack and Heap Allocation

Characteristic Stack Allocation Heap Allocation (Box, Vec, String, Arc)
Allocation Cost Free (~0–1 cycle: single adjustment of stack pointer at function entry) 15–100+ cycles (allocator size-class lookup, thread cache or lock, potential mmap/brk syscall)
Deallocation Cost Free (stack pointer restored when function returns) 15–100+ cycles (returning block to free list and coalescing)
Cache Locality Always hot in L1 data cache (L1d) May point to cold, non-contiguous memory pages (L2/L3/RAM miss)
Size Requirement Must be Sized (exact byte size known at compile time) Supports dynamically sized collections that grow/shrink at runtime
Capacity Limit Bounded (~2 MiB per thread on Linux/macOS, ~8 MiB on main thread) Bounded only by available system RAM / address space

Avoiding Unnecessary Heap Allocations on Hot Paths

  1. Use fixed-size arrays [T; N] instead of Vec<T> when the maximum element count is small and known at compile time.
  2. Use std::fmt::Write into a reusable buffer or stream (write!) instead of allocating a temporary String with format! on every iteration.
  3. Avoid boxing small closures (Box<dyn Fn()>) when generic impl Fn() or function pointers fn() work on the stack.
/// Computes a 4-bucket histogram on the stack without allocating a `Vec<u32>` on the heap.
pub fn compute_quartile_buckets(samples: &[u8]) -> [u32; 4] {
    let mut buckets = [0u32; 4]; // Allocated directly in registers / stack frame!
    for &s in samples {
        let idx = (s >> 6) as usize; // Top 2 bits map 0..=255 into buckets 0..=3
        buckets[idx] += 1;
    }
    buckets
}

/// Small-Buffer Optimization (SBO) pattern: stores up to `N` items inline on the stack,
/// spilling to a heap `Vec<T>` ONLY when the dynamic count exceeds `N`!
pub enum SmallBuffer<T, const N: usize> {
    Inline { len: usize, data: [Option<T>; N] },
    Heap(Vec<T>),
}

impl<T: Copy, const N: usize> SmallBuffer<T, N> {
    pub const fn new() -> Self {
        Self::Inline {
            len: 0,
            data: [None; N],
        }
    }

    pub fn push(&mut self, value: T) {
        match self {
            Self::Inline { len, data } if *len < N => {
                data[*len] = Some(value);
                *len += 1;
            }
            Self::Inline { len, data } => {
                let mut vec = Vec::with_capacity(N * 2);
                for item in data.iter().take(*len).flatten() {
                    vec.push(*item);
                }
                vec.push(value);
                *self = Self::Heap(vec);
            }
            Self::Heap(vec) => vec.push(value),
        }
    }

    pub fn is_on_stack(&self) -> bool {
        matches!(self, Self::Inline { .. })
    }
}

fn main() {
    let data = [10u8, 50, 70, 130, 200, 250];
    println!("Quartile buckets (stack array): {:?}", compute_quartile_buckets(&data));

    let mut sbo = SmallBuffer::<u32, 4>::new();
    for x in [1, 2, 3, 4] {
        sbo.push(x);
    }
    println!("4 items -> on stack: {}", sbo.is_on_stack());

    sbo.push(5); // 5th item spills to heap automatically!
    println!("5 items -> on stack: {}", sbo.is_on_stack());
}

Quartile buckets (stack array): [2, 1, 1, 2]
4 items -> on stack: true
5 items -> on stack: false

Guarding Against Stack Overflow with Large Arrays

While small arrays ([u8; 256] or [u64; 64]) belong on the stack, placing a massive multi-megabyte array (let buf = [0u8; 4 * 1024 * 1024];) on the stack can overflow a worker thread's 2 MiB stack limit. For buffers larger than ~16–64 KiB, allocate on the heap via vec![0u8; size] (which allocates directly on the heap without first constructing the array on the stack!).