mimalloc: Microsoft's Speed Boost for Apps

Microsoft's mimalloc offers a potent solution for the memory management demands of today's hyper-concurrent applications. Developed by researchers at Microsoft Research, this open-source memory allocator is designed as a direct replacement for traditional `malloc` and `free` functions.

Applications today often juggle hundreds of threads and manage hundreds of gigabytes of memory, especially with the rise of large language models. mimalloc addresses this head-on, promising bounded worst-case allocation times and minimal contention by relying heavily on atomic operations. It's a compact library, around 12,000 lines of C code, making it easy to integrate.

Initially conceived in 2020 for Microsoft's Lean and Koka programming languages, mimalloc's scalable design quickly proved its mettle in large-scale Microsoft services. Close collaboration with product teams led to significant response time improvements in services like Bing.

The allocator is now a go-to for critical infrastructure. It serves as the default allocator for NoGIL CPython 3.13+, is integrated into Unreal Engine, and powers games like Death Stranding. Its Rust wrapper alone boasts over 100,000 daily downloads.

mimalloc shines across a spectrum of use cases, from small languages to services exceeding 500 GiB memory footprints with hundreds of threads. Its clear internal data structures, a nod to foundational software engineering principles, simplify understanding and porting.

The Fast Path to Allocation

At its core, mimalloc employs a thread-local heap, dubbed a "theap," for each thread. This theap manages memory pages, typically 64 KiB each, segmented into fixed-size blocks. This isolation means most allocations and deallocations occur without needing inter-thread synchronization.

For small allocations, mimalloc employs a remarkably efficient fast path. The process involves retrieving the thread-local theap, checking if the size exceeds a small threshold, and then directly accessing a pre-allocated block from the page's free list. This design minimizes branches and atomic operations, translating to minimal CPU cycles.

The fast path for freeing blocks is equally optimized. If the freeing thread owns the memory page, the block is simply pushed onto a local free list. This avoids synchronization overhead for the most common freeing scenario.

When a block must be freed across threads, mimalloc utilizes atomic operations, specifically a compare-and-swap, to add the block to a thread-free list associated with the page. While this requires atomicity, it's highly efficient on modern hardware when uncontended.

mimalloc’s strategy involves three free lists per page: one for active allocations, one for locally freed blocks, and an atomic list for cross-thread frees. This ensures that free lists are periodically managed, occasionally forcing a return to the more general, albeit slower, allocation path.

Balancing Scalability and Sharing

A key challenge mimalloc addresses is the inherent tension between maximizing scalability through thread isolation and enabling efficient memory sharing. Giving each thread exclusive page ownership minimizes synchronization but can lead to memory waste if other threads need similar blocks.

Conversely, a single, lock-protected shared memory pool offers optimal memory utilization but severely limits scalability. Benchmarks show mimalloc striking an effective balance, allocating significantly more data than simpler allocators while maintaining a much lower committed-to-live memory ratio.

This balance is achieved through a "page stealing" technique, akin to work-stealing in thread pools. This allows threads to acquire ownership of idle pages from other threads without expensive cross-thread synchronization, a feature developed in close collaboration with the Azure Cosmos DB team.