Mimalloc – A compact general-purpose allocator
1–10 of 70 posts
Re: Mimalloc – A compact general-purpose allocator
#2[deleted]
Re: Mimalloc – A compact general-purpose allocator
#3The tricky part with allocators is always the multi-threaded setups.
Even something as simple as a bunch of threads doing malloc-free in a loop will drop performance of a lot of allocators to the floor, due to some sort of central locking or excessive cache thrashing. This is typically solved by adding per-thread block pools, free lists or some such.
If you go further down the rabbit hole, there's a case when blocks are allocated in one thread and freed in another, your very typical producer-consumer setup. This too further complicates things with the pool/freelist setup and requires periodic rebalancing of freelists and pools.
So once all this is accommodated, a well-tuned allocator inevitably converges to a model with central slabs/pools/freelists and per-thread caches of the same, which are periodically flushed into the former. Then it all comes down to routine code optimization to make fastpaths fast, through lock-free data structures, some clever tricks and what not.
In other words, it's always nice to read through someone's allocator code, but in the end this is a very well-explored area and there's basically a single stable point once all common scenarios are considered.
Re: Mimalloc – A compact general-purpose allocator
#4The tricky part with allocators is always the multi-threaded setups. Even something as simple as a bunch of threads doing malloc-free in a loop will drop performance of a lot of allocators to the floor, due to some sort of central locking or excessive cache thrashing. This is typically solved by adding per-thread block pools, free lists or some such. If you go further down the rabbit hole, there's a case when blocks…
To the point you really need specialized knowledge.
I remember DrDobbs and The C/C++ Users Journal having ads for companies whose sole product was a memory allocator for different kinds of deployment scenarios.
Re: Mimalloc – A compact general-purpose allocator
#5The tricky part with allocators is always the multi-threaded setups. Even something as simple as a bunch of threads doing malloc-free in a loop will drop performance of a lot of allocators to the floor, due to some sort of central locking or excessive cache thrashing. This is typically solved by adding per-thread block pools, free lists or some such. If you go further down the rabbit hole, there's a case when blocks…
They claim to perform well on at least some multi-thread workloads (read https://github.com/microsoft/mimalloc#performance):
"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)."
Re: Mimalloc – A compact general-purpose allocator
#6The tricky part with allocators is always the multi-threaded setups. Even something as simple as a bunch of threads doing malloc-free in a loop will drop performance of a lot of allocators to the floor, due to some sort of central locking or excessive cache thrashing. This is typically solved by adding per-thread block pools, free lists or some such. If you go further down the rabbit hole, there's a case when blocks…
There are a lot of ways to write the same story; Mimalloc has a few innovations of its own, has good benchmarks to justify them, and the paper is a very good read. In particular, Mimalloc works to increase data locality, by using per-‘page’ (64kB memory blocks) free queues. All this with a codebase almost a tenth the size of jemalloc, and it's looking very promising.
Re: Mimalloc – A compact general-purpose allocator
#7The benchmarks are very impressive! I am excited to read through this code and think on it.
Edit: They do mention they're all from AMD's EPYC chip, which is a little idiosyncratic. Speculation: perhaps page locality is more important on this architecture.
Re: Mimalloc – A compact general-purpose allocator
#8The tricky part with allocators is always the multi-threaded setups. Even something as simple as a bunch of threads doing malloc-free in a loop will drop performance of a lot of allocators to the floor, due to some sort of central locking or excessive cache thrashing. This is typically solved by adding per-thread block pools, free lists or some such. If you go further down the rabbit hole, there's a case when blocks…
It's a little hidden, but this is out of MS research, and seems to be initially designed for ref-counted scripting languages. I'm not really sure how much they focused on multi-threaded stuff.
>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.
https://www.microsoft.com/en-us/research/publication/mimallo...
Re: Mimalloc – A compact general-purpose allocator
#9The tricky part with allocators is always the multi-threaded setups. Even something as simple as a bunch of threads doing malloc-free in a loop will drop performance of a lot of allocators to the floor, due to some sort of central locking or excessive cache thrashing. This is typically solved by adding per-thread block pools, free lists or some such. If you go further down the rabbit hole, there's a case when blocks…
What if I'm writing code that's strictly single-threaded? Presumably malloc could be simpler and/or faster in this special case?
Is there a production-ready allocator that's optimized for single-threaded use?
Re: Mimalloc – A compact general-purpose allocator
#10The tricky part with allocators is always the multi-threaded setups. Even something as simple as a bunch of threads doing malloc-free in a loop will drop performance of a lot of allocators to the floor, due to some sort of central locking or excessive cache thrashing. This is typically solved by adding per-thread block pools, free lists or some such. If you go further down the rabbit hole, there's a case when blocks…
It's a little hidden, but this is out of MS research, and seems to be initially designed for ref-counted scripting languages. I'm not really sure how much they focused on multi-threaded stuff. >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 ba…
That's not what the quote means, really. They have best-in-class performance on both single- and multi-threaded workloads. It is just saying that the allocator supports a deferred_free callback, which is zero-overhead in the fast path and negligible overhead in the slow path.