vault

mimalloc

13 min read

mimalloc

mimalloc (from “microsoft malloc”) is a general-purpose allocator from Microsoft Research, written primarily by Daan Leijen, whose central idea is free-list sharding: instead of one free list per size class, it keeps a separate free list per page, dramatically improving spatial locality (Leijen, Zorn, de Moura 2019, MSR-TR-2019-18). It was born as the allocator backend for the Lean theorem prover and the Koka language — reference-counting runtimes that make enormous numbers of small, short-lived allocations — and it is engineered around a tiny, extremely regular fast path with a deterministic “heartbeat” slow path that batches all the expensive work. Its core library is remarkably small (under 3,500 lines of code, versus roughly 20,000 for tcmalloc and 25,000 for jemalloc), and it ships an optional security-hardened build with encoded free lists and guard pages. This note is written as of mimalloc v3.3.2 / v2.3.2 (released 2026-04-29), and draws the algorithmic detail from the original tech report, which describes what is now the v1 lineage.

Mental Model

The one idea to hold onto is free-list sharding. A conventional allocator keeps one free list per size class, so the free objects of a given size are scattered across the entire heap; walking that list (as functional-style code does when it folds over a structure and rebuilds it) touches memory all over the address space, thrashing the CPU cache. mimalloc instead divides the heap into pages, each page holding blocks of a single size class with its own free list. Because malloc drains one page fully before moving to the next, a burst of allocations comes back tightly packed within one page — good locality by construction (tech report §2.1). Layered on top is a three-list scheme per page that separates local frees, deferred maintenance, and cross-thread frees so that the fast path is a single branch and a pointer pop.

flowchart TD
  subgraph PAGE["one mimalloc page (one size class)"]
    FREE["free list<br/>(alloc pops from here)"]
    LOCAL["local_free list<br/>(this thread's frees)"]
    TFREE["thread_free list<br/>(other threads' frees, atomic)"]
  end
  ALLOC["mi_malloc(size)"] --> POP{"free != NULL?"}
  POP -- "yes (fast path)" --> RET["pop block, used++"]
  POP -- "no (slow path)" --> GEN["malloc_generic:<br/>free = local_free;<br/>collect thread_free;<br/>deferred_free()"]
  GEN --> RET
  LFREE["free(p) on owner thread"] -. push .-> LOCAL
  XFREE["free(p) on other thread"] -. atomic push .-> TFREE

mimalloc’s per-page three-list design. What it shows: allocation only ever pops from the page’s free list (one branch, no lock); the owning thread’s frees go to local_free, and frees from other threads go atomically to thread_free. When free empties, the generic slow path refills it from local_free and atomically drains thread_free, and does deferred maintenance at the same time. The insight to take: by keeping three lists, mimalloc turns the fast path into a single unconditional pop while guaranteeing the slow path runs at a bounded, regular cadence — a deterministic “heartbeat” where all the expensive work is amortized.

Why It Exists: Reference-Counting Runtimes

mimalloc’s design goals are legible only against its origin. It was built for Lean and Koka, functional languages that manage memory by reference counting and therefore “allocate many small short-lived objects” and free large structures recursively (tech report §1). Two consequences fall out. First, allocation and free must be blisteringly fast because they dominate runtime. Second — and this is the unusual part — freeing a large data structure means a cascade of decrements, and to avoid long pauses the runtime wants to defer some of that work and resume it “when there is memory pressure.” An allocator that offers a cooperative hook to do deferred work at a predictable time is therefore valuable. mimalloc bakes exactly that in. The authors report that in Lean, a custom single-free-list allocator initially “outperformed even highly optimized allocators like jemalloc,” and mimalloc was their attempt to generalize that win — later measuring, for instance, a >25% speedup in the Lean compiler simply by replacing a single free list with a per-page sharded one (tech report §2.1).

The Three Free Lists

Every mimalloc page carries three singly linked lists, and understanding their interplay is understanding mimalloc (tech report §2).

free — the allocation list. mi_malloc does nothing but pop the head of the current page’s free list. There is no bump pointer: the authors tested one and found it “consistently about 2% worse” because it adds a second branch (bump-or-pop) to the hot path and, for security, sequential bump allocation is undesirable anyway. A used counter is incremented on each allocation so the page knows when all its blocks have been returned. The entire fast path is:

void* malloc_in_page(page_t* page, size_t size) {
  block_t* block = page->free;             // page-local free list
  if (block == NULL) return malloc_generic(size);  // slow path
  page->free = block->next;                // pop
  page->used++;
  return block;
}

local_free — deferred local frees. When the owning thread frees a block, mimalloc does not push it back onto free. It pushes it onto a separate local_free list. This is the trick that makes the slow path fire on a schedule: because frees never refill free, the free list is guaranteed to empty after a bounded number of allocations, at which point the generic routine runs. Deferring frees this way is what gives mimalloc a deterministic heartbeat (tech report §2.3).

thread_free — cross-thread frees. Pages belong to a thread-local heap, so local allocation needs no synchronization. But any thread may free any object. A free from a non-owning thread is pushed onto the page’s thread_free list with a lock-free compare-and-swap loop:

void atomic_push(block_t** list, block_t* block) {
  do { block->next = *list; }
  while (!atomic_compare_and_swap(list, block, block->next));
}

Because the list is sharded per page, threads freeing into different pages never contend; a single uncontended CAS is cheap on modern hardware (tech report §2.4).

The generic slow path (malloc_generic) is the heartbeat that ties them together. When free empties, it runs deferred_free() (the cooperative hook for reference-count decrements), then for each page collects local_free into free and atomically swaps thread_free out and appends it to free:

void page_collect(page_t* page) {
  page->free = page->local_free;   // move local frees back
  page->local_free = NULL;
  // ... atomically take thread_free and append to free ...
}

This single routine amortizes every expensive operation — deferred frees, collecting local and cross-thread frees, finding a page with space — over many fast allocations. The maximum number of pages freed in one pass is bounded to cap worst-case allocation time (tech report §3.3).

Heap Layout: Segments and Pages

Pages live inside segments. In the original (v1) design a segment is 4 MiB aligned, holding 64 pages of 64 KiB for small objects (blocks under 8 KiB); large objects (under 512 KiB) get one page spanning the whole segment, and huge objects (over 512 KiB) get a single page of the required size (tech report §3.1). Keeping one uniform representation for small, large, and huge is a deliberate simplification that shrinks the code.

The alignment is what makes free cheap. To free a pointer p, mimalloc masks off the low bits to find the enclosing segment, then shifts by the segment’s page_shift (16 for 64 KiB small pages, 22 for 4 MiB large/huge) to index the page:

void free(void* p) {
  segment_t* segment = (segment_t*)((uintptr_t)p & ~(4*MB - 1));
  if (segment == NULL) return;                 // p == NULL folds in
  page_t* page = &segment->pages[(p - segment) >> segment->page_shift];
  // ... push to local_free or thread_free depending on owning thread ...
}

It then checks whether the current thread is the segment’s owner (thread_id() == segment->thread_id, where thread_id() is read cheaply from a fixed offset off the fs register on Linux x86-64) to decide between the local_free and thread_free push (tech report §3.2). No per-object header is needed; everything is derived from pointer arithmetic.

Uncertain

Verify: the current segment/page sizes and the arena layer. Reason: the algorithmic detail above is from the 2019 tech report (v1 lineage), which uses 4 MiB segments; the current README instead states an arenas → segments → pages hierarchy with segments typically 32–64 MiB and pages “usually 64 KiB,” and v2/v3 reworked the memory management (v2 uses “thread-local segments to reduce fragmentation,” v3 “simplifies the lock-free design” and adds first-class heaps allocatable from any thread) (mimalloc README). The free-list-sharding core is unchanged, but exact sizes and the arena layer differ by major version. To resolve: read the source for the specific version deployed. uncertain

The Full List and Cross-Thread Frees to Full Pages

A naive implementation traverses every page of a size class in the generic routine, which becomes pathological when a workload holds thousands of full pages (the authors hit “over 18,000 full pages” on the SPEC gcc benchmark, a 30% slowdown). The fix is a full list: full pages are moved out of the regular per-size-class lists and only moved back when an object in them is freed (tech report §3.4).

That reintroduces a hard case: how does a thread freeing into someone else’s full page signal the owner to un-full it, without a lock? mimalloc encodes a small state machine in the two least-significant bits of the thread_free pointer — states NORMAL, DELAYED, and DELAYING. A full page’s cross-thread frees are routed to a heap-owned thread_delayed_free list instead of the page’s own thread_free; the DELAYING transient state keeps the owning heap structure alive during the handoff, and after one delayed free the state returns to NORMAL so that only one delayed free per page is needed to flag it as no-longer-full. This optimization matters: without it the xmalloc-test asymmetric-workload benchmark is 30% slower (tech report §3.4).

Security-Hardened Mode

Because the design has few, regular structures, it lends itself to cheap hardening. The secure variant (originally “smalloc”, built today with -DMI_SECURE=ON) adds four mitigations (tech report §3.5; README):

  • Guard pages between mimalloc pages, so a heap overflow hits an unmapped page and faults rather than corrupting adjacent metadata.
  • Randomized initial free lists, defeating “heap feng shui” grooming that relies on predictable allocation addresses.
  • Encoded (xor-encoded) free-list pointers with a per-page key, so an attacker overwriting a next pointer with a known value cannot redirect the allocator, and such corruption is detectable.
  • Separate heaps, letting an application isolate sensitive objects (e.g. C++ virtual-method tables) from attacker-controlled allocations.

The report’s striking result is that all this costs only about 3% on average — far less than the authors expected — because the mitigations piggyback on already-cheap, regular operations (tech report §3.5). (The current README quotes roughly 10% overhead for the full secure build, a difference worth attributing to version and configuration.)

First-Class Heaps and Bounded Guarantees

mimalloc exposes first-class heaps via the mi_heap_t type: a program can create multiple independent heaps, allocate into any of them, and destroy an entire heap at once rather than freeing each object — an arena-style bulk-free that suits request-scoped or phase-scoped memory. v3 extends this to “true first-class heaps where one can allocate in a heap from any thread” (README). The allocator advertises strong worst-case properties: no “blowup” (unbounded growth from producer/consumer free patterns), bounded worst-case allocation time up to OS primitives, ~0.2% metadata overhead, and at most 1/8 (12.5%) internal fragmentation from size-class rounding, achieved “using only atomic operations” with no internal locks (tech report abstract).

Using mimalloc

The API mirrors standard C with an mi_ prefix — mi_malloc, mi_free, mi_calloc, mi_realloc — and C++ operators via <mimalloc-new-delete.h>. Without touching source, it can override the system allocator through dynamic preloading (README):

# Linux / BSD (ELF): interpose libmimalloc ahead of libc's malloc
env LD_PRELOAD=/usr/lib/libmimalloc.so ./my_program
 
# macOS: the Mach-O equivalent
env DYLD_INSERT_LIBRARIES=/usr/lib/libmimalloc.dylib ./my_program

LD_PRELOAD works because the dynamic linker resolves malloc to the first definition in the search scope — see Symbol Interposition and LD_PRELOAD. Behavior is tuned with MIMALLOC_-prefixed environment variables: MIMALLOC_SHOW_STATS=1 prints statistics at exit, MIMALLOC_VERBOSE=1 enables diagnostics, MIMALLOC_PURGE_DELAY=N sets how long (in ms, default 1000 in v3) freed memory lingers before being returned to the OS, and MIMALLOC_ALLOW_LARGE_OS_PAGES=1 / MIMALLOC_RESERVE_HUGE_OS_PAGES=N opt into 2–4 MiB or 1 GiB huge pages (README).

Every environment variable has a programmatic twin. The mi_option_t enum and the mi_option_get() / mi_option_set() / mi_option_enable() / mi_option_disable() functions let a program set the same knobs in code (mimalloc options API). Notable options include mi_option_purge_delay (“memory purging is delayed by N milliseconds”), mi_option_reserve_huge_os_pages (“reserve N huge OS pages (1 GiB pages) at startup”), mi_option_eager_commit (whether to commit segment memory eagerly rather than on first touch), and mi_option_arena_eager_commit (the same for the arena layer, with a value of 2 meaning “enable just on overcommit systems”). The mi_heap_t first-class-heap API pairs with a heap-walking facility so tooling can iterate every live block in a heap — useful for leak analysis and for the bulk mi_heap_destroy() teardown pattern that frees an entire heap in one call.

Failure Modes, Alternatives, and Production Notes

Windows override is fragile. On Linux the LD_PRELOAD path is clean, but on Windows overriding malloc requires mimalloc-redirect.dll, linking the C runtime as a DLL (/MD), and specific link ordering — a frequent source of “override didn’t take” problems (README).

Version confusion. Three lineages are maintained in parallel — v1 (legacy, the tech-report design), v2 (stable, thread-local segments), and v3 (recommended, simplified lock-free design with cross-thread first-class heaps), with 2026-04-29 releases v3.3.2 / v2.3.2 / v1.9.10 (README). Benchmark numbers and design details cited for one lineage may not hold for another.

Benchmark claims are self-reported and dated. The tech report’s headline figures — mimalloc 7% faster than tcmalloc and 14% faster than jemalloc on Redis — come from the authors using mimalloc v1.0.0 in 2019, and the README’s “outperforms other leading allocators” is the project’s own claim (tech report abstract; README). Treat them as favorable vendor data, not independent verification; the honest summary is that mimalloc is competitive with and often ahead of jemalloc and tcmalloc across many workloads while being far smaller.

Uncertain

Verify: the comparative benchmark claims (7% over tcmalloc, 14% over jemalloc on Redis). Reason: self-reported by the mimalloc authors, dated 2019, on mimalloc v1.0.0 and then-current competitor versions. Allocator rankings are workload-dependent and shift between versions. To resolve: consult independent, current benchmarks for the specific workload and versions in question. uncertain

Against its peers, mimalloc’s distinctive strengths are code size (auditability and portability), locality (the free-list-sharding thesis), a deterministic slow-path cadence (valuable for latency-sensitive and reference-counting runtimes), and cheap security hardening. jemalloc beats it on introspection depth and fragmentation tuning knobs; tcmalloc targets Google-scale many-core throughput with rseq per-CPU caches. For the “which allocator?” decision, see Allocator Trade-offs and Selection, and for the default it displaces, ptmalloc and glibc malloc.

See Also

Graph View