13 ms·
The Lost Art of C Structure Packing
- rwmj 13y agoHe should mention this tool: http://linux.die.net/man/1/pahole http://linux.die.net/man/1/pahole
- JoachimSchipper 13y agogcc -Wpadded is very useful, too (its chief downside is that you don't usually want to combine it with -Werror - padding is not always bad.)
- agwa 13y agoYou can always add -Wno-error=padded to disable -Werror just for -Wpadded
- JoachimSchipper 13y agoI seem to have missed that trick. Thanks!
- dllthomas 13y agoYou could always pad manually to clear the warnings.
- jevinskie 13y agoYou beat me to it. =) Here is an introductory article http://lwn.net/Articles/335942/ http://lwn.net/Articles/335942/
- alextingle 13y agoIs this a "lost art"? I always consider the layout when I'm writing a C struct. It's the principal concern that governs the correct ordering of the members.
- Iftheshoefits 13y agoI was wondering that myself. This doesn't seem like a "lost art" so much as a basic necessity for even moderately constrained applications. I can't remember the last time I did not consider the layout of members of my C structs (other than toy, or proof-of-concept applications).
- deleted 13y ago[deleted]
- pandaman 13y agoFor a guy who thinks that x86 is a modern architecture and all architectures that can only do aligned memory access are "older"? I guess it is.
- derleth 13y ago> x86 is a modern architecture It's a modern ISA, implemented by modern microarchitectures.
- colin_mccabe 13y agoIf you go back to 1993, SPARC, PA-RISC, MIPS, and Alpha all seemed like serious contenders for the next big CPU architecture. To my knowledge, none of them supported unaligned access (though I'm sure someone will point out a counterexample). 20 years later, all of them are dead and x86_64 and ARM are the new "modern architectures." x86_64 supports unaligned access and ARM has been gradually gaining support for it. So yes, chips that can only do aligned memory access do tend to be older.
- pandaman 13y agoIf you go back to 1992 you will find PowerPC which is still around. Same as MIPS. Listen, I know that there are people who worked into retirement without ever seeing anything other than x86 but a) this shows how old x86 is and b) does not give them expertise over different ISAs.
- 13y ago
- drdaeman 13y agoThis could be partially automated with `__attribute__((__packed__))` and a bit of -fipa-struct-reorg for better cache performance. Sadly, there's no any kind of `__reorder_yes_i_know_and_i_want_to_violate_c_standard__` attribute. But I really believe managing and optimizing memory layout (unless explicitly necessary, like when declaring serialization formats) should be compiler's job, not human's.
- JoachimSchipper 13y agoI'm not sure letting the compiler go wild would be such a great idea: one of the strengths of C is predictable performance, which would be hard to obtain if the compiler is allowed to e.g. move data across cache lines.
- _delirium 13y agoIf you're running on one microarchitecture, I agree. But if you're running on more than one, manual structure packing may actually give more unpredictable performance than letting GCC handle it. At least GCC will make an effort to optimize for each one and hopefully avoid things that are absolutely terrible to do on that arch (orders-of-magnitude performance loss type stuff), while a manually chosen packing optimized for one microarch can be hugely pessimal on another one. That's a guess though, no numbers. :)
- pm215 13y agoAdding just the __packed__ attribute and not also an __aligned__ attribute is not necessarily a good idea -- if a struct is marked __packed__ gcc assumes it might be at any alignment, so on architectures which don't permit unaligned loads it may have to generate a lot of byte loads and shifts to do simple reads of integer members.
- _delirium 13y agoFwiw, -fipa-struct-reorg was removed in GCC 4.8.x. From the release notes: The struct reorg and matrix reorg optimizations (command-line options -fipa-struct-reorg and -fipa-matrix-reorg) have been removed. They did not always work correctly, nor did they work with link-time optimization (LTO), hence were only applicable to programs consisting of a single translation unit.
- danellis 13y ago__attribute__((packed)) in GCC is probably worth mentioning if you only want to apply it to selected structs.
- YZF 13y ago#pragma pack(push) #pragma pack(1) MSVC
- eps 13y ago#pragma pack(push, 1) // :)
- pjscott 13y agoGCC also supports that pragma, for compatibility with MSVC: http://gcc.gnu.org/onlinedocs/gcc/Structure-Packing-Pragmas.html http://gcc.gnu.org/onlinedocs/gcc/Structure-Packing-Pragmas.... Clang has this, too.
- userbinator 13y agoAnd MSVC doesn't support GCC's pragma, so for optimal portability #pragma pack(1) is my preferred way of doing it.
- JoachimSchipper 13y agoNote that the key takeaway is just to order struct members by size, largest first; this isn't always sufficient, but it's a good habit wherever performance could matter.
- nnethercote 13y agoYeah. It's an incredibly verbose document, with that key insight buried in a mere two sentences near the end: > The simplest way to eliminate slop is to reorder the structure members by decreasing alignment. That is: make all the pointer-aligned subfields come first, because on a 64-bit machine they will be 8 bytes. Then the 4-byte ints; then the 2-byte shorts; then the character fields.
- jandrewrogers 13y agoI 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 ago
- solarexplorer 13y agoIf your struct covers more than one cache line, you may want to think about which members are accessed together and put those in the same cache line. E.g. if you manage to fit all frequently accessed members in the first cache line, you will bring likely useful data into the cache when you access any of them. At the same time you avoid cache pollution with not so useful data from other cache lines.
- jkrems 13y agoFor people like myself who need a short reminder what a "cache line" is: * http://en.wikipedia.org/wiki/CPU_cache#Cache_entries http://en.wikipedia.org/wiki/CPU_cache#Cache_entries * http://stackoverflow.com/questions/14707803/line-size-of-l1-and-l2-caches http://stackoverflow.com/questions/14707803/line-size-of-l1-...
- jeremiep 13y agoI tend to only use packed structures when I need to match a binary format or know I'll create huge arrays of structures. For the rest I blindly trust the compiler to choose optimal boundaries and alignments.
- dfox 13y agoProblem with that approach is that compiler cannot do any optimalizations of struct field layout as it's completely specified by platform ABI and order in which are fields declared.
- soup10 13y agoThe compiler can't rearrange your structure data for optimal packing, because it doesn't know if you rely on the ordering of it. I agree that structure packing is mostly unnecessary optimization except for a few high performance scenarios where cache miss frequency has a huge impact.
- waynecochran 13y agoClassic use case: creating a packed structures to directly read TCP packets. There is still the "convert from big to little endian" problem, but I think you can use GCC's method for individually packing a struct: struct TCP_Packet { uint16_t source_port; uint16_t dest_port; uint32_t seq_no; uint16_t flags; uint16_t window_size; uint16_t checksum; unit16_t urgent; ... } __attribute__ ((packed));
- throwaway2048 13y agomany packet/wire formats are conceived as structs when they are designed
- Dylan16807 13y ago>It’s still 24 bytes because c cannot back into the inner struct’s trailing padding. To collect that gain you would need to redesign your date structures. Well that's disappointing. Is there any [nonstandard] way to get a compiler to take advantage of that space?
- overgard 13y agoJust a feature idea: I'd love an IDE plugin (for something like visual studio or eclipse) that would show this sort of information. Sort of like a disassembly, but for structs instead. I can imagine lots of industries where they'd pay for that sort of thing (IE, game programmers or OS developers, etc.)
- aidenn0 13y agoEmbedded IDEs already do this (showing the offsets of elements in a structure in a column when you are viwing structs).
- hdevalence 13y agoIt's not exactly what you're looking for, but clang can give you record dumps of C and C++ structs and classes. (In general, clang has lots of interesting tooling for C and C++, and I highly recommend looking into using it). I wrote here [1] about using it in a KDE program (KStars) to cut 10% off the memory usage. In particular you can also use this tool to see some of the many bad effects of deeply nested classes: your class may be 8-byte aligned, so a 'char' at the end can take up eight bytes with padding, and it's not possible (AFAIK) to rearrange fields up and down inheritance heirarchies [2]. [1]: http://www.hdevalence.ca/blog/2013-12-22-better-living-through-clangistry http://www.hdevalence.ca/blog/2013-12-22-better-living-throu... [2]: C++ is not my favorite programming language.
- xarien 13y agoThere are still statically typed languages used today like ada. although even within Ada, you'll often see programmers package spare buffers into structures to increase flexibility.
- anatoly 13y agoOne trick that's not mentioned is unbundling the struct. Suppose you have a struct with a pointer and a character in it, and a huge array of those structs. If you resent the padding tax, refactor your code to use and pass around two arrays instead, one of pointers and the other of chars.
- danieldk 13y agoIn fact, in Java this is the only way to simulate structs as POD rather than paying for the overhead of an array of objects.
- tokenrove 13y agoJust a note, this is sometimes called SOA (Structure of Arrays) or AOS -> SOA refactoring and comes up a lot when trying to take advantage of vector operations, too.
- _delirium 13y agoIt's interesting this is making a revival in C for efficiency. When I was first learning to code ('90s), this style of "parallel arrays" was seen as a scripting-language wart. When you semantically want an array-of-struct in a bash script, you resort to parallel arrays instead, because it's what you can do easily.
- soup10 13y agoIs there an easy way to get the compiler to show what padding it's using for a structure? (other than filling the structure with marker values then dumping the data and picking through it with a hex editor)
- jgale 13y agoThe pahole(1) utility, mentioned above.
- stinos 13y agosmall typo, under 4 it says a 54-bit machine. small remark: this will cover dates to 2050 that's a bit of a gamble, not sure I would have done that myself. It's probably ok but you never know in 40 years CVS and your code is still in use somewhere and you'll cause some people headaches :]
- Dylan16807 13y agoIt's especially weird as an optimization when an unsigned int would last until 2118. (Or 2106 if the weird base-changing was removed)
- stinos 13y agoexcellent point.
- tjgq 13y agoIn this particular case, it's not that big of a deal. As I understand it, this is an in-memory format that does not outlive program execution. One can safely assume that, even if CVS still exists in 40 years, no one will be using a 40-year-old version of this program by then.
- toast0 13y agoOne could also error out in this case; which is better than assuming!
- colomon 13y agoAs I understand it, he needed the compression to make the code work at all in the available memory. Since this is a source code distribution, presumably it will be pretty easy to fix in thirty years if the code is still being used. (Presumably we'll all have at least 256GB RAM available in 2043...)
- DigitalJack 13y agoI recently had to do this (padding) as I was using memcpy to load a struct from reading a binary file for a personal project.
- jjacobson 13y agoThis is the kind of stuff they teach you in college with a CS degree.
- lmm 13y agoIt really shouldn't be. Struct packing is a purely technical skill, not really computer science at all; there's no general insight you gain from understanding it, and it's easy to look up and teach yourself if you need to learn it later. (Not that most programmers will ever need to do it; these days even many embedded systems have enough memory and cpu performance that this kind of microoptimization is a poor use of programmer time)
- Moto7451 13y agoNot universally. None of my university's Java based curriculum or my brother's university's Python based curriculum mentioned this. My community college's C++ based curriculum mentioned it in passing. I seem to remember it being mentioned in Bruce Eckel's excellent "Thinking in C++". That said, I'm kinda curious how much this affects Objective C objects.
- krapp 13y agoNever mentioned once in my curriculum at all...
- ChuckMcM 13y agoInteresting timing, I've been playing around with Cortex M chips and a lot of the demo code has structures that are almost pathologically mis-aligned things like struct SomeCamelCaseNonsenseStructure { uint8_t flag; uint32_t pointer; uint8_t another_flag; uint32_t another_pointer; ... } I feel like flinching every time I read it.
- bjornsing 13y ago> If the compiler happened to map [the first member of a struct] c to the last byte of a machine word, the next byte (the first of p) would be the first byte of the next one and properly pointer-aligned. No, a compiler can't do this. You have to assume that the first member of a struct will be machine word aligned. I'm sure there are many reasons, but the one I can think of now is that structs can be dynamically allocated. That means it has to be possible to take the return value of malloc() and assign it to a pointer, and there is no way to get malloc() to return a memory block with that wired alignment (starting on the last byte of a machine word).
- jeffdavis 13y agoThis is still very practical when considering disk layouts of the structures. You want something compact enough on disk, but when it comes into memory, you still benefit from aligned access.
- userbinator 13y agoComing from an 8-bit assembly background, I've always found this alignment size/speed tradeoff to be a little vexing (either it's slower, or we're wasting memory), and thought "couldn't the hardware be better?" so finding out that x86 has evolved to the point where unaligned accesses basically have no penalty was really pleasing. No more bytes wasted, so we can have small and fast. (How do they do this? By making the memory bus a lot wider than a word, among other things.) IMHO ARM is just starting to see the value of this and catching up, if only the other architectures would do the same...
- jheriko 13y agothis is indeed somewhat lost. i learned it from coding standards at one place a long time ago... but since then I've had to explain it x number of times to juniors to the point where I wrote an article to point them at instead: http://jheriko-rtw.blogspot.co.uk/2011/02/know-your-cc-struct-layout-rules.html http://jheriko-rtw.blogspot.co.uk/2011/02/know-your-cc-struc...
- bobowzki 13y agoThis is very useful when programming microcontrollers. Especially if you create many structs in an array. Many parallel state machines or something like that.
- mcguire 13y agoFor those of you playing along at home, Rust currently manually interoperates with C structures. This[1] is one of the struct stat structures: pub struct stat { st_dev: dev_t, __pad1: c_short, st_ino: ino_t, st_mode: mode_t, st_nlink: nlink_t, st_uid: uid_t, st_gid: gid_t, st_rdev: dev_t, __pad2: c_short, st_size: off_t, Note the __pad elements. [1] https://github.com/mozilla/rust/blob/master/src/libstd/libc.rs#L369-L390 https://github.com/mozilla/rust/blob/master/src/libstd/libc....
- deleted 13y ago[deleted]
- xkarga00 13y agoWhy does "sizeof(struct foo5))" in packtest.c returns 8 instead of 6?