10 ms·
Benchmarking C++ Allocators
- mehrdadn 7y ago> For C++ programs, replacing malloc and free at runtime is the worst choice. When the compiler can see the definition of new and delete at build time it can generate far better programs. When it can’t see them, it generates out-of-line function calls to malloc for every operator new, which is bananas. I feel like whenever I've dealt with general-purpose memory allocation (as opposed to special-purpose like from a stack buffer without freeing) this kind of overhead has been dwarfed by the actual overhead of the allocation and pointless to worry about. Is this not the case in others' experience?
- Ididntdothis 7y agoI tend to agree. For some types of applications it may make sense to worry about it but there are usually other things to look into first.
- winrid 7y agoYeah I think it's very situational. Like an arena allocator is going to give you a tremendous bump in allocation performance since you just allocate once and replace memory every frame - to give the gaming industry example.
- BubRoss 7y agoAn arena allocator isn't going to be the underpinning of the new operator.
- jeffbee 7y agoThere are a wide variety of outcomes available when the implementation of global operator new is visible to the compiler. It may inline the entire new, and having done so it may also apply any other optimization that would apply to any other function. Without an allocator at build time the only thing it can do it generate a call to malloc. Leaving malloc resolution to runtime also negates all benefits of sized delete.
- the8472 7y agoMy understanding is that compilers are allowed to treat malloc specially, i.e. they can assume that it returns non-aliasing memory, does not mutate other memory and can be elided if its result is unused.
- mehrdadn 7y agoI'm not aware of that being a blanket assumption they can make, is it? (Is it in the C++ standard?) That kind of thing is generally dictated by compiler-specific annotations (noalias etc.) which you can put on any function, and which shouldn't apply unless you write them explicitly...
- gpderetta 7y agoon gcc you can use __attribute__((malloc)) to tell the compiler that your function is malloc-like (i.e. its result type won't alias any other pointer), but any call to the litterall 'malloc' function itself is implicitly treated as such even if you do not include the appropriate header and declare it yourself (you can use -fno-builtin-functions or -free-standing or something like that to disable this treatment).
- jcranmer 7y agoLLVM is capable of eliminating calls to malloc if it can prove that they don't escape the function.
- saagarjha 7y ago
- acqq 7y ago> Is this not the case in others' experience? My experience is that C++ programs that try to be "Java" are the worst programs, from the performance standpoint, that can be written of all. And here I mean the "Java" practice that whatever object you have, it has to be made with "new." When one wants the really good performance in C++ that's the worst one can do. And my observation includes all implicit allocations due to the use of the "containers." Not to mention other effects that then get to be problem by the long-running programs. That being said, in the targets I used the compiler was effectively never able to avoid calling actual malloc and free behind the new, and that matches your experience: malloc an free themselves were much bigger overhead than a few instructions that wrapped them to appear as "new." It was however a few years ago the last time I analyzed something like that -- specifically for the code which has to be really fast I simply avoid having these wrapped "malloc" allocations in the hot paths, so I haven't had to investigate that specific aspect.
- gpderetta 7y agoThis 'new-all-the-things' style is called the Java style, but it is a bit unfair to Java, as that languages was designed, among other things, to make this style, which was prevalent in OO-heavy C++ programs from the '90s, usable. It is still somewhat common in OO heavy GUI libraries and applications like Qt, although there the allocation performance is probably not the biggest bottleneck.
- acqq 7y ago> it is a bit unfair to Java, as that languages was designed, among other things, to make this style, which was prevalent in OO-heavy C++ programs from the '90s, usable. It could be completely fair, however, unless that language now allows an alternative paradigm, which it didn't the last time I've checked. If that changed since, I'd be really glad to read about it.
- pjmlp 7y agoIt will come, just not yet, because JARs compiled 25 years ago are supposed to still run unchanged in this new world. https://cr.openjdk.java.net/~briangoetz/valhalla/sov/01-background.html https://cr.openjdk.java.net/~briangoetz/valhalla/sov/01-back... https://jdk.java.net/valhalla/ https://jdk.java.net/valhalla/ OWL, VCL, MFC, wxWidgets, Turbo Vision, CSet++, Motif++, BeOS, Epoch were all Java style, before Java was even born.
- chubot 7y agoI also think that if it does matter, it could be a sign you're using new too much. In other words, the style of "invoke new every time I need a new object" is not really what most people who care about performance do. There are higher level patterns than that, and often pluggable allocators, which could make the call out-of-line anyway, etc.
- userbinator 7y agoThis. Before trying to make allocation faster, try to eliminate them first. A lot of code I've seen in higher-level languages, even (or especially?) most C++, seems completely oblivious to the amount of memory manipulation they're doing. "The fastest way to do something is to not do it at all." A related old article about how Chrome's "omnibox" would do 25k allocations on each keystroke: https://news.ycombinator.com/item?id=8704318 https://news.ycombinator.com/item?id=8704318
- oddity 7y ago> even (or especially?) most C++ C++ hits the particularly nasty sweet spot of hiding boilerplate just enough that you have no idea what you're actually calling while also not having a sophisticated JIT that can do escape analysis and other tricks to optimize that kind of code. It doesn't help that, often, the default response to not having a clear understanding of resource ownership in a code-base is to make a copy. I also find that people struggle to internalize the costs of memory allocation. These days, the default allocators on modern systems are fairly well tuned for crap code, and the cost of any one particular allocation is a complicated function of all the allocations that came before it. They're different orders of magnitude in the badness scale, but any one allocation never looks so bad, just like any one memory load/store never looks so bad.
- MaxBarraclough 7y ago> Before trying to make allocation faster, try to eliminate them first Not sure if memory pools still count as allocation, but they should be faster, and are easily done in C++. Boost.Pool for instance.
- 7y ago
- summerlight 7y agoModern allocators are extremely optimized for a fast path which consists of tens of instructions and usually takes a few nanoseconds. Function call overheads are not negligible for this case.
- mehrdadn 7y agoIt feels a little bit like saying modern cars are extremely optimized for a fast acceleration which consists of a 0-to-60 of 3 seconds instead of 9 seconds, and acceleration delay is not negligible in this case. I mean, I suppose you're right and it would be a 3x improvement, but surely you're not using your (general-purpose) heavyweight tool (car) to just zoom down the block and back at peak acceleration all the time, right? And if you really do have a niche requirement like that, aren't there bigger fish to fry here (like eliminating the car or the need to transport people there & back altogether)?
- summerlight 7y agoI'm not sure what you're trying to achieve with this metaphor. Are you suggesting that fast path itself is "niche" in terms of allocator performance?
- mehrdadn 7y agoI'm saying it's very likely you should be looking into alternative approaches if the fast path performance is genuinely your bottleneck, and that in my experience it's overwhelmingly likely that that's not the case. Most likely you're doing too many dynamic memory allocations to begin with. Note that even if you invoke the fast path 20x more often than the slow path, it's still going to be peanuts if your slow path is 1000x slower. Best way to support your point would be to illustrate with realistic examples instead of hypotheticals. Otherwise this is like the JIT vs. AOT debate that always goes nowhere because the JIT side only ever uses hypotheticals to support their case.
- saagarjha 7y agoThat's not fair, though, because it really depends on how often the fast path gets hit. In good dynamic language runtimes, for example, the fast path is extremely optimized and hit very often, so even though the slow path can be thousands or millions of times slower the application performance might track the fast path rather than the slow one.
- favorited 7y agoA bit unrelated, but if anyone is interested, I recently watched Andrei Alexandrescu's 2015 talk about a composable allocator design in C++ and it was really interesting. And Andrei's presentation style was fantastic, per usual. Note that this talk is about a std::allocator-like type, potentially on top of one of malloc/jemalloc/etc. https://www.youtube.com/watch?v=LIb3L4vKZ7U https://www.youtube.com/watch?v=LIb3L4vKZ7U
- CppCoder 7y agoLet’s not forget a benchmark is not a typical application. Just because it does improve without using dynamic linking does not conclude it would so in every application. But, I definitely would not dynamically link a custom allocator. For me it would be the improved memory usage and performance, which I do not want to risk loosing.
- AshamedCaptain 7y ago> For C++ programs, replacing malloc and free at runtime is the worst choice. When the compiler can see the definition of new and delete at build time it can generate far better programs. When it can’t see them, it generates out-of-line function calls to malloc for every operator new, which is bananas. This argument smells like bullshit, sorry, and it's totally not justified in the article. Giving just numbers without even explaining a potential causality points to benchmark setup failure more than anything. Unless you are talking about statically linking your malloc implementation, your entire STL and all depending libraries AND then performing LTO on it, and even then I'd be surprised if there's any noticeable improvement over this. Not to mention I don't know of _any_ real-life executable that does this...
- notacoward 7y ago> statically linking your malloc implementation AND then performing LTO This is exactly how some large tech companies build all their executables. You might not get to run those, but they definitely exist.
- jlebar 7y agoThere indeed isn't a ton of detail in TFA, and so I can understand your skepticism. Jeff Baker is an expert on this at Google. Until you've seen the sorts of analyses that are conducted inside of Google, it may be hard to appreciate the level of scrutiny that every CPU instruction in tcmalloc has gotten from people like Jeff.
- banachtarski 7y ago> This argument smells like bullshit, sorry, and it's totally not justified in the article. Giving just numbers without even explaining a potential causality points to benchmark setup failure more than anything. Why? This argument sounds perfectly reasonable and is true in many other contexts as well.
- deleted 7y ago[deleted]
- 7y ago
- mitchs 7y agoWhen I backtrace from my malloc wrapper, injected with LD_PRELOAD, I see malloc, std::new, then the call site that involved new. Unless std::new is doing some funky shit (Like detecting dlsym("malloc") isn't glibc's malloc, and changing implementations) I have my doubts about the claim that dynamic replacement is costly. It appears new is already dynamically linking malloc.
- jeffbee 7y agoThat is the entire point of the post. If you leave the resolution of malloc to run time, the best you can hope for is that new calls malloc, out of line. If you build with an implementation of new, the outcomes may be dramatically better. By the way there is no such thing as std::new. We are discussing ::new.
- mitchs 7y agoHeh, std::new was some cruft I got out of backtrace(3) with some wacky embedded tool chain. Are these gains supposed to be from inlining the top level function of malloc into new? Compared to the costs of what can go on inside malloc... Is that the biggest problem?
- ckennelly 7y agoDynamic linking requires calling through the PLT to get to the implementation, so there's a data dependency on determining where the code for it is. Independent of inlining (with LTO, since the C++ language rules requires inhibit optimizing out "operator new"), the static call is far simpler.
- The_rationalist 7y agoThey should include mimalloc. It is gaining momentum, for example it is the default allocator for kotlin native
- jeffbee 7y agoPicking the best allocator was not my goal. I was writing about how to correctly use any allocator. I agree that mimalloc is worth evaluating. Note that Microsoft says this in their docs, which agrees with what I am driving at: """ For best performance in C++ programs, it is also recommended to override the global new and delete operators. For convience, mimalloc provides mimalloc-new-delete.h which does this for you -- just include it in a single(!) source file in your project. """
- moonchild 7y agoNote that there are other considerations like absolute allocation speed, like memory fragmentation, which isn't affected by inlining. In the ithare post they link, jemalloc thrashes all other allocators[1] on that front. It would be interesting to see if the newer version of tcmalloc is improved at all in that respect. 1: http://ithare.com/wp-content/uploads/malloc-overhead.png http://ithare.com/wp-content/uploads/malloc-overhead.png
- jeffbee 7y agoIn this test jemalloc actually uses the most memory of all. With default tunings it uses 700k pages at peak, compared to 170k for tcmalloc and 131k for glibc. I have no idea if that is relevant in real life and I have never cared, so I didn't mention it.
- saagarjha 7y agoThat's actually quite interesting, as IIRC jemalloc has much looser alignment than other allocators and thus can give "tighter" blocks for small allocations.
- riking 7y agoThat's due to differences in your workload - in e.g. Ruby on Rails, the total uncertainty of which objects are going to survive a request means that jemalloc does a much better job at packing.
- the8472 7y agoThe post has no date, does not mention versions used or allocator tunables. Considering that this is a shifting landscape that makes it difficult to judge how relevant those results are today.
- jeffbee 7y agoTrue. I added a date at the top. I wrote it this morning with head revisions of both jemalloc and tcmalloc.
- benibela 7y agoSomething that could help a lot with performance would be functions to handle memory for many small blocks at once. Like a malloc extension function that allocates many small blocks at once. Rather than returning one block of size n, it would return k blocks of size n. Of course the user could do something similar by allocating one big block of size k · n ordinarly. But then the user needs to keep track which small blocks belong to which big block, and it might too big, when some small blocks are not needed anymore. Say, the function needs k small blocks temporarily for processing, but only returns k/10 small blocks. Then 90% of the memory would be wasted. But if you could allocate k small blocks at once, the allocator could allocate one big array of k·(n + sizeof metadata). Then each of the small blocks could be freed like a normally allocated block of size k, but they have all the advantages of quick allocation and cache locality like a big array. Or, alternatively, there could be a partial free that does not free the entire malloced block, but only a part of it. Then you could allocate a block of size k·n, and when you do not need it anymore, free the 90% of the block that you do not need, but keep the 10% that you need.
- scott_s 7y agoRegion-based allocation is similar to this: https://en.wikipedia.org/wiki/Region-based_memory_management https://en.wikipedia.org/wiki/Region-based_memory_management
- munchbunny 7y agoObject pools are a pretty common pattern for that kind of usage. Is this any different, or are you just asking to push the "allocation" into the memory allocator instead?
- benibela 7y agoThe difference would be that each object can be freed individually when it is no longer needed. Especially when the code that creates the objects and the code that uses/discards the objects are in two different projects. Like a library that can load a JSON file as some kind of tree structure. Then someone uses the library, loads a file of a million objects, but then only needs a single object. All the other objects should be freed, but if they are in a pool, they cannot. The library does not know which object the user wants, and an user of the library should not need to know how the library allocates the objects
- pizlonator 7y agoMy data says that perf of malloc/free in actual programs (not fake ass shit calling malloc in a loop) is never affected by the call overhead. Not by dynamic call overhead, not even if you write a wrapper that uses a switch or indirect call to select mallocs. Reason is simple: malloc perf is all about data dependencies in the malloc/free path and how many cache misses it causes or prevents. Adding indirection on the malloc call path is handled gracefully by the CPU’s ability to ILP, and malloc is a perfect candidate since it’s bottlenecks will be cache misses inside the malloc/free paths.
- saagarjha 7y agoHas per-thread arenas made locking less of an issues these days?
- pizlonator 7y agoNot everyone does per thread arenas as a way of solving this problem. And I don’t think any solution to locking in malloc is a silver bullet. Some schemes work exceedingly well for specific use cases. So, there will always be folks in the malloc space who think theirs is better or theirs completely solves the problem because it is better and does solve the problem for their use case.
- s_kanev 7y agoThis was the case a few years back when the fastest pools were implemented with recursive data structures (e.g. linked lists for the freelists in gperftools). In the new tcmalloc (and, I think, hoard?) the fastest pools are essentially slabs with bump allocation, so the fastest (and by far, the most common) calls are a grand total of 15 or so instructions, without many cache misses (size class lookups tend to stay in the cache). Call overhead can be a substantial chunk of that.
- pizlonator 7y agoFirst of all, let’s be clear: for a lot of algorithms adding call overhead around them is free because the cpu predicts the call, predicts the return, and uses register renaming to handle arguments and return. But that’s not the whole story. Malloc perf is about what happens on free and what happens when the program accesses that memory that malloc gave it. When you factor that all in, it doesn’t matter how many instructions the malloc has. It matters whether those instructions form a bad dependency chain, if they miss cache, whether the memory we return is in the “best” place, and how much work happens in free (using the same metrics - dependency chain length and misses, not total number of instructions or whether there’s a call).
- quotemstr 7y agoThe C++ allocator interface really needs to support realloc. Vector, in many cases, could avoid copying elements, particularly in cases where the move constructor is trivial --- e.g., vector<int>.
- leni536 7y agoIt's a shame we don't have "destructive move"/relocation yet. Many more objects are trivially relocatable than trivially movable.
- inquirrer 7y agoHow does tcmalloc optimize away new/deletes at compile time exactly?
- scott_s 7y agoNot optimize them away entirely, but eliminate the actual function call through inlining. User-code can implement their own new and delete. If those implementations are available during compilation, then they are candidates for inlining just like any other function.
- balls187 7y agoThank you for sharing. Would you consider linking your source code, including make files?
- ape4 7y agoIn my experience an applications specific pool works the best. Lets say a part of your programs does a bunch of malloc()s then frees... put it into a pool then delete the pool when its done.
- haberman 7y agoWe often call this "arena allocation". Wikipedia calls it Region-based memory management: https://en.wikipedia.org/wiki/Region-based_memory_management https://en.wikipedia.org/wiki/Region-based_memory_management
- nteon 7y agoCan you compare `tcmalloc` to e.g. tcmalloc dynamically loaded, or jemalloc specified with Bazel's malloc option? It is unclear from the post whether the wins are improvements from the internal Google improvements to tcmalloc post-gperftools, or to reduction in overhead from bypassing the PLT
- gok 7y agoThe big problem with malloc/new/free/delete is that the interface is way too flexible. Allowing objects to be allocated one thread and freed on another fundamentally requires a bunch of complicated bookkeeping. Particularly in C++ it's usually more productive to change your allocation strategy entirely if malloc/free is really a hot spot in your code.
- saagarjha 7y agoEh, on the fast path many allocators will just pull the block from what’s essentially a bump allocator on the allocating thread and then stick the block in the freeing thread’s tcache when it’s done with it, doing rebalancing once in a while when necessary. It’s not too horrible.