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

11–20 of 70 posts

Re: Mimalloc – A compact general-purpose allocator

#11

Post by gok »

bakery2k wrote: post #9
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…

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?

It's very hard to not accidentally pull in a dependency that makes your code multithreaded.

Re: Mimalloc – A compact general-purpose allocator

#12

Post by AndrewStephens »

pjmlp wrote: post #4
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…

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.

And those products really did help. Microsoft's implementation of malloc performed terribly for many workloads - dropping in a 3rd party allocator could speed up your software considerably.

It wasn't until well into the 2000s until the standard allocators started to become good enough to make the 3rd party libraries less essential. Many of them you can still buy today and they probably still help with certain types of software.

Re: Mimalloc – A compact general-purpose allocator

#13

Post by the_duke »

fwip wrote: post #7

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

The benchmark repo contains results with a Intel Xeon.

Looks roughly similar: https://github.com/daanx/mimalloc-bench

Re: Mimalloc – A compact general-purpose allocator

#14

Post by pizlonator »

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 avoiding the need for the thread that owns the heap to stop or synchronize at the moment that happens even though that thread is non-atomically allocating and freeing in that same heap.

So, it’s always easy to sound smart by saying that a field is well explored - but it looks like this thing actually has some cool new ideas in it.

Re: Mimalloc – A compact general-purpose allocator

#15

Post by Quekid5 »

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…

Andrei Alexandrescu had a great talk[0] on allocators and this convinced me that if you really care about allocator performance[1] what you need is a tunable and composable system. The whole idea of how and when (runtime/compile-time) to choose the appropriate allocator is also interesting.

[0] https://www.youtube.com/watch?v=LIb3L4vKZ7U

[1] I suppose there's a digression to be had here about allocation being trivial and RAII-style deallocation not really being deterministic, but...

Re: Mimalloc – A compact general-purpose allocator

#17

Post by longcommonname »

Just a general question in regards to using memory allocators, in the consideration of a C only application.

The problems I encounter with allocator and heap manager are almost never solved by these types of frameworks. These problems include:

1. Improper usage of the memory returned that contradict implementation. 2. Pool allocators that don't have separation between individual blocks (performance reasons). 3. Specifying the lifetime of the memory to a thread or until specific events happen. 4. Difficult to diagnose corruption, with any tool available.

Here's a specific scenario I deal with very often: There are N persistent worker threads. These worker threads have their own pool of memory, and prior to getting work we know this pool is clean. After the work is finished and before more work is recieved the memory is cleaned. Any excess requested memory is returned to the global-pool, and any memory that is "unmanaged" is dealt with properly.

This means that people can do whatever heap management call you use (void * obtainMemory(size_t);) in the scope of business logic without having to worry about infrastructure concerns.

Having a faster malloc/calloc doesn't benefit me as much as making the usage of memory easier, and the understanding of what happens easier.

Re: Mimalloc – A compact general-purpose allocator

#18

Post by shereadsthenews »

I always find comparisons with tcmalloc hard to parse, since it has a million knobs and the defaults are terrible. If they are running with 16 threads I would normally advise increasing the thread cache size far above the default 3MiB. also interesting would be jemalloc in per-CPU mode.

As always the thing to do is build and run your own workload and see the results.

Re: Mimalloc – A compact general-purpose allocator

#19

Post by 01100011 »

gok wrote: post #11
bakery2k wrote: post #9

Earlier quoted context omitted.

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?

It's very hard to not accidentally pull in a dependency that makes your code multithreaded.

You guys could argue this all day and both be right. Depending on what type of system you're working on, you are either very likely to pull in a multithreaded dependency or you are not. Systems programming is different from game programming is different from web client programming is different from kernel development. In most of my career, I would have never accidentally pulled in a multithreaded dependency, but I could see how that could be easy to do in some cases.
Post reply on HN