This is a good article, but it bugs me that it sort of only tells half the story.
Why are you making your structs smaller. Probably for "performance". If your goal is literally just reducing memory usage, then this is all fine. Maybe you're running on a small microcontroller and you just straight up don't have much RAM.
But these days, in most areas, memory is cheap and plentiful. What's expensive is CPU cache. If you're optimizing memory use for that, it's really about runtime speed and less about total memory usage. You're trying to make things small so you have fewer cache misses and the CPU doesn't get stuck waiting as much.
In that case, the advice here is only part of the story. Using bitfields and smaller integers saves memory. But in order to access those fields and do anything with them, they need to get loaded into registers. I'm not an expert here, but my understanding is that loading a bitfield or small int into a word-sized register can sometimes have some bit of overhead, so you have to pay attention to the trade-off.
If I was optimizing for overall runtime speed and considering packing structs to do that, I'd really want to have good profiling and benchmarks in place first. Otherwise it's easy to think you're making progress when you're actually going backwards.
> If you're optimizing memory use for that, it's really about runtime speed and less about total memory usage. You're trying to make things small so you have fewer cache misses and the CPU doesn't get stuck waiting as much.
The complication is that cache is a global resource. Code that has larger data structures, even if it runs faster, can contribute to a larger working set and a slightly higher cache miss rate in other code. This can lead to a death-by-thousand cuts scenario and it's hard to get solid data on this when profiling.
You're right, though, that there are a number of ways that smaller structs can be slower, either directly by execution time or indirectly by larger code causing more misses in the instruction cache. Some other factors include whether the compiler can coalesce accesses to multiple fields grouped together, or whether the struct hits a magic power of two size for faster array indexing or vectorization. Which means you can end up speeding up code occasionally by making the struct bigger.
If you are using an intrusive data structure, keeping the key on the same cache line as the pointers can make traversals faster. Reducing padding can make this easier to do.
In general, keeping commonly accessed together things on the same cache line is a good idea and the work needed to remove excessive padding overlaps with the work needed to do this.
I most agree, only except that perf is determined by a myriad of facors. Even if this piece of data fits into a cache line, it may have no or negative effect on the following code. For complex softwares, even if it's faster after the change, it's hard to tell what's the contributing factor really is. I once read a system paper (forgot the name) from a recent system research conference on how changing the code layout, e.g., moving a block of code, randomly may have unexpected impacts on perf.
Personally, I only pay attention to the cache line and layout when the structure is a concurrent data structure and needs to sync across multiple cores.
I pack structs because the packed layout matches some hardware or network structre and thus I get direct access . This isn't a common case but it exists.
That case is much more common in embedded/bare-metal programming. A decent chunk of the code I've written so far for getting Zig running on a Nintendo 64 is a bunch of packed structs representing various registers (and a bunch of methods on those structs representing common uses of those registers).
It's also a reasonably common case for parsing binary data formats (e.g. a file's header has fields at exact byte offsets, and it's much faster and easier to just grab all the bytes of that header and interpret those bytes as a packed struct).
If you're really accessing those fields it's overwhelmingly likely that you're accessing the same field for all of your instances. Your access pattern is going to be
Striding over your monsters array means you have to load each monster to access one field which just blows your cache to hell. Much better is to pack all of your health values together in a structures-of-arrays layout as opposed to the usual arrays-of-structures approach here. Entity-component-system architectures are a brilliant tool for managing this with some pretty performant results.
Could you give some intuition on why this is likely to be the case more frequently than accessing different values from a single entity?
I'm not a games developer, so I don't have a good feel for why you'd need to iterate over every monster's health property in a tightly loop vs accessing each monster and calculating their position, what properties they have and updating one or more of their values in an iteration.
Sure. If your monsters have health, then their health is going to need updating pretty much by definition. Option 1 would be to make each entity responsible for updating itself with an overloaded `update` function in sort of a "classical OOP" fashion:
for(auto &entity: entities) {
entity.update();
}
You're then responsible for weaving the health changes into your update (or getting it from your parent). Weird stuff can happen if one entity updates before another, too: you likely want all of the health updates to occur after all of the damaging events. So now this update function has to register a deferred health update to occur down the line.
Option 2 with something like an Entity-Component-System design would have a "Health" system that handles health updates across the board.
Neither of these options is strictly better than the other. Option 1 is good if you need a lot of bespoke logic for health updates (dragons update differently from humans which are different from vehicles etc.). Option 2 is better if everyone has `newHealth = oldHealth - damage`. Things are generally more similar than they are different, so you end up changing all values of a single "kind" (structures-of-arrays) more often.
which is the value that would be updated by healthEntity.updateHealth() ? So because you're sequentially updating only that attribute it should lend itself to being cache friendly and potentially prefetch prediction? (can't remember the term)
Yes, exactly. If you have to update everyone's health (you do) and the updates are pretty much the same (they are), then things don't get any more cache friendly than this.
The real issue with packed structs and bitfields happens when concurrency gets involved. Majority of modern CPU caches are private and only allow one core to hold the cache line - so it creates more false dependencies when cores are trying to alter information that was compacted into a cache line on another core.
Avoiding false sharing is a separate problem best solved by explicitly aligning the struct or relevant members to std::hardware_destructive_interference_size.
The obvious and charitable read of their post is that they use "memory" to mean main memory/RAM, "CPU cache" to mean CPU cache, and "memory is cheap and plentiful" to mean "memory has a low dollar cost and most systems have a whole lot of it".
Your read -- that they use "memory" to mean "anything which stores bytes, including caches", and that they use "memory is cheap" to mean "accessing RAM has a low latency" -- is uncharitable, contrived and even literally self-contradictory ("CPU cache is memory" + "memory is expensive to access while CPU cache is cheap to access" is a contradiction which can only be resolved through using different definitions of "memory" in those two sentences).
Why are you making your structs smaller. Probably for "performance". If your goal is literally just reducing memory usage, then this is all fine. Maybe you're running on a small microcontroller and you just straight up don't have much RAM.
But these days, in most areas, memory is cheap and plentiful. What's expensive is CPU cache. If you're optimizing memory use for that, it's really about runtime speed and less about total memory usage. You're trying to make things small so you have fewer cache misses and the CPU doesn't get stuck waiting as much.
In that case, the advice here is only part of the story. Using bitfields and smaller integers saves memory. But in order to access those fields and do anything with them, they need to get loaded into registers. I'm not an expert here, but my understanding is that loading a bitfield or small int into a word-sized register can sometimes have some bit of overhead, so you have to pay attention to the trade-off.
If I was optimizing for overall runtime speed and considering packing structs to do that, I'd really want to have good profiling and benchmarks in place first. Otherwise it's easy to think you're making progress when you're actually going backwards.