7 ms·

> 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 ge

> 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 ago
I 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 ago
Yeah 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 ago
  An arena allocator isn't going to be the underpinning of the new operator.
  - saagarjha 7y ago
    It could be!
  - enhray 7y ago
    I think it’s the other way around. Instead of redefining operator new() to allocate from an arena, user allocates memory from the arena and then constructs instance there using placement new.
    - winrid 7y ago
      Right
jeffbee 7y ago
There 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 ago
  My 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 ago
    I'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 ago
      on 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 ago
    LLVM 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 ago
  This '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 ago
      It 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 ago
I 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 ago
  This. 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 ago
Modern 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 ago
  It 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 ago
    I'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 ago
      I'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 ago
    That'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.

Ididntdothis 7y ago

I 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 ago

Yeah 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 ago
An arena allocator isn't going to be the underpinning of the new operator.
- saagarjha 7y ago
  It could be!
- enhray 7y ago
  I think it’s the other way around. Instead of redefining operator new() to allocate from an arena, user allocates memory from the arena and then constructs instance there using placement new.
  - winrid 7y ago
    Right

jeffbee 7y ago

There 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 ago
My 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 ago
  I'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 ago
    on 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 ago
  LLVM 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 ago
This '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 ago
    It 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 ago

I 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 ago
This. 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 ago

Modern 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 ago
It 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 ago
  I'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 ago
    I'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 ago
  That'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.