Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Mimalloc – A compact general-purpose allocator

github.com

Post reply on HN
Print view View original

31–40 of 70 posts

Re: Mimalloc – A compact general-purpose allocator

#31

Post by gpderetta »

pizlonator wrote: post #14
huhtenberg wrote: post #3

The 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…

This allocator appears to have some genuinely interesting things in its multi thread support: - it looks like it avoids atomics on common cases of malloc and free. That’s a big deal and not all malloc a accomplish that. - it looks like it has cleverness specifically for the case that one thread frees an object into another thread’s heap. It seems like this case was given some special consideration - in particular avo…

>it looks like it avoids atomics on common cases of malloc and free. That’s a big deal and not all malloc a accomplish that.

Many mallocs implementations try to avoid one cache per thread because it can waste a huge amount of memory in applications with thousands of threads opting for per cpu pools or similar solutions. These solutions help with contention but still require atomics (unless using something like restartable sequences).

It is a trade-off, but for applications that use one thread per cpu, completely private free lists can branch win of course.

Re: Mimalloc – A compact general-purpose allocator

#32

Post by danlark »

MaxBarraclough wrote: post #29
danlark wrote: post #25

We tried mimalloc in ClickHouse and it is two times slower than jemalloc in our common use case https://github.com/microsoft/mimalloc/issues/11

To be clear, your program ran at half speed, right? That's far worse than doubling the time spent in memory-management functions.

Yes, our program ran at half speed.

Re: Mimalloc – A compact general-purpose allocator

#33

Post by plietar »

huhtenberg wrote: post #3

The 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…

You may want to look at snmalloc, another allocator we did at Microsoft Research. It specifically targets these producer / consumer scenarios.

https://github.com/microsoft/snmalloc

And the paper, which I’ll be presenting tomorrow at ISMM: https://github.com/microsoft/snmalloc/blob/master/snmalloc.p...

Re: Mimalloc – A compact general-purpose allocator

#34

Post by Reelin »

pizlonator wrote: post #14
huhtenberg wrote: post #3

The 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…

This allocator appears to have some genuinely interesting things in its multi thread support: - it looks like it avoids atomics on common cases of malloc and free. That’s a big deal and not all malloc a accomplish that. - it looks like it has cleverness specifically for the case that one thread frees an object into another thread’s heap. It seems like this case was given some special consideration - in particular avo…

This is quite possibly an uninformed question, but is it possible to use multiple allocator implementations simultaneously in the same program?

Obviously this would introduce additional creative ways in which to mess up memory management, but at least theoretically it seems like it ought to be doable. When I tried to search for information on the topic just now, I found only a few items about using multiple allocators in C++ that involved the STL and templates, but nothing about low level code or best practices.

Re: Mimalloc – A compact general-purpose allocator

#35

Post by jasonzemos »

nh2 wrote: post #27

Are there functions available with which I can at run-time query how much OS memory is used, how much handed out in allocations, how many mmap()ed pools are used, and so on? I find that one of the most important features of a malloc library to debug memory usage. glibc has these functions (like malloc_info()) -- they are very bugged in that they return wrong results, but after patching them to be correct, they are su…

Any more info/link on how they are incorrect and the patches you need to fix them?

Re: Mimalloc – A compact general-purpose allocator

#36

Post by pizlonator »

Reelin wrote: post #34
pizlonator wrote: post #14

Earlier quoted context omitted.

This allocator appears to have some genuinely interesting things in its multi thread support: - it looks like it avoids atomics on common cases of malloc and free. That’s a big deal and not all malloc a accomplish that. - it looks like it has cleverness specifically for the case that one thread frees an object into another thread’s heap. It seems like this case was given some special consideration - in particular avo…

This is quite possibly an uninformed question, but is it possible to use multiple allocator implementations simultaneously in the same program? Obviously this would introduce additional creative ways in which to mess up memory management, but at least theoretically it seems like it ought to be doable. When I tried to search for information on the topic just now, I found only a few items about using multiple allocator…

Yeah you can but then you pay a tax on free() because you have to do some dispatch to decide what algorithm you are using. The more algorithms the higher the tax.

Also, you want to make sure that the mallocs can share free pages with each other directly. Otherwise you will likely het higher peak memory overhead or worse perf or both.

Re: Mimalloc – A compact general-purpose allocator

#39

Post by emeryberger »

gpderetta wrote: post #31
pizlonator wrote: post #14

Earlier quoted context omitted.

This allocator appears to have some genuinely interesting things in its multi thread support: - it looks like it avoids atomics on common cases of malloc and free. That’s a big deal and not all malloc a accomplish that. - it looks like it has cleverness specifically for the case that one thread frees an object into another thread’s heap. It seems like this case was given some special consideration - in particular avo…

>it looks like it avoids atomics on common cases of malloc and free. That’s a big deal and not all malloc a accomplish that. Many mallocs implementations try to avoid one cache per thread because it can waste a huge amount of memory in applications with thousands of threads opting for per cpu pools or similar solutions. These solutions help with contention but still require atomics (unless using something like restar…

All modern allocator implementations I am aware of (including Hoard and Mesh) use per-thread caches (of a limited size), and thus avoid the use of atomic operations in the common case while also avoiding blowup (wasted memory caused by using a memory allocator that "leaks" -- see the Hoard paper (ASPLOS 2000, https://people.cs.umass.edu/~emery/pubs/berger-asplos2000.pd...) for a full discussion).

Re: Mimalloc – A compact general-purpose allocator

#40

Post by kllrnohj »

civility wrote: post #37

Is anyone aware of a good/fast single threaded allocator for cases where you don't need/want to pay for thread safety?

If you're single threaded then you'll never have mutex contention so they'll always be fast-path. I'd suggest you actually prove that the memory barriers are actually a problem for you via profiling, since it's somewhat unlikely it is.
Post reply on HN