Hacker News Reader

Comment by mehrdadn | Hacker News Reader

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

View on HN

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.

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

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

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

And this applies to all languages, for example just because a language has a GC it doesn't mean new is the only way to do allocations.

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

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.

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

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

https://jdk.java.net/valhalla/

OWL, VCL, MFC, wxWidgets, Turbo Vision, CSet++, Motif++, BeOS, Epoch were all Java style, before Java was even born.

The old GUI frameworks I used (e.g. MFC) surely weren't that bad as you claim: they did depend on the allocations, but not dogmatically like those writing Java-inspired C++ code later or today. I remember:

They worked even in the very memory-constrained systems with some GUI elements having the number of elements that would never be able to perform what they did had they been all "new"-ed. An example: an editor having a huge number of lines, working on the computer in which the total RAM was e.g. 4 MB, which included the one needed fro the code of the OS.

The "trick" in these frameworks was to have "new" only for those GUI elements which exist in very limited number of instances. The rest was the no-"new" wrapping of the calls to the low-level code, which was C or even assembly at that time.

I am plenty sure they did, as I started using C++ for GUI code around 1992, 4 years before Java was born.

As for the MFC, not only do CString, CArray, CDocumentView and everything CSomething depend on the heap, all the COM related classes only exist on the heap.

Nowadays even more so, given the role that COM has taken as main way for all new APIs after Vista, by building the Longhorn ideas with COM instead of .NET.

Even if it looks stack allocated, it is actually an handle to a COM/UWP instance.

> CArray ... everything CSomething depend on the heap

One can have only one allocation per CArray and when using MFC one doesn't have to keep everything in MFC CStrings at all. Specifically, I've used CSomething structures with pointers to the C-style strings which were part of the single allocated pool, for example. The MFC is carefully made to allow for many such use cases, which were, as I've said, actually fundamentally necessary to allow programming efficient applications under the older memory limitations and the older processor speeds.

Specifically, MFC allowed one to use MFC classes for things like CDocumentView, but to have the "work" part of the application conveniently NOT dependent on these, and to pass to the underlying Windows Win32 C-level interfaces everything as cleanly as assembly or C would allow.

I've used that and most performant applications used something similar.

The point was about the C++ Frameworks, and their code patterns, not how we worked around their issues.

Frameworks that were the inspiration for how Java should do OOP, on a project (Oak) that initially was considering to use C++.

Also considering the programming language landscape at the time, if we leave C++ aside, it would be more correct to say Smalltalk or CLOS style then.

> considering the programming language landscape at the time, if we leave C++ aside, it would be more correct to say Smalltalk

I'm quite sure Smalltalk didn't have a "new" mapped to malloc, and also most of other stuff that C++ had the way it had. Nevertheless, Smalltalk was also never something performant, it was more "an experiment" not an environment for many commercial products.

Regarding the "landscape" you are right that there were some people that influenced the "dogma" of "how C++ should be written" that actually didn't even know C++ or the consequences of their promotion of some "OOP techniques." Horrible stuff, if you asked me, was good only for the clueless managers and buzzword catchers, but never resulted in efficient applications, where the policy was to "do as the promoters say."

Likewise, performant C++ usually looks more like the "C with classes" that's widely disliked by the "modern C++" people.

Not really, it's more trying to use constexpr better and measuring everything as well as inlining as much as you can. This leads to extra compile times which you can combat with precompiled headers. Overall C++ just wins out heavily. Not because C is worse, but because the C codebases I've looked at tend to not put code in headers.

C also has a lot of void* which prevent the compiler from doing optimizations it otherwise could. C lacks template programming, which means they will try to reuse the same containers for everything, again lowering performance. Typically some kind of list based on macros.

https://stackoverflow.com/questions/4707012/is-it-better-to-...

Just std::copy alone. I really could go on forever.

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.

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.

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

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

LLVM is capable of eliminating calls to malloc if it can prove that they don't escape the function.

Even if the allocation is large?

Have you ever seen operator new inlined in pratice? I've always seen it make a call to malloc, because I can't think of a compiler actually containing the implementation of a memory allocator inside of it…

I'm completely aware of everything you said, but it's not what I asked. I was very specifically not asking what is theoretically possible but what actually happens in practice. Because I don't see any evidence that this is actually the case in practice. For a memory allocator that has a legitimate general-purpose deallocator (i.e. ones that are reasonable replacements for malloc/free), my experience says this kind of overhead being worth optimizing is very much hypothetical rather than the reality. Of course for allocators that skip half the steps (e.g. don't bother to return memory dynamically or only work in specific cases) then the story might be very different but it's not really fair to compare them against general purpose ones?

Now I'm perfectly happy to accept my imagination/experience is just lacking and that's why I don't see such use cases, but I'm seeing multiple other top comments voicing the same concerns as I am, so I'm mostly suggesting a plausible example to demonstrate this is likely to really help convince people this might be the right thing to focus on.

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.

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)?

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?

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.

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.

> In good dynamic language runtimes, for example

I'm talking about C++, not dynamic languages?

Are you talking about implementing a dynamic language in C++? Sure, do whatever you want in that case. Seems pretty fair to >99.9(9...?)% of developers aren't doing that.

I think it's safe to say dynamic language writing is to dynamic memory allocation as NASCAR is to car acceleration. You (should) already know your metrics will necessarily differ from most other people's.

That was just an example of a place where fast path performance defined the runtime performance, as that’s how they become optimized. You can see a similar pattern when inserting keys into a hashmap, for example.

That only applies to short lived allocations in a garbage collected heap or allocation arenas that were specifically chosen on a case by case basis. Most memory allocations on the heap don't even happen in C or C++. Short lived objects exist on the stack and swapping your allocator with a different one won't change that.

That most allocations happen on the stack doesn't change the fact that most malloc implementations are still heavily optimized for the fast path. As far as I can tell the glibc implementation at least has a fast path for small allocations.

Not an expert but I don't agree. You're talking about bump allocators I assume, a nursery area. Do much of that and the TLB gets used more, which can get expensive.

If it's not bump-allocating then you have to traverse data structures to find a suitable block of free mem. At the other end, each alloc() must get a free() and reclaiming and unifying memory to prevent fragmentation isn't cheap I guess.

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.

An arena allocator isn't going to be the underpinning of the new operator.

It could be!

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.

Right

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.

Reply on news.ycombinator.com