8 ms·
How often is "reduce cache misses" that different from "use as little space as possible"? They're basically the same if the struct can be no more than one cache
by scottlamb 5y ago
How often is "reduce cache misses" that different from "use as little space as possible"? They're basically the same if the struct can be no more than one cacheline wide. When the struct is larger, it's possible you're accessing certain sets of fields together often enough for this to be a useful consideration, but I have no intuition on how common it is. Although it occurs to me that when this happens, switching from arrays of structs to structs of arrays may be a better optimization anyway.
fwiw, Rust leaves the ordering unspecified (unless you specify it via #repr[(C)]). Currently it orders to minimize padding. (In theory a future compiler could reorder to minimize cache misses based on a profile or something.) According to https://doc.rust-lang.org/nomicon/repr-rust.html https://doc.rust-lang.org/nomicon/repr-rust.html part of the rationale for reordering was generics. If you have a struct Foo<T, U>, the optimal ordering depends on the size of T and U. The same argument won't apply to Go until 1.18 is released.
- staticassertion 5y ago> How often is "reduce cache misses" that different from "use as little space as possible"? I thought the same exact thing. If I can reduce my struct sizes I can pack N more structs into my cache line. That's almost certainly going to be the best cache-based win.
- deleted 5y ago[deleted]
- tedunangst 5y agoIf your struct is large enough that you care about shaving padding, you probably have hot fields and cold fields and the best cached based win will be arranging them contiguously.
- morelisp 5y agoIf I have a [10000]T I need to shave very little padding before I see some impact, even though both the padded and unpadded T might be relatively small. Specifically in Go, a smaller size can get even lone values into a smaller size class. Saving one byte may save you 384 if it's from 2305 to 2304.
- fredophile 5y agoThe example in the link had 3 fields and padding made the structure 50% bigger than it needed to be. That probably likely big enough to have hot and cold fields but clearly they cared about shaving padding.
- anonymoushn 5y agoMost structs that care about shaving padding will be very small.
- mcherm 5y agoActually, you care about shaving padding when the FIELDS are small compared to the alignment, not the structs. This frequently is a concern in Go.
- pornel 5y agoIf you have a large-enough group of distinctly cold fields, a better option may be to move them to another struct, possibly allocated out of line.
- usrusr 5y agoCan go structs be nested by value? (As opposed to by reference) I'd imagine that this could be a very practical way to to do a manual hot/cold grouping in an environment that prioritizes packing over keeping order. (if the cold ones are particularly cold you might of course prefer them to be in a by reference nested struct anyways, so the hot subset packs better with their peers in an array)
- jeltz 5y agoThat does not match my real world experience. If you have an array of small structs then the padding matters. And if some fields are hot while others are cold you usually want to split the array of structs into two arrays of structs, one with the cold part and one with the hot. The use case Go optimizes for is not common in the fields I have been working in. I think the default should be to minimize size and that it should be possible to opt out for the rare case where exact order matters.
- scottlamb 5y agoCounterexample: the struct in the article. It's "large enough that you care about shaving padding" in aggregate. The 2 optimal arrangements eliminate padding so it uses 1/16th of an x86-64 cache line. This guarantees the whole struct is on one cache line and uses the least total cache, so the 2 arrangements with padding are strictly worse, regardless of which fields are hot or cold. A struct of arrays form may be better still, but that's more than rearranging fields and beyond the compiler to produce. More generally, there are surely cases where it's better to arrange all the hot fields together at the expense of increasing the struct size, but I'm unsure it's the common case, and my bullshit alarm fires when people say so without evidence. (Even more so if they're also saying programmers are commonly arranging the fields optimally by hand.)
- jlrubin 5y agoit's very likely that it's one of the cases that when reducing cache misses does really matter it's very different from using as little space as possible, and the degree to which it matter dwarfs the degree to which it's not a frequent concern (i.e. fat tail). for example, if I have a struct that contains a bunch of atomic fields, I may actually want to control the layout to ensure they are far apart (even inserting padding) to prevent e.g. false sharing https://en.wikipedia.org/wiki/False_sharing https://en.wikipedia.org/wiki/False_sharing.
- masklinn 5y agoMay is very much the operative word here. The common and normal behaviour you want is to minimise struct size so you can fit the maximum instances in cache and memory. The need for more precise control is very much the exception, and thus not unlike preventing inlining (which you may actually want) it could (and should) be an opt-out.
- jlrubin 5y agomy point is that these are the fat tail + survivor bias of cases where you do actually care about performance to this degree, so it probably is actually more common in practice when you're looking into it. even though precise control is the exception, if you can't do it, you can't use your language in a lot of critical contexts (and end up linking C, Zig, Rust, etc).
- masklinn 5y ago… Nobody said you should not be able to do it, at all? The argument is about default behaviour. Rust is specifically a langage which reorders by default.
- jlrubin 5y agoscottlamb seemed to be implying it's not worth being able to since it's an uncommon use case, so I was explaining why even if it's uncommon it's must-have.
- nspattak 5y agostruct packing is one way to reduce cache misses. One can also reduce cache misses by redesigning structs to better match the data usage pattern (eg ArraysOfStructs vs StructsOfArrays).
- Symmetry 5y agoYeah, a cache line is 64 bytes. If you care about putting data that's used together adjacent you're assuming that objects a lot larger than 64 bytes are the most common case but I'm not at all sure that's true. I would guess that we're using up our memory with large heap allocated arrays and large numbers of structs that fit within a cache line. But of course, that's something that ought to be actually measured.
- mhh__ 5y agoIf you need to pack the structs for a certain cache optimization you almost definitely should be grouping the data together differently.