12 ms·
The Lost Art of C Structure Packing (2014)
- thinkMOAR 10y agogreat bit! still, but how often is this going to be reposted? https://hn.algolia.com/?query=The%20Lost%20Art%20of%20C%20Structure%20Packing&sort=byPopularity&prefix&page=0&dateRange=all&type=story https://hn.algolia.com/?query=The%20Lost%20Art%20of%20C%20St...
- jessaustin 10y agoEvery time we'd like another round of "Lost art? Why, I packed me some C structs this morning over breakfast! You young whippersnappers!" comments from crusty old C dudes.
- jgrahamc 10y agoAh, yes. BUS ERROR: http://blog.jgc.org/2007/04/debugging-solaris-bus-error-caused-by.html http://blog.jgc.org/2007/04/debugging-solaris-bus-error-caus...
- bogomipz 10y agoJohn Graham-Cumming that blog's author seems like an interesting guy, he's started something called 'Plan 28' to faithfully build Charles Babbage's Analytical Engine. He also wrote the Geek Atlas. Blast form the past, I remember Bus Errors from Solaris days.
- jgrahamc 10y agoThat would be me.
- Roboprog 10y agoUsing a byte array and manually marshalling stuff in and out is tedious, but it does avoid alignment issues. There's a certain amount of irony that dynamic languages (e.g. Perl) make it easier to implement something like "pack" and "unpack" to move values in and out of such a byte array, due to the variable type arguments/results of the "unpacked" values.
- Roboprog 10y agoOtherwise, I assume that avoiding this problem is a matter of putting the larger elements at the start of the struct, and the smaller elements at the end (with the exception that for a nested array, you consider the element size, not the total array) 8 byte entries, then 4 byte entries, 2 byte entries, chars/bytes, bits.
- Uptrenda 10y agoVery nice guide. I remember seeing extremely similar code when I was working with raw TCP packets and I always wondered what all the esoteric rules were for working with raw struct memory. There was no where that seemed to explain things happening on this level so it kind of just never made any sense to me. Guess now I can finally figure out what all that code meant, awesome.
- khedoros 10y agoA few years ago, I ran into some situations where packed structs would be useful. I ended up writing a lot of little test programs to verify struct sizes based on different element orders, packing pragmas, etc. It was certainly illuminating, but it would've been helpful having a write-up like this to work from. It got even more complicated when I threw unions into the mix. Knowing how the data is stored at the bit level becomes important in some of those cases.
- minipci1321 10y agoSigh... apparently this is now enough of rocket science to be considered for posting on HN... People using packing pragma of GCC should also beware -- an access to a field of a packed structure will be done bytewise, whether a variable happens to be actually aligned or not (I guess the compiler simplified its life by assuming no variable is ever aligned in packet structs), so memory size would go down but CPU use might grow. At least this used to be true a few years ago, haven't reverified recently.
- looki 10y agoYou mean that it reads the values into single byte registers and assembles those back into the value you want?
- minipci1321 10y agoYes, that is what I meant. It does that even for fields of a structure that are, strictly speaking, not subject to packing -- when, for example, you put a double as the very first field in a struct, and define the entire struct as packed. The double will still be assembled from 8 1-byte reads.
- looki 10y agoThat sounds quite horrible - today was very eye-opening on why people almost never pack structs tightly, thank you.
- vvanders 10y agoYup, same type of thinking helps when working with byte streams, image formats and the like. Working within your native, aligned word size can have wonderful performance benefits.
- jcranmer 10y agoOn x86, most memory can be accessed unaligned (and, unless you cross a cache line boundary, there's effectively no penalty. If you're on Haswell or newer, even if you cross a cache line boundary, there's no latency hit for an L1 cache hit). The code for a struct { char a; double b; } load reference on x86-64 after -O3 is: movsd 1(%rdi), %xmm0 So it looks like gcc is able to condense the load on platforms with unaligned accesses. On ARM, it does look like the double is loaded byte-by-byte.
- kbob 10y agoIt concerns me when a technique I've used this week is called a "lost art". I'd suggest putting a [NOOB] tag on this kind of post. Except ESR wrote this one. So maybe [FAUX-NOOB].
- zerohp 10y agoAgreed. It is also taught by at least one university (UIUC) in a required class (in 2016.) Not a lost art.
- tedunangst 10y agoHey kids! ESR here. I'm the last programmer on earth. The very definition of a hacker. (Coincidentally I also wrote that definition.)
- chocolatebunny 10y agoI had two job interviews last year for embedded software positions and in both of them struct packing had come up. I don't think it's a lost art.
- wangchow 10y agoNot a lost art--but a dying one. Think of how many people using languages that don't care about this sort of detail. Great article though I read it a while back. I was thinking of sending network packets you can pack structs into a wire-format version like. struct Position { char x[4]; char y[4]; }; instead of: #pragma pack(1) struct Position { uint32 x; uint32 y; }; #pragma pack()
- mschwaig 10y agoSee also previous discussions of this article from 2014 and 2015: https://news.ycombinator.com/item?id=6995568 https://news.ycombinator.com/item?id=6995568 https://news.ycombinator.com/item?id=9069031 https://news.ycombinator.com/item?id=9069031
- dspeyer 10y agoLast time I manually packed structures I was doing GPU programming. I forget the details, but the CPU and GPU had different alignment requirements so anything other than a manually packed structure broke in weird ways.
- _RPM 10y agoI compile with -Wpacked when I'm building something to serialize structs to disk. It helps. I know sizeof will return the value with the padding, but I'd rather do it myself.
- rwmj 10y agoStrange that he doesn't mention dwarves (https://github.com/acmel/dwarves/ https://github.com/acmel/dwarves/ http://www.ukuug.org/events/linux2007/2007/papers/Melo.pdf http://www.ukuug.org/events/linux2007/2007/papers/Melo.pdf). Edit: He does mention it in passing but says he hasn't used it. Suggest that he does use it because it's a really useful tool and lots of the manual stuff he's doing is better done automatically.
- samfisher83 10y agoYou can kind of do this is in C# with StructLayoutAttribute. One of the few high level languages you can do it with.
- blaisio 10y agoI hate to well actually but... well actually basically any language that allows interop with C will have this feature since it's basically the only way to guarantee that the struct layouts will be compatible.
- pjmlp 10y agoAda, Modula-2, Modula-3, Eiffel, D, Rust, Turbo Pascal, Free Pascal, Delphi, ... There are more than just a few.
- sfrailsdev 10y agoMy understanding (and i I'm wrong, tell me) is that if you try to serialize or save to disk something with a bitfield directly, you can have big problems.
- bluGill 10y agoBitfields orders are "implementation defined". So you need to ask the vendor of every compiler you support what the compiler does. Once you know what the compilers you support do you can write code specific for them and everything works great. It is only when someone tried a different compiler (including an upgrade of the existing one) that you can run into problems.
- tboneatx 10y agoKnowing about struct memory alignment can come in in very handy when reverse-engineering 3rd party binary protocols. Often you come across many "unknown" bytes which turned out they were just padding because of 4 byte struct alignment and could be discarded. Saved a bunch of time not having to try to figure out what they were.
- Roboprog 10y agoYou can sometimes save some memory in these sort of "flyweight" records by moving all the strings in a group into a string table. Make one byte-array buffer for the text from multiple records, then use a ("small") offset integer in each record to refer to the starting position of strings within the string table. Rather than using a 64 bit pointer, or an inline array of max-size, for each string, just use perhaps a 16 bit offset into the table for each string. (or 32 bit if you expect enough data). Of course, this also requires wrapper setter/getter type code, but it can be a good trade to save space.
- Artlav 10y agoHuh? "Lost art"? That's, like, programming 101 grade material, not some "lost art". Then again, i worked in telecom and HPC, and play with uCs, so perhaps i'm wearing the wrong googles...
- qwertyuiop924 10y agoyou are. It's not exactly a lost art, but it's not known except to those inside of the secret, uninviting inner circles of C programming, which you can only enter if you memorize all the UB.
- kazinator 10y agoTL;DR: to get smaller structures, don't do stuff like this: struct foo { char a; int b; char c; int d; }; but this: struct foo { int b; // or int b, c; int c; char a; char c; }; Basically if you sort the types by size in reverse descending order, you get optimal packing without messing with compiler-specific packing extensions that skew alignment and possibly bloat code. The worst that you will get is padding at the end of the structure so that if two or more of them are arrayed, the first member is correctly aligned at all the array indices.
- vonmoltke 10y ago> The worst that you will get is padding at the end of the structure so that if two or more of them are arrayed, the first member is correctly aligned at all the array indices. This is not guaranteed. If you want to ensure all array member starting addresses are aligned for all compilers and platforms you need to add explicit dead space. You should also be using the fixed-width numeric types.
- kazinator 10y agoIt's not guaranteed (as in "money back" or whatever). It's merely required by ISO C for conformance. If a struct is declared like this: struct foo { whatever_type_t first_member; // ... }; then an array of this type can also be declared: struct foo farray[42]; A conforming ISO C implementation has to ensure that farray[1].first_member, and farray[2].first_member, and so on, are all allocated such that they meet the alignment requirements fro whatever_type_t. It cannot be that farray[0].first_member is accessible, but farray[1].first_member throws an alignment exception or whatever. Programmers should not have to do anything to ensure this. So, if necessary, padding is added at the end of struct foo to make this alignment happen. In practice, compilers add the padding even if it's not required for at least two reasons: performance (misaligned accesses, though supported, may be slow) and compatibility (having the structure look the same across multiple architectures supported by the same compiler, at most modulo byte order). > You should also be using the fixed-width numeric types. I'm not aware that C provides any other, currently. Though you can simulate them with libraries, of course.
- cheez 10y agoIn this thread: people who do this for a living making people who don't feel dumb. Guys, it's called "The Lost Art of C Structure Packing" for a reason. Python and Ruby guys have no idea. Even most C or C++ devs wouldn't know. Take a chill pill.
- tedunangst 10y agoThat doesn't make it a lost art. I've no clue how to make wine (something to do with grapes?) but I don't describe it as a lost art.
- thesimpsons1022 10y agoI learned it a few years ago in undergrad..
- qwertyuiop924 10y agoESR is a good programmer, and this is a handy guide for those who don't know how to pack structures. He's also insane, so don't trust anything he says. Oh, you don't think he's insane? He thinks there's a conspiracy amongst women in open source to discredit Linus Torvalds. No, I'm not joking. I wish I was.
- andrepd 10y agoOfftopic. His opinions on open source politics are little matter to his technical insights. I can appreciate Hitler's paintings, etc etc.
- qwertyuiop924 10y ago...Which is why despite that, I still think this article is good, and said so.
- Sacho 10y agoHere are ESR's words on the subject: http://esr.ibiblio.org/?p=6907 http://esr.ibiblio.org/?p=6907
- mikestew 10y agoHowever, ignore the way it's worded and the overall message is good advice whether there's a conspiracy or not (which I agree, there is likely not). If you're a male whose name I'd likely recognize, the only woman with whom you should ever be in a room alone is your SO. Someone might still accuse you of sexual assault, but it'll be pretty darned hard to prove if it can never be demonstrated that the two of you were alone together. Got the idea from the Rev. Billy Graham. Ever notice that no one (to my knowledge) accused him of sexual assault while his peers (for lack of a more accurate word) were making the news regularly in the 90s? Because he did exactly that. Maybe it sounds harsh or paranoid, I dunno, but it's not that hard to implement and is easier than dealing with being falsely accused, no matter how small the odds.
- 10y ago
- ThatGeoGuy 10y agoAlthough I somewhat tire of constant comparisons between Rust and C, in this case it's interesting so I'll ask: Does Rust do struct packing any differently than C and what kinds of tradeoffs are associated with that? Most people don't even think about struct packing in the context of C++ (which is in many ways closer to Rust) because of vtables / inheritance / etc, but in this case I'd like to know if Rust does anything differently or requires something new to think about in this respect.
- Crespyl 10y agoIIRC, Rust struct layout is undefined/unstable, unless you explicitly use the #repr(C) tag on the struct definition, in which case it behaves pretty much exactly like C. You can also specify that the struct be packed, with no padding between items if necessary. I'm not sure if unmarked Rust structs actually get layout optimized or not right now, but they've worked to keep that option available.
- Gankro 10y agoUnless someone's recenrly bothered to implement it, I believe Rust doesn't currently bother to optimize your struct layout. It can and it surely will but not yet (this is a dangerous state of affairs since people may start to rely on it).
- blaisio 10y agoRust will reorder struct members in the most efficient way possible unless you explicitly tell it not to. This is also how most other low level languages (like C++) do it. The main reason to have an option at all is it makes it easier to work with arrays of bytes. For example, in networking if you receive a packet, instead of parsing a packet you can just cast it to a struct with fields in the correct order. And if you send a packet, you can just cast the struct to a byte array. This avoids a lot of copying and can greatly simplify code.
- zeusk 10y agoAn article on C structure packing without any mention of __attribute__((__packed__))?? meh.
- khedoros 10y ago> GCC and clang have an attributepacked you can attach to individual structure declarations; GCC has an -fpack-struct option for entire compilations. He mentioned it in passing (and without proper syntax) in section 11.
- blaisio 10y agoIs this really a lost art? I feel like this is one of the main reasons people who use C still use C: you have a lot more control over how memory is handled. Honestly, if someone doesn't know about this, then they really just don't know C, because it's a pretty fundamental piece of information.
- deleted 10y ago[deleted]
- jevinskie 10y agoI wish pahole got more attention since I had some great experiences with it years ago. I tried it recently and it didn't like the DWARF info that my compiler was spitting out. Perhaps I need to tweak the DWARF versioning or, gulp, try and add the missing DWARF support to pahole. EDIT: I'm starting to think my "recent" testing hasn't been too recent. It looks like development picked up again mid-2015. I'll have to give it another run! http://git.kernel.org/cgit/devel/pahole/pahole.git/log/ http://git.kernel.org/cgit/devel/pahole/pahole.git/log/
- Animats 10y agoThe bit-field feature of C structs is underutilized. People are still writing hex constants and using AND and OR to clear and set bits. Let the compiler do that; it's more readable. As of C99, there's named structure initialization, which makes bitfield constants more readable.
- stephencanon 10y agoC11 §6.7.2.1: "The order of allocation of bit-fields within a unit (high-order to low-order or low-order to high-order) is implementation-defined. The alignment of the addressable storage unit is unspecified." This makes bitfields quite difficult to use correctly when portability is of interest. It's often easier to write a couple inline get/set functions and use bit indices. If portability isn't a concern, then sure, have at it.
- Animats 10y agoThat's an escape clause for endian issues. If you write hex constants, you still have endian issues.
- tedunangst 10y agoVery annoying when you want to pass the flags field to a function, however.
- Animats 10y agoRight, because a structure initializer in C is not a first-class object. You can't use it in an expression.
- Too 10y agoIf your struct is mapped to a register then writing two bit fields in sequence will trigger two separate writes on the hardware register when you intended to write both the bits in one shot.
- Annatar 10y agoesr, brilliant as always. However: since shipping the first version of this guide I have been asked why, if reordering for minimal slop is so simple, C compilers don’t do it automatically. The answer: C is a language originally designed for writing operating systems and other code close to the hardware. Automatic reordering would interfere with a systems programmer’s ability to lay out structures that exactly match the byte and bit-level layout of memory-mapped device control blocks. If the programmer wants or needs absolute control, just do not provide the reordering option to the optimizing compiler. So why wouldn't compilers provide a command line option to do automatic reordering?
- qwertyuiop924 10y agoBrilliant, but crazy.
- gambiting 10y agoIt's not lost at all - I work as a games dev, and I can assure you that a major AAA title released this year on all platforms cares a lot about C struct packing(it's actually part of our code review process!).
- edem 10y agoI've heard about this at a talk 4 years ago and I'm not even a C programmer so there is hope!
- jstelly 10y agoThis can also be important for routines that treat structures as strings of bytes. e.g. void MD5( unsigned char *pStructure, size_t size ); struct foo { char a; int x; }; if I MD5( &foo, sizeof(foo) ); on two foo with the same a & x, they may not produce the same MD5 because the pad bytes might contain noise from the stack or heap. The solution is to either zero memory on anything you will MD5 or explicitly declare all of the padding (easy if you have internalized the rules) so your code can handle it.
- Too 10y agoIn chapter 4, padding outside structure. Isn't the compiler free to do whatever it wants there? There might not even be a need to reserve memory for some variables if the optimizer concludes they are irrelevant for the program?