11 ms·
I do optimal structure (and bit) packing without much thought because it is an old habit. As the article states, I have noticed that the only other people that
by jandrewrogers 13y ago
I do optimal structure (and bit) packing without much thought because it is an old habit. As the article states, I have noticed that the only other people that do habitual careful structure optimization these days have been doing low-level and high-performance code as long as I have. Most programmers are oblivious to it.
The reasons you would do it today are different than a decade ago and the rules have changed because the processors have changed. To add two clarifying points to the original article:
- The main reason to do optimal structure packing today is to reduce cache line misses. Because cache line misses are so expensive it is a big net performance gain in many cases to have the code do a little more work if it reduces cache line fills; optimal structure packing is basically a "free" way of minimizing cache misses.
- On modern Intel microarchitectures, alignment matters much less for performance than it used to. One of the big changes starting with the i7 is that unaligned memory accesses have approximately the same cost as aligned memory accesses. This is a pretty radical change to the optimization assumptions for structure layout. Consequently, it is possible to do very tight memory packing without the severe performance penalty traditionally implied.
What constitutes "optimal" structure packing is architecture dependent. The original C structure rules were designed in part to allow the structures to be portable above all else. If you design highly optimized structures for a Haswell processor, code may run much more slowly or create a CPU exception and crash on other architectures, so keep these tradeoffs in mind. The article is discussing basic structure packing which typically has easily predictable behavior almost anywhere C compiles.
- 3pt14159 13y agoWhy doesn't the compiler handle this for the programmer? Seems "free" in the no-tradeoffs sense.
- kristoffer 13y agoThe elements of a C struct must be sequentially ordered in memory as specified in the code, that's defined in the standard.
- MaulingMonkey 13y agoIn turn, various C code is then written depending on this expectation, meaning a non-compliant compiler would break a significant number of codebases.
- antimagic 13y agoOn the other hand, I for one would happily throw such brittle, unportable code under the bus in the name of automatically reduce cache line missing. About the only safe usage of structure memory layout that I can think of is offsetof, and even then, I think you could make offsetof's behaviour definable in the ABI to make it deterministic.
- dfox 13y agoThat unportable code includes CPython, Sun JVM, essentially anything GUI related in Windows and anything that uses BSD sockets.
- EpicEng 13y agoI'm not sure you know what "unportable" means. Every program compiled by a compliant compiler will work. "unportable" doesn't apply to compilers which do the wrong thing, it applies to programs which do not assume anything outside what is in the specification.
- MaulingMonkey 13y ago> On the other hand, I for one would happily throw such brittle, unportable code under the bus in the name of automatically reduce cache line missing. Spoken like someone who's never been forced to fix such code left behind by previous coders. > About the only safe usage of structure memory layout that I can think of is offsetof, and even then, I think you could make offsetof's behaviour definable in the ABI to make it deterministic. Sure, especially considering offsetof is standard defined and allowed to be compiler implemented AFAIK. That said, you bring up a great point: You're talking about breaking decades old ABIs if you were to enable such memory layout reordering by default. Good luck tracking down updated .libs or original source to build .libs from for every single one of your dependencies!
- merraksh 13y agoI would assume you can't safely do arithmetic within a structure, for instance. As an example, take a struct { char a; char b; char c; char *p; char d; } A valgrind error that points at "0 bytes within an area of memory..." would signal an error originating somewhere in the struct, but who knows whether it's p or a.
- deleted 13y ago[deleted]
- pandaman 13y agoI believe one of the reasons for adding "class" types in C++ was to break from the C's restrictions on the struct layout. But even then the trouble of breaking binary compatibility was too much to pay for freeing programmers from minding their own data.
- archangel_one 13y agoNo, the same restrictions apply to class as to struct. The most relevant difference in C++ is that the compiler can reorder data members that are in different visibility specifications (public, protected, private) but not within one of those blocks, to maintain compatibility with C.
- pandaman 13y agoThis is what I said. Even though they could change the rules for the classes they did not because it's far from "free".
- haberman 13y agoWell you only have guaranteed compatibility with C if a class is standard-layout, which requires that all members have the same access control (public, protected, private). So if there is any rule in C++ that mandates ordering within a "block" when there are multiple such "blocks", it's not for compatibility with C.
- pmr_ 13y agoFunnily, this is one of the freedoms granted by the standard which neither gcc, clang, or MSVC actually make use of.
- pandaman 13y agoOh, putting "class" in the first sentence was a mistake as people hit downvote without reading the rest. I do not say that "class" allows rearranging members (other than C++ access-based rearrangement that applies to structs as well). Really. Please read.
- colin_mccabe 13y agoWhy doesn't the compiler handle this for the programmer? Seems "free" in the no-tradeoffs sense. Traditionally, C and C++ programs have been compiled by running the compiler on each .c file, and then linking together the results. If each invocation of the compiler could put the fields of a structure in arbitrary order, the different object files would not work together correctly. C structures do not include runtime type information and all offsets are calculated during the compile phase. The same issues come up with libraries. We need a stable application binary interface, or ABI. Even if the ABI problem was solved, there are advantages to letting the programmer determine the order of fields in a structure. If you know that different threads are going to be using different parts of a structure, you will want to arrange things (or insert padding) so that the different threads are using different cache lines. This avoids so-called "false-sharing."
- pedrocr 13y ago>If each invocation of the compiler could put the fields of a structure in arbitrary order, the different object files would not work together correctly. That just requires that your packing algorithm be deterministic and there's no reason for it not to be. I suppose it would fail in cases where someone defines a 2 element struct in one file that's a subset of a 3 element struct in another file, and then casts the 3 element into the 2 element.
- TheZenPsycho 13y agoThe offsets of code and data blocks are already undetermined before linking. Even if the algorithm is non-deterministic, what's stopping the optimisation from not running until link time?
- RogerL 13y agosizeof (foo) would not be known until link time. static_assert(sizeof(foo)==64, "you didn't align foo correctly") would not be possible.
- chj 13y ago
- jheriko 13y agothis is one of those classic things where we could actually improve C for performance. the standard is restricting here - data that requires to be identical in all cases for network, file etc. purposes should be marked with a special keyword - or for legacy purposes we mark the ones we want the compiler to order for us. its more complicated than just keeping the size down though - you might want things to start on 64 or 128 or 256-bit boundaries as well - e.g. if your class contains aligned vector members and is itself aligned.
- AYBABTME 13y agoBecause if the compiler reorders your fields under your foot, you won't be able to know how things a serialized. You lose control over the memory layout.
- AshleysBrain 13y agoIt would break things. If you have a structure that is part of a network transmission or file format, reordering the fields would read the wrong data. On top of that C programmers are used to doing memory hacking type things like taking the address of fields and in some case may need to rely on the certain memory layout of a struct being what they declared it as.
- kristoffer 13y agoYou can't use a struct in a portable way for sending directly on the network or writing/reading to disk. You must always properly serialize the data despite the fact that the _order_ of the elements is defined.
- valleyer 13y agoStarting with "the i7"? What microarchitecture do you mean?
- pjscott 13y agoThe Nehalem microarchitecture made aligned and unaligned memory accesses have the same latency and throughput, except in weird edge cases like loads which span an L1 cache line boundary.
- valleyer 13y agoThanks.
- userbinator 13y agoIt used to be the case that unaligned memory accesses were twice or more slower because they literally required multiple bus cycles, but for x86 that hasn't been true since the Core 2 at least: http://lemire.me/blog/archives/2012/05/31/data-alignment-for-speed-myth-or-reality/ http://lemire.me/blog/archives/2012/05/31/data-alignment-for...