When a program on Linux calls malloc, it is almost always talking to ptmalloc2, the allocator that has shipped inside glibc since 2004. It is a descendant of Doug Lea’s classic dlmalloc, extended by Wolfram Gloger with the one feature dlmalloc lacked: support for multiple threads. Understanding its design — and where that design shows its age — is the key to understanding what tcmalloc and mimalloc do differently.

Chunks and boundary tags

The unit of allocation is the chunk. Every chunk carries an inline header immediately before the pointer returned to the user: a size field with three flag bits, and — when the previous chunk is free — a copy of that neighbor’s size (the boundary tag). Free chunks additionally store forward and back pointers inside the freed user data itself, linking them into free lists. This is wonderfully memory-efficient, but it interleaves allocator metadata with user data: every allocation pays an 8–16 byte header tax, a stray buffer overflow corrupts heap metadata, and freeing a chunk requires touching the headers of its neighbors to attempt coalescing — often a cache miss.

Bins: segregated free lists

Freed chunks are recycled through a family of bins. Fastbins hold very small chunks in LIFO singly-linked lists; they are deliberately never coalesced on free, trading fragmentation for speed. The unsorted bin is a staging queue: recently freed chunks land there and get one chance to be reused verbatim before being sorted. Sixty-two small bins hold exact size classes, and large bins hold size ranges kept sorted for best-fit search. A chunk bordering the top of the heap is absorbed into the wilderness, and truly large requests bypass the heap entirely via mmap.

Arenas: threading, bolted on

Threading is handled by replicating the whole structure. The main arena grows the classic heap with sbrk; additional arenas are carved from mmap regions, capped at roughly eight per core. Every arena is guarded by a mutex: a thread tries its last-used arena, and if that lock is contended it hunts for a free one or spawns another. Since threads outnumber arenas, every allocation and free still takes a lock, and hot arenas become serialization points.

Google’s tcmalloc (“thread-caching malloc”) inverts the arena idea. Instead of replicating a heavyweight heap and making threads share it, it gives each thread — or in its modern per-CPU mode, each core — a tiny private cache of ready-to-hand objects, and organizes everything behind it as a three-tier pipeline: front end, middle end, back end.

Small allocations are rounded up to one of roughly a hundred size classes. The front-end cache keeps a singly-linked free list per size class, so the common path is: map size to class, pop the list head, return. No lock, no atomic, no header write — a handful of instructions. Frees push onto the same list. In per-CPU mode the caches live in a fixed slab indexed by core and are manipulated with restartable sequences (rseq): the kernel restarts the critical section if the thread is preempted, giving lock-free per-core caching regardless of how many threads exist.

When a front-end list runs dry or overflows, it exchanges objects with the middle end in batches — a transfer cache holding prefabricated batches, backed by a central free list per size class. One lock acquisition amortizes across dozens of objects. The back end is the page heap: it carves memory into spans (runs of pages), assigns each span to a single size class, and records span ownership in a radix-tree pagemap. That last detail quietly removes ptmalloc2’s header tax: the size of any small object is derived from which span its address falls in, so objects carry no per-object metadata at all, packing tighter in cache.

Mapping sizes to classes

The size-to-class step must itself be branch-cheap, so it is a table lookup, not arithmetic. Requests up to 1 KiB index a dense array keyed on (size + 7) >> 3; larger small requests use a coarser 128-byte-granularity table. The classes themselves are chosen offline to bound internal fragmentation (waste within a rounded-up object) to roughly 12–25% while keeping each class packable into whole pages with little slack — a static optimization problem solved once, baked into the binary.

Restartable sequences, precisely

The per-CPU mode deserves a closer look, because it achieves mutual exclusion with no atomic instructions on the fast path. Each CPU owns a region of a fixed slab holding, per size class, a small array used as a stack of free pointers plus current/begin/end offsets. A push or pop is written as an rseq critical section: the thread registers the section’s address range with the kernel, and if it is preempted or migrated anywhere inside it, the kernel steers it to an abort handler instead of resuming — the half-finished operation simply retries on the new CPU. Since only one thread runs on a CPU at a time, plain loads and stores are safe inside the window. The cost of a cache hit is a size-class lookup, an offset compare, and one store.

What free() actually does

Because objects are headerless, free(ptr) must recover the size from the address alone. It shifts the pointer down to a page number and walks the radix-tree pagemap — two or three dependent loads into mostly-hot index nodes — to the owning span, which records the size class. The object is then pushed onto the local cache’s list for that class. Both paths, side by side:

// malloc(size) — fast path            // free(ptr) — fast path
cl   = size_to_class[idx(size)];       page = ptr >> kPageShift;
list = cpu_cache[cpu][cl];             span = pagemap.lookup(page);   // radix walk
obj  = list.pop();     // rseq window  cl   = span->size_class;
return obj;                            cpu_cache[cpu][cl].push(ptr);  // rseq window

When a list empties or overflows its cap, the thread exchanges a fixed-size batch (typically 32–128 objects, tuned per class) with the transfer cache. That tier is literally an array of ready-made batches guarded by a spinlock, so the common refill is a memcpy of pointers; only when it too is exhausted does the request fall through to the central free list, which pops objects threaded through free slots of its spans. A span’s live-object count rises and falls as batches move; when it hits zero the whole span returns to the page heap.

The back end: hugepages as the unit of thought

The modern back end (the “Temeraire” page allocator) organizes memory around 2 MiB hugepages: it prefers to satisfy spans from partially-used hugepages, densely packs long-lived spans together, and returns memory to the OS at hugepage granularity via MADV_DONTNEED only when a whole hugepage drains. Keeping hot memory on intact hugepages cuts TLB misses — worth several percent of total fleet CPU in Google’s published numbers — while a background thread steadily releases cold pages. Front-end caches are bounded too: per-CPU slabs have fixed capacity, and idle threads’ caches are scavenged, so cached-but-unused memory stays capped.

Microsoft’s mimalloc (2019) pushes the sharding idea one level deeper. Where tcmalloc keeps one free list per size class per thread, mimalloc keeps free lists per page — a mimalloc “page” being a ~64 KiB block inside a larger segment, dedicated to one size class. A thread allocates from one page at a time until it fills, so consecutive allocations come from one small, contiguous region. This free-list sharding yields striking locality: objects allocated together sit together, and the working set of the allocator itself stays inside a page.

The second trick is that each page carries three free lists. The free list feeds allocation; keeping it separate from the local_free list (same-thread frees) guarantees the allocation list empties at a steady rhythm, and that moment doubles as a heartbeat where deferred work — collecting lists, returning empty pages — runs with amortized-constant cost. Frees arriving from other threads are pushed onto an atomic thread_free list with a single compare-and-swap, so cross-thread frees never take a lock and never touch the owner’s hot lists until harvested. The result is an allocator whose entire fast path — both malloc and free — is a few inlinable instructions, with no locks anywhere in ordinary operation.

The fast path, in code

mimalloc’s allocation path is short enough to read whole. Each heap keeps a pages_free_direct array mapping small sizes straight to the page currently being filled for that class, so there is no separate size-to-class computation at all. Freeing exploits alignment: segments are aligned to their 4 MiB size, so masking the low bits of any object pointer lands on the segment header, and a shift from there finds the page — no global lookup structure, no radix walk:

// mi_malloc(size)                        // mi_free(ptr)
page  = heap->pages_free_direct[wsize];   seg  = ptr & ~(4MiB - 1);        // mask
block = page->free;                       page = seg->pages[(ptr - seg) >> shift];
if (block == NULL)                        if (thread_id == page->thread_id)
  return mi_malloc_generic(size); // slow   { block->next = page->local_free;
page->free = block->next;                     page->local_free = block; }
page->used++;                             else
return block;                               atomic_push(&page->thread_free, block);

Note what is absent: no lock, no size lookup on free, and the only atomic anywhere is the compare-and-swap push for a foreign-thread free. Both functions are small enough for the compiler to inline into the caller.

The generic path: where all the work hides

Everything the fast path skips is deferred to mi_malloc_generic, reached only when a page’s free list is empty — which, because same-thread frees go to local_free instead of refilling it, is guaranteed to happen once per page-worth of allocations. At that heartbeat the allocator atomically swaps out thread_free (one xchg collects every pending foreign free), moves local_free over to free, runs any registered deferred-free callback, retires empty pages, and picks or requests a fresh page. Bounding how much runs per heartbeat is what makes the whole allocator’s worst case amortized-constant — there is no “occasionally we sort the unsorted bin” cliff as in ptmalloc2.

Full pages, delayed frees, and lazy extension

Two subtleties keep the invariants cheap. A page that fills completely is removed from the heap’s page queues so allocation never scans full pages; but then nobody would ever look at its thread_free list again. mimalloc steals the two low bits of the thread_free pointer as a state flag: the first foreign free to a full page is redirected onto the owning heap’s thread_delayed_free list, which the owner drains at its next heartbeat — rediscovering the page and requeuing it. Second, a fresh page does not thread its whole free list up front: it is extended a bounded chunk at a time as allocation proceeds, so grabbing a page is O(1) and untouched tail memory stays clean for the OS. Thread exit is handled the same lock-light way: the dead thread’s segments are abandoned, and other threads adopt them when they next need pages of that class.

Two smaller decisions round out the design. First-fit reuse within a page keeps heaps compact under churn. And because metadata lives at the segment edge rather than beside each object, a secure build can add guard pages, randomized allocation order, and encrypted free-list pointers at roughly 10% overhead — hardening that ptmalloc2’s inline-metadata layout structurally cannot offer.

The advantages reduce to four themes. Synchronization: ptmalloc2 locks an arena on nearly every call; tcmalloc and mimalloc make the common path lock-free, resorting to shared state only in amortized batches. Metadata placement: headerless objects (tcmalloc’s pagemap, mimalloc’s segment-edge metadata) waste no bytes per allocation and keep user data densely packed in cache. Locality: size-class pages mean neighbors in time become neighbors in memory, where ptmalloc2’s best-fit search and eager coalescing scatter allocations and chase cold pointers. Fragmentation and reuse: bounded caches, span/page reclamation, and (in mimalloc) first-fit-in-page keep long-running processes from the slow heap growth that plagues multi-arena ptmalloc2. In published multi-threaded benchmarks both allocators routinely run severalfold faster than glibc on allocation-heavy workloads, with equal or lower peak memory.

None of this makes ptmalloc2 a bad allocator — it is remarkably economical for single-threaded programs and has two decades of battle scars. But its central bet, that threads can share a heap if we replicate it a few times and lock carefully, has been overtaken by core counts. tcmalloc answers with a cache hierarchy; mimalloc answers by making the free list itself so small and so local that sharing never happens. Both are drop-in replacements: often the cheapest severalfold speedup a multi-threaded service will ever get is one LD_PRELOAD away.

Design differences only matter insofar as they meet a workload. Here is each allocator’s ledger of strengths and weaknesses, followed by the archetypal systems where the choice is known to move the needle. The honest caveat first: results vary with allocation size mix, thread count, and lifetime patterns — always benchmark your own service before committing. But the designs predict the outcomes well.

ptmalloc2

Pros — ships with glibc, so there is nothing to deploy or keep patched; very frugal for single-threaded programs, with low idle footprint and no up-front slab reservations; two decades of production hardening; boundary-tag coalescing keeps small, steady heaps compact.

Cons — an arena mutex on nearly every call, so throughput collapses under thread contention; per-arena heaps drift upward and rarely shrink on long uptimes; the 8–16 byte inline header taxes every object and is the canonical heap-exploitation target; cross-thread frees lock the owner’s arena.

tcmalloc

Pros — lock-free fast path from per-thread or per-CPU caches, so it scales with core count rather than thread count; headerless small objects pack densely in cache; the best telemetry of the three (heap profiles, peak-memory accounting) for observing a production fleet; tuned continuously against Google-scale workloads.

Cons — higher baseline footprint — caches, slabs and the pagemap are reserved up front, a poor trade for small processes; per-CPU mode wants a modern kernel (rseq); cross-thread frees land in the wrong cache and must be rebalanced through the middle end; a heavier dependency to build and vendor.

mimalloc

Pros — the shortest fast path of the three, on malloc and free alike; cross-thread frees cost one CAS, never a lock; sharded pages give excellent locality and low fragmentation under churn; tiny codebase (a few C files) that vendors anywhere; first-class multiple heaps; a secure build with guard pages and encrypted free lists at ~10% cost.

Cons — far less built-in introspection than tcmalloc; the youngest of the three, with fewer years of fleet mileage; page-granular reuse can briefly hold more memory than best-fit on adversarial size mixes; deferred thread_free harvesting delays reclamation when owner threads go quiet.

Example applications

A workable rule of thumb: stay on ptmalloc2 when single-threaded and short-lived; reach for tcmalloc when running a large threaded fleet you need to observe; reach for mimalloc when objects cross threads, when embedding, or when the heap itself is attack surface. Since all three sit behind the same malloc interface, the experiment costs one environment variable.