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.
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.
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.
You say not very often, but the true usefulness is almost never. Extremely little. One in a trillion times. Even when you think linked lists would be faster, they usually aren't.
Naturally the mind races to think of where linked lists are used.
The Linux kernel uses them, at least some of the time they're used with their lock-free RCU pattern. I'm not sure if it's for performance reasons though, I think they're using it in contexts where correctness requires the absence of blocking operations.
I'd expect a lock-free non-linked-list solution would also be possible, but I don't know enough to state that definitively.
Linux is definitely a mix of "It's a linked list because multiple CPUs are simultaneously doing swap operations on the list while it is still in use, with linked lists that's an atomic operation whereas if we did something else it would need a lock" and "C does not provide a growable array type, so I used a linked list 'cos that's easy to write in C"
My guess for the 0.x releases in particular is that there's a lot of the latter and as Linux goes from "Like Minix but I made it in my bedroom" to Serious Business™ more and more of the former.
> My guess for the 0.x releases in particular is that there's a lot of the latter and as Linux goes from "Like Minix but I made it in my bedroom" to Serious Business™ more and more of the former.
In the early releases of Linux, the cache locality argument wasn't as prominent an issue on the hardware of the day. So the computer science textbook argument of O(1) inserts and [if you have the node pointer already] removals was more compelling.
I'm not sure I can answer that about their malloc, now and in the past.
But your question reminded me of another aspect of linked lists in the Linux kernel: unlike a lot of high level languages, there isn't an extra allocation for a node structure. The node structure is a member of the structure being linked.
Often the structure being linked might be something like a reference counted heap object, so the question of adding an extra member to store the next pointer is not a big difference.
> unlike a lot of high level languages, there isn't an extra allocation for a node structure. The node structure is a member of the structure being linked.
That's good, but it seems like how-hanging fruit. Boost offers intrusive_prt for this. [0]
make_shared goes half way, and performs a single allocation to return a shared_ptr to a new object. It eventually made its way from Boost to the standard. [1][2]
See also [3] which contrasts the two. (As you can imagine, intrusive_prt is slightly more efficient.)
Linux uses linked lists because they can reserve a fixed amount of memory for the linked list cells inside the element itself (intrusive list) and they can be allocated non-continguously aka you can freely extend them as you like. This is useful if you want to reserve a chunk of memory statically. This guarantees that you can do work before your allocator is online and then when the allocator is online, you can transparently extend your memory with further allocations.
You can also take independent modules that provide their own statically allocated memory and chain them together using the reserved linked list cells. (think kernel modules)
This is a bit of a wishy washy explanation because I work on a highly adjacent project that has similar constraints but I never looked at the kernel source (strictly working with statically allocated memory during startup).
It's pretty useful, just not as a "sequential container" as people are usually taught. And definitely now with an interface C++ provides. There are two main cases for linked lists:
1. When you need a persistent version of sequential data structure. I.e. you need addition not to change the previous version of list. Very useful in traversals which can fail and/or have multiple routes. C++ list obviously fails here because it's a mutable data structure and each addition is mutation. The proper interface is cons(head, old_list) -> new_list, where old_list exists after new_list is constructed.
2. When you need the values be never moved in memory. Aka intrusive lists. Can be optimized for more cache friendliness by having lists of big chunks of values instead of just lists in some cases. Useful in operating systems and many low level apps. Alternative is usually a vector of pointers which still gives you indirection.
I'm not sure I follow the second point. Array-based solutions are able to guarantee that an element is never relocated, it's just that std::vector doesn't offer this guarantee. The Boost libraries offer this though, they call it stable_vector.
> Array-based solutions are able to guarantee that an element is never relocated
This is an array of pointers, I mentioned it in the post you're replying to. It completely obliterates the "cache-friendliness" argument, making it worse than linked list (now you have same indirection overhead plus overhead of copying minus benefits of being able to CAS your value atomically into a list making it lock-free)
Yes you're right. Here's an alternative that behaves the way I had in mind but doesn't support deletions, as handling deletions the way std::vector does would naturally mean relocating elements. [0]
I figure it would be possible to add support for deletions, but it would cost us: we would lose guaranteed contiguous placement of elements with neighbouring indices, and (unless no deletions are made) we'd need a private data structure to correspond vector indices to addresses, and to determine where to locate new elements. This would of course bring us back to continually paying the price of indirection overhead, and simple lock-free modifications would not be possible.
My completely unsupported guess is the cache behaviour wouldn't be too bad unless deletions (of elements that aren't at the end of the vector) are common. I imagine the cache behaviour of a linked list must depend greatly on what the allocator gives you. Presumably using a pool, specific to that particular list, could help there.
I suspect that the performance advantage of allowing the CPU to cache-prefetch many pointers at once (vs. having to follow a pointer to get the next pointer, in the case of the linked list) still makes a vector of pointers better than a linked list for sequential traversal.
This is wildly overstating it. Yeah, I agree, they're much less often the right choice compared to a good-ol' growable array, but they have lots of uses in high-performance code and concurrent code, and they're building blocks in lots of other data structures. Like, in a bucket hash-table, the buckets are linked lists, in a LRU cache you interleave a hash table and linked list, std::hive is a linked list of chunks of elements, etc. Anything that has ever had to deal with memory pooling/allocation uses free-lists which are linked lists. And on and on and on.
Firstly, Rust doesn't consider "array" a library type here, in C++ the language has built-in arrays but they're very poor because they are the C arrays - so you use the library feature to get good arrays. In Rust they... just fixed the language, because duh.
Next thing you'll notice is that C++ has lots more of these types, about twice as many. I stopped at C++ 23 because in C++ 26 they added even more. These are a significant maintenance burden and of course having more means in practice maintenance gets worse. But this could be good if these types were all high quality and kept that way.
All of the C++ unordered containers are the same crap hash table design but with slightly different parameters. The Rust HashMap and HashSet are Swiss Tables though they do not promise that and if a better design comes along they will probably switch. C++ can't change the design because the API welds them to a very specific shape for this data structure, a shape which delivers bad performance on any vaguely modern hardware.
std::deque is the most horrible surprise. A modern programmer who has thought about it at all is expecting a type like Rust's VecDeque. Generalise the amortized growable array from the language to use it as a ring buffer. Cheap push & pop at both ends, canonically use it as a FIFO but also practical in lots of other situations. But that's not what std::deque is at all, instead inside it's an array of links to small arrays. On MSVC it's effectively a linked list again because those inner arrays contain only one item due to ABI considerations.
std::set and std::map are very principled red-black trees. I say principled because in practice this is too expensive on modern hardware because (say it with me) it spends too long chasing pointers up and down your tree. Rust's choice here in BTreeMap and BTreeSet packs more data in each "node" on the tree, which makes the big-O worse but the practical performance better. Figuring out how to best do this for the general case is an active area of research but "I bet a pure red-black tree will be fast" is not a good guess for the past several decades.
Finally std::forward_list and std::list are the singly and doubly extrusive linked list types. The thing you most likely have seen in some high performance software is an intrusive linked list, and C++ doesn't provide those. In an intrusive linked list each item in the list itself links to where the next (and for simple double links also the previous) item is, so the item needs to know it's in a list [in some systems more than one list, thus more than one set of links]. C++ provides extrusive linked lists where those links live in a separate object and so the items in the list don't know about this at all. Rust provides only a doubly-linked extrusive list exactly like C++ std::list, but again, this almost certainly isn't what you wanted, you most likely do not need a linked list and if you do have a good reason for a linked list you probably want an intrusive linked list.
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.
"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.
'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..
>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.
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.
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.
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
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.
>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.
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.
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.
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.
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.
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.
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.
Actually it really depends, because allocators can also be kind of smart (and you don't have to use the default allocator).
And then, on the other hand - I really doubt GP's map beats a vector, with all of those pointers bins and stuff, in a non-contrived benchmark with 10 elements.
Finally - it's not either-or: There are better hash maps whose memory is sequentially allocated and/or are otherwise cache-aware. And there are data structures geared towards parallel execution on multiple threads; and towards SIMD; etc. etc.
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.
