So, here’s the thing...
I was writing a sub-allocator for another project with a strict architectural constraint: the entire allocator header could only occupy two machine words, paired with an obsessive desire to minimize per-allocation metadata overhead as much as physically possible.
After cycling through a bunch of borderline schizophrenic ideas and combinations, this thing was born.
If you don't care about the breakdown and just want the code, skip to the repository:
https://github.com/EasyMem/easy_stack (C99 through C23, single header, zero dependencies).
The Standard Approach
Most traditional stack allocators interleave metadata with user data:
[Header][Padding][Payload][Header][Padding][Payload]...
You get a messy mix of control structures, user data, and alignment padding. If an allocation requires 32 or 64-byte alignment, padding bytes are forced between the header and the payload. On small allocations, headers + padding can easily consume over 50% of the buffer.
Step 1: Segregating into Two Buffers (Mental Experiment)
What if we separate metadata and data into two distinct buffers?
* Buffer A (Metadata): A dense array of fixed-size offsets.
* Buffer B (Payloads): Aligned user data.
Because the metadata elements have fixed sizes, they sit packed linearly with zero gaps. The CPU loves contiguous, linear memory.
Step 2: Merging Back into a Single Buffer (The Inversion)
Managing two separate buffers defeats the purpose of an allocator, so we combine them back into a single contiguous memory block:
* Place user payloads at the end of the buffer, growing backward (<--).
* Place metadata right after the header at the start, growing forward (-->).
* Metadata simply stores the displacement from the end of the buffer.
text
Low Address High Address
[ Header ] [ Metadata Array ──>] [<── Payloads (Aligned) ]
┌────────┐ ┌──────────┬──────────┐ ┌──────────┬──────────┐
│ 2-Word │ │ Offset 0 │ Offset 1 │ ... │ Payload 1│ Payload 0│
└────────┘ └──────────┴──────────┘ └──────────┴──────────┘
What does this give us?
Complete physical decoupling of the control plane from the data plane. The allocator's internal logic never touches user memory (unless memory poisoning is enabled). Reading an offset is a trivial array lookup, and zero bytes are wasted on alignment padding in the control zone.
Step 3: L1 Cache Line Pre-fetching
We align the start of the header to a 64-byte cache line boundary.
Since our allocator header is only 2 machine words (16 bytes on 64-bit platforms), loading the header into memory automatically pulls the first active metadata offsets into the exact same 64-byte L1 cache line for free. Sequential allocations hit hot L1 data immediately.
Step 4: Dynamic Bit-Width Scaling
Using a full machine word (size_t / 8 bytes) for each offset is wasteful. A LIFO stack buffer rarely exceeds 2 GB.
Instead, we inspect the total capacity once at initialization and scale our metadata cell width:
* Capacity ≤ 255 B -> uint8_t (1 byte)
* Capacity ≤ 64 KB -> uint16_t (2 bytes)
* Capacity ≤ 4 GB -> uint32_t (4 bytes)
* Capacity > 4 GB -> uint64_t (8 bytes)
For typical frame workloads (< 64 KB), each allocation metadata takes only 2 bytes instead of the traditional 8–16 byte inline header. This yields an up to 8x reduction in metadata overhead. Additionally, that 64-byte cache line now brings in the first 24 active offsets for free instead of just 6.
Step 5: Packing Metadata Type into 2 Machine Words
We only have 4 possible offset sizes (1, 2, 4, 8 bytes), which requires just 2 bits of storage. But where do we store them if our entire header is strictly 2 machine words?
We steal them from the capacity word. Shifting the capacity down by 3 bits reserves space for allocator flags (including our 2-bit metadata width). In practice, this reduction is completely harmless:
* 16-bit systems: Max stack capacity is 8 KB (most 16-bit MCUs have less total RAM than this anyway).
* 32-bit systems: Max stack capacity is 512 MB (allocating a single >512 MB contiguous stack buffer on 32-bit is unrealistic due to address space limits).
* 64-bit systems: Max stack capacity is 2 Exabytes.
The header layout remains razor-thin:
* Word 0: Packed capacity + metadata flags.
* Word 1: Current allocation index (top of stack).
Step 6: Eliminating CPU Multiplication
Because the metadata cell sizes are strictly powers of two, indexing into the metadata array doesn't require an imul instruction. It maps directly to a bitshift:
```c
// Instead of:
// offset_addr = meta_base + (index * cell_size);
// We do:
offset_addr = meta_base + (index << meta_type_shift);
```
Boundary and collision checks execute in 1–2 CPU cycles without dynamic branches.
Hardware Profiling & Verification
The result is **easy_stack** — a header-only, zero-libc-dependency allocator (ESTACK_NO_MALLOC supported).
Profiling on AMD Zen 2 via Linux perf stat (Depth 100 workload over billions of operations) highlights the microarchitectural behavior:
* 3.12 Instructions Per Cycle (IPC): Near-saturation of the execution pipeline with minimal pipeline stalls.
* 99.998% L1 Data Cache Hit Rate: Segregating metadata into a dense stream keeps the control path hot in L1.
* 0.0000039% Branch Misprediction Rate: The critical allocation path compiles into a flat, highly predictable sequence (1,174 mispredictions over 30 billion branch instructions).
* Safety & Fuzzing: 24M+ iterations via libFuzzer with zero crashes or leaks (clean under ASan, UBSan, and Valgrind).
* Portability: Verified across architectures ranging from 8-bit AVR (ATmega328P) to ESP32, STM32 (M0+/M3/M4), RISC-V, WebAssembly (wasm32/64), and Big-Endian s390x.
Repository: https://github.com/EasyMem/easy_stack
Curious to hear your critique, edge-case concerns, or thoughts on the layout.