175 points•ibobev•5 days ago•157 comments•

157 comments

asveikau3 days ago
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.
tialaramex3 days ago
This is partly because the C++ stdlib looks like they've given you all the basic tools you need - unlike the C standard library - yet in fact many of these tools are hopelessly obsolete. It's not quite PHP's "fractal of bad design", these are all reasonable tools... if it's 1985. The linked lists make sense on hardware where five pointer fetches and five consecutive memory reads cost roughly the same - 1985 hardware.

The growable array type std::vector<T> is least impacted by these archaic choices out of the tools in the box you're likely to reach for. So it will make sense very often to choose this type first.

adrianN3 days ago
Linked lists are great data structures for the use cases where you need their properties. It’s just that you don’t encounter those scenarios very often in most kinds of software.
socalgal23 days ago
vs what? What languages make these choices better?
smj-edison3 days ago
It's interesting because I tried to follow this advice when I wrote my own interpreter, but either 1. I just had a bad intuition and it's gotten better, or 2. It's trickier with interpreters when you have thousands of objects.

For example, since I allowed for objects to be shared between threads, I decided to use struct of arrays so the reference count, metadata, and value would be stored in separate cache lines. This ended up hurting me because object initialization touched three separate cache lines (obvious in hindsight, but the advice of using SoA failed me here). I also heard that you want to pack your values as tight as possible, so I used a packed string index, but then I ended up with integer division to unpack the string (also a mistake, but again the advice failed me). I used a custom allocator to avoid indirection with lists (list items were allocated directly after the list head), but then I had heap fragmentation and the implementation complexity exploded.

Anyways, I am now happily using two to three levels of indirection in my data structures, large structs, and malloc for individual objects, and it's still been faster in my end to end testing. So maybe this is unique to interpreters, and maybe I could have done it better, but the suggestions don't automatically apply in my experience.

someonebaggy3 days ago
"Good advice tends to come with a rationale so you can tell when it becomes bad advice" - Raymond Chen

I'd say the rule was followed in this case - the rationale of SoA is to reduce cache misses when iterating all objects and only using some of the attributes, which is something games do all the time, but it's bad if you are always accessing one object at a time. Maybe an array language interpreter would have luck with SoA.

renox3 days ago
'data oriented' doesn't mean 'just use SoA' it means use data structures which correspond to your data access pattern. Which is quite difficult to know in complex applications and which can change..
carlmr3 days ago
>This ended up hurting me because object initialization touched three separate cache lines (obvious in hindsight, but the advice of using SoA failed me here).

I mean this is kind of what happens with any advice that has nuance to it, that's not carried with the advice.

E.g. if you have a point in 3D space with x, y, z coordinates. Array points as SoA of individual dimensions makes sense only if you do a lot of averaging and such on the individual dimensions.

If you mostly use the 3 coordinates together, SoA will have bad caching behavior.

So the better advice would be to try to keep things that are used together in the same cache line, whether it's on dimension or all 3. Usage makes the difference.

spider-mario3 days ago
Or even, stuff it into several parallel vectors (structure of arrays instead of array of structures).
stackghost3 days ago
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.

Pannoniae3 days ago
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.

nnevatie3 days ago
> C++ is fast enough

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.

Agentlien3 days ago
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.

asveikau3 days ago
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.

djmips3 days ago
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.
bluGill3 days ago
While this advice isn't wrong, it is misleading. In my benchmarks std::map beats vector after 9 elements. Less than that and linear search is better but branch prediction and cache loading is very good.

Run your own benchmarks on your own data of course. Also map is not considered the best key value store.

mandarax83 days ago
Because in your benchmark all std::map nodes were allocated in succession, most likely being placed in adjacent memory locations...

This likely won't be true in a real application with a non-trivial allocation pattern.

danbolt3 days ago
I’ve definitely been on teams where they ran the numbers, and found that they were mostly working with smaller containers, and std::vector was the way to go.

If you’re down to that sort of decision-making, you have to measure.

someonebaggy3 days ago
That is not a plausible result, sorry. Perhaps you're using the painfully slow MSVC debug mode vector?
Jeaye3 days ago
While we're here, has anyone seen any resources related to data-oriented design when GCs are involved? So much of data-oriented design is arena-focused, but that's not always possible, when the lifetime model of the code requires a GC (for whatever reason).

I feel like the DoD movement is a slow-moving, but big, change through how systems programming is done, but that there's still insufficient material for how to do this in different scenarios. I would really like to apply this more to my areas of work, which are also in C++, but there seems to be a gap between what they're presenting and how it can be applied.

More specifically, I'm using C++ to build a dynamic programming language runtime for a Clojure dialect. That runtime is required to be garbage collected, type-erased, and highly polymorphic. So I surely can't just SoA or AoS everything. Yes, I can pack my data, and I can avoid the GC whenever possible, both in compiler/runtime code and in generated code via escape analysis. But what about everything else, which is the 80% or more of the system? It could be that this runtime is too far at odds with DoD, but I generally see things as a gradient rather than black and white.

smj-edison3 days ago
Not sure if this is relevant, but I was in a discussion about heap layout a while ago, and one of the commenters was talking about how they were able to have classic lisp-style linked lists with decent performance by using a copying garbage collector: https://ziggit.dev/t/memory-layout-suggestions-for-tcl-inter...

Or were you referring more to all the intermediate allocations that aren't the object heap? V8's zones are interesting in this area, because they're like an arena, except that they're only partially reset when a zone ends, so zones can nest inside each other.

MaxBarraclough3 days ago
There's no mention of branch prediction, or context switching, or synchronisation. Depending on what you're doing, they could be very consequential. There's only very brief mention of parallelisation with threads and with SIMD.

High-performance programming is a big topic. The scope is far too broad for a single blog post, which naturally gives only cursory discussion of C++ and computer architecture. The article isn't bad considering, but I do think it's the wrong format. A blog series, or even a book, would be more fitting.

creata3 days ago
They're a bit old and missing some details, but I like Agner Fog's manuals.

https://www.agner.org/optimize/

MaxBarraclough3 days ago
I've not read Fog's Optimizing software in C++ but I see it's freely available there as a PDF (182 pages). Looks like a great resource on these topics.

https://www.agner.org/optimize/optimizing_cpp.pdf

glouwbug3 days ago
Learn which instructions SIMD nicely (sqrt / fabs, etc). Use ternaries in loops for masking. Use trig identities and lookup tables (don't recompute sin(3t) when you can use two vector multiples using a table of sin(t) eg. sin(t) * sin(t) * sin(t)). Use divisible constexpr constants in loops to eliminate the SIMD tail. Be careful with type casts and floats. `float x; x += 0.5` will introduce *cvt instructions even if the compiler statically knew better otherwise (use 0.5f). Compile with --fast-math and friends so errno doesn't invalidate your SIMD pipeline.
creata3 days ago
Most applications (including most applications that care about numerical performance) should not use -ffast-math.
MaxBarraclough3 days ago
That has a similar problem to the article, it's trying to fit far too much into too small a format.

What you've written mostly makes sense to someone who already has a solid understanding of SIMD and of C++ (although I can't say I follow all of it), but the target audience is people who don't. For them, each point needs a much lengthier explanation.

asveikau3 days ago
This seems like domain specific advice.
Jeaye3 days ago
Do you have any recommended essential reading for this?
MaxBarraclough3 days ago
I'm no expert in this stuff but:

creata's comment [0] mentions the works of Agner Fog, which seem very good, and are freely available.

I haven't read C++ High Performance [1] but it looks like it covers the sorts of topics you'd expect, although it looks like it doesn't cover computer architecture in detail e.g. branch prediction. There are books on that too, of course.

[0] https://news.ycombinator.com/item?id=49868657

[1] https://www.packtpub.com/en-us/product/c-high-performance-97...

hn_submit3 days ago
I write in C++ almost every day but never have the need to optimize for speed. Even when you write straightforward code it's already blazingly fast.
gbin3 days ago
It is probably very domain specific. In robotics for example everything is a zero sum game: CPU, memory bandwidth, GPU, battery life etc ... So it is really a topic, probably true for anything embedded actually. Some other offline applications: HFT, Telco etc.. I wish the GUI apps devs respect more the laptop resources they are running on, don't get me started on the 4 instances of chrome I need to run just for discord, signal etc ...
serbuvlad3 days ago
GUI engine developers need to trade EVERYTHING for execution time, otherwise JavaScript would simply not be fast enough to handle modern applications.

If your device has enough resources to power V8, modern GUIs are certainly very pleasant and snappier than a more minimal GUI like HN. Otherwise they are horrendous and very laggy.

flowerbreeze3 days ago
When writing code for end-user applications, I think it's mostly true. When it's writing code for a database engine, a game engine, a 3d renderer, or anything else that involves heavy data processing, optimization is the core "thing" often and it might not even be a good enough solution without it. Although, a lot of time even then C++ is good enough even then when picking reasonable data structures to represent the data.
hn_submit3 days ago
These are what I like to call "infinity applications" where the need for speed is essentially infinite.

Even if you write them in hand-optimized assembly they would still clamor for more speed.

8n4vidtmkvmk3 days ago
Definitely need to optimize a bit for games and huge scale web apps. We've been finding big optimizations in our app recently. App works without them because we can scale horizontally but cutting CPU usage by 30% by eliminating redundant work and reducing copies of big objects? Why wouldn't we want to do that? This isn't even fancy algorithm stuff, mostly just shoddy initial implementations by 100s of eng working on a codebase over 7 years (not even that old). Stuff like that creeps in.
senderista3 days ago
Then why are you using C++? Java/C#/Go are already fast enough for general application development. Why would you accept the footguns if not for performance?
bluGill3 days ago
In my case, about 5% of our code needs the power of C++. Mixing C++ with any other language is a huge pain. Even if we were using C, mixing C with anything else is a pain, and that's despite being the most supported FFI.

Note that we started our project before Rust was an option. These days I would certainly look at rust to see if that would cover our 5% of the needs but now we have a lot of C++ and mixing rust with C++ is a pain.

palata3 days ago
Sometimes it's about the libraries. E.g. writing Computer Vision is nicer in C++ right now (IMHO) because most CV libraries are in C++.

Similarly I like to do video stuff in C just because I call gstreamer/ffmpeg directly in C, rather than having to bridge everything.

oso2k3 days ago
This follows Rob Pike’s 5 Rules for Programming

https://web.archive.org/web/20250201145327/https://users.ece...

chombier3 days ago
A few weeks back there was this nice little database query language as a language library [1] posted on HN, with the constraint that everything had to be 6NF.

At the time I thought this would naturally fit in a data-oriented design/ECS system to run complex queries. I wonder whether anyone has tried this before and whether this actually works in practice?

[1] https://prela-lang.org/tutorial/

wolfi13 days ago
thanks, today I learned there are NFs beyond 3NF

Read the full thread on Hacker News →

Related stories