The Lost Art of C Structure Packing

http://www.catb.org/esr/structure-packing/

by Tsiolkovsky • 13 years ago

335 143 13 years ago

catb.org

rwmj• 13 years ago

He should mention this tool:

http://linux.die.net/man/1/pahole

JoachimSchipper4• 13 years ago

gcc -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• 13 years ago

You can always add -Wno-error=padded to disable -Werror just for -Wpadded

dllthomas2• 13 years ago

You could always pad manually to clear the warnings.

jevinskie• 13 years ago

You beat me to it. =) Here is an introductory article http://lwn.net/Articles/335942/

alextingle• 13 years ago

Is 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• 13 years ago

I 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).

pandaman5• 13 years ago

For 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• 13 years ago

x86 is a modern architecture

It's a modern ISA, implemented by modern microarchitectures.

colin_mccabe3• 13 years ago

If 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.

gaius2• 13 years ago

Agreed. This is just how normal people, err, construct structs.

You are not an advanced C programmer until you have grasped it. You are not a master of C until you could have written this document yourself and can criticize it intelligently

In other words, a "hacker" is someone just like ESR. More blowhardery. I for one don't claim to be a master...

hobs• 13 years ago

To be fair, he didn't claim that by writing this document he was a master of C, or that a master would only know this document, just that it was a piece of knowledge a master would should definitely have. Phrasing I guess.

pjscott3• 13 years ago

Elapsed time until someone used this article as an excuse to complain about the author, derailing the thread into non-struct-related flaming: about two hours.

That's longer than I was expecting! I think 2014 is going to be a good year!

FedRegister• 13 years ago

Yup, ESR is the embodiment of the American exceptionalism, white, male, heterosexual privilege resident in the hacker community, and the sooner that we move beyond his worldview (while still observing he is technically astute) the better.

tjgq2• 13 years ago

I strongly suspect this depends on how one comes across C. In my experience, people who learn C as a first language seem to develop a much deeper intuition for these subtleties than, say, someone who has cut their chops in higher-level languages and only then progresses (regresses? :)) to C.

stackcollision• 13 years ago

I think this is a pretty good assessment. I learned C first, so a lot of this stuff comes naturally to me. On the other hand, a friend of mine learned Java first. Now he's in a Master's program and doing C, and he's constantly asking me about low level stuff like byte alignment.

philh6• 13 years ago

I can read and write C, but I didn't know much about this, and I was only vaguely aware that bitfields exist.

vanderZwan• 13 years ago

His definition of "lost art" can be summed up as "can't be Googled". I think that is fair, at least when it come to programming.

ben0x539• 13 years ago

It's 2014, these days I'm gonna order struct members so members that logically belong together are adjacent, and spaced apart from other members!

drdaeman• 13 years ago

This 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.

JoachimSchipper4• 13 years ago

I'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.

_delirium3• 13 years ago

If 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• 13 years ago

Adding 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.

_delirium3• 13 years ago

Fwiw, -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• 13 years ago

__attribute__((packed)) in GCC is probably worth mentioning if you only want to apply it to selected structs.

YZF• 13 years ago

#pragma pack(push)

#pragma pack(1)

MSVC

eps• 13 years ago

#pragma pack(push, 1) // :)

pjscott3• 13 years ago

GCC also supports that pragma, for compatibility with MSVC:

http://gcc.gnu.org/onlinedocs/gcc/Structure-Packing-Pragmas....

Clang has this, too.

JoachimSchipper4• 13 years ago

Note 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• 13 years ago

Yeah. 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• 13 years 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• 13 years ago

Why doesn't the compiler handle this for the programmer? Seems "free" in the no-tradeoffs sense.

kristoffer3• 13 years ago

The elements of a C struct must be sequentially ordered in memory as specified in the code, that's defined in the standard.

merraksh• 13 years ago

I 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.

pandaman5• 13 years ago

I 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.

colin_mccabe3• 13 years ago

Why 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."

jheriko2• 13 years ago

this 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• 13 years ago

Because 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• 13 years ago

It 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.

valleyer2• 13 years ago

Starting with "the i7"? What microarchitecture do you mean?

pjscott3• 13 years ago

The 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.

solarexplorer• 13 years ago

If 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• 13 years ago

For people like myself who need a short reminder what a "cache line" is:

* http://en.wikipedia.org/wiki/CPU_cache#Cache_entries

* http://stackoverflow.com/questions/14707803/line-size-of-l1-...

jeremiep• 13 years ago

I 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.

dfox4• 13 years ago

Problem 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.

soup102• 13 years ago

The 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.

Dylan168072• 13 years 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?

overgard2• 13 years ago

Just 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• 13 years ago

Embedded IDEs already do this (showing the offsets of elements in a structure in a column when you are viwing structs).

sitkack• 13 years ago

Do you have some screenshot examples? I like the idea of this feature.

overgard2• 13 years ago

Neat, what IDE?

hdevalence2• 13 years ago

It'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-throu...

[2]: C++ is not my favorite programming language.

xarien• 13 years ago

There 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.

waynecochran• 13 years ago

Classic 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• 13 years ago

many packet/wire formats are conceived as structs when they are designed

anatoly• 13 years ago

One 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.

microtonal• 13 years ago

In fact, in Java this is the only way to simulate structs as POD rather than paying for the overhead of an array of objects.

wging2• 13 years ago

Sorry, POD?

finnw• 13 years ago

Not the only way. You can interleave fields in a ByteBuffer.

tokenrove• 13 years ago

Just 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.

_delirium3• 13 years ago

It'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.

evincarofautumn2• 13 years ago

Working with unzipped structures (xs+ys instead of xys) can be a bit of a pain. It seems like a transformation that a compiler should be able to do easily, given enough information about structure and (ugh) aliasing. I wish C had real array types. :(

carterschonwald2• 13 years ago

Happily, in Haskell the standard array library does the struct of arrays format for unboxed arrays. It's super handy!

PurplePanda• 13 years ago

Some lisp systems implemented pairs this way. A global array of CARs and a global array of CDRs

rcfox• 13 years ago

It's also great for minimizing cache misses if you find yourself iterating over arrays of large structs and just operating on one field from each of them.

slavak• 13 years ago

The ISPC[1] language has syntax for requesting the compiler perform this transformation for you, giving you the performance benefits for free without requiring manually writing out the code or even paying the price in syntactic clarity (you can still write out p[0].x+p[1].x instead of px[0]+px[1]).

[1] http://ispc.github.io/

soup102• 13 years ago

Is 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• 13 years ago

The pahole(1) utility, mentioned above.

stinos2• 13 years ago

small 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 :]

Dylan168072• 13 years ago

It's especially weird as an optimization when an unsigned int would last until 2118. (Or 2106 if the weird base-changing was removed)

stinos2• 13 years ago

excellent point.

tjgq2• 13 years ago

In 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• 13 years ago

One could also error out in this case; which is better than assuming!

colomon• 13 years ago

As 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• 13 years ago

I 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• 13 years ago

This is the kind of stuff they teach you in college with a CS degree.

lmm• 13 years ago

It 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• 13 years ago

Not 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• 13 years ago

Never mentioned once in my curriculum at all...

ChuckMcM• 13 years ago

Interesting 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• 13 years 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• 13 years ago

This 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.

userbinator4• 13 years ago

Coming 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...

jheriko2• 13 years ago

this 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-struc...

bobowzki• 13 years ago

This is very useful when programming microcontrollers. Especially if you create many structs in an array. Many parallel state machines or something like that.

mcguire2• 13 years ago

For 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....

xkarga00• 13 years ago

Why does "sizeof(struct foo5))" in packtest.c returns 8 instead of 6?

The Lost Art of C Structure Packing

Related Stories