Mimalloc: Free List Sharding in Action

Modern memory allocators have to balance many simultaneous demands,
including performance, security, the presence of concurrency, and
application-specific demands depending on the context of their use. One
increasing use-case for allocators is as back-end implementations of
languages, such as Swift and Python, that use reference counting to
automatically deallocate objects. We present mimalloc, a memory allocator
that effectively balances these demands, shows significant performance
advantages over existing allocators, and is tailored to support languages
that rely on the memory allocator as a backend for reference counting.
Mimalloc combines several innovations to achieve this result. First, it
uses three page-local sharded free lists to increase locality, avoid
contention, and support a highly-tuned allocate and free fast path. These
free lists also support *temporal cadence*, which allows the allocator to
predictably leave the fast path for regular maintenance tasks such as
supporting deferred freeing, handling frees from non-local threads, etc.
While influenced by the allocation workload of the reference-counted Lean
and Koka programming language, we show that mimalloc has superior
performance to modern commercial memory allocators, including tcmalloc
and jemalloc, with speed improvements of 7% and 14%, respectively, on
redis, and consistently out performs over a wide range of sequential and
concurrent benchmarks. Allocators tailored to provide an efficient
runtime for reference-counting languages reduce the implementation burden
on developers and encourage the creation of innovative new language
designs.