The 12,000-line secret behind Bing's speed: how mimalloc beat the allocator trade-off

Memory allocation often goes unnoticed in systems performance. But for Microsoft's Bing team, switching to a custom allocator built by the company's own research division translated directly into faster response times. That allocator, mimalloc, is the subject of a new blog post from the RiSE group at Microsoft Research, which explains the design decisions that let it scale from a single-threaded programming language runtime to a 500-GiB cloud service.

At just 12,000 lines of C, mimalloc is deliberately compact. Its real innovation is how it sidesteps a classic systems trade-off: choosing between scaling across many threads and keeping memory usage close to what the application actually needs. The blog, published on the Microsoft Research website, digs into the architecture with unusual technical depth, including code snippets from the fast path and a description of the "page stealing" mechanism developed with the Azure Cosmos DB team.

The fast path: few branches, no atomics

mimalloc's core insight is that most allocations are small and thread-local. Each thread gets its own thread-local heap, or "theap", which owns a set of 64-KiB "mimalloc pages". Each page contains blocks of a single size class. To allocate a block, the thread simply pops it from a free list, no locks, no atomic operations. The blog provides the assembly output for the fast path on x64: seven instructions with just two rare branches (one for oversized allocations, one for an empty page).

This branch-minimization comes from a careful initialization strategy: the thread-local theap pointer is never NULL, and all entries in the small_pages array point to pre-initialized empty pages (whose free list is NULL). As the authors note, this eliminates two conditional checks that most allocators need, converting the common case into a straight line of instructions.

Three free lists per page, the randomized inspiration

Where mimalloc diverges most sharply from its peers is in its free list design. Each mimalloc page maintains three free lists: the main free list for allocations, the local_free list for blocks freed by the owning thread, and the thread_free list, atomic, for blocks freed by other threads. A program can easily have thousands of free lists in flight.

The blog explicitly links this design to randomized algorithms. Just as a treap uses random splits to keep a tree balanced without complex rotations, mimalloc relies on the law of large numbers: with thousands of per-page atomic lists, the chance that two threads simultaneously try to free to the same page is low. Most compare-and-swap operations are uncontended and cheap. "By sheer chance, we also end up with trees that are balanced enough," the authors write, extending the analogy.

This per-page arrangement also improves cache locality. Because allocation tends to stay within the same page until it is full, recently freed blocks are likely to be in the same cache lines that the thread is already using, a sharp contrast to designs with a single free list per size class, which can scatter blocks across memory.

The allocator's trilemma: benchmarks that show the tension

The post includes a benchmark that makes the trade-off visible. Using the Windows thread pool with about 800 active threads, the test runs a workload that alternates allocation, deallocation, and brief blocking periods, a simulation of modern cloud services. Three allocators are compared:

• Standard system allocator: excellent memory sharing (only 1.1× committed over live data), but managed to allocate only 56 GB over the test duration. It did not scale.
• A competing concurrent allocator: allocated 262 GiB, nearly 4× more, but committed 4× more memory than the live data. At scale, that ratio becomes prohibitive.
• mimalloc: allocated the same 262 GiB while keeping committed memory at just 1.3× the live data. The red line (committed) stays close to the blue line (live).

The blog attributes the breakthrough to "page stealing", a mechanism developed with the Azure Cosmos DB team that lets threads take ownership of pages without expensive cross-thread synchronization. The authors promise a forthcoming technical report with a precise description, but the benchmark results already suggest that mimalloc achieves what was long considered impossible: scaling throughput without blowing up memory.

From Lean to Bing to CPython

Originally designed in 2020 to support the Lean and Koka programming languages, both of which rely on compiler-guided reference counting, mimalloc has since been adopted far beyond Microsoft Research. Bing uses it in production, contributing directly to faster response times. Outside the company, it is the memory allocator for the NoGIL version of CPython 3.13+, integrated into Unreal Engine, and used in games like Death Stranding. Its Rust wrapper alone sees over 100,000 downloads per day.

The project is hosted on GitHub and has amassed over 12,000 stars. Ports exist for Windows, macOS, Linux, FreeBSD, NetBSD, DragonFly BSD, and various game consoles. The blog emphasizes that its clear internal data structures, the "tables, not flowcharts" philosophy borrowed from Fred Brooks, have made it easier for external contributors to port and customize than many industry allocators.

What this means for systems builders

For teams building high-concurrency services, especially those using large language models with memory footprints in the hundreds of gigabytes, mimalloc's bounded worst-case allocation times and low internal fragmentation offer a concrete path to better performance without rewriting application code. It is a drop-in replacement for malloc and free.

The deeper lesson is that the allocator scales not because of a revolutionary data structure but because of a deliberate statistical bet: spread the coordination cost across thousands of tiny lists, and the probability of conflict collapses. In an era where number of threads per server continues to grow, and where LLM inference often consumes hundreds of gigabytes, that bet is paying off in production, at scale, inside Microsoft and out.