Memory Allocators
from Scratch

01Why every engine writes its own allocator

A generic malloc has a hard job. It must serve any size, from a 12-byte node to a 16-megabyte texture, with no idea how long the caller will hold it, from any thread, and with no help from the caller about which of those it's about to do next. The price of that generality is a free-list search, a heap-lock acquisition, sometimes a syscall, and an answer whose worst case can be hundreds of times slower than its median. An engine knows more than that. It knows the per-frame scratch lifetime is one frame. It knows particles are 96 bytes each. It knows the texture heap wants 64 KB alignment. The job of an engine allocator is to turn that domain knowledge into faster code with simpler invariants, without ever surprising the frame budget.

The widget below draws allocation latencies from models of two allocators. The first models a general-purpose malloc on a fragmented heap. The second models a linear bump allocator. Both medians sit in the tens of nanoseconds. The difference is the tail: the modeled malloc has a heavy right tail where the rarest calls hit a page fault, a free-list scan, or a heap-lock wait, and its worst sample lands several orders of magnitude above its median. The bump allocator has effectively no tail because every call runs the same handful of instructions:

Four questions every allocator answers

The rest of the tutorial walks one allocator per section, and each one is built to answer four questions in a different way. You can mostly predict an allocator's behavior from the answers:

• What sizes does it serve? One fixed size (pool, slab), a small set of size classes (TLSF, slab caches), powers of two (buddy), or anything (linear, free-list).
• What lifetime does it serve? A single frame (linear, stack), a single scope (stack with a marker), object-by-object (pool, slab, buddy, TLSF), or anywhere from a frame to the whole session (general-purpose).
• What's the worst-case time for one allocation? Constant (linear, stack, pool, slab fast path, TLSF), logarithmic in the heap size (buddy), or proportional to the length of the free list (first-fit, best-fit).
• What kind of waste does it produce? Alignment padding only (linear, stack), internal fragmentation only (pool, slab), internal plus external fragmentation (buddy), or mostly external (general-purpose free lists).

02A short history of getting allocation right

The C library's malloc didn't arrive fully formed, and neither did the specialized allocators engines use. Most of them trace back to a short list of papers and talks:

03Under the call to malloc

Before any of the specialized allocators make sense, the picture under a generic malloc needs to be on paper. The call consults a data structure the C library has maintained since the program started, and the cost of one call is the cost of finding a fit in that structure, plus a system call when the structure runs dry.

A generic heap is a region of address space, broken into blocks. Each block has a header (size, free/used flag, sometimes a back-pointer for coalescing) and a payload that the caller sees. Free blocks are threaded onto one or more free lists, sorted by size or by address depending on the policy. A call to malloc(n) finds a free block whose payload is at least n bytes, splits off the remainder, and returns the payload pointer. A call to free(p) looks at the header in front of p, marks it free, and tries to coalesce with the previous and next blocks via boundary tags^[10].

Three slow-path costs make up the tail of a malloc latency distribution:

• The free-list scan. First-fit walks the list until something fits; best-fit walks all of it; segregated fits index by size class. On a heap with thousands of free blocks, a sequential scan is bounded by the length of the list, not by the size of the request.
• The heap lock. Modern allocators (jemalloc, tcmalloc, mimalloc) keep a thread- or CPU-local cache so most calls never touch a shared lock; the kernel-allocator lineage from Bonwick & Adams 2001^[8] uses per-CPU magazines for the same purpose. The shared tier underneath usually still takes a lock, and a spike happens when several threads need it at once.
• The system call. When the heap runs out, the allocator asks the kernel for more address space with mmap or sbrk. The kernel backs and zeroes each page on first touch (a page fault per 4 KB page). One fault costs on the order of a microsecond rather than nanoseconds, so a thousand of them in one frame cost about a millisecond.

Every allocator in this tutorial removes one or more of those costs by giving up some of the generality. A linear allocator removes the free-list scan by removing the free list. A pool removes the size search by fixing the size. A slab removes the constructor cost by handing back objects that are still constructed. Each is a worse general-purpose allocator and a better one for its workload.

04The linear (bump) allocator

The simplest allocator that's still useful. One pointer. Every allocation moves the pointer forward by the requested size. There is no per-object free. The entire region resets in one instruction at the end of the frame, the level, or whatever lifetime the caller picked. Unreal calls its version FMemStack^[5]; Naughty Dog's engine runs per-thread linear allocators on 2 MiB blocks from its tagged heap^[24]; Apache calls a sibling design apr_pool. Hanson 1990 is the usual academic reference^[13]; Ryan Fleury's "Untangling Lifetimes" essay is a thorough modern walkthrough^[26].

The widget is the picture you keep in your head. Click alloc 32 to grab 32 bytes; the head pointer moves. Free is the reset button: one assignment, all 256 bytes released at once. Try to allocate past the end and you get the only failure mode this allocator has, out-of-memory:

The code, in about 30 lines

// One pointer of state. No headers, no free lists, no locks.
struct LinearAllocator {
  char* base;         // start of the region
  char* head;         // next free byte
  char* end;          // one past the end

  void init(void* memory, size_t bytes) {
    base = head = (char*)memory;
    end  = base + bytes;
  }

  // Allocate `size` bytes aligned to `alignment` (default 16, SIMD-friendly).
  void* allocate(size_t size, size_t alignment = 16) {
    // Round head up to alignment (alignment is required to be a power of two).
    uintptr_t raw     = reinterpret_cast<uintptr_t>(head);
    uintptr_t aligned = (raw + alignment - 1) & ~(uintptr_t(alignment) - 1);
    size_t padding   = aligned - raw;            // bytes skipped to reach alignment
    size_t available = end - head;
    // Compare sizes, not pointers: a pointer computed past `end` is undefined behavior,
    // and checking padding first keeps the subtraction from wrapping.
    if (padding > available || size > available - padding) return nullptr;  // out of memory
    char* result = head + padding;
    head = result + size;
    return result;
  }

  // No per-object free. The whole region resets in one assignment.
  void reset() { head = base; }

  size_t used()     const { return head - base; }
  size_t capacity() const { return end - base; }
};

Every line of the allocator's hot path is on screen. allocate is a load, a round-up, a bounds check, a store. reset is a single store. The only branch is the out-of-memory check, and the alignment math is a power-of-two mask, so a call costs a few nanoseconds.

05The stack allocator (linear with markers)

A linear allocator with one extra rule: you can save the head pointer ("push a marker") and rewind to it later ("pop to a marker"). Allocations are still pointer bumps; freeing happens in LIFO order at the granularity of a marker, not an individual object. This is what the C call stack is, generalized: a function pushes its locals on entry and pops them on exit, and the caller does the same one level up. Engines use the same shape for nested scopes that have their own scratch: load a level, push a marker, allocate everything the loader needs, pop the marker, and every byte the loader touched is free in one instruction.

Try the widget. Allocate a few blocks, hit save marker, allocate a few more, then pop to marker. Everything after the marker is gone in one step; everything before it stays:

The marker pattern in code

struct StackAllocator {
  char* base;
  char* head;
  char* end;

  using Marker = char*;          // just the head value at the time of save

  Marker mark() const { return head; }
  void   pop(Marker m)    { head = m; }   // rewind to the saved head

  // Same bump as LinearAllocator::allocate.
  void* allocate(size_t size, size_t alignment = 16) {
    uintptr_t raw     = reinterpret_cast<uintptr_t>(head);
    uintptr_t aligned = (raw + alignment - 1) & ~(uintptr_t(alignment) - 1);
    size_t padding   = aligned - raw;
    size_t available = end - head;
    if (padding > available || size > available - padding) return nullptr;
    char* result = head + padding;
    head = result + size;
    return result;
  }
};

// RAII helper so a scope's allocations free automatically.
class StackScope {
  StackAllocator& allocator;
  StackAllocator::Marker savedHead;
public:
  explicit StackScope(StackAllocator& a)
    : allocator(a), savedHead(a.mark()) {}
  ~StackScope() { allocator.pop(savedHead); }   // pop on scope exit
};

// Use:
void loadLevel(StackAllocator& frame) {
  StackScope scope(frame);                                 // save marker
  // Construct in place. pop() runs no destructors, so keep scoped types trivially
  // destructible (scope stacks add a finalizer list for the ones that aren't).
  auto* manifest = new (frame.allocate(sizeof(Manifest), alignof(Manifest))) Manifest{};
  parseManifest(manifest);
  loadAssets(frame, manifest);
}                                                          // every allocation in here is freed here

The StackScope destructor is the entire lifetime story. Anything the function allocates from frame is released when the function returns. Anything allocated by a caller's scope before loadLevel is untouched, because the caller's marker is lower in the stack. Unreal's FMemMark is the same RAII marker over FMemStack^[5], and Fredriksson's "Scope Stack Allocation" talk from DICE extends the pattern with a finalizer chain so objects with destructors can live in a scope too^[28].

06The pool allocator (fixed-size free list)

One size of slot, many slots, a free list threaded through the empty ones. Allocate pops the head of the free list. Free pushes the slot back onto the head. Both operations are O(1) and the slots are interchangeable, which gives the allocator a property linear allocators don't have: per-object free in any order, with no external fragmentation, because every hole is exactly the same shape as every fit. Wilson's survey calls this "simple segregated storage"^[1]; Alexandrescu's Loki SmallObjectAllocator is the C++ template version^[15]; Boost.Pool is a widely used open-source one^[29].

The widget shows why a pool can't fragment. Allocate a few slots, then free one at random. The hole is a single slot, the same size as every other slot, and it becomes the new free-list head, so the next alloc reuses it without searching. There is no "I have 96 bytes free but no contiguous block big enough" failure mode here, because every block is already the right size:

The free list lives in the empty slots

template <typename T, size_t kSlotCount>
class PoolAllocator {
  static_assert(sizeof(T) >= sizeof(int),
                "slot must be big enough to hold a free-list index");
  static_assert(kSlotCount >= 1 && kSlotCount <= INT_MAX,
                "slot indices must fit in an int");

  // Storage: kSlotCount slots, each sized like T and aligned for T. unsigned char,
  // because only unsigned char and std::byte arrays formally provide storage for objects.
  alignas(T) unsigned char storage[kSlotCount * sizeof(T)];

  // Free-list head: index of the next free slot, or -1 if pool is full.
  int freeHead = 0;

  unsigned char* slotPtr(int slot) { return storage + size_t(slot) * sizeof(T); }

  // The link lives in a free slot's first bytes. memcpy, because no int object exists
  // there and T may be less aligned than int; compilers emit a single load or store.
  int  readLink(int slot)            { int next; std::memcpy(&next, slotPtr(slot), sizeof next); return next; }
  void writeLink(int slot, int next) { std::memcpy(slotPtr(slot), &next, sizeof next); }

public:
  PoolAllocator() {
    // Thread the free list through every slot: slot[i] -> slot[i+1], last -> -1.
    for (int i = 0; i < int(kSlotCount) - 1; ++i) writeLink(i, i + 1);
    writeLink(int(kSlotCount) - 1, -1);
  }

  // O(1): pop the free-list head. Returns raw storage; construct with placement new.
  T* allocate() {
    if (freeHead < 0) return nullptr;        // free list empty: pool exhausted
    int slot = freeHead;
    freeHead = readLink(slot);                 // the popped slot's link is the new head
    return reinterpret_cast<T*>(slotPtr(slot));
  }

  // O(1): push the slot back onto the free-list head. Destroy the object first.
  void deallocate(T* p) {
    int slot = int((reinterpret_cast<unsigned char*>(p) - storage) / sizeof(T));
    writeLink(slot, freeHead);                 // next = old head
    freeHead = slot;                           // new head
  }
};

The free list costs no extra memory: each empty slot's first few bytes hold the link, since nothing else lives there. A pool of 24 slots of 96-byte particles uses exactly 24 * 96 = 2304 bytes plus a single 4-byte head index. A general-purpose allocator typically adds 8 to 16 bytes of header per allocation, so for small objects the pool also packs more of them into each cache line.

07The buddy allocator

A pool serves one size. A buddy allocator serves many, with one rule that makes coalescing on free cheap: every block is a power-of-two size, and every block has a buddy at a fixed place (its offset from the start of the arena, XOR'd with its size). When a block frees, the allocator checks whether the buddy is also free, and if so the two coalesce into a block of the next power of two, recursively. Allocation is the inverse: find the smallest power-of-two block that fits the request, splitting larger free blocks if no suitable one exists. Linux's physical page allocator (__alloc_pages) is a binary buddy^[30]; AMD's Vulkan Memory Allocator offered a buddy algorithm for custom pools from v2.2 until v3.0 replaced it with TLSF^[18]; BitSquid documented a CPU buddy in 2015^[31].

The widget draws the arena as a binary tree: each row is one block size, and a block that has been split shows its two halves in the row below. Pick a request size and allocate; the allocator splits the smallest free block that fits until it reaches the right size. Free random frees one allocated block, and if its buddy is also free the two coalesce back up the tree:

Why coalescing is one XOR

A buddy is determined by address. If a block is at offset a from the start of the arena with size s (a power of two, with a a multiple of s), the buddy of that block sits at offset a ⊕ s. So when block B frees, the allocator computes B's buddy address, looks up that address in the free table, and if it's free, merges. The merged block has size 2s and starts at the lower of the two buddy offsets, a & ~s; its own buddy at the next level sits at that offset ⊕ 2s. Coalescing terminates in O(log heap_size) steps in the worst case (no extra work after one merge fails).

// Sketch: the Block header, the per-class freeList array, split() and blockAt()
// are left abstract; the offset arithmetic is the part that matters.

// A block at offset `offset` with size `size` (a power of two, offset a multiple of
// size) has its buddy at offset ^ size. Free both and they merge.
size_t buddyOf(size_t offset, size_t size) {
  return offset ^ size;
}

// Round a request up to the smallest power-of-two block that fits.
size_t roundUpPow2(size_t bytes) {
  return std::bit_ceil(bytes);                   // C++20 <bit>: 1 << ceil(log2(bytes))
}

// Free-list index of a power-of-two block: 0 for kMinBlockSize, 1 for twice that, ...
size_t classOf(size_t blockSize) {
  return std::countr_zero(blockSize) - std::countr_zero(kMinBlockSize);
}

// Allocate: take the smallest free block of `size` bytes (a power of two),
// splitting a larger free block on the way down if none exists.
Block* allocate(size_t size) {
  size_t wanted = classOf(size);
  for (size_t i = wanted; i < kMaxClasses; ++i) {
    if (!freeList[i].empty()) {
      Block* block = freeList[i].pop();
      while (i > wanted) {                        // split down to the requested size
        --i;
        Block* upperHalf = split(block);         // halves block->size, returns the upper buddy
        freeList[i].push(upperHalf);
      }
      block->isFree = false;
      return block;
    }
  }
  return nullptr;                                // no free block large enough
}

// Free: merge with the buddy while it is free and whole; repeat up the tree.
void deallocate(Block* block) {
  size_t blockSize = block->size;
  while (blockSize < kMaxBlockSize) {
    Block* buddy = blockAt(buddyOf(block->offset, blockSize));
    // A buddy that is allocated, or split into smaller blocks, can't merge.
    if (!buddy->isFree || buddy->size != blockSize) break;
    freeList[classOf(blockSize)].remove(buddy);
    if (buddy->offset < block->offset) block = buddy;   // merged block starts at the lower half
    blockSize *= 2;
  }
  block->size   = blockSize;                     // the surviving header records the merged size
  block->isFree = true;
  freeList[classOf(blockSize)].push(block);
}

08TLSF: a general-purpose allocator with a bounded worst case

Linear, stack, pool, and buddy each give up some of the generality of malloc to win speed and a bounded worst case. TLSF (Two-Level Segregated Fit) goes the other direction: keep the generality of a free-list allocator (any size, any lifetime, no special workload assumption) but index the free lists with a two-level bitmap that hardware bit-scan instructions search without a loop. The result is an O(1) allocator with a bounded worst case: the 2008 paper measures at most 160 instructions for malloc and 176 for free on x86^[17]. Unity's dynamic heap allocator uses TLSF^[4], AMD's VMA defaults to it since v3.0^[18], and MorphOS 2.0 and later use it as the default system allocator^[32].

Every free block is bucketed by its size into a first-level class indexed by its power-of-two bucket, and a second-level class that linearly subdivides that bucket into 2^SLI sub-buckets (shipping implementations typically pick SLI = 4 or 5; the widget below uses SLI = 2 for visual density). Each (first, second) pair has its own free list. Two bitmaps record which lists are non-empty:

(fl, sl) is the request's class after rounding it up to the next sub-bucket boundary, so every block on the chosen list is big enough. The search first looks in the request's own row: SL_bitmap[fl], masked to sub-buckets at or above sl. If that row is empty from there up, FL_bitmap, masked to rows above fl, names the next power-of-two row with any free block, and that row's lowest non-empty list is taken. At most two ffs bit-scans and two masked ANDs, plus the size-to-class mapping: a few dozen instructions with no loop, however full the heap is.

The widget below draws each row of the grid as one first-level class, so the lit cells in a row are that row's SL bitmap, and the green column on the right is the FL bitmap. Pick a request size and allocate: the dashed box marks where the search starts, the yellow box marks the list it pops, and the line under the grid traces each step:

The size-class encoding

For a request size n, a smallest block size 2^FLI (16 bytes in the widget, so FLI = 4), and a chosen SLI (number of second-level bits), the class indices are:

Within a power-of-two bucket of size [2^f, 2^f+1), the second-level index sl is the position of n in that range, scaled to 2^SLI sub-buckets. With SLI = 4, each power-of-two range splits into 16 sub-buckets: the 1024..2048 range gets sub-buckets at 1024, 1088, 1152, ..., each 64 bytes wide. The search rounds a request up to the next sub-bucket boundary, adding less than 2^{f − SLI} bytes, which is under 1 / 2^SLI of the request: at most 6.25% with SLI = 4, 3.1% with SLI = 5. The original TLSF hands the rounded size to the caller, so that rounding is its internal fragmentation^[17]; Conte's implementation rounds only for the search and splits the block to the exact request^[33].

Matt Conte's mattconte/tlsf on GitHub is a widely used open-source implementation: BSD-licensed, about 1,300 lines of C, one word of header per allocated block (4 bytes on 32-bit targets, 8 on 64-bit), and about 3 KB of control structure^[33]. VMA carries its own C++ TLSF implementation; Unity's is closed-source.

09The slab allocator

Bonwick's 1994 paper starts from one observation: allocating a kernel object costs more than its bytes, because the object also has to be constructed. A kernel object typically carries locks, condition variables, and reference counts that must be initialized before first use. Free the object and allocate another, and a plain allocator makes you pay for that initialization again. The slab idea is to keep freed objects in their constructed state so the next allocate hands one back ready to use, with the initialization amortized across reuses^[6]. The 2001 follow-up added per-CPU magazines so the fast path touches only CPU-local state behind an uncontended per-CPU lock^[8]. Linux's SLUB, a descendant design, has been the kernel's only slab allocator since SLAB was removed in 6.8^[25].

A slab is a contiguous region of memory carved into objects of one type. A slab cache is a set of slabs, sorted into full slabs (no free objects), partial slabs (some free, some used), and empty slabs (all free, ready to be returned to the page allocator). Bonwick's paper keeps them in one list in that order, so allocation always drains partial slabs before breaking into an empty one. Allocation pops a free object from a partial slab. Free pushes it back; if that leaves the slab with every object free, the slab moves to the empty end of the list and can be reclaimed.

The widget below shows three slabs of a single object type. Each slab is a row of slots, labelled empty / partial / full. The next allocation comes from a partial slab. The magazine column on the right is one CPU's stack of recently freed objects. Only that CPU touches it, so a push or pop needs no shared lock (Solaris guards each CPU's magazines with a per-CPU lock that is almost never contended). An object parked in the magazine is still allocated as far as its slab knows, drawn with a purple outline. The slab layer only gets involved when the magazine is empty on an allocation or full on a free:

Why slabs suit entity caches

An ECS spawns and despawns enemies, bullets, pickups, particles, audio sources. Each type has a fixed object size. The allocation pattern is bursty (a wave of 30 enemies, then 200 bullets) and locality matters (iterating enemies should be cache-friendly). A slab cache covers each of those:

• Fixed size per type, so the only waste is the unused tail of each slab (SunOS 5.4 kept it under 12.5%) plus, for caches with constructors, one extra word per object so the free-list link doesn't overwrite constructed state^[6].
• Contiguous storage, so iterating live objects in a slab is sequential, prefetchable, and free of pointer-chasing. This is an AoS layout at the object level: traversals that touch every field of every object hit the line economy the next section describes.
• Per-CPU magazines, so the hot path touches only CPU-local state, even when one thread frees what another allocated.
• Partial slabs first, so allocations fill partly used slabs and fully free ones can go back to the page allocator when the working set shrinks.

Frykholm's "Custom Memory Allocation in C++"^[27] and Reinalter's Molecule engine memory series^[34] both include fixed-size pool allocators of this shape, without Bonwick's object caching. An ECS archetype chunk has a similar structure: a fixed-size block holding entities of one component-set shape, where allocation takes the next free slot in a partly filled chunk. The magazine layer is the part archetype storage doesn't usually replicate, since ECS schedulers typically batch structural changes rather than allocating from many threads at once.

10Fragmentation: internal, external, and measured

Fragmentation is the gap between "bytes free" and "bytes usefully allocatable". There are two kinds, and allocator designs mostly trade one for the other. Internal fragmentation is space wasted inside a block: a 65-byte request in a 128-byte buddy slot wastes 63 bytes; a 12-byte object in a 96-byte pool slot wastes 84. External fragmentation is space wasted between blocks: a free-list allocator with thousands of 16-byte holes and a request for 4 KB has plenty of bytes free but no usable block. Pools have only internal fragmentation by construction; linear allocators have neither (until they fail entirely); buddy has bounded internal fragmentation plus external fragmentation whenever a live block keeps its buddy from merging; general-purpose malloc can develop arbitrary external fragmentation.

The widget below runs the same workload through four allocators in parallel, each on its own 4 KB heap, in two phases. Phase 1 churns: bimodal request sizes, random frees, live bytes held near 60% of the heap, and a slider-set share of allocations marked long-lived and sprinkled through the run. Phase 2 is a level unload: every short-lived block is freed and only the long-lived ones stay. The stat to watch is the largest contiguous free block once phase 2 finishes. With the long-lived mix at zero, every row coalesces back to one 4 KB run. Raise it and each survivor that landed mid-heap splits the free space around it. At the default setting, first fit usually keeps the largest hole, because it packs early allocations toward low addresses, with the TLSF-style segregated fit a little behind; at high mixes the two finish close together. Buddy usually ends smallest, because one survivor keeps its whole power-of-two neighborhood from merging. The pool row always reports one slot, since any free slot serves any request:

The worst case is theoretical; the typical case is measured

Robson 1971 proved that any non-relocating allocator has a worst-case overhead bound of Θ(M log n), where M is the maximum simultaneous live bytes and n is the ratio of largest to smallest allocation^[12]. The proof constructs an adversarial sequence of allocations and frees that no clever policy can survive without paying that bound. It's why moving garbage collectors can guarantee what a native heap can't.

Wilson, Johnstone, Neely, and Boles 1995 argued from the other direction: allocators should be judged on traces of real C and C++ programs, with the lifetime patterns those programs actually produce, rather than on synthetic random traces^[1]. Johnstone and Wilson's 1998 follow-up did the measuring^[14]: on eight real programs, best fit and address-ordered first fit averaged under 1% true fragmentation once header and alignment overhead were counted separately. Their explanation is phase behavior: objects allocated at about the same time tend to die at about the same time, and those two policies place such objects next to each other, so their holes merge back into large free blocks.

The two results don't conflict. The theory says any non-moving allocator can be fragmented by an adversarial request stream; the measurements say a good policy (best fit or address-ordered first fit) keeps real programs near zero, while poor ones (next fit, simple segregated storage without coalescing) waste far more. When a shipping engine does fragment, a common cause is a lifetime mix the policy can't see: a long-lived allocation (texture pool, level state, asset cache) lands among short-lived ones and blocks coalescing around it, which is the pattern in the widget above. The usual fix is structural, separating allocations by lifetime or size, more often than a better general-purpose allocator. Bonwick makes the same argument for slabs^[6], and MacDougall's GDC 2016 system splits the address space by allocation size for the same reason^[35].

11Array-of-Structures vs Structure-of-Arrays

Allocators decide where memory comes from. Layout decides how it's arranged, and on the same CPU running the same algorithm, layout often decides whether the core is fed or stalled on memory. The headline experiment is Tony Albrecht's "Pitfalls of Object-Oriented Programming" from 2009^[21]. On a PS3 scene-tree traversal of 11,111 nodes, he reports four data points: 19.6 ms for the original OO graph of node objects, 12.9 ms after custom allocators place the nodes, matrices, and bounding spheres contiguously ("35% faster just by moving things around in memory!", per the slide), 4.8 ms after restructuring the traversal to process that data in order with the hierarchy made implicit, and 3.3 ms after adding software prefetch on top. About 6× end-to-end, of which roughly 4× comes from layout and traversal order and the remainder from prefetching.

The difference is a cache question. With the 32-byte Entity below, a 64-byte cache line holds two whole entities in AoS, so a loop that reads only the 12-byte position uses 24 of every 64 bytes it pulls in. In SoA the same line holds 16 floats of just the field the loop reads, so every byte fetched is used.

struct Entity {
  vec3 position;   // 12 B
  vec3 velocity;   // 12 B
  float health;    // 4 B
  uint32_t flags;  // 4 B
}; // 32 B per entity

Entity entities[N];

// Loop touches positions only:
for (int i = 0; i < N; ++i)
  entities[i].position += wind * dt;
// Each cache line: 64 B / 32 B = 2 entities; the loop
// reads 2 x 12 B = 24 of the 64 B (37.5%).

struct Entities {
  vec3* positions;
  vec3* velocities;
  float* healths;
  uint32_t* flags;
  int count;
};

// Loop touches positions only:
for (int i = 0; i < entities.count; ++i)
  entities.positions[i] += wind * dt;
// Each cache line: 64 B / 12 B ≈ 5.3 positions, all
// of it read: ~2.7x the useful bytes per miss.

The widget below lays out the same entities both ways. Pick a workload (position only, position plus velocity, or every field): bright fields are the ones the loop reads, thin lines mark 64-byte cache lines, and the stats count the lines each layout loads and the fraction of their bytes the loop uses. AoS wins when the workload touches every field of every entity (because the entity is already on the line); SoA wins when the workload touches one or two fields, which is the common case in physics, rendering, and AI passes:

When AoS is right anyway

SoA isn't always the answer. If you iterate every field of every entity together (a serializer, a debug visualizer that draws all state, an entity that's used as a single unit), AoS is fine and the indirection of SoA's separate arrays costs you. Acton's CppCon 2014 talk puts the rule as solving for the most common case first^[38]: find the dominant access pattern, lay out the data for that pattern, and accept that the minor patterns will pay for it. Most engine systems have one dominant pass (physics integrates position and velocity, the renderer iterates transforms, the audio system iterates AudioSources); design for it, not for hypothetical generality.

12Generational handles: the right pointer for a slot you'll free and reuse

A raw pointer is what the compiler hands you: a 64-bit address into the address space, valid until something frees it. The "until something frees it" is the trouble. In a game where entities spawn and die every frame, holding a raw pointer to an entity is a contract you can't enforce: by the time you dereference it, the slot may belong to a different entity. The C++ answer is shared_ptr and weak_ptr, which charge an atomic refcount and a control block per object. The engine answer is the generational handle: 32 or 64 bits split into an index (which slot) and a generation (which generation of that slot). Freeing bumps the generation. A handle is valid if and only if handle.gen == slot.gen. A stale handle fails the check instead of reaching the wrong object; a live one costs a single cache-line load to validate. Frykholm's 2011 BitSquid post is the standard engine-side description^[23]; floooh's "Handles are the better pointers" makes the case for them in C APIs^[39]; Bevy's Entity^[2] and EnTT's entt::entity^[3] are widely used ECS implementations.

The widget shows the lifecycle. Spawn creates an entity, Store handle keeps a copy of the newest entity's handle, and Free latest frees the newest live entity and bumps its slot's generation. A handle stored before the free still points to the same slot index but has the old generation, and the lookup correctly rejects it as stale:

The 32-bit handle

struct Handle {
  uint32_t bits;                       // 24 bits index | 8 bits generation

  static Handle make(uint32_t index, uint8_t generation) {
    return { (index & 0xFFFFFF) | (uint32_t(generation) << 24) };
  }
  uint32_t index()      const { return bits & 0xFFFFFF; }
  uint8_t  generation() const { return uint8_t(bits >> 24); }
};

template <typename T>
class HandleTable {
  struct Slot {
    T       value;
    uint8_t generation;                // same width as the handle's field, so the two
    bool    alive;                     // wrap together (see the note on wrap below)
  };
  std::vector<Slot> slots;
  std::vector<uint32_t> freeIndices;  // indices ready for reuse

public:
  Handle spawn(const T& value) {
    uint32_t slotIndex;
    if (!freeIndices.empty()) {
      slotIndex = freeIndices.back(); freeIndices.pop_back();
    } else {
      assert(slots.size() < (1u << 24));  // the index field is 24 bits wide
      slotIndex = uint32_t(slots.size());
      slots.push_back({});
    }
    slots[slotIndex].value = value;
    slots[slotIndex].alive = true;
    return Handle::make(slotIndex, slots[slotIndex].generation);
  }

  void free(Handle handle) {
    if (!isValid(handle)) return;
    Slot& slot = slots[handle.index()];
    slot.alive = false;
    slot.generation++;                      // retires every prior handle to this slot
    freeIndices.push_back(handle.index());  // slot can now be reused
  }

  bool isValid(Handle handle) const {
    const uint32_t slotIndex = handle.index();
    return slotIndex < slots.size()
        && slots[slotIndex].alive
        && slots[slotIndex].generation == handle.generation();
  }

  T* get(Handle handle) {
    return isValid(handle) ? &slots[handle.index()].value : nullptr;
  }
};

24 bits of index supports 16,777,216 slots, far more than most games keep alive at once. 8 bits of generation supports 256 distinct generations per slot before it wraps. Wrap is the only failure mode: after 256 free-and-reuse cycles on the same slot, a handle from generation N matches generation N+256 and validates incorrectly. The mitigations are a wider generation field, or retiring a slot for good instead of reusing it once its generation is about to wrap. EnTT uses 12 bits of generation by default^[3]; Bevy uses 32 bits^[2].

13Cheat sheet

A page you can paste into your engine's contributing guide. For each allocator: what sizes, what lifetimes, what worst-case time, what waste, and where it ships.

14How shipping engines stack these up

Shipping engines run several allocators at once, each pinned to a subsystem and sometimes to a thread. The design question is which allocator serves which lifetime.

Unreal Engine 5

UE5 routes general allocation through one global FMalloc interface, with the backend chosen per platform and build configuration. The engine's allocator enum lists Ansi, Stomp, TBB, Jemalloc, Binned, Binned2, Binned3, Platform, Mimalloc, and Libpas^[41]. The binned backends are Epic's own: fixed-size bins for small allocations (which dominate engine workloads) plus a separate path for large blocks, with Binned3 built on reserved virtual address ranges for 64-bit targets. Stomp is a debugging backend that places each allocation against an inaccessible page so overruns and use-after-free fault immediately, and Ansi forwards to the C runtime. On top of FMalloc, the engine provides FMemStack^[5], a thread-local linear-with-markers allocator for per-frame and per-scope temporaries; FMemMark is the RAII wrapper that rewinds it when a scope ends, the marker pattern from the stack allocator section.

Unity

Unity's manual documents its native allocators: the dynamic heap allocator uses TLSF for large, long-lived allocations, and a lock-free bucket allocator takes small ones so they don't fragment the main heap^[4]. The DOTS and Native Collections layer adds lifetime-scoped allocators through the Allocator enum^[42]: Allocator.Temp (the fastest; one per frame on the main thread and one per job), Allocator.TempJob (can be passed to jobs, must be freed within four frames), and Allocator.Persistent (the slowest, for allocations with no fixed lifetime). ECS components live in archetype chunks, fixed-size blocks that each hold entities of one component-set shape, a slab-like layout.

Naughty Dog, Frostbite, id Tech

Gyrling's 2015 GDC slides^[24] describe the Naughty Dog engine's frame memory. An earlier design gave each use its own linear allocator, sized for its own worst case, and wasted 100 to 200 MiB because the worst cases never coincide. The replacement is a tagged heap of 2 MiB blocks (one large page on PS4, so one TLB entry), where every block belongs to a tag such as a frame's game-logic stage. Each allocator keeps one block per worker thread, so almost no allocation takes a lock, and freeing a tag returns all of its blocks at once. A job that sleeps and wakes on another thread just continues in that thread's block; the tag, not the thread, decides when the memory dies. Frostbite has Fredriksson's "Scope Stack Allocation" slides for the CPU-side scope allocator^[28] and the FrameGraph talk for aliasing transient GPU resources within a frame^[43]. id Software published its old source: the original Doom 3's idHeap in neo/idlib/Heap.cpp^[44] is a tiered small-block + medium-pool + large-block layout (the BFG Edition later replaced this with thin wrappers around the platform allocator).

The pattern across all of them

Strip the names and the same pieces recur: a per-frame or per-scope linear allocator for scratch, a general-purpose allocator (TLSF or binned) for object-lifetime allocations, a separate path for large blocks (a buddy, a page-aligned heap, or reserved virtual address ranges), pools, slabs, or archetype chunks for hot fixed-size types, and generational handles or weak references for any identity that outlives a frame. Most of the engineering goes into deciding which allocation belongs to which of these, and into tracking and budgeting memory per subsystem.

15Pitfalls

Production problems the tutorial code is too small to show.

• Alignment is not optional. SSE types want 16-byte alignment, AVX 32, and cache-line-sized data 64. GPU APIs add their own rules (D3D12 wants 256 bytes for constant-buffer data and 64 KB for most placed resources). An allocator that hands back under-aligned pointers will fault on aligned SIMD loads (MOVAPS, VMOVDQA), fault on some older ARM cores' scalar accesses, and pay for a split access whenever a load straddles two cache lines, even where the hardware tolerates misalignment. Always take the requested alignment as a parameter and round the head up before returning.
• Debug allocators are not free. Pattern-fill on alloc and free, guard pages, leak tracking, and stack-trace capture can multiply allocation cost many times over; a stack-trace capture alone costs on the order of microseconds per call, and a guard page costs at least one page of address space per allocation. Unreal keeps leak tracking in a separate wrapper around the real allocator, switched on with MALLOC_LEAKDETECTION, rather than in the allocator itself; keep it out of shipping builds.
• Thread-local stack allocators break when jobs migrate. A job that saves a marker in thread A's arena, yields, and resumes on thread B (fibers, work-stealing schedulers) will later pop thread B's arena to a marker that belongs to A, freeing B's live allocations and leaking A's. Either attach the arena to the job rather than the thread, or free by lifetime instead of by scope: Naughty Dog's tagged heap gives each worker thread its own block but frees every block with a given tag at once, so a job that moves mid-frame just keeps allocating on its new thread^[24]. The job-systems tutorial covers the work-stealing side.
• Use-after-free on a pool slot reads the free-list link. A freed slot's first bytes hold the index of the next free slot, so a stale read returns a plausible small integer instead of crashing, and a stale write corrupts the free list. Debug builds commonly fill the rest of a freed slot with a poison pattern (MSVC's debug heap uses 0xDD for freed memory) so a use-after-free shows up as an obviously wrong value; shipping builds skip the fill.
• Generational handles don't survive a save and load. After load, every entity gets whatever slot index and generation the fresh table hands out, so saved handles point at the wrong slots or fail validation. Serialize a stable ID (entity name, GUID) and translate it back to a handle at load time. Network replication has the same problem for the same reason.
• Cross-allocator frees corrupt the heap. A pointer from FMemStack passed to FMalloc::Free hands the general-purpose allocator a block it never issued, and the damage usually surfaces later, somewhere else. Every allocation must go back to the allocator that made it. One common defense is to keep pointers from special-purpose allocators out of APIs that might free them, so call sites hold the allocator or a scope object rather than an owning raw pointer.
• Buddy rounding can erase the gains of a slab above it. A 65-byte request to a buddy that rounds to 128 wastes 49% of the block. If request sizes don't cluster at powers of two, put pools or slabs of the actual object sizes on top of the buddy and give the buddy only large, power-of-two-friendly requests.

16What's next

Three directions from here.

Read the surveys. Wilson, Johnstone, Neely, Boles 1995^[1] is still the standard survey of the field, history included; Johnstone & Wilson 1998^[14] is the measurement follow-up. The Jones, Hosking, Moss Garbage Collection Handbook^[45] covers the other half of the picture: collectors that can move objects, and so can compact away the fragmentation a native heap has to live with.

Read the talks and papers. Gyrling 2015^[24] and MacDougall 2016^[35] are two GDC talks on shipped console memory systems; Acton's CppCon 2014 talk^[38] covers the data-layout side; Pedriana's EASTL paper^[19] covers what game code needs from a container library's allocator interface.

Read the source. Matt Conte's TLSF^[33] is a complete production allocator in about 1,300 lines of C; the VMA repository has its TLSF implementation alongside a linear algorithm for ring-buffer use^[18]; Bevy ECS^[2] and EnTT^[3] both implement generational entity IDs in the open. The original Doom 3 idHeap^[44] is a rare case of a shipped game's allocator published with the rest of its source.

17Sources

1. Wilson, P. R., Johnstone, M. S., Neely, M., Boles, D. (1995). "Dynamic Storage Allocation: A Survey and Critical Review." Proc. International Workshop on Memory Management (IWMM '95), LNCS 986. PDF. The canonical taxonomy of allocator strategies and the critique that synthetic random traces don't match real workloads.
2. Bevy ECS, Entity documentation. docs.rs/bevy_ecs/entity/struct.Entity. Shipping Rust ECS using index+generation entity IDs.
3. EnTT, Crash Course: entity-component system. skypjack.github.io/entt. C++ ECS whose default 32-bit identifier splits 20 bits of entity index and 12 bits of version; its component storage is sparse-set based, not archetype based.
4. Unity Manual, "Native memory allocators." docs.unity3d.com. States that the dynamic heap allocator "uses a Two Level Segregated Fit (TLSF) algorithm to manage its memory," and describes the lock-free bucket allocator for small allocations.
5. Unreal Engine, FMemStackBase API documentation. dev.epicgames.com. Reference for UE's stack allocator, used with FMemMark scopes that rewind it.
6. Bonwick, J. (1994). "The Slab Allocator: An Object-Caching Kernel Memory Allocator." USENIX Summer 1994. PDF. The origin of slab/object caching, the "construct cost amortized across reuse" thesis.
7. Russell, D. L. (1977). "Internal Fragmentation in a Class of Buddy Systems." SIAM Journal on Computing 6(4), pp. 607-621. SIAM. Estimates internal fragmentation for binary and Fibonacci buddy systems under Zipf-like size distributions and compares the estimates with simulations on three measured distributions (binary buddy: about 44% predicted, 30% observed, as summarized by Wilson et al. [1]).
8. Bonwick, J., Adams, J. (2001). "Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources." USENIX ATC. PDF. The per-CPU magazine layer and its depot, protected by per-CPU locks rather than by disabling interrupts; also vmem and the user-level libumem.
9. Knowlton, K. C. (1965). "A Fast Storage Allocator." Communications of the ACM 8(10), pp. 623-624. ACM DL. First public description of the binary buddy algorithm.
10. Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd ed., Addison-Wesley. Section 2.5 "Dynamic Storage Allocation," pp. 435-456. The canonical textbook treatment, source of the 50% rule and the boundary-tag idea.
11. Shore, J. E. (1977). "Anomalous Behavior of the Fifty-Percent Rule in Dynamic Memory Allocation." CACM 20(11), pp. 812-820. ACM DL. Shows that address-ordered first fit violates a statistical assumption behind Knuth's fifty-percent rule, and that whether best fit or first fit wins depends on the lifetime distribution.
12. Robson, J. M. (1971). "An Estimate of the Store Size Necessary for Dynamic Storage Allocation." Journal of the ACM 18(3), pp. 416-423. ACM DL. The worst-case bound: a non-relocating allocator can be forced to use a heap on the order of M log n.
13. Hanson, D. R. (1990). "Fast Allocation and Deallocation of Memory Based on Object Lifetimes." Software: Practice and Experience 20(1), pp. 5-12. Wiley. The standard academic reference for arena (region) allocation; Wilson et al. [1] trace the idea back to 1960s zone allocators.
14. Johnstone, M. S., Wilson, P. R. (1998). "The Memory Fragmentation Problem: Solved?" ISMM '98, ACM SIGPLAN Notices 34(3), pp. 26-36. PDF. Measured fragmentation on real C/C++ programs; near-zero for sensible policies once header overhead is factored out.
15. Alexandrescu, A. (2001). Modern C++ Design, Chapter 4 "Small-Object Allocation." Addison-Wesley. O'Reilly. The Loki SmallObjectAllocator: segregated pools by size, embedded free lists.
16. Masmano, M., Ripoll, I., Crespo, A., Real, J. (2004). "TLSF: A New Dynamic Memory Allocator for Real-Time Systems." Proc. ECRTS 2004, pp. 79-86. IEEE. The original TLSF paper: an O(1) bound via a two-level bitmap and hardware bit-scan.
17. Masmano, M., Ripoll, I., Real, J., Crespo, A., Wellings, A. J. (2008). "Implementation of a constant-time dynamic storage allocator." Software: Practice and Experience 38(10), pp. 995-1026. Wiley. Implementation details, the round-up split policy, and measurements: worst cases of 160 instructions per malloc and 176 per free on x86.
18. AMD Vulkan Memory Allocator. Documentation; changelog. v2.2.0 (2018) added a buddy algorithm for custom pools; v3.0.0 (2022) made TLSF the default algorithm and removed the buddy algorithm.
19. Pedriana, P. (2007). "EASTL: Electronic Arts Standard Template Library." WG21 N2271. open-std.org. Where the C++ standard library hurt game code in 2007 and how EA's library worked around it.
20. Halpern, P. (2014). "Polymorphic Memory Resources." WG21 N3916. open-std.org. The design rationale for C++17's std::pmr (adopted via P0220).
21. Albrecht, T. (2009). "Pitfalls of Object-Oriented Programming." Sony Computer Entertainment Europe R&D, GCAP 2009. PDF. The PS3 scene-tree case study: 11,111 nodes, 19.6 ms → 12.9 → 4.8 → 3.3 ms (~6× end-to-end) through contiguous allocation, in-order processing, and prefetch.
22. Llopis, N. (2009). "Data-Oriented Design." Games from Within. gamesfromwithin.com. An early essay that popularized the term.
23. Frykholm, N. (2011). "Managing Decoupling Part 4: The ID Lookup Table." BitSquid blog. bitsquid.blogspot.com. A 32-bit ID with a 16-bit index whose upper bits advance on every reuse of the slot, from the engine that became Autodesk Stingray.
24. Gyrling, C. (2015). "Parallelizing the Naughty Dog Engine Using Fibers." GDC 2015. Slides PDF. The fiber job system, plus the tagged heap: 2 MiB blocks owned by tags, per-thread linear allocators, and the 100 to 200 MiB the older worst-case-sized allocators wasted.
25. Babka, V. (2023). "remove the SLAB allocator." Kernel patch series, Nov 13, 2023, via LWN. lwn.net. SLAB was deprecated in 6.5; the series removes it, leaving SLUB as the only slab allocator (merged for Linux 6.8).
26. Fleury, R. (2022). "Untangling Lifetimes: The Arena Allocator." rfleury.com. A modern essay on structuring C programs around arena allocators.
27. Frykholm, N. (2010). "Custom Memory Allocation in C++." BitSquid blog. bitsquid.blogspot.com. The BitSquid allocator interface, with heap, pool, frame (bump), page, and tracking-proxy allocators behind it.
28. Fredriksson, A. "Scope Stack Allocation." DICE. PDF. Nested-scope linear allocation with a finalizer chain for objects that need destructors.
29. Boost.Pool documentation. boost.org. Boost's pool library and its description of simple segregated storage.
30. Gorman, M. Understanding the Linux Virtual Memory Manager, Ch. 6. kernel.org. The Linux page allocator (buddy at order 0-10) explained.
31. Frykholm, N. (2015). "Allocation Adventures 3: The Buddy Allocator." BitSquid blog. bitsquid.blogspot.com. A CPU buddy allocator in an engine context.
32. MorphOS, TLSF system allocator. morphos-team.net. MorphOS 2.0+ ships TLSF as the default allocator.
33. Conte, M. tlsf: Two-Level Segregated Fit memory allocator implementation. github.com/mattconte/tlsf. BSD-licensed C implementation, about 1,300 lines; one word of overhead per allocation and about 3 KB of control structure.
34. Reinalter, S. "Molecule engine: Memory system" series. blog.molecular-matters.com. Linear, stack, pool, arena allocators walked through in working C++.
35. MacDougall, A. (2016). "Building a Low-Fragmentation Memory System for 64-bit Games." SCE London Studio, GDC 2016. Slides PDF. A PS4-era memory system that splits the virtual address space into size-segregated modules (small, medium, large, giant) and maps physical pages on demand.
36. Dubé, J.-F. (2012). "Memory Management Part 4: Allocators Overhead, Waste and Fragmentation." jfdube.wordpress.com. Developer-testimony fragmentation report on a shipping Xbox 360 title (~10-30 MB of fragmentation from level-load temporaries).
37. Nikolov, S. (2018). "OOP is Dead, Long Live Data-Oriented Design." CppCon 2018. YouTube. Measured cache-miss and performance deltas on an HTML rendering engine refactor.
38. Acton, M. (2014). "Data-Oriented Design and C++." CppCon 2014. YouTube. The DOD framing for engine programmers: "the purpose of code is to transform data."
39. Weissflog, A. (2018). "Handles are the better pointers." floooh.github.io. The case for index-plus-generation handles over pointers in C APIs.
40. Deutsch, A. (2017). "slot_map Container in C++." WG21 P0661R0. open-std.org. The proposal to standardize std::slot_map; not adopted.
41. Unreal Engine, FGenericPlatformMemory::EMemoryAllocatorToUse API documentation. dev.epicgames.com. The list of FMalloc backends UE can select.
42. Unity Collections package manual, "Allocator overview." docs.unity3d.com. The DOTS / Native Collections allocator enum: Temp, TempJob, Persistent.
43. O'Donnell, Y. (2017). "FrameGraph: Extensible Rendering Architecture in Frostbite." GDC 2017. gdcvault.com. Transient GPU resource memory.
44. id Software, Doom 3 source, neo/idlib/Heap.cpp. github.com/id-Software/DOOM-3. Production AAA heap source: tiered idHeap::SmallAllocate / MediumAllocate / LargeAllocate.
45. Jones, R., Hosking, A., Moss, E. (2023). The Garbage Collection Handbook, 2nd ed., CRC Press. gchandbook.org. The book on relocating allocators (compacting GCs); the half of the field native engines can't use directly.