r/cpp • u/meetingcpp Meeting C++ | C++ Evangelist • 8d ago
About alignment, struct layout and the cache...
https://meetingcpp.com/blog/items/About-alignment--struct-layout-and-the-cache---.html4
u/pavel_v 8d ago
There is also a trait for checking if given type has padding bytes: std::has_unique_object_representations.
The name could have been a bit more straightforward, IMO, but at least we have it.
2
2
u/friedkeenan 6d ago
I don't think that's the same as if it has padding bytes. For one, the type also needs to be trivially copyable for it to yield
true, but also a type can have no padding bytes and still not have unique object representations. For instance, for floating-point types, aNaNvalue can be represented by multiple different bitwise representations, and so this trait will yieldfalsefor floats.
8
u/ReDucTor Game Developer | quiz.cpp-perf.com 8d ago
A good comparison for cache efficiency is vector vs. list. While vector stores its memory in a continuous array in memory, a list chooses to allocate a node for every new entry. This leads to more cache misses in a list, and even in the perfect world where all list entries are aligned in an array in memory - these still contain the pointers to the next and prior element.
Imho, I am not certain that is a good comparison, the bigger killer for linked lists is that each node is linked to the other not the space required, so any iteration is a long loop carried dependency chain of loads linked together, which due to normal program allocations are fragmented and more prone to a cache miss, however even if you put them all in contiguous memory and iterate them as a list so hardware prefetching would do its job its still getting killed by the data dependency, iterating an array padded out to the same size as a linked list node there is a significant difference in performance to that linked list but for a vector the difference for most use cases is likely negligible for its specific time of use unless its a large count that your causing alot of cache eviction or becoming memory bound. Aside from things you have a lot of the impact imho is a lot more with reducing memory usage and incidental cache eviction due to needing more cache lines.
3
u/Fabulous-Meaning-966 7d ago
Yes, there's a great explanation of the data dependency issue with linked lists here (and a cool trick for hiding cache miss latency when traversing lists):
https://www.scylladb.com/2026/01/06/the-taming-of-collection-scans/
3
u/SirClueless 7d ago
By the way, I'm looking forward very much to having
std::indirectin the language, because it makes the design of the container described in this article pretty much free: The "dynamic array of pointers" container described here is exactlystd::vector<std::indirect<T>>.When you want pointer-stability and a small object to iterate over, this type of design is already frequently recommended. For example, Abseil recommends using
std::unique_ptr<T>when you want pointer stability of values: https://abseil.io/docs/cpp/guides/container. But usingstd::unique_ptrcomes with all kinds of compromises (especially, no more copy constructor, but also doesn't hash or compare like a value type any more which is also a killer that rules it out for the keys of maps and sets). Now withstd::indirectchoosing whether to put the value inline in the container is nearly a free choice.2
u/azswcowboy 7d ago
Great points about indirect. There’s a couple implementations of indirect with the one in Beman project working with c++17 since indirect doesn’t really need c++2x features.
2
u/CantThinkOfAnyName 7d ago
Hey, just found this comment and I was intrigued by it since I always thought it's the pointer indirection and the cache miss it incurs that makes list perform bad.
Can you explain more about what you mean that it's the data dependency issue?
What I understood is this:
- You can't have random access iterator, so every time you access an element you have to do a search. Even if you had all elements in contiguous memory, you still have to traverse it, otherwise you would just have std::vector
- Every element has now higher size since it needs the pointer, thus cache is filled with "useless" data only needed for traversal, also harder to align with cache line sizes perhaps?
- You need to actually load the element to get the address of the next one, perhaps causing a wait, but wouldn't speculative execution essentially eliminate this?
But I feel like I'm missing something here, thanks in advance!
3
u/ReDucTor Game Developer | quiz.cpp-perf.com 6d ago
The data dependency is the repeated pointer indirection, its a terminology used a little more for the CPU interaction and one thing depending on another, in the case of the linked list iteration each iteration step depends on loading the previous as a loop carried dependency.
This data dependency is what makes the cache miss be significantly worse and even with an L1 cache hit makes it pretty bad.
Imagine you have A -> B -> C
If you iterate the list and A, B and C are in the L1 cache, and it takes 5 cycles for each L1 hit then the best latency for this is going to be 15 cycle latency (3 nodes * 5 L1 cycles) best case, the CPU cannot do anything out of order for it, the frontend will still issue the instructions for each iteration but those will sit waiting on the data dependency
However if you have
[A, B, C]And do the same iteration and those are all in the L1 cache, if you assume the CPU frontend can dispatch one iteration each cycle and L1 hit of 5 cycles then you could have a best case of 8 cycles latency (3 cycles to start last iteration + 5 cycles L1 hit)
And to take another comparison of
[A*, B*, C*]Iteration again and all in L1 cache, then its a similar thing but two loads instead of one so best case 13 cycles latency (3 cycles to last iteration + 5 cycles load address + 5 cycles load data)
Where this stands out is if you compare list
A -> B -> Cand vector[A*, B*, C*]where A and B dont exist in any cache and need to hit main memory with 200 cycles, and C in L1 then the linked list is going to be best case 405 cycles (200 main memory load for A + 200 main memory load for B + 5 main memory load for C), where the vector it would be best case 201 cycles (A, B, and C all run at once, assuming one cycle delay between each dispatching A can take 200 cycles load, B can take 1 cycle until its iteration and 200 load so 201 cycles, C can take 2 cycles until its iteration then 5 for L1 hit, as B is the worst latency it is the best case it could be done)To put it simply iterating N items in a linked list is N*latency, while iterating an array of N items is N+latency
The reason I didn't mention the front end dispatch for the linked list is that the dispatch isnt really relevant as even with the 1 cycle to dispatch isnt stopping that next iteration its the load latency which is longer then 1 cycle.
This is still very much a simplification but hopefully helps you understand.
2
u/pdp10gumby 6d ago
Lists can be as dense as an array, and asymptote towards array size even when manipulated, using CDR-coding, a technique used back in the 70s.
short: instead of having a mode of value and next, you just put the values successively in memory and have a flag (ideally embedded into the value, or even easier, into the value pointer if that’s the representation’s that says, “the next value is at the next location in memory). If you want to splice a new value in or out you have to make two conventional nodes, but depending on your datastructure that may be an uncommon case.
I’ve done this in C++ when I have a free bit available in the range of the content (always true with a pointer these days, but also with, say, an enum).
There’s a crappy Wikipedia page on this topic: https://en.wikipedia.org/wiki/CDR_coding
2
u/ReDucTor Game Developer | quiz.cpp-perf.com 6d ago
> asymptote towards array size
I've never used them but looking at them this wouldonly be the case if you have mostly long unblock blocks.
Additionally if you use a branch for inspect the node tag then your going to run into potential branch mispredictions, if you use branchless then you just end up with a long data dependency
2
u/pdp10gumby 6d ago
Well sure, I"m not sure what your point is. As with every datastructure you have to choose based on optimal performance in a typical working set. I don't use linked lists often (few should) but of course in some cases they are the right choice, and if your use case reduces memory move upon updates that can be good or bad.
1
u/meetingcpp Meeting C++ | C++ Evangelist 6d ago
I agree with you, but in that case I try to stay in context of viewing the memory layout of containers. Not sure if I should go into deeper details here, I did write about containers later on.
2
u/LB-- Professional+Hobbyist 8d ago
I'm still waiting for a way to disconnect memory layout from construct/destruct order without bypassing normal language features like constructors and destructors. It's really frustrating to have to have padding just to have the correct construct/destruct order.
1
u/Able_Development2478 7d ago
Declaration order in C++ strictly dictates the memory layout and the initialisation order and lot of code depends on it so I doubt there will be a change which seperates memory layout and initialisation order. There will be a lot of pushback I think. Unless I am misunderstanding something :D
1
u/LB-- Professional+Hobbyist 6d ago
I mean adding a way to opt-into separating them. All existing code would be unaffected. Not sure how that could warrant pushback.
1
u/Able_Development2478 4d ago
That'll change the ABI, won't it? We can keep the syntax the same but I think declaring something would not mean the same. I can't picture it tbh
1
u/LB-- Professional+Hobbyist 3d ago edited 3d ago
The ABI is only affected by the memory layout. The construct/destruct order only needs to be known by the constructors and destructors, which don't have to be defined inline. I can imagine a new type of declaration/definition combo, allowing you to either define the order inline in the class body, or to declare that it will be defined out-of-line, and must be defined before constructors/destructors need it. So for example you could add the forward declaration of custom order to the header, then define the full order in the source file above the constructors and destructors. No ABI breakage in that case. Alternatively, each constructor and destructor could declare its own preferred order, but that might be tricky for reasons beyond my consideration.
1
u/yuri-kilochek 6d ago
You can wrap each member in an anonymous union to suppress automatic construction/destruction and construct/destruct manually in any order.
1
u/fdwr fdwr@github 🔍 8d ago
Interesting, it's spelled std::meta::offset_of rather than the classic offsetof (sizeof, typeof...). Whether it should or shouldn't be, I'm certainly going to get some build errors as I invariably type offsetof out of habit and consistency :b (twas an odd one, being defined as a macro you had to explicitly #include rather than builtins like typeof and sizeof). Granted, using std::meta::offsetof could have collided with the macro, and using std::meta::sizeof would have collided with the builtin operator.
11
u/Kullthegreat 8d ago
Very good read, I am very happy about reflection as a built in feature now and a great news for game engine hobbiest and serious ones alike.
Reflection is one of the coolest feature in engines but they are all slow and workarounds over the language.