mimalloc (pronounced “me-malloc”)
is a general purpose allocator with excellent performance characteristics.
Initially developed by Daan Leijen for the run-time systems of the
Koka and Lean languages.
It is a drop-in replacement for malloc and can be used in other programs
without code changes, for example, on Unix you can use it as:
> LD_PRELOAD=/usr/bin/libmimalloc.so myprogram
Notable aspects of the design include:
- small and consistent: the library is less than 3500 LOC using simple and
consistent data structures. This makes it very suitable
to integrate and adapt in other projects. For runtime systems it
provides hooks for a monotonic heartbeat and deferred freeing (for
bounded worst-case times with reference counting). - free list sharding: the big idea: instead of one big free list (per size class) we have
many smaller lists per memory “page” which both reduces fragmentation
and increases locality —
things that are allocated close in time get allocated close in memory.
(A memory “page” in mimalloc contains blocks of one size class and is
usually 64KiB on a 64-bit system). - eager page reset: when a “page” becomes empty (with increased chance
due to free list sharding) the memory is marked to the OS as unused (“reset” or “purged”)
reducing (real) memory pressure and fragmentation, especially in long running
programs. - secure: mimalloc can be build in secure mode, adding guard pages,
randomized allocation, encrypted free lists, etc. to protect against various
heap vulnerabilities. The performance penalty is only around 3% on average
over our benchmarks. - first-class heaps: efficiently create and use multiple heaps to allocate across different regions.
A heap can be destroyed at once instead of deallocating each object separately. - bounded: it does not suffer from blowup [1], has bounded worst-case allocation
times (wcat), bounded space overhead (~0.2% meta-data, with at most 16.7% waste in allocation sizes),
and has no internal points of contention using only atomic operations. - fast: In our benchmarks (see below),
mimalloc always outperforms all other leading allocators (jemalloc, tcmalloc, Hoard, etc),
and usually uses less memory (up to 25% more in the worst case). A nice property
is that it does consistently well over a wide range of benchmarks.
The documentation gives a full overview of the API.
You can read more on the design of mimalloc in the technical report which also has detailed benchmark results.
Enjoy!
Windows
Open ide/vs2017/mimalloc.sln in Visual Studio 2017 and build.
The mimalloc project builds a static library (in out/msvc-x64), while the
mimalloc-override project builds a DLL for overriding malloc
in the entire program.
MacOSX, Linux, BSD, etc.
We use cmake1 as the build system:
> mkdir -p out/release
> cd out/release
> cmake ../..
> make
This builds the library as a shared (dynamic)
library (.so or .dylib), a static library (.a), and
as a single object file (.o).
> sudo make install (install the library and header files in /usr/local/lib and /usr/local/include)
You can build the debug version which does many internal checks and
maintains detailed statistics as:
> mkdir -p out/debug
> cd out/debug
> cmake -DCMAKE_BUILD_TYPE=Debug ../..
> make
This will name the shared library as libmimalloc-debug.so.
Finally, you can build a secure version that uses guard pages, encrypted
free lists, etc, as:
> mkdir -p out/secure
> cd out/secure
> cmake -DSECURE=ON ../..
> make
This will name the shared library as libmimalloc-secure.so.
Use ccmake2 instead of cmake
to see and customize all the available build options.
Notes:
- Install CMake:
sudo apt-get install cmake - Install CCMake:
sudo apt-get install cmake-curses-gui
The preferred usage is including
the shared- or static library, and using the mi_malloc API exclusively for allocation. For example,
gcc -o myprogram -lmimalloc myfile.c
mimalloc uses only safe OS calls (mmap and VirtualAlloc) and can co-exist
with other allocators linked to the same program.
If you use cmake, you can simply use:
find_package(mimalloc 1.0 REQUIRED)
in your CMakeLists.txt to find a locally installed mimalloc. Then use either:
target_link_libraries(myapp PUBLIC mimalloc)
to link with the shared (dynamic) library, or:
target_link_libraries(myapp PUBLIC mimalloc-static)
to link with the static library. See testCMakeLists.txt for an example.
You can pass environment variables to print verbose messages (MIMALLOC_VERBOSE=1)
and statistics (MIMALLOC_STATS=1) (in the debug version):
> env MIMALLOC_STATS=1 ./cfrac 175451865205073170563711388363
175451865205073170563711388363 = 374456281610909315237213 * 468551
heap stats: peak total freed unit
normal 2: 16.4 kb 17.5 mb 17.5 mb 16 b ok
normal 3: 16.3 kb 15.2 mb 15.2 mb 24 b ok
normal 4: 64 b 4.6 kb 4.6 kb 32 b ok
normal 5: 80 b 118.4 kb 118.4 kb 40 b ok
normal 6: 48 b 48 b 48 b 48 b ok
normal 17: 960 b 960 b 960 b 320 b ok
heap stats: peak total freed unit
normal: 33.9 kb 32.8 mb 32.8 mb 1 b ok
huge: 0 b 0 b 0 b 1 b ok
total: 33.9 kb 32.8 mb 32.8 mb 1 b ok
malloc requested: 32.8 mb
committed: 58.2 kb 58.2 kb 58.2 kb 1 b ok
reserved: 2.0 mb 2.0 mb 2.0 mb 1 b ok
reset: 0 b 0 b 0 b 1 b ok
segments: 1 1 1
-abandoned: 0
pages: 6 6 6
-abandoned: 0
mmaps: 3
mmap fast: 0
mmap slow: 1
threads: 0
elapsed: 2.022s
process: user: 1.781s, system: 0.016s, faults: 756, reclaims: 0, rss: 2.7 mb
The above model of using the mi_ prefixed API is not always possible
though in existing programs that already use the standard malloc interface,
and another option is to override the standard malloc interface
completely and redirect all calls to the mimalloc library instead.
Overriding the standard malloc can be done either dynamically or statically.
Dynamic override
This is the recommended way to override the standard malloc interface.
Unix, BSD, MacOSX
On these systems we preload the mimalloc shared
library so all calls to the standard malloc interface are
resolved to the mimalloc library.
-
env LD_PRELOAD=/usr/lib/libmimalloc.so myprogram(on Linux, BSD, etc.) -
env DYLD_INSERT_LIBRARIES=usr/lib/libmimalloc.dylib myprogram(On MacOSX)Note certain security restrictions may apply when doing this from
the shell.
You can set extra environment variables to check that mimalloc is running,
like:
env MIMALLOC_VERBOSE=1 LD_PRELOAD=/usr/lib/libmimalloc.so myprogram
or run with the debug version to get detailed statistics:
env MIMALLOC_STATS=1 LD_PRELOAD=/usr/lib/libmimalloc-debug.so myprogram
Windows
On Windows you need to link your program explicitly with the mimalloc
DLL, and use the C-runtime library as a DLL (the /MD or /MDd switch).
To ensure the mimalloc DLL gets loaded it is easiest to insert some
call to the mimalloc API in the main function, like mi_version().
Due to the way mimalloc intercepts the standard malloc at runtime, it is best
to link to the mimalloc import library first on the command line so it gets
loaded right after the universal C runtime DLL (ucrtbase). See
the mimalloc-override-test project for an example.
Static override
On Unix systems, you can also statically link with mimalloc to override the standard
malloc interface. The recommended way is to link the final program with the
mimalloc single object file (mimalloc-override.o). We use
an object file instead of a library file as linkers give preference to
that over archives to resolve symbols. To ensure that the standard
malloc interface resolves to the mimalloc library, link it as the first
object file. For example:
gcc -o myprogram mimalloc-override.o myfile1.c ...
We tested mimalloc against many other top allocators over a wide
range of benchmarks, ranging from various real world programs to
synthetic benchmarks that see how the allocator behaves under more
extreme circumstances.
In our benchmarks, mimalloc always outperforms all other leading
allocators (jemalloc, tcmalloc, Hoard, etc), and usually uses less
memory (up to 25% more in the worst case). A nice property is that it
does consistently well over the wide range of benchmarks.
Allocators are interesting as there exists no algorithm that is generally
optimal — for a given allocator one can usually construct a workload
where it does not do so well. The goal is thus to find an allocation
strategy that performs well over a wide range of benchmarks without
suffering from underperformance in less common situations (which is what
the second half of our benchmark set tests for).
We show here only the results on an AMD EPYC system (Apr 2019) — for
specific details and further benchmarks we refer to the technical report.
The benchmark suite is scripted and available separately
as mimalloc-bench.
Benchmark Results
Testing on a big Amazon EC2 instance (r5a.4xlarge)
consisting of a 16-core AMD EPYC 7000 at 2.5GHz
with 128GB ECC memory, running Ubuntu 18.04.1 with LibC 2.27 and GCC 7.3.0.
The measured allocators are mimalloc (mi),
Google’s tcmalloc (tc) used in Chrome,
jemalloc (je) by Jason Evans used in Firefox and FreeBSD,
snmalloc (sn) by Liétar et al. [8], rpmalloc (rp) by Mattias Jansson at Rampant Pixels,
Hoard by Emery Berger [1],
the system allocator (glibc) (based on PtMalloc2), and the Intel thread
building blocks allocator (tbb).
Memory usage:
(note: the xmalloc-testN memory usage should be disregarded is it
allocates more the faster the program runs).
In the first five benchmarks we can see mimalloc outperforms the other
allocators moderately, but we also see that all these modern allocators
perform well — the times of large performance differences in regular
workloads are over :-).
In cfrac and espresso, mimalloc is a tad faster than tcmalloc and
jemalloc, but a solid 10% faster than all other allocators on
espresso. The tbb allocator does not do so well here and lags more than
20% behind mimalloc. The cfrac and espresso programs do not use much
memory (~1.5MB) so it does not matter too much, but still mimalloc uses
about half the resident memory of tcmalloc.
The leanN program is most interesting as a large realistic and
concurrent workload of the Lean theorem prover
compiling its own standard library, and there is a 8% speedup over tcmalloc. This is
quite significant: if Lean spends 20% of its time in the
allocator that means that mimalloc is 1.3× faster than tcmalloc
here. (This is surprising as that is not measured in a pure
allocation benchmark like alloc-test. We conjecture that we see this
outsized improvement here because mimalloc has better locality in
the allocation which improves performance for the other computations
in a program as well).
The redis benchmark shows more differences between the allocators where
mimalloc is 14% faster than jemalloc. On this benchmark tbb (and Hoard) do
not do well and are over 40% slower.
The larson server workload allocates and frees objects between
many threads. Larson and Krishnan [2] observe this
behavior (which they call bleeding) in actual server applications, and the
benchmark simulates this.
Here, mimalloc is more than 2.5× faster than tcmalloc and jemalloc
due to the object migration between different threads. This is a difficult
benchmark for other allocators too where mimalloc is still 48% faster than the next
fastest (snmalloc).
The second benchmark set tests specific aspects of the allocators and
shows even more extreme differences between them.
The alloc-test, by
OLogN Technologies AG, is a very allocation intensive benchmark doing millions of
allocations in various size classes. The test is scaled such that when an
allocator performs almost identically on alloc-test1 as alloc-testN it
means that it scales linearly. Here, tcmalloc, snmalloc, and
Hoard seem to scale less well and do more than 10% worse on the
multi-core version. Even the best allocators (tcmalloc and jemalloc) are
more than 10% slower as mimalloc here.
The sh6bench and sh8bench benchmarks are
developed by MicroQuill as part of SmartHeap.
In sh6bench mimalloc does much
better than the others (more than 2× faster than jemalloc).
We cannot explain this well but believe it is
caused in part by the “reverse” free-ing pattern in sh6bench.
Again in sh8bench the mimalloc allocator handles object migration
between threads much better and is over 36% faster than the next best
allocator, snmalloc. Whereas tcmalloc did well on sh6bench, the
addition of object migration caused it to be almost 3 times slower
than before.
The xmalloc-testN benchmark by Lever and Boreham [5] and Christian Eder,
simulates an asymmetric workload where
some threads only allocate, and others only free. The snmalloc
allocator was especially developed to handle this case well as it
often occurs in concurrent message passing systems (like the [Pony] language
for which snmalloc was initially developed). Here we see that
the mimalloc technique of having non-contended sharded thread free
lists pays off as it even outperforms snmalloc here.
Only jemalloc also handles this reasonably well, while the
others underperform by a large margin.
The cache-scratch benchmark by Emery Berger [1], and introduced with the Hoard
allocator to test for passive-false sharing of cache lines. With a single thread they all
perform the same, but when running with multiple threads the potential allocator
induced false sharing of the cache lines causes large run-time
differences, where mimalloc is more than 18× faster than jemalloc and
tcmalloc! Crundal [6] describes in detail why the false cache line
sharing occurs in the tcmalloc design, and also discusses how this
can be avoided with some small implementation changes.
Only snmalloc and tbb also avoid the
cache line sharing like mimalloc. Kukanov and Voss [7] describe in detail
how the design of tbb avoids the false cache line sharing.
-
[1] Emery D. Berger, Kathryn S. McKinley, Robert D. Blumofe, and Paul R. Wilson.
Hoard: A Scalable Memory Allocator for Multithreaded Applications
the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IX). Cambridge, MA, November 2000.
pdf -
[2] P. Larson and M. Krishnan. Memory allocation for long-running server applications. In ISMM, Vancouver, B.C., Canada, 1998.
pdf -
[3] D. Grunwald, B. Zorn, and R. Henderson.
Improving the cache locality of memory allocation. In R. Cartwright, editor,
Proceedings of the Conference on Programming Language Design and Implementation, pages 177–186, New York, NY, USA, June 1993.
pdf -
[4] J. Barnes and P. Hut. A hierarchical O(n*log(n)) force-calculation algorithm. Nature, 324:446-449, 1986.
-
[5] C. Lever, and D. Boreham. Malloc() Performance in a Multithreaded Linux Environment.
In USENIX Annual Technical Conference, Freenix Session. San Diego, CA. Jun. 2000.
Available at https://github.com/kuszmaul/SuperMalloc/tree/master/tests -
[6] Timothy Crundal. Reducing Active-False Sharing in TCMalloc.
2016. http://courses.cecs.anu.edu.au/courses/CSPROJECTS/16S1/Reports/Timothy*Crundal*Report.pdf. CS16S1 project at the Australian National University. -
[7] Alexey Kukanov, and Michael J Voss.
The Foundations for Scalable Multi-Core Software in Intel Threading Building Blocks.
Intel Technology Journal 11 (4). 2007 -
[8] Paul Liétar, Theodore Butler, Sylvan Clebsch, Sophia Drossopoulou, Juliana Franco, Matthew J Parkinson,
Alex Shamis, Christoph M Wintersteiger, and David Chisnall.
Snmalloc: A Message Passing Allocator.
In Proceedings of the 2019 ACM SIGPLAN International Symposium on Memory Management, 122–135. ACM. 2019.
This project welcomes contributions and suggestions. Most contributions require you to agree to a
Contributor License Agreement (CLA) declaring that you have the right to, and actually do, grant us
the rights to use your contribution. For details, visit https://cla.microsoft.com.
When you submit a pull request, a CLA-bot will automatically determine whether you need to provide
a CLA and decorate the PR appropriately (e.g., label, comment). Simply follow the instructions
provided by the bot. You will only need to do this once across all repos using our CLA.
