15 ms·
The Lost Art of C Structure Packing (2014)
- digikata 4y agoIs what the article says re: the pahole utility still correct (that it's not maintained)? Looks like it might be maintained now w/ kernel git under the dwarves area. Pahole is a decent utility to look at what the packing of a structure actually ended up after everything has had its last effect in the compile chain.
- dang 4y agoRelated: The Lost Art of C Structure Packing - https://news.ycombinator.com/item?id=15626205 https://news.ycombinator.com/item?id=15626205 - Nov 2017 (49 comments) The Lost Art of C Structure Packing (2014) - https://news.ycombinator.com/item?id=12231464 https://news.ycombinator.com/item?id=12231464 - Aug 2016 (112 comments) The Lost Art of C Structure Packing - https://news.ycombinator.com/item?id=9517623 https://news.ycombinator.com/item?id=9517623 - May 2015 (4 comments) The Lost Art of C Structure Packing - https://news.ycombinator.com/item?id=9069031 https://news.ycombinator.com/item?id=9069031 - Feb 2015 (113 comments) The Lost Art of C Structure Packing - https://news.ycombinator.com/item?id=6995568 https://news.ycombinator.com/item?id=6995568 - Jan 2014 (143 comments)
- mlindner 4y agoIt's so lost it's been posted almost every year since it was posted.
- dragontamer 4y agoI feel like "struct of arrays" style coding has really taken off in the past decade, and seems to be the best way to maximize memory operations these days. Its not so much that "structure packing" is dead, as much as a wide variety of techniques have been developed above-and-beyond just simply structure packing. There's many ways to skin a cat these days, and packing your structures more intelligently is just one possible data optimization.
- kolbusa 4y agoIt really depends on the domain. HPC is more frequently SOA (think CSR sparse matrices), while AOS may make more sense in other cases.
- monocasa 4y agoWasn't that one of the cool things about the language Jai? Struct definitions could be cleanly inverted between AoS and SoA at use time?
- pclmulqdq 4y ago"Struct of arrays" becoming popular may also have something to do with few people understanding structure packing. AOS has much better performance if you pack your structs well than if you pack them naively.
- layer8 4y agoThat entirely depends on the access patterns. SOA makes sense when you don’t often access the different fields of the same object (array index) at the same time. If you do, on the other hand, then AOS is more efficient.
- TillE 4y agoRight. There's a little too much cargo-culting in the "struct of arrays" pattern, you really want to understand why it works or doesn't. If you have some giant bloated struct and you only care about one or two fields at a time, that's one thing. But if you have a well-aligned, correctly packed struct and you're processing all its data, it's total nonsense to break that up.
- layer8 4y agoIt’s similar to row vs. column oriented databases.
- dragontamer 4y agoI certainly think SOA has been cargo-culted to all hell and back. But empirically speaking, it seems like SOA / AOS is the easiest "beginner topic" to get high performance-programmers thinking about memory-layout issues. Maybe in the 90s or 00s, it was more popular to think about struct layouts, alignment issues and the like. But today, SOA is popular because RAM has gotten less... random... and more sequential. I think its the changing nature of 90s era computers (RAM behaving more random-accessy) vs the nature of 10s era computers (RAM behaving more sequential-accessy) -------- Its not like the 90s techniques don't work anymore. But the 10s technique of "structure of arrays" and then iterating for-loops over your data works better with prefetchers, multiple-cache hierarchies, and other tidbits that have made RAM more sequential than ever before. Hopefully programmers continue to study the techniques and understand what is going on under-the-hood, instead of cargo-culting the pattern. Alas, we all know that cargo-culting works in the short term and is easier to do than actually learning the underlying machine!
- deleted 4y ago[deleted]
- deleted 4y ago[deleted]
- hnur 4y ago"a technique for reducing the memory footprint of programs in compiled languages with C-like structures" I figure that's not the primary reason for structure packing, but rather for fine-grained control over writing to very specific memory layouts (think global descriptor table) as structs.
- UncleEntity 4y agoI know in blender there is a compile time check to ensure the structs are properly packed and it has nothing to do specific memory layouts. I think it has to do with reading/writing them to disk but honestly never cared enough to ask anyone. Did make things convenient sometimes when you could ‘steal’ a padding value and magically got backwards compatibly because the older versions just ignored that field (and when reading an older file just set it to a sane default).
- pokey00 4y agoYeah, I use them all the time for the specific memory layout part. At the same time, I've never had to go as far with optimization as trimming a few bytes off my structs for the program's memory footprint. If that struct is getting written to storage or shoved over the wire though, I'll always optimize/pack them down, both for the size reduction and because it makes it easy to reconstruct on any other CPU.
- ncmncm 4y agoIt neglects to mention that bit fields have always been the buggiest part of C compilers, and there is never a good enough reason to rely on them, if you have a choice at all. Honest shift-and-mask operations on unsigned machine words are always better, if you absolutely must pack bitwise.
- chrisseaton 4y ago> shift-and-mask operations on unsigned machine words are always better ... but that's what a bit field is?
- layer8 4y agoBit fields are a specific C language feature, allowing to treat bit slices as a unit whose length doesn’t need to correspond to one of the integer types. See for example https://docs.microsoft.com/en-us/cpp/c-language/c-bit-fields?view=msvc-170 https://docs.microsoft.com/en-us/cpp/c-language/c-bit-fields....
- chrisseaton 4y agoYeah they compile to the same machine code operations though. If those machine code operations aren't right as a bitfield then they aren't going to be right done manually either. https://godbolt.org/z/csvTx89EG https://godbolt.org/z/csvTx89EG
- layer8 4y agoBit field support being buggy exactly means that they don’t compile to the same machine code as the bit shifting/masking code you would write by hand (if your hand-written code is correct).
- minipci1321 4y ago> Yeah they compile to the same machine code operations though. Not always. Switch your example to AARCH64 and check out the BFI instruction.
- Comevius 4y agoAlso related: https://media.handmade-seattle.com/practical-data-oriented-design/ https://media.handmade-seattle.com/practical-data-oriented-d...
- mistrial9 4y agobad compilers make bad days.. custom hardware used to (?) use memory locations to control/enable features.. anything from electronic access paths to actual servo-motors firing. Probably a better idea to use human-readable constructs and avoid this compact and tiny use pattern, IMO. If you want a tricky test for yourself, perhaps some actual hardware design is a better use of time these days?
- CalChris 4y agoStruct packing has its points for small structs. Indeed, you can reduce cache use and increase cache locality. However for large structs, page aligned structs, the cache lines will be constrained to a particular set. Moreover, pointer following from struct to struct can incur a TLB hit; the TLB is another small cache. So while you may cleverly encode things to squeeze size, you may then watch things slow to a crawl. You are packing small structs in order to squeeze lots of them into the caches. However for large structs, you should at least consider refactoring them into small structs which you can then pack to your heart's content.
- waynecochran 4y agoI found it interesting that Pascal had a "packed" keyword and C didn't (outside of implementation specific attributes like __attribute__ ((aligned (8))) in GNU).
- layer8 4y agoThe reason is that Pascal was used on computers with long machine words (e.g. 36 bits) where memory wasn’t byte addressable. It was customary (in assembly code) to “pack” multiple logical fields into a single word, in particular multiple characters of a text string. The “packed” feature in Pascal was added for that purpose.
- loup-vaillant 4y agoI once encountered a structured that were packed, even though it shouldn’t have been. Took me over a day to notice where the error came from. I was poking at the internals of a library so I could gather information that it had, but did not provide. There was this context structure I normally only could access through a pointer, but copying the definition of the structure into my own code ought to do the trick… …except it didn’t. The way the library was compiled by default made the structure there smaller than my copy. Took me some time to guess why my data was all garbled, but the cause was pretty simple: there was no padding, even if it meant some members ended up unaligned. I had to replace the unaligned members by char arrays to get it to work (I did not dare explore the compilation options of the library). And then I found a totally different solution for my problem. Oh well.
- benibela 4y agoReminds me of this article on how to pack an XML DOM node into 8 bytes: https://blog.grijjy.com/2020/10/07/an-xml-dom-with-just-8-bytes-per-node/ https://blog.grijjy.com/2020/10/07/an-xml-dom-with-just-8-by... Each element node has 6 pointers, so a naive struct would need at least 48 bytes, but you can do it with 8
- MichaelMoser123 4y agocheck if this is relevant to your platform: 64 bit Intel does allow unaligned access, so you don't get an interrupt on misaligned access, and it's acceptable to have one byte alignment. (I guess that's the reason why pahole isn't maintained any more, because it stopped to matter for the dominant platform). Of course it may very different if you work on embedded systems...