search

microsoft / mimalloc

mimalloc is a compact general purpose allocator with excellent performance.
MIT License
9.74k stars 791 forks source link

readme

mimalloc

 

mimalloc (pronounced "me-malloc") is a general purpose allocator with excellent performance characteristics. Initially developed by Daan Leijen for the runtime systems of the Koka and Lean languages.

Latest release tag: v2.1.7 (2024-05-21).
Latest v1 tag: v1.8.7 (2024-05-21).

mimalloc is a drop-in replacement for malloc and can be used in other programs without code changes, for example, on dynamically linked ELF-based systems (Linux, BSD, etc.) you can use it as:

> LD_PRELOAD=/usr/lib/libmimalloc.so  myprogram

It also includes a robust way to override the default allocator in Windows. Notable aspects of the design include:

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!

Branches

Releases

Note: the v2.x version has a different algorithm for managing internal mimalloc pages (as slices) that tends to use reduce memory usage and fragmentation compared to mimalloc v1.x (especially for large workloads). Should otherwise have similar performance (see below); please report if you observe any significant performance regression.

Special thanks to:

Usage

mimalloc is used in various large scale low-latency services and programs, for example:

Building

Windows

Open ide/vs2022/mimalloc.sln in Visual Studio 2022 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.

macOS, 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 -DMI_SECURE=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:

  1. Install CMake: sudo apt-get install cmake
  2. Install CCMake: sudo apt-get install cmake-curses-gui

Single source

You can also directly build the single src/static.c file as part of your project without needing cmake at all. Make sure to also add the mimalloc include directory to the include path.

Using the library

The preferred usage is including <mimalloc.h>, linking with 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.4 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 test\CMakeLists.txt for an example.

For best performance in C++ programs, it is also recommended to override the global new and delete operators. For convenience, mimalloc provides mimalloc-new-delete.h which does this for you -- just include it in a single(!) source file in your project. In C++, mimalloc also provides the mi_stl_allocator struct which implements the std::allocator interface.

You can pass environment variables to print verbose messages (MIMALLOC_VERBOSE=1) and statistics (MIMALLOC_SHOW_STATS=1) (in the debug version):

> env MIMALLOC_SHOW_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 .

Environment Options

You can set further options either programmatically (using mi_option_set), or via environment variables:

Advanced options:

Further options for large workloads and services:

Use caution when using fork in combination with either large or huge OS pages: on a fork, the OS uses copy-on-write for all pages in the original process including the huge OS pages. When any memory is now written in that area, the OS will copy the entire 1GiB huge page (or 2MiB large page) which can cause the memory usage to grow in large increments.

Secure Mode

mimalloc can be build in secure mode by using the -DMI_SECURE=ON flags in cmake. This build enables various mitigations to make mimalloc more robust against exploits. In particular:

As always, evaluate with care as part of an overall security strategy as all of the above are mitigations but not guarantees.

Debug Mode

When mimalloc is built using debug mode, various checks are done at runtime to catch development errors.

Overriding Standard Malloc

Overriding the standard malloc (and new) can be done either dynamically or statically.

Dynamic override

This is the recommended way to override the standard malloc interface.

Dynamic Override on Linux, BSD

On these ELF-based 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

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_SHOW_STATS=1 LD_PRELOAD=/usr/lib/libmimalloc-debug.so myprogram

Dynamic Override on MacOS

On macOS we can also preload the mimalloc shared library so all calls to the standard malloc interface are resolved to the mimalloc library.

> env DYLD_INSERT_LIBRARIES=/usr/lib/libmimalloc.dylib myprogram

Note that certain security restrictions may apply when doing this from the shell.

Dynamic Override on Windows

Dynamically overriding on mimalloc on Windows is robust and has the particular advantage to be able to redirect all malloc/free calls that go through the (dynamic) C runtime allocator, including those from other DLL's or libraries. As it intercepts all allocation calls on a low level, it can be used reliably on large programs that include other 3rd party components. There are four requirements to make the overriding work robustly:

  1. Use the C-runtime library as a DLL (using the /MD or /MDd switch).
  2. Link your program explicitly with mimalloc-override.dll library. To ensure the mimalloc-override.dll is loaded at run-time it is easiest to insert some call to the mimalloc API in the main function, like mi_version() (or use the /INCLUDE:mi_version switch on the linker). See the mimalloc-override-test project for an example on how to use this.
  3. The mimalloc-redirect.dll (or mimalloc-redirect32.dll) must be put in the same folder as the main mimalloc-override.dll at runtime (as it is a dependency of that DLL). The redirection DLL ensures that all calls to the C runtime malloc API get redirected to mimalloc functions (which reside in mimalloc-override.dll).
  4. Ensure the mimalloc-override.dll comes as early as possible in the import list of the final executable (so it can intercept all potential allocations).

For best performance on Windows with C++, it is also recommended to also override the new/delete operations (by including mimalloc-new-delete.h a single(!) source file in your project).

The environment variable MIMALLOC_DISABLE_REDIRECT=1 can be used to disable dynamic overriding at run-time. Use MIMALLOC_VERBOSE=1 to check if mimalloc was successfully redirected.

We cannot always re-link an executable with mimalloc-override.dll, and similarly, we cannot always ensure the the DLL comes first in the import table of the final executable. In many cases though we can patch existing executables without any recompilation if they are linked with the dynamic C runtime (ucrtbase.dll) -- just put the mimalloc-override.dll into the import table (and put mimalloc-redirect.dll in the same folder) Such patching can be done for example with CFF Explorer or the minject program.

Static override

On Unix-like 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.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.o  myfile1.c ...

Another way to override statically that works on all platforms, is to link statically to mimalloc (as shown in the introduction) and include a header file in each source file that re-defines malloc etc. to mi_malloc. This is provided by mimalloc-override.h. This only works reliably though if all sources are under your control or otherwise mixing of pointers from different heaps may occur!

Tools

Generally, we recommend using the standard allocator with memory tracking tools, but mimalloc can also be build to support the address sanitizer or the excellent Valgrind tool. Moreover, it can be build to support Windows event tracing (ETW). This has a small performance overhead but does allow detecting memory leaks and byte-precise buffer overflows directly on final executables. See also the test/test-wrong.c file to test with various tools.

Valgrind

To build with valgrind support, use the MI_TRACK_VALGRIND=ON cmake option:

> cmake ../.. -DMI_TRACK_VALGRIND=ON

This can also be combined with secure mode or debug mode. You can then run your programs directly under valgrind:

> valgrind <myprogram>

If you rely on overriding malloc/free by mimalloc (instead of using the mi_malloc/mi_free API directly), you also need to tell valgrind to not intercept those calls itself, and use:

> MIMALLOC_SHOW_STATS=1 valgrind  --soname-synonyms=somalloc=*mimalloc* -- <myprogram>

By setting the MIMALLOC_SHOW_STATS environment variable you can check that mimalloc is indeed used and not the standard allocator. Even though the Valgrind option is called --soname-synonyms, this also works when overriding with a static library or object file. Unfortunately, it is not possible to dynamically override mimalloc using LD_PRELOAD together with valgrind. See also the test/test-wrong.c file to test with valgrind.

Valgrind support is in its initial development -- please report any issues.

ASAN

To build with the address sanitizer, use the -DMI_TRACK_ASAN=ON cmake option:

> cmake ../.. -DMI_TRACK_ASAN=ON

This can also be combined with secure mode or debug mode. You can then run your programs as:'

> ASAN_OPTIONS=verbosity=1 <myprogram>

When you link a program with an address sanitizer build of mimalloc, you should generally compile that program too with the address sanitizer enabled. For example, assuming you build mimalloc in out/debug:

clang -g -o test-wrong -Iinclude test/test-wrong.c out/debug/libmimalloc-asan-debug.a -lpthread -fsanitize=address -fsanitize-recover=address

Since the address sanitizer redirects the standard allocation functions, on some platforms (macOSX for example) it is required to compile mimalloc with -DMI_OVERRIDE=OFF. Adress sanitizer support is in its initial development -- please report any issues.

ETW

Event tracing for Windows (ETW) provides a high performance way to capture all allocations though mimalloc and analyze them later. To build with ETW support, use the -DMI_TRACK_ETW=ON cmake option.

You can then capture an allocation trace using the Windows performance recorder (WPR), using the src/prim/windows/etw-mimalloc.wprp profile. In an admin prompt, you can use:

> wpr -start src\prim\windows\etw-mimalloc.wprp -filemode
> <my_mimalloc_program>
> wpr -stop <my_mimalloc_program>.etl

and then open <my_mimalloc_program>.etl in the Windows Performance Analyzer (WPA), or use a tool like TraceControl that is specialized for analyzing mimalloc traces.

Performance

Last update: 2021-01-30

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 benchmark suite, mimalloc outperforms other leading allocators (jemalloc, tcmalloc, Hoard, etc), and has a similar memory footprint. A nice property is that it does consistently well over the wide range of benchmarks.

General memory allocators are interesting as there exists no algorithm that is 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 (too much) underperformance in less common situations.

As always, interpret these results with care since some benchmarks test synthetic or uncommon situations that may never apply to your workloads. For example, most allocators do not do well on xmalloc-testN but that includes even the best industrial allocators like jemalloc and tcmalloc that are used in some of the world's largest systems (like Chrome or FreeBSD).

Also, the benchmarks here do not measure the behaviour on very large and long-running server workloads, or worst-case latencies of allocation. Much work has gone into mimalloc to work well on such workloads (for example, to reduce virtual memory fragmentation on long-running services) but such optimizations are not always reflected in the current benchmark suite.

We show here only an overview -- for more specific details and further benchmarks we refer to the technical report. The benchmark suite is automated and available separately as mimalloc-bench.

Benchmark Results on a 16-core AMD 5950x (Zen3)

Testing on the 16-core AMD 5950x processor at 3.4Ghz (4.9Ghz boost), with with 32GiB memory at 3600Mhz, running Ubuntu 20.04 with glibc 2.31 and GCC 9.3.0.

We measure three versions of mimalloc: the main version mi (tag:v1.7.0), the new v2.0 beta version as xmi (tag:v2.0.0), and the main version in secure mode as smi (tag:v1.7.0).

The other allocators are Google's tcmalloc (tc, tag:gperftools-2.8.1) used in Chrome, Facebook's jemalloc (je, tag:5.2.1) by Jason Evans used in Firefox and FreeBSD, the Intel thread building blocks allocator (tbb, tag:v2020.3), rpmalloc (rp,tag:1.4.1) by Mattias Jansson, the original scalable Hoard (git:d880f72) allocator by Emery Berger [1], the memory compacting Mesh (git:67ff31a) allocator by Bobby Powers et al [8], and finally the default system allocator (glibc, 2.31) (based on PtMalloc2).

Any benchmarks ending in N run on all 32 logical cores in parallel. Results are averaged over 10 runs and reported relative to mimalloc (where 1.2 means it took 1.2× longer to run). The legend also contains the overall relative score between the allocators where 100 points is the maximum if an allocator is fastest on all benchmarks.

The single threaded cfrac benchmark by Dave Barrett is an implementation of continued fraction factorization which uses many small short-lived allocations. All allocators do well on such common usage, where mimalloc is just a tad faster than tcmalloc and jemalloc.

The leanN program is interesting as a large realistic and concurrent workload of the Lean theorem prover compiling its own standard library, and there is a 13% speedup over tcmalloc. This is quite significant: if Lean spends 20% of its time in the allocator that means that mimalloc is 1.6× 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 single threaded redis benchmark again show that most allocators do well on such workloads.

The larsonN server benchmark by Larson and Krishnan [2] allocates and frees between threads. They observed this behavior (which they call bleeding) in actual server applications, and the benchmark simulates this. Here, mimalloc is quite a bit faster than tcmalloc and jemalloc probably due to the object migration between different threads.

The mstressN workload performs many allocations and re-allocations, and migrates objects between threads (as in larsonN). However, it also creates and destroys the N worker threads a few times keeping some objects alive beyond the life time of the allocating thread. We observed this behavior in many larger server applications.

The rptestN benchmark by Mattias Jansson is a allocator test originally designed for rpmalloc, and tries to simulate realistic allocation patterns over multiple threads. Here the differences between allocators become more apparent.

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.

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.5× faster than jemalloc). We cannot explain this well but believe it is caused in part by the "reverse" free-ing pattern in sh6bench. The sh8bench is a variation with object migration between threads; whereas tcmalloc did well on sh6bench, the addition of object migration causes it to be 10× 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 -- they observed this pattern in larger server applications. Here we see that the mimalloc technique of having non-contended sharded thread free lists pays off as it outperforms others by a very large margin. Only rpmalloc, tbb, and glibc also scale well on this benchmark.

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 can cause large run-time differences. 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 the tbb, rpmalloc and mesh allocators also avoid the cache line sharing completely, while Hoard and glibc seem to mitigate the effects. Kukanov and Voss [7] describe in detail how the design of tbb avoids the false cache line sharing.

On a 36-core Intel Xeon

For completeness, here are the results on a big Amazon c5.18xlarge instance consisting of a 2×18-core Intel Xeon (Cascade Lake) at 3.4GHz (boost 3.5GHz) with 144GiB ECC memory, running Ubuntu 20.04 with glibc 2.31, GCC 9.3.0, and Clang 10.0.0. This time, the mimalloc allocators (mi, xmi, and smi) were compiled with the Clang compiler instead of GCC. The results are similar to the AMD results but it is interesting to see the differences in the larsonN, mstressN, and xmalloc-testN benchmarks.

Peak Working Set

The following figure shows the peak working set (rss) of the allocators on the benchmarks (on the c5.18xlarge instance).

Note that the xmalloc-testN memory usage should be disregarded as it allocates more the faster the program runs. Similarly, memory usage of larsonN, mstressN, rptestN and sh8bench can vary depending on scheduling and speed. Nevertheless, we hope to improve the memory usage on mstressN and rptestN (just as cfrac, larsonN and sh8bench have a small working set which skews the results).

References

Contributing

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.

Older Release Notes