Source Browser ?

1
2
3
4[](https://dev.azure.com/Daan0324/mimalloc/_build?definitionId=1&_a=summary)
5
6# mimalloc
7
8 
9
10mimalloc (pronounced "me-malloc")
11is a general purpose allocator with excellent [performance](#performance) characteristics.
12Initially developed by Daan Leijen for the runtime systems of the
13[Koka](https://koka-lang.github.io) and [Lean](https://github.com/leanprover/lean) languages.
14
15Latest release tag: `v2.1.7` (2024-05-21).  
16Latest v1 tag: `v1.8.7` (2024-05-21).
17
18mimalloc is a drop-in replacement for `malloc` and can be used in other programs
19without code changes, for example, on dynamically linked ELF-based systems (Linux, BSD, etc.) you can use it as:
20```
21> LD_PRELOAD=/usr/lib/libmimalloc.so  myprogram
22```
23It also includes a robust way to override the default allocator in [Windows](#override_on_windows). Notable aspects of the design include:
24
25- __small and consistent__: the library is about 8k LOC using simple and
26  consistent data structures. This makes it very suitable
27  to integrate and adapt in other projects. For runtime systems it
28  provides hooks for a monotonic _heartbeat_ and deferred freeing (for
29  bounded worst-case times with reference counting).
30  Partly due to its simplicity, mimalloc has been ported to many systems (Windows, macOS,
31  Linux, WASM, various BSD's, Haiku, MUSL, etc) and has excellent support for dynamic overriding.
32  At the same time, it is an industrial strength allocator that runs (very) large scale
33  distributed services on thousands of machines with excellent worst case latencies.
34- __free list sharding__: instead of one big free list (per size class) we have
35  many smaller lists per "mimalloc page" which reduces fragmentation and
36  increases locality --
37  things that are allocated close in time get allocated close in memory.
38  (A mimalloc page contains blocks of one size class and is usually 64KiB on a 64-bit system).
39- __free list multi-sharding__: the big idea! Not only do we shard the free list
40  per mimalloc page, but for each page we have multiple free lists. In particular, there
41  is one list for thread-local `free` operations, and another one for concurrent `free`
42  operations. Free-ing from another thread can now be a single CAS without needing
43  sophisticated coordination between threads. Since there will be
44  thousands of separate free lists, contention is naturally distributed over the heap,
45  and the chance of contending on a single location will be low -- this is quite
46  similar to randomized algorithms like skip lists where adding
47  a random oracle removes the need for a more complex algorithm.
48- __eager page purging__: when a "page" becomes empty (with increased chance
49  due to free list sharding) the memory is marked to the OS as unused (reset or decommitted)
50  reducing (real) memory pressure and fragmentation, especially in long running
51  programs.
52- __secure__: _mimalloc_ can be built in secure mode, adding guard pages,
53  randomized allocation, encrypted free lists, etc. to protect against various
54  heap vulnerabilities. The performance penalty is usually around 10% on average
55  over our benchmarks.
56- __first-class heaps__: efficiently create and use multiple heaps to allocate across different regions.
57  A heap can be destroyed at once instead of deallocating each object separately.
58- __bounded__: it does not suffer from _blowup_ \[1\], has bounded worst-case allocation
59  times (_wcat_) (upto OS primitives), bounded space overhead (~0.2% meta-data, with low
60  internal fragmentation), and has no internal points of contention using only atomic operations.
61- __fast__: In our benchmarks (see [below](#performance)),
62  _mimalloc_ outperforms other leading allocators (_jemalloc_, _tcmalloc_, _Hoard_, etc),
63  and often uses less memory. A nice property is that it does consistently well over a wide range
64  of benchmarks. There is also good huge OS page support for larger server programs.
65
66The [documentation](https://microsoft.github.io/mimalloc) gives a full overview of the API.
67You can read more on the design of _mimalloc_ in the [technical report](https://www.microsoft.com/en-us/research/publication/mimalloc-free-list-sharding-in-action) which also has detailed benchmark results.
68
69Enjoy!
70
71### Branches
72
73* `master`: latest stable release (based on `dev-slice`).
74* `dev`: development branch for mimalloc v1. Use this branch for submitting PR's.
75* `dev-slice`: development branch for mimalloc v2. This branch is downstream of `dev` (and is essentially equal to `dev` except for
76`src/segment.c`)
77
78### Releases
79
80Note: the `v2.x` version has a different algorithm for managing internal mimalloc pages (as slices) that tends to use reduce 
81memory usage
82  and fragmentation compared to mimalloc `v1.x` (especially for large workloads). Should otherwise have similar performance
83  (see [below](#performance)); please report if you observe any significant performance regression.
84
85* 2024-05-21, `v1.8.7`, `v2.1.7`: Fix build issues on less common platforms. Started upstreaming patches
86  from the CPython [integration](https://github.com/python/cpython/issues/113141#issuecomment-2119255217). Upstream `vcpkg` patches.
87* 2024-05-13, `v1.8.6`, `v2.1.6`: Fix build errors on various (older) platforms. Refactored aligned allocation.
88* 2024-04-22, `v1.8.4`, `v2.1.4`: Fixes various bugs and build issues. Add `MI_LIBC_MUSL` cmake flag for musl builds.
89  Free-ing code is refactored into a separate module (`free.c`). Mimalloc page info is simplified with the block size
90  directly available (and new `block_size_shift` to improve aligned block free-ing). 
91  New approach to collection of abandoned segments: When
92  a thread terminates the segments it owns are abandoned (containing still live objects) and these can be
93  reclaimed by other threads. We no longer use a list of abandoned segments but this is now done using bitmaps in arena's 
94  which is more concurrent (and more aggressive). Abandoned memory can now also be reclaimed if a thread frees an object in
95  an abandoned page (which can be disabled using `mi_option_abandoned_reclaim_on_free`). The option `mi_option_max_segment_reclaim`
96  gives a maximum percentage of abandoned segments that can be reclaimed per try (=10%).
97
98* 2023-04-24, `v1.8.2`, `v2.1.2`: Fixes build issues on freeBSD, musl, and C17 (UE 5.1.1). Reduce code size/complexity 
99  by removing regions and segment-cache's and only use arenas with improved memory purging -- this may improve memory
100  usage as well for larger services. Renamed options for consistency. Improved Valgrind and ASAN checking.
101  
102* 2023-04-03, `v1.8.1`, `v2.1.1`: Fixes build issues on some platforms.
103
104* 2023-03-29, `v1.8.0`, `v2.1.0`: Improved support dynamic overriding on Windows 11. Improved tracing precision
105  with [asan](#asan) and [Valgrind](#valgrind), and added Windows event tracing [ETW](#ETW) (contributed by Xinglong He). Created an OS
106  abstraction layer to make it easier to port and separate platform dependent code (in `src/prim`). Fixed C++ STL compilation on older Microsoft C++ compilers, and various small bug fixes.
107
108* 2022-12-23, `v1.7.9`, `v2.0.9`: Supports building with [asan](#asan) and improved [Valgrind](#valgrind) support.
109  Support arbitrary large alignments (in particular for `std::pmr` pools). 
110  Added C++ STL allocators attached to a specific heap (thanks @vmarkovtsev). 
111  Heap walks now visit all object (including huge objects). Support Windows nano server containers (by Johannes Schindelin,@dscho). Various small bug fixes.
112
113* 2022-11-03, `v1.7.7`, `v2.0.7`: Initial support for [Valgrind](#valgrind) for leak testing and heap block overflow
114  detection. Initial
115  support for attaching heaps to a speficic memory area (only in v2). Fix `realloc` behavior for zero size blocks, remove restriction to integral multiple of the alignment in `alloc_align`, improved aligned allocation performance, reduced contention with many threads on few processors (thank you @dposluns!), vs2022 support, support `pkg-config`, .
116
117* 2022-04-14, `v1.7.6`, `v2.0.6`: fix fallback path for aligned OS allocation on Windows, improve Windows aligned allocation
118  even when compiling with older SDK's, fix dynamic overriding on macOS Monterey, fix MSVC C++ dynamic overriding, fix
119  warnings under Clang 14, improve performance if many OS threads are created and destroyed, fix statistics for large object
120  allocations, using MIMALLOC_VERBOSE=1 has no maximum on the number of error messages, various small fixes.
121
122* 2022-02-14, `v1.7.5`, `v2.0.5` (alpha): fix malloc override on
123  Windows 11, fix compilation with musl, potentially reduced
124  committed memory, add `bin/minject` for Windows,
125  improved wasm support, faster aligned allocation,
126  various small fixes.
127
128* [Older release notes](#older-release-notes)
129
130Special thanks to:
131
132* [David Carlier](https://devnexen.blogspot.com/) (@devnexen) for his many contributions, and making
133  mimalloc work better on many less common operating systems, like Haiku, Dragonfly, etc.
134* Mary Feofanova (@mary3000), Evgeniy Moiseenko, and Manuel Pöter (@mpoeter) for making mimalloc TSAN checkable, and finding
135  memory model bugs using the [genMC] model checker.
136* Weipeng Liu (@pongba), Zhuowei Li, Junhua Wang, and Jakub Szymanski, for their early support of mimalloc and deployment
137  at large scale services, leading to many improvements in the mimalloc algorithms for large workloads.
138* Jason Gibson (@jasongibson) for exhaustive testing on large scale workloads and server environments, and finding complex bugs
139  in (early versions of) `mimalloc`.
140* Manuel Pöter (@mpoeter) and Sam Gross(@colesbury) for finding an ABA concurrency issue in abandoned segment reclamation. Sam also created the [no GIL](https://github.com/colesbury/nogil) Python fork which
141  uses mimalloc internally.
142
143
144[genMC]: https://plv.mpi-sws.org/genmc/
145
146### Usage
147
148mimalloc is used in various large scale low-latency services and programs, for example:
149
150
151
152
153
154
155
156
157# Building
158
159## Windows
160
161Open `ide/vs2022/mimalloc.sln` in Visual Studio 2022 and build.
162The `mimalloc` project builds a static library (in `out/msvc-x64`), while the
163`mimalloc-override` project builds a DLL for overriding malloc
164in the entire program.
165
166## macOS, Linux, BSD, etc.
167
168We use [`cmake`](https://cmake.org)1 as the build system:
169
170```
171> mkdir -p out/release
172> cd out/release
173> cmake ../..
174> make
175```
176This builds the library as a shared (dynamic)
177library (`.so` or `.dylib`), a static library (`.a`), and
178as a single object file (`.o`).
179
180`> sudo make install` (install the library and header files in `/usr/local/lib`  and `/usr/local/include`)
181
182You can build the debug version which does many internal checks and
183maintains detailed statistics as:
184
185```
186> mkdir -p out/debug
187> cd out/debug
188> cmake -DCMAKE_BUILD_TYPE=Debug ../..
189> make
190```
191This will name the shared library as `libmimalloc-debug.so`.
192
193Finally, you can build a _secure_ version that uses guard pages, encrypted
194free lists, etc., as:
195```
196> mkdir -p out/secure
197> cd out/secure
198> cmake -DMI_SECURE=ON ../..
199> make
200```
201This will name the shared library as `libmimalloc-secure.so`.
202Use `ccmake`2 instead of `cmake`
203to see and customize all the available build options.
204
205Notes:
2061. Install CMake: `sudo apt-get install cmake`
2072. Install CCMake: `sudo apt-get install cmake-curses-gui`
208
209
210## Single source
211
212You can also directly build the single `src/static.c` file as part of your project without
213needing `cmake` at all. Make sure to also add the mimalloc `include` directory to the include path.
214
215
216# Using the library
217
218The preferred usage is including ``, linking with
219the shared- or static library, and using the `mi_malloc` API exclusively for allocation. For example,
220```
221> gcc -o myprogram -lmimalloc myfile.c
222```
223
224mimalloc uses only safe OS calls (`mmap` and `VirtualAlloc`) and can co-exist
225with other allocators linked to the same program.
226If you use `cmake`, you can simply use:
227```
228find_package(mimalloc 1.4 REQUIRED)
229```
230in your `CMakeLists.txt` to find a locally installed mimalloc. Then use either:
231```
232target_link_libraries(myapp PUBLIC mimalloc)
233```
234to link with the shared (dynamic) library, or:
235```
236target_link_libraries(myapp PUBLIC mimalloc-static)
237```
238to link with the static library. See `test\CMakeLists.txt` for an example.
239
240For best performance in C++ programs, it is also recommended to override the
241global `new` and `delete` operators. For convenience, mimalloc provides
242[`mimalloc-new-delete.h`](https://github.com/microsoft/mimalloc/blob/master/include/mimalloc-new-delete.h) which does this for you -- just include it in a single(!) source file in your project.
243In C++, mimalloc also provides the `mi_stl_allocator` struct which implements the `std::allocator`
244interface.
245
246You can pass environment variables to print verbose messages (`MIMALLOC_VERBOSE=1`)
247and statistics (`MIMALLOC_SHOW_STATS=1`) (in the debug version):
248```
249> env MIMALLOC_SHOW_STATS=1 ./cfrac 175451865205073170563711388363
250
251175451865205073170563711388363 = 374456281610909315237213 * 468551
252
253heap stats:     peak      total      freed       unit
254normal   2:    16.4 kb    17.5 mb    17.5 mb      16 b   ok
255normal   3:    16.3 kb    15.2 mb    15.2 mb      24 b   ok
256normal   4:      64 b      4.6 kb     4.6 kb      32 b   ok
257normal   5:      80 b    118.4 kb   118.4 kb      40 b   ok
258normal   6:      48 b       48 b       48 b       48 b   ok
259normal  17:     960 b      960 b      960 b      320 b   ok
260
261heap stats:     peak      total      freed       unit
262    normal:    33.9 kb    32.8 mb    32.8 mb       1 b   ok
263      huge:       0 b        0 b        0 b        1 b   ok
264     total:    33.9 kb    32.8 mb    32.8 mb       1 b   ok
265malloc requested:         32.8 mb
266
267 committed:    58.2 kb    58.2 kb    58.2 kb       1 b   ok
268  reserved:     2.0 mb     2.0 mb     2.0 mb       1 b   ok
269     reset:       0 b        0 b        0 b        1 b   ok
270  segments:       1          1          1
271-abandoned:       0
272     pages:       6          6          6
273-abandoned:       0
274     mmaps:       3
275 mmap fast:       0
276 mmap slow:       1
277   threads:       0
278   elapsed:     2.022s
279   process: user: 1.781s, system: 0.016s, faults: 756, reclaims: 0, rss: 2.7 mb
280```
281
282The above model of using the `mi_` prefixed API is not always possible
283though in existing programs that already use the standard malloc interface,
284and another option is to override the standard malloc interface
285completely and redirect all calls to the _mimalloc_ library instead .
286
287## Environment Options
288
289You can set further options either programmatically (using [`mi_option_set`](https://microsoft.github.io/mimalloc/group__options.html)), or via environment variables:
290
291- `MIMALLOC_SHOW_STATS=1`: show statistics when the program terminates.
292- `MIMALLOC_VERBOSE=1`: show verbose messages.
293- `MIMALLOC_SHOW_ERRORS=1`: show error and warning messages.
294
295Advanced options:
296
297- `MIMALLOC_ARENA_EAGER_COMMIT=2`: turns on eager commit for the large arenas (usually 1GiB) from which mimalloc 
298   allocates segments and pages. Set this to 2 (default) to 
299   only enable this on overcommit systems (e.g. Linux). Set this to 1 to enable explicitly on other systems 
300   as well (like Windows or macOS) which may improve performance (as the whole arena is committed at once). 
301   Note that eager commit only increases the commit but not the actual the peak resident set 
302   (rss) so it is generally ok to enable this.
303- `MIMALLOC_PURGE_DELAY=N`: the delay in `N` milli-seconds (by default `10`) after which mimalloc will purge 
304   OS pages that are not in use. This signals to the OS that the underlying physical memory can be reused which 
305   can reduce memory fragmentation especially in long running (server) programs. Setting `N` to `0` purges immediately when
306   a page becomes unused which can improve memory usage but also decreases performance. Setting `N` to a higher
307   value like `100` can improve performance (sometimes by a lot) at the cost of potentially using more memory at times.
308   Setting it to `-1` disables purging completely.
309- `MIMALLOC_PURGE_DECOMMITS=1`: By default "purging" memory means unused memory is decommitted (`MEM_DECOMMIT` on Windows,
310   `MADV_DONTNEED` (which decresease rss immediately) on `mmap` systems). Set this to 0 to instead "reset" unused
311   memory on a purge (`MEM_RESET` on Windows, generally `MADV_FREE` (which does not decrease rss immediately) on `mmap` systems).
312   Mimalloc generally does not "free" OS memory but only "purges" OS memory, in other words, it tries to keep virtual 
313   address ranges and decommits within those ranges (to make the underlying physical memory available to other processes).
314
315Further options for large workloads and services:
316
317- `MIMALLOC_USE_NUMA_NODES=N`: pretend there are at most `N` NUMA nodes. If not set, the actual NUMA nodes are detected
318   at runtime. Setting `N` to 1 may avoid problems in some virtual environments. Also, setting it to a lower number than
319   the actual NUMA nodes is fine and will only cause threads to potentially allocate more memory across actual NUMA
320   nodes (but this can happen in any case as NUMA local allocation is always a best effort but not guaranteed).
321- `MIMALLOC_ALLOW_LARGE_OS_PAGES=1`: use large OS pages (2 or 4MiB) when available; for some workloads this can significantly
322   improve performance. When this option is disabled, it also disables transparent huge pages (THP) for the process 
323   (on Linux and Android). Use `MIMALLOC_VERBOSE` to check if the large OS pages are enabled -- usually one needs
324   to explicitly give permissions for large OS pages (as on [Windows][windows-huge] and [Linux][linux-huge]). However, sometimes
325   the OS is very slow to reserve contiguous physical memory for large OS pages so use with care on systems that
326   can have fragmented memory (for that reason, we generally recommend to use `MIMALLOC_RESERVE_HUGE_OS_PAGES` instead whenever possible).   
327- `MIMALLOC_RESERVE_HUGE_OS_PAGES=N`: where `N` is the number of 1GiB _huge_ OS pages. This reserves the huge pages at
328   startup and sometimes this can give a large (latency) performance improvement on big workloads.
329   Usually it is better to not use `MIMALLOC_ALLOW_LARGE_OS_PAGES=1` in combination with this setting. Just like large 
330   OS pages, use with care as reserving
331   contiguous physical memory can take a long time when memory is fragmented (but reserving the huge pages is done at
332   startup only once).
333   Note that we usually need to explicitly give permission for huge OS pages (as on [Windows][windows-huge] and [Linux][linux-huge])).
334   With huge OS pages, it may be beneficial to set the setting
335   `MIMALLOC_EAGER_COMMIT_DELAY=N` (`N` is 1 by default) to delay the initial `N` segments (of 4MiB)
336   of a thread to not allocate in the huge OS pages; this prevents threads that are short lived
337   and allocate just a little to take up space in the huge OS page area (which cannot be purged as huge OS pages are pinned
338   to physical memory).
339   The huge pages are usually allocated evenly among NUMA nodes.
340   We can use `MIMALLOC_RESERVE_HUGE_OS_PAGES_AT=N` where `N` is the numa node (starting at 0) to allocate all
341   the huge pages at a specific numa node instead.
342
343Use caution when using `fork` in combination with either large or huge OS pages: on a fork, the OS uses copy-on-write
344for all pages in the original process including the huge OS pages. When any memory is now written in that area, the
345OS will copy the entire 1GiB huge page (or 2MiB large page) which can cause the memory usage to grow in large increments.
346
347[linux-huge]: https://access.redhat.com/documentation/en-us/red_hat_enterprise_linux/5/html/tuning_and_optimizing_red_hat_enterprise_linux_for_oracle_9i_and_10g_databases/sect-oracle_9i_and_10g_tuning_guide-large_memory_optimization_big_pages_and_huge_pages-configuring_huge_pages_in_red_hat_enterprise_linux_4_or_5
348[windows-huge]: https://docs.microsoft.com/en-us/sql/database-engine/configure-windows/enable-the-lock-pages-in-memory-option-windows?view=sql-server-2017
349
350## Secure Mode
351
352_mimalloc_ can be build in secure mode by using the `-DMI_SECURE=ON` flags in `cmake`. This build enables various mitigations
353to make mimalloc more robust against exploits. In particular:
354
355- All internal mimalloc pages are surrounded by guard pages and the heap metadata is behind a guard page as well (so a buffer overflow
356  exploit cannot reach into the metadata).
357- All free list pointers are
358  [encoded](https://github.com/microsoft/mimalloc/blob/783e3377f79ee82af43a0793910a9f2d01ac7863/include/mimalloc-internal.h#L396)
359  with per-page keys which is used both to prevent overwrites with a known pointer, as well as to detect heap corruption.
360- Double free's are detected (and ignored).
361- The free lists are initialized in a random order and allocation randomly chooses between extension and reuse within a page to
362  mitigate against attacks that rely on a predicable allocation order. Similarly, the larger heap blocks allocated by mimalloc
363  from the OS are also address randomized.
364
365As always, evaluate with care as part of an overall security strategy as all of the above are mitigations but not guarantees.
366
367## Debug Mode
368
369When _mimalloc_ is built using debug mode, various checks are done at runtime to catch development errors.
370
371- Statistics are maintained in detail for each object size. They can be shown using `MIMALLOC_SHOW_STATS=1` at runtime.
372- All objects have padding at the end to detect (byte precise) heap block overflows.
373- Double free's, and freeing invalid heap pointers are detected.
374- Corrupted free-lists and some forms of use-after-free are detected.
375
376
377# Overriding Standard Malloc
378
379Overriding the standard `malloc` (and `new`) can be done either _dynamically_ or _statically_.
380
381## Dynamic override
382
383This is the recommended way to override the standard malloc interface.
384
385### Dynamic Override on Linux, BSD
386
387On these ELF-based systems we preload the mimalloc shared
388library so all calls to the standard `malloc` interface are
389resolved to the _mimalloc_ library.
390```
391> env LD_PRELOAD=/usr/lib/libmimalloc.so myprogram
392```
393
394You can set extra environment variables to check that mimalloc is running,
395like:
396```
397> env MIMALLOC_VERBOSE=1 LD_PRELOAD=/usr/lib/libmimalloc.so myprogram
398```
399or run with the debug version to get detailed statistics:
400```
401> env MIMALLOC_SHOW_STATS=1 LD_PRELOAD=/usr/lib/libmimalloc-debug.so myprogram
402```
403
404### Dynamic Override on MacOS
405
406On macOS we can also preload the mimalloc shared
407library so all calls to the standard `malloc` interface are
408resolved to the _mimalloc_ library.
409```
410> env DYLD_INSERT_LIBRARIES=/usr/lib/libmimalloc.dylib myprogram
411```
412
413Note that certain security restrictions may apply when doing this from
414the [shell](https://stackoverflow.com/questions/43941322/dyld-insert-libraries-ignored-when-calling-application-through-bash).
415
416
417### Dynamic Override on Windows
418
419Dynamically overriding on mimalloc on Windows 
420is robust and has the particular advantage to be able to redirect all malloc/free calls that go through
421the (dynamic) C runtime allocator, including those from other DLL's or libraries.
422As it intercepts all allocation calls on a low level, it can be used reliably 
423on large programs that include other 3rd party components.
424There are four requirements to make the overriding work robustly:
425
4261. Use the C-runtime library as a DLL (using the `/MD` or `/MDd` switch).
4272. Link your program explicitly with `mimalloc-override.dll` library.
428   To ensure the `mimalloc-override.dll` is loaded at run-time it is easiest to insert some
429    call to the mimalloc API in the `main` function, like `mi_version()`
430    (or use the `/INCLUDE:mi_version` switch on the linker). See the `mimalloc-override-test` project
431    for an example on how to use this. 
4323. The [`mimalloc-redirect.dll`](bin) (or `mimalloc-redirect32.dll`) must be put
433   in the same folder as the main `mimalloc-override.dll` at runtime (as it is a dependency of that DLL).
434   The redirection DLL ensures that all calls to the C runtime malloc API get redirected to
435   mimalloc functions (which reside in `mimalloc-override.dll`).
4364. Ensure the `mimalloc-override.dll` comes as early as possible in the import
437   list of the final executable (so it can intercept all potential allocations).
438
439For best performance on Windows with C++, it
440is also recommended to also override the `new`/`delete` operations (by including
441[`mimalloc-new-delete.h`](include/mimalloc-new-delete.h) 
442a single(!) source file in your project).
443
444The environment variable `MIMALLOC_DISABLE_REDIRECT=1` can be used to disable dynamic
445overriding at run-time. Use `MIMALLOC_VERBOSE=1` to check if mimalloc was successfully redirected.
446
447We cannot always re-link an executable with `mimalloc-override.dll`, and similarly, we cannot always
448ensure the the DLL comes first in the import table of the final executable.
449In many cases though we can patch existing executables without any recompilation
450if they are linked with the dynamic C runtime (`ucrtbase.dll`) -- just put the `mimalloc-override.dll`
451into the import table (and put `mimalloc-redirect.dll` in the same folder)
452Such patching can be done for example with [CFF Explorer](https://ntcore.com/?page_id=388) or
453the [`minject`](bin) program.
454
455## Static override
456
457On Unix-like systems, you can also statically link with _mimalloc_ to override the standard
458malloc interface. The recommended way is to link the final program with the
459_mimalloc_ single object file (`mimalloc.o`). We use
460an object file instead of a library file as linkers give preference to
461that over archives to resolve symbols. To ensure that the standard
462malloc interface resolves to the _mimalloc_ library, link it as the first
463object file. For example:
464```
465> gcc -o myprogram mimalloc.o  myfile1.c ...
466```
467
468Another way to override statically that works on all platforms, is to
469link statically to mimalloc (as shown in the introduction) and include a
470header file in each source file that re-defines `malloc` etc. to `mi_malloc`.
471This is provided by [`mimalloc-override.h`](https://github.com/microsoft/mimalloc/blob/master/include/mimalloc-override.h). This only works reliably though if all sources are
472under your control or otherwise mixing of pointers from different heaps may occur!
473
474
475# Tools
476
477Generally, we recommend using the standard allocator with memory tracking tools, but mimalloc
478can also be build to support the [address sanitizer][asan] or the excellent [Valgrind] tool. 
479Moreover, it can be build to support Windows event tracing ([ETW]).
480This has a small performance overhead but does allow detecting memory leaks and byte-precise 
481buffer overflows directly on final executables. See also the `test/test-wrong.c` file to test with various tools.
482
483## Valgrind
484
485To build with [valgrind] support, use the `MI_TRACK_VALGRIND=ON` cmake option:
486
487```
488> cmake ../.. -DMI_TRACK_VALGRIND=ON
489```
490
491This can also be combined with secure mode or debug mode.
492You can then run your programs directly under valgrind:
493
494```
495> valgrind 
496```
497
498If you rely on overriding `malloc`/`free` by mimalloc (instead of using the `mi_malloc`/`mi_free` API directly),
499you also need to tell `valgrind` to not intercept those calls itself, and use:
500
501```
502> MIMALLOC_SHOW_STATS=1 valgrind  --soname-synonyms=somalloc=*mimalloc* -- 
503```
504
505By setting the `MIMALLOC_SHOW_STATS` environment variable you can check that mimalloc is indeed
506used and not the standard allocator. Even though the [Valgrind option][valgrind-soname]
507is called `--soname-synonyms`, this also
508works when overriding with a static library or object file. Unfortunately, it is not possible to
509dynamically override mimalloc using `LD_PRELOAD` together with `valgrind`.
510See also the `test/test-wrong.c` file to test with `valgrind`.
511
512Valgrind support is in its initial development -- please report any issues.
513
514[Valgrind]: https://valgrind.org/
515[valgrind-soname]: https://valgrind.org/docs/manual/manual-core.html#opt.soname-synonyms
516
517## ASAN
518
519To build with the address sanitizer, use the `-DMI_TRACK_ASAN=ON` cmake option:
520
521```
522> cmake ../.. -DMI_TRACK_ASAN=ON
523```
524
525This can also be combined with secure mode or debug mode. 
526You can then run your programs as:'
527
528```
529> ASAN_OPTIONS=verbosity=1 
530```
531
532When you link a program with an address sanitizer build of mimalloc, you should
533generally compile that program too with the address sanitizer enabled. 
534For example, assuming you build mimalloc in `out/debug`:
535
536```
537clang -g -o test-wrong -Iinclude test/test-wrong.c out/debug/libmimalloc-asan-debug.a -lpthread -fsanitize=address -fsanitize-recover=address
538```
539
540Since the address sanitizer redirects the standard allocation functions, on some platforms (macOSX for example)
541it is required to compile mimalloc with `-DMI_OVERRIDE=OFF`.
542Adress sanitizer support is in its initial development -- please report any issues.
543
544[asan]: https://github.com/google/sanitizers/wiki/AddressSanitizer
545
546## ETW
547
548Event tracing for Windows ([ETW]) provides a high performance way to capture all allocations though
549mimalloc and analyze them later. To build with ETW support, use the `-DMI_TRACK_ETW=ON` cmake option. 
550
551You can then capture an allocation trace using the Windows performance recorder (WPR), using the 
552`src/prim/windows/etw-mimalloc.wprp` profile. In an admin prompt, you can use:
553```
554> wpr -start src\prim\windows\etw-mimalloc.wprp -filemode
555> 
556> wpr -stop .etl
557``` 
558and then open `.etl` in the Windows Performance Analyzer (WPA), or 
559use a tool like [TraceControl] that is specialized for analyzing mimalloc traces.
560
561[ETW]: https://learn.microsoft.com/en-us/windows-hardware/test/wpt/event-tracing-for-windows
562[TraceControl]: https://github.com/xinglonghe/TraceControl
563
564
565# Performance
566
567Last update: 2021-01-30
568
569We tested _mimalloc_ against many other top allocators over a wide
570range of benchmarks, ranging from various real world programs to
571synthetic benchmarks that see how the allocator behaves under more
572extreme circumstances. In our benchmark suite, _mimalloc_ outperforms other leading
573allocators (_jemalloc_, _tcmalloc_, _Hoard_, etc), and has a similar memory footprint. A nice property is that it
574does consistently well over the wide range of benchmarks.
575
576General memory allocators are interesting as there exists no algorithm that is
577optimal -- for a given allocator one can usually construct a workload
578where it does not do so well. The goal is thus to find an allocation
579strategy that performs well over a wide range of benchmarks without
580suffering from (too much) underperformance in less common situations.
581
582As always, interpret these results with care since some benchmarks test synthetic
583or uncommon situations that may never apply to your workloads. For example, most
584allocators do not do well on `xmalloc-testN` but that includes even the best
585industrial allocators like _jemalloc_ and _tcmalloc_ that are used in some of
586the world's largest systems (like Chrome or FreeBSD).
587
588Also, the benchmarks here do not measure the behaviour on very large and long-running server workloads,
589or worst-case latencies of allocation. Much work has gone into `mimalloc` to work well on such
590workloads (for example, to reduce virtual memory fragmentation on long-running services)
591but such optimizations are not always reflected in the current benchmark suite.
592
593We show here only an overview -- for
594more specific details and further benchmarks we refer to the
595[technical report](https://www.microsoft.com/en-us/research/publication/mimalloc-free-list-sharding-in-action).
596The benchmark suite is automated and available separately
597as [mimalloc-bench](https://github.com/daanx/mimalloc-bench).
598
599
600## Benchmark Results on a 16-core AMD 5950x (Zen3)
601
602Testing on the 16-core AMD 5950x processor at 3.4Ghz (4.9Ghz boost), with
603with 32GiB memory at 3600Mhz, running	Ubuntu 20.04 with glibc 2.31 and GCC 9.3.0.
604
605We measure three versions of _mimalloc_: the main version `mi` (tag:v1.7.0),
606the new v2.0 beta version as `xmi` (tag:v2.0.0), and the main version in secure mode as `smi` (tag:v1.7.0).
607
608The other allocators are
609Google's [_tcmalloc_](https://github.com/gperftools/gperftools) (`tc`, tag:gperftools-2.8.1) used in Chrome,
610Facebook's [_jemalloc_](https://github.com/jemalloc/jemalloc) (`je`, tag:5.2.1) by Jason Evans used in Firefox and FreeBSD,
611the Intel thread building blocks [allocator](https://github.com/intel/tbb) (`tbb`, tag:v2020.3),
612[rpmalloc](https://github.com/mjansson/rpmalloc) (`rp`,tag:1.4.1) by Mattias Jansson,
613the original scalable [_Hoard_](https://github.com/emeryberger/Hoard) (git:d880f72) allocator by Emery Berger \[1],
614the memory compacting [_Mesh_](https://github.com/plasma-umass/Mesh) (git:67ff31a) allocator by
615Bobby Powers _et al_ \[8],
616and finally the default system allocator (`glibc`, 2.31) (based on _PtMalloc2_).
617
618
619
620
621Any benchmarks ending in `N` run on all 32 logical cores in parallel.
622Results are averaged over 10 runs and reported relative
623to mimalloc (where 1.2 means it took 1.2× longer to run).
624The legend also contains the _overall relative score_ between the
625allocators where 100 points is the maximum if an allocator is fastest on
626all benchmarks.
627
628The single threaded _cfrac_ benchmark by Dave Barrett is an implementation of
629continued fraction factorization which uses many small short-lived allocations.
630All allocators do well on such common usage, where _mimalloc_ is just a tad
631faster than _tcmalloc_ and
632_jemalloc_.
633
634The _leanN_ program is interesting as a large realistic and
635concurrent workload of the [Lean](https://github.com/leanprover/lean)
636theorem prover compiling its own standard library, and there is a 13%
637speedup over _tcmalloc_. This is
638quite significant: if Lean spends 20% of its time in the
639allocator that means that _mimalloc_ is 1.6× faster than _tcmalloc_
640here. (This is surprising as that is not measured in a pure
641allocation benchmark like _alloc-test_. We conjecture that we see this
642outsized improvement here because _mimalloc_ has better locality in
643the allocation which improves performance for the *other* computations
644in a program as well).
645
646The single threaded _redis_ benchmark again show that most allocators do well on such workloads.
647
648The _larsonN_ server benchmark by Larson and Krishnan \[2] allocates and frees between threads. They observed this
649behavior (which they call _bleeding_) in actual server applications, and the benchmark simulates this.
650Here, _mimalloc_ is quite a bit faster than _tcmalloc_ and _jemalloc_ probably due to the object migration between different threads.
651
652The _mstressN_ workload performs many allocations and re-allocations,
653and migrates objects between threads (as in _larsonN_). However, it also
654creates  and destroys the _N_ worker threads a few times keeping some objects
655alive beyond the life time of the allocating thread. We observed this
656behavior in many larger server applications.
657
658The [_rptestN_](https://github.com/mjansson/rpmalloc-benchmark) benchmark
659by Mattias Jansson is a allocator test originally designed
660for _rpmalloc_, and tries to simulate realistic allocation patterns over
661multiple threads. Here the differences between allocators become more apparent.
662
663The second benchmark set tests specific aspects of the allocators and
664shows even more extreme differences between them.
665
666The _alloc-test_, by
667[OLogN Technologies AG](http://ithare.com/testing-memory-allocators-ptmalloc2-tcmalloc-hoard-jemalloc-while-trying-to-simulate-real-world-loads/), is a very allocation intensive benchmark doing millions of
668allocations in various size classes. The test is scaled such that when an
669allocator performs almost identically on _alloc-test1_ as _alloc-testN_ it
670means that it scales linearly.
671
672The _sh6bench_ and _sh8bench_ benchmarks are
673developed by [MicroQuill](http://www.microquill.com/) as part of SmartHeap.
674In _sh6bench_ _mimalloc_ does much
675better than the others (more than 2.5× faster than _jemalloc_).
676We cannot explain this well but believe it is
677caused in part by the "reverse" free-ing pattern in _sh6bench_.
678The _sh8bench_ is a variation with object migration
679between threads; whereas _tcmalloc_ did well on _sh6bench_, the addition of object migration causes it to be 10× slower than before.
680
681The _xmalloc-testN_ benchmark by Lever and Boreham \[5] and Christian Eder, simulates an asymmetric workload where
682some threads only allocate, and others only free -- they observed this pattern in
683larger server applications. Here we see that
684the _mimalloc_ technique of having non-contended sharded thread free
685lists pays off as it outperforms others by a very large margin. Only _rpmalloc_, _tbb_, and _glibc_ also scale well on this benchmark.
686
687The _cache-scratch_ benchmark by Emery Berger \[1], and introduced with
688the Hoard allocator to test for _passive-false_ sharing of cache lines.
689With a single thread they all
690perform the same, but when running with multiple threads the potential allocator
691induced false sharing of the cache lines can cause large run-time differences.
692Crundal \[6] describes in detail why the false cache line sharing occurs in the _tcmalloc_ design, and also discusses how this
693can be avoided with some small implementation changes.
694Only the _tbb_, _rpmalloc_ and _mesh_ allocators also avoid the
695cache line sharing completely, while _Hoard_ and _glibc_ seem to mitigate
696the effects. Kukanov and Voss \[7] describe in detail
697how the design of _tbb_ avoids the false cache line sharing.
698
699
700## On a 36-core Intel Xeon
701
702For completeness, here are the results on a big Amazon
703[c5.18xlarge](https://aws.amazon.com/ec2/instance-types/#Compute_Optimized) instance
704consisting of a 2×18-core Intel Xeon (Cascade Lake) at 3.4GHz (boost 3.5GHz)
705with 144GiB ECC memory, running	Ubuntu 20.04 with glibc 2.31, GCC 9.3.0, and
706Clang 10.0.0. This time, the mimalloc allocators (mi, xmi, and smi) were
707compiled with the Clang compiler instead of GCC.
708The results are similar to the AMD results but it is interesting to
709see the differences in the _larsonN_, _mstressN_, and _xmalloc-testN_ benchmarks.
710
711
712
713
714
715## Peak Working Set
716
717The following figure shows the peak working set (rss) of the allocators
718on the benchmarks (on the c5.18xlarge instance).
719
720
721
722
723Note that the _xmalloc-testN_ memory usage should be disregarded as it
724allocates more the faster the program runs. Similarly, memory usage of
725_larsonN_, _mstressN_, _rptestN_ and _sh8bench_ can vary depending on scheduling and
726speed. Nevertheless, we hope to improve the memory usage on _mstressN_
727and _rptestN_ (just as _cfrac_, _larsonN_ and _sh8bench_ have a small working set which skews the results).
728
729
773
774
775# References
776
777- \[1] Emery D. Berger, Kathryn S. McKinley, Robert D. Blumofe, and Paul R. Wilson.
778   _Hoard: A Scalable Memory Allocator for Multithreaded Applications_
779   the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IX). Cambridge, MA, November 2000.
780   [pdf](http://www.cs.utexas.edu/users/mckinley/papers/asplos-2000.pdf)
781
782- \[2] P. Larson and M. Krishnan. _Memory allocation for long-running server applications_.
783  In ISMM, Vancouver, B.C., Canada, 1998. [pdf](http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.45.1947&rep=rep1&type=pdf)
784
785- \[3] D. Grunwald, B. Zorn, and R. Henderson.
786  _Improving the cache locality of memory allocation_. In R. Cartwright, editor,
787  Proceedings of the Conference on Programming Language Design and Implementation, pages 177–186, New York, NY, USA, June 1993. [pdf](http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.43.6621&rep=rep1&type=pdf)
788
789- \[4] J. Barnes and P. Hut. _A hierarchical O(n*log(n)) force-calculation algorithm_. Nature, 324:446-449, 1986.
790
791- \[5] C. Lever, and D. Boreham. _Malloc() Performance in a Multithreaded Linux Environment._
792  In USENIX Annual Technical Conference, Freenix Session. San Diego, CA. Jun. 2000.
793  Available at 
794
795- \[6] Timothy Crundal. _Reducing Active-False Sharing in TCMalloc_. 2016. CS16S1 project at the Australian National University. [pdf](http://courses.cecs.anu.edu.au/courses/CSPROJECTS/16S1/Reports/Timothy_Crundal_Report.pdf)
796
797- \[7] Alexey Kukanov, and Michael J Voss.
798   _The Foundations for Scalable Multi-Core Software in Intel Threading Building Blocks._
799   Intel Technology Journal 11 (4). 2007
800
801- \[8] Bobby Powers, David Tench, Emery D. Berger, and Andrew McGregor.
802 _Mesh: Compacting Memory Management for C/C++_
803 In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'19), June 2019, pages 333-–346.
804
805
811
812# Contributing
813
814This project welcomes contributions and suggestions.  Most contributions require you to agree to a
815Contributor License Agreement (CLA) declaring that you have the right to, and actually do, grant us
816the rights to use your contribution. For details, visit https://cla.microsoft.com.
817
818When you submit a pull request, a CLA-bot will automatically determine whether you need to provide
819a CLA and decorate the PR appropriately (e.g., label, comment). Simply follow the instructions
820provided by the bot. You will only need to do this once across all repos using our CLA.
821
822
823# Older Release Notes
824
825* 2021-11-14, `v1.7.3`, `v2.0.3` (beta): improved WASM support, improved macOS support and performance (including
826  M1), improved performance for v2 for large objects, Python integration improvements, more standard
827  installation directories, various small fixes.
828* 2021-06-17, `v1.7.2`, `v2.0.2` (beta): support M1, better installation layout on Linux, fix
829  thread_id on Android, prefer 2-6TiB area for aligned allocation to work better on pre-windows 8, various small fixes.
830* 2021-04-06, `v1.7.1`, `v2.0.1` (beta): fix bug in arena allocation for huge pages, improved aslr on large allocations, initial M1 support (still experimental).
831* 2021-01-31, `v2.0.0`: beta release 2.0: new slice algorithm for managing internal mimalloc pages.
832* 2021-01-31, `v1.7.0`: stable release 1.7: support explicit user provided memory regions, more precise statistics,
833  improve macOS overriding, initial support for Apple M1, improved DragonFly support, faster memcpy on Windows, various small fixes.
834
835* 2020-09-24, `v1.6.7`: stable release 1.6: using standard C atomics, passing tsan testing, improved
836  handling of failing to commit on Windows, add [`mi_process_info`](https://github.com/microsoft/mimalloc/blob/master/include/mimalloc.h#L156) api call.
837* 2020-08-06, `v1.6.4`: stable release 1.6: improved error recovery in low-memory situations,
838  support for IllumOS and Haiku, NUMA support for Vista/XP, improved NUMA detection for AMD Ryzen, ubsan support.
839* 2020-05-05, `v1.6.3`: stable release 1.6: improved behavior in out-of-memory situations, improved malloc zones on macOS,
840  build PIC static libraries by default, add option to abort on out-of-memory, line buffered statistics.
841* 2020-04-20, `v1.6.2`: stable release 1.6: fix compilation on Android, MingW, Raspberry, and Conda,
842  stability fix for Windows 7, fix multiple mimalloc instances in one executable, fix `strnlen` overload,
843  fix aligned debug padding.
844* 2020-02-17, `v1.6.1`: stable release 1.6: minor updates (build with clang-cl, fix alignment issue for small objects).
845* 2020-02-09, `v1.6.0`: stable release 1.6: fixed potential memory leak, improved overriding
846  and thread local support on FreeBSD, NetBSD, DragonFly, and macOSX. New byte-precise
847  heap block overflow detection in debug mode (besides the double-free detection and free-list
848  corruption detection). Add `nodiscard` attribute to most allocation functions.
849  Enable `MIMALLOC_PAGE_RESET` by default. New reclamation strategy for abandoned heap pages
850  for better memory footprint.
851* 2020-02-09, `v1.5.0`: stable release 1.5: improved free performance, small bug fixes.
852* 2020-01-22, `v1.4.0`: stable release 1.4: improved performance for delayed OS page reset,
853more eager concurrent free, addition of STL allocator, fixed potential memory leak.
854* 2020-01-15, `v1.3.0`: stable release 1.3: bug fixes, improved randomness and [stronger
855free list encoding](https://github.com/microsoft/mimalloc/blob/783e3377f79ee82af43a0793910a9f2d01ac7863/include/mimalloc-internal.h#L396) in secure mode.
856
857* 2019-12-22, `v1.2.2`: stable release 1.2: minor updates.
858* 2019-11-22, `v1.2.0`: stable release 1.2: bug fixes, improved secure mode (free list corruption checks, double free mitigation). Improved dynamic overriding on Windows.
859* 2019-10-07, `v1.1.0`: stable release 1.1.
860* 2019-09-01, `v1.0.8`: pre-release 8: more robust windows dynamic overriding, initial huge page support.
861* 2019-08-10, `v1.0.6`: pre-release 6: various performance improvements.
862