This article reminds me of performance advice I was starting to see in the 2000s decade. Basically it was to not introduce a bunch of pointer heavy data structures to get lower algorithmic complexity. Stuff it all into a vector. You will use some algorithms that the computer science textbook will say it's slower, but if it fits all in cache it doesn't matter. The cache misses following pointers all over town hurts you more.
I too am in the "premature optimization bad" camp.
Beyond the low-hanging fruit like ensuring you aren't creating O(n^2) complexity by accident, I think C++ is fast enough/has mature-enough compilers that by the time you're worrying about cache hits materially affecting performance, you're probably also sufficiently staffed and capitalized to pay people to A/B test that performance.
I don’t understand the question. Are you implying someone cannot know how to do something in a particular codebase unless they’ve already done it on that same codebase?
To be a good performance optimize yes,you need to have done it a few times to be good at it and have acquired not just the skill but the discipline and taste.
More than having done it a few times though, what is more important is to have thrived in a space that is welcoming of intellectual curiosity and play in matters of performance. That's how one becomes good at it.
I don't know if this advice is strictly advocating to avoid premature optimization. Many problems are modeled intuitively with lots of tiny allocations and pointer heavy structures, and this advice is saying to avoid that.
I think it's more like: prioritize cache locality over big O compexity.
I don't really agree because it's so hard to reform a full application that's been written without regard to performance, after it's been written. You really need to pay attention from the beginning.
1. Compilers barely do even basic optimisations such as interprocedural register allocation when faced with non-trivial code.
You often also need the most aggressive optimisation settings, LTO or even PGO enabled for many of these.
2. Virtuals are, with the exception of PGO, mostly a black box i.e. you get a hard optimisation boundary, no inlining at all.
3. The C++ standard library is usually comically slow (yes, even compared to Java/C#/the likes) so if your project uses std::vector and the such instead of specialised libraries, you've already lost at the beginning.
4. If you don't pay attention to performance from the get-go, the approximate amount of autovectorisation you'll get is close to zero. Some compilers are better than others (Clang>MSVC for example) but I've seen codebases with 8 figures of LoC where the number of vectorised divides/multiplys was like less than ten when you dumped the object listing. In the whole program.
5. Since aliasing and other optimisation barriers (you didn't use restrict or manually hoist, did ya?), it's not uncommon for large C++ programs to spend a third of their runtime doing atomic increments because shared_ptr is supposedly cheap and who cares about lifetimes anyway.
6. If you're targeting Windows, the default new operator / malloc is also comically slow. Luckily that one is fairly easy to fix with installing mimalloc and deploying the hijack dll, but the negative effects on cache by the fragmented allocations is also significant.
Regarding 5., I have fortunately never seen a program overusing shared_ptr like that, but when I recently had a performance-sensitive use case for shared_ptr, I found boost::local_shared_ptr with non-atomic reference counting.
>If you're targeting Windows, the default new operator / malloc is also comically slow. Luckily that one is fairly easy to fix with installing mimalloc and deploying the hijack dll, but the negative effects on cache by the fragmented allocations is also significant.
Surely nobody outside microsoft is doing serious work targeting Windows any more are they? Isn't that a dead platform? I read somewhere a while back they're now below 60% market share.
There's an enormous amount of serious work targeting Windows. For example, the video game industry still has a very strong PC user base and is very concerned with performance.
No I'm not. And it's not just MSVC-specific either, they're just not very good.
std::vector doesn't have trivial relocation so any type with a destructor ends up doing elementwise destruct+construct instead of a memcpy.
std::map and std::list are memes and if you use them you're giving your CPU the 1995 treatment with all that pointer chasing.
You thought std::unordered_map is better? Well, actually not because node stability, so it's still chained-bucket, you almost always want to use a flat map like boost::unordered_flat_map or the abseil/eastl version.
<random> is hard-to-use and isn't very performant, std::regex is "you might as well write it in Python and it'd be faster", <iostreams> is virtual calls galore, both the formatting and the stdio functionality are slow.
The conveniently-named std::function is a very general device resulting in a heap allocation and usually a virtual call, there's specific optimisations but don't rely on it.
The STL string manipulation functions are also usually slow, they check the locale for string manipulation rules.
The floating-point functions set errno preventing vectorisation and emitting branches in your straight-line float code unless you use fastmath (the thing people tell you never to do) or one of the more fine-grained compiler-specific switches to turn it off.
std::shared_ptr is Arc<T>, not Rc<T> and eating the cost of atomics can add up in many situations especially with all the other memory traffic going on.
std::variant and std::visit are also not very fast either.
std::filesystem as a whole also has several pain points like iteration which is like a magnitude slower than the native APIs, std::chrono isn't much better either
std::error_code sounds like a simple integer or even a struct.... lol no guess what, more virtual calls
Your mention of eastl gave me flashbacks to my time at EA (2015-2019). While the library was great overall, there were some very weird bugs. In particular an implicit copy constructor for eastl::optional which caused crashes due to it not considering whether it was holding a value or not. Which always struck my as such a bizarre bug for that particular type. Looks like that was patched in later versions.
Regarding 3: depends on what you're doing with it? Take std::vector: we have a codebase where pretty much everything is allocated once but we still want bounds checking on that memory. So we have a lot of std::vector in those places. What would a specialised library change there?
1. I'm not familiar with the hardened stdlib stuff except for the msvc debug runtime but if you have a solution for this, skip this one. You presumably want boundschecking (and throwing/failing hard) or at the very least, logging out of bounds accesses.
2. A non-inlined grow. If you have large collections you modify often, you want a vector implementation where the reallocation is out of line and the rare case. All the STLs treat it as a normal method and have inlined by codegen.
3. Trivial relocation support so you don't need to destruct objects where there are no pointers inside or external objects pointing to them.
In your case it's probably not as relevant/important, yes
You really aren't in the "premature optimization bad" camp you just don't realize you optimize all the time but justify it as obvious. The main thing to know is that what is 'obvious' isn't unless you are profiling.
"Good design" is not what I would call optimization.
As a contrived example: there are specific cases when a particular non-quicksort algorithm is optimal. In almost all real world scenarios, though, you're just going to say fuck it and use quicksort until profiling determines that the sort is the bottleneck.
Unless you already have specific knowledge that your data comes in a particular shape, defaulting to quicksort is good design (IMHO). Worrying about pathological sorting before you've seen benchmarks is premature optimization.
This depends so much on what your work and industry is. I hear A/B and immediately think this is alien and inapplicable to me.
I work in game development and for the last six years I've spent most of my time specifically on optimization. A lot of that effort has been focused on cache behaviors. Not because it's fun, but because it's often the difference between being able to ship the game on weaker hardware (e.g. Nintendo Switch) or not.
There are multiple areas of work, where C++ can be considered a glue language. The high-performance work is then done in explicit SIMD (intrinsics, ISPC, etc.) and/or GPU-targeting languages such as CUDA or Vulkan.
In these areas of work, high performance is part of the design and not something that can be easily added as after-thought.
Also, relying on optimization features such as compiler auto-vectorization is way too finicky - your hot-loop performance may completely break without anyone noticing by someone changing a trivial-looking part of a loop.
asveikau · · focus · HN ↗
stackghost · · focus · HN ↗
Beyond the low-hanging fruit like ensuring you aren't creating O(n^2) complexity by accident, I think C++ is fast enough/has mature-enough compilers that by the time you're worrying about cache hits materially affecting performance, you're probably also sufficiently staffed and capitalized to pay people to A/B test that performance.
srean · · focus · HN ↗
stackghost · · focus · HN ↗
srean · · focus · HN ↗
More than having done it a few times though, what is more important is to have thrived in a space that is welcoming of intellectual curiosity and play in matters of performance. That's how one becomes good at it.
asveikau · · focus · HN ↗
I think it's more like: prioritize cache locality over big O compexity.
jeffbee · · focus · HN ↗
Pannoniae · · focus · HN ↗
2. Virtuals are, with the exception of PGO, mostly a black box i.e. you get a hard optimisation boundary, no inlining at all.
3. The C++ standard library is usually comically slow (yes, even compared to Java/C#/the likes) so if your project uses std::vector and the such instead of specialised libraries, you've already lost at the beginning.
4. If you don't pay attention to performance from the get-go, the approximate amount of autovectorisation you'll get is close to zero. Some compilers are better than others (Clang>MSVC for example) but I've seen codebases with 8 figures of LoC where the number of vectorised divides/multiplys was like less than ten when you dumped the object listing. In the whole program.
5. Since aliasing and other optimisation barriers (you didn't use restrict or manually hoist, did ya?), it's not uncommon for large C++ programs to spend a third of their runtime doing atomic increments because shared_ptr is supposedly cheap and who cares about lifetimes anyway.
6. If you're targeting Windows, the default new operator / malloc is also comically slow. Luckily that one is fairly easy to fix with installing mimalloc and deploying the hijack dll, but the negative effects on cache by the fragmented allocations is also significant.
ahartmetz · · focus · HN ↗
stackghost · · focus · HN ↗
Surely nobody outside microsoft is doing serious work targeting Windows any more are they? Isn't that a dead platform? I read somewhere a while back they're now below 60% market share.
Agentlien · · focus · HN ↗
someonebaggy · · focus · HN ↗
Pannoniae · · focus · HN ↗
std::vector doesn't have trivial relocation so any type with a destructor ends up doing elementwise destruct+construct instead of a memcpy.
std::map and std::list are memes and if you use them you're giving your CPU the 1995 treatment with all that pointer chasing.
You thought std::unordered_map is better? Well, actually not because node stability, so it's still chained-bucket, you almost always want to use a flat map like boost::unordered_flat_map or the abseil/eastl version.
<random> is hard-to-use and isn't very performant, std::regex is "you might as well write it in Python and it'd be faster", <iostreams> is virtual calls galore, both the formatting and the stdio functionality are slow.
The conveniently-named std::function is a very general device resulting in a heap allocation and usually a virtual call, there's specific optimisations but don't rely on it.
The STL string manipulation functions are also usually slow, they check the locale for string manipulation rules.
The floating-point functions set errno preventing vectorisation and emitting branches in your straight-line float code unless you use fastmath (the thing people tell you never to do) or one of the more fine-grained compiler-specific switches to turn it off.
std::shared_ptr is Arc<T>, not Rc<T> and eating the cost of atomics can add up in many situations especially with all the other memory traffic going on.
std::variant and std::visit are also not very fast either.
std::filesystem as a whole also has several pain points like iteration which is like a magnitude slower than the native APIs, std::chrono isn't much better either
std::error_code sounds like a simple integer or even a struct.... lol no guess what, more virtual calls
Agentlien · · focus · HN ↗
stinos · · focus · HN ↗
Pannoniae · · focus · HN ↗
2. A non-inlined grow. If you have large collections you modify often, you want a vector implementation where the reallocation is out of line and the rare case. All the STLs treat it as a normal method and have inlined by codegen.
3. Trivial relocation support so you don't need to destruct objects where there are no pointers inside or external objects pointing to them.
In your case it's probably not as relevant/important, yes
djmips · · focus · HN ↗
stackghost · · focus · HN ↗
As a contrived example: there are specific cases when a particular non-quicksort algorithm is optimal. In almost all real world scenarios, though, you're just going to say fuck it and use quicksort until profiling determines that the sort is the bottleneck.
Unless you already have specific knowledge that your data comes in a particular shape, defaulting to quicksort is good design (IMHO). Worrying about pathological sorting before you've seen benchmarks is premature optimization.
djmips · · focus · HN ↗
stackghost · · focus · HN ↗
Agentlien · · focus · HN ↗
I work in game development and for the last six years I've spent most of my time specifically on optimization. A lot of that effort has been focused on cache behaviors. Not because it's fun, but because it's often the difference between being able to ship the game on weaker hardware (e.g. Nintendo Switch) or not.
nnevatie · · focus · HN ↗
Yeah, it's really not.
There are multiple areas of work, where C++ can be considered a glue language. The high-performance work is then done in explicit SIMD (intrinsics, ISPC, etc.) and/or GPU-targeting languages such as CUDA or Vulkan.
In these areas of work, high performance is part of the design and not something that can be easily added as after-thought.
Also, relying on optimization features such as compiler auto-vectorization is way too finicky - your hot-loop performance may completely break without anyone noticing by someone changing a trivial-looking part of a loop.