Every 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.
John 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.
Using 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.
Otherwise, 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)
Very 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.
A 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.
Sigh... 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.
Yes, 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.
Yup, 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.
On 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.
True (for some processors), but if you are doing packaged structs that should imply you have a reason to tell the compiler you know better than it how to write the struct. That most often (in my experience) means the struct is used for data interchange (ie network or files) and so you have to pay that price for byte access because byte access is a requirement. The other time to do that you might do this is when your are memory constrained and so you are willing to pay a runtime cost just to save a couple bytes of precious memory.
I have encountered the first often in the real world: networks are very common. I have only seen the latter one 8 bit CPUs (there they are paying a price to access bits not bytes)
> but if you are doing packaged structs that should imply you have a reason to tell the compiler you know better
I am pretty sure this could have been implemented better -- for malloc-ed and statically-allocated structs the compiler can know the alignment of the structure, so should be able to emit optimal code according to each case. Admittedly, probably a very minor improvement.
It is the feeling of surprise at the time that made me react -- this side-effect wasn't documented in GCC manual at the time, and still isn't.
We now have the attribute "aligned", so I am not sure what the code would look like for a struct {} __attribute__((__packed__,__aligned(8))).
I would guess that if the struct is packed, the compiler won't assume any particular alignment for the struct itself either, so even if a member is properly aligned relative to the beginning of the struct, it may not be properly aligned in memory.
On Intel CPUs there's virtually no cost for misaligned access. Of course, if your misalignment results in your data spanning 2 cache lines instead of 1, that'll be costly, but that's regardless of alignment.
Last 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.
I 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.
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.
I 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.
My 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.
Bitfields 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.
Knowing 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.
You 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.
you 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.
TL;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.
> 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.
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.
I agree with you, but it'd be nicer if it were easier to figure this out from the standard --- either I'm missing something or else you have to infer it from reading between the lines:
6.7.2.1 para 15 of the C11 standard:
Within a structure object, the non-bit-field members and the units in which bit-fields
reside have addresses that increase in the order in which they are declared. A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa.
6.7.2.1 para 17:
There may be unnamed padding at the end of a structure or union.
6.2.5 para 20:
An array type describes a contiguously allocated nonempty set of objects with a
particular member object type, called the element type.
So, on a platform with strict alignment, in order to achieve contiguous packing of structures (required by the last) and to achieve each structure member having a valid pointer (required by the first) the implementation must add enough optional padding (allowed by the middle) to make the size of the structure aligned.
> You should also be using the fixed-width numeric types.
I believe the parent is referring to the int8_t, int16_t types rather than the implementation-defined int, short, long types here.
> I agree with you, but it'd be nicer if it were easier to figure this out from the standard --- either I'm missing something or else you have to infer it from reading between the lines:
> So, on a platform with strict alignment, in order to achieve contiguous packing of structures (required by the last) and to achieve each structure member having a valid pointer (required by the first) the implementation must add enough optional padding (allowed by the middle) to make the size of the structure aligned.
It's not in the standard per se. It's a requirement for machine code to function on certain platforms. The standard basically just says that in all cases compilers have to generate machine code that works properly. It is imposed by the designers of the processor, not the C standard.
> I believe the parent is referring to the int8_t, int16_t types rather than the implementation-defined int, short, long types here.
> 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.
The alignment requirement is platform-dependent. Some platforms can perform unaligned loads, which means an object can be allocated at any byte offset in memory. There are no requirements in the C standard for alignment other than conforming to the specific hardware.
> 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).
Yes, and in practice this depends on the compiler and the platform, which was my point.
> I'm not aware that C provides any other, currently. Though you can simulate them with libraries, of course.
None of the numeric types enumerated in the standard have a fixed size associated with them in the C standard[1]. They have minimum representation ranges, but that is it.
[1] I'm not counting IEEE754 floating-point types, since that is a standard imposed on the C standard itself.
uint32_t and friends instead of the implementation-defined unsigned int/long.
See http://pubs.opengroup.org/onlinepubs/007904975/basedefs/stdi... for many details (including things like the name for "the fastest signed integer type with at least 8 bits", which could be signed char on machines that support byte access in hardware and signed 32-bit on machines where byte addressing means loading a word, bit-bashing the new value in, and storing it back).
Can you give an example of a compiler and platform where this isn't true? I thought it was part of the standard, and I've never seen C code that didn't make the assumption that this is true.
IIRC, icc does not normally pad structures, since x86-64 supports unaligned loads fairly well. xlc on POWER generally tries to do what kazinator stated above because unaligned loads are expensive, if even possible, on those platforms.
Alright this might be a stupid question, but if packing is about the order in which the fields are arranged... shouldn't the compiler optimize that? I mean, it does much more complex optimizations already doesn't it?
>The optimization is present in other languages that did not start with this restriction, but it's too late for C now.
Which?
.NET is the only one I could find that appears to do some from of smart packing [1]
The new hotness languages behave like:
Go doesn't sort by size. It packs to the byte, but guarantees structures within structures will start on the 32/64bit boundary (depending on 32/64bit system) so it'll pad for them.
Rust ignores field size and just aligns to the 32bit boundary, unless you trigger `#[repr(C)]` which will pack like C. Rust doesn't give any guarantees about a structure is laid out to be perfectly honest.
C++, NIM, D.
I can find no reference on Crystal except that you can opt into C behavior. So I don't know what default is.
Rust doesn't ignore field size nor does it align to any particular boundary. E.g. struct Foo { x: u8 } is one byte and has alignment 1, and similarly struct Bar { x: u8, y: i16 } is 4 bytes and has alignment 2. The compiler doesn't give guarantees about structure layout so that it is able to reduce the size by reordering fields.
It says Struct fields are aligned to to the 32/64bit boundary based on system architecture. Then you have #[repr(u8/u16/u32/u64)] which will align to 8/16/32/64 boundary.
The bulk of this section is describing how Rust has reserved the right to reorder and pack stuff. The first example happens to be 32-bit aligned because it contains a value that is.
The compiler can't optimize this in general as this affects the ABI when the struct itself is exposed (that's one of the reason why it is useful to avoid exposing struct themselves but just pointer when you can).
A lot of systems code involves directly messing with the memory of a specific struct, and if a compiler moved the struct fields around with the programmer knowing, there would be a lot of memory problems.
What if your struct is actually a memory-mapped I/O device? Far from optimizing you need to give a hard guarantee that it will NEVER be optimized by the compiler.
Suppose C didn't require order of struct members. How could we support I/O devices? Simply by wrapping them behind functions or macros which take a base address and access a specific register relative to that address using pointer arithmetic and dereferencing. You see this being done anyway!
if ((SERIAL_STATUS_PORT(port_addr) & SERIAL_DTR) != 0) {
/* DTR line is asserted */
}
More likely you'd have to drop down into ASM for those bits...
You see in a lot of high performance networking code too, you just get a block of bytes off the wire, cast it to a struct and use it straight away. High risk, high reward :-)
ISO C has codified the C tradition that structure members are laid out in the order in which they are declared. The first member has the same address as the struct itself. The remaining members are then at increasing offsets from that address.
Languages which allow compilers to reorganize structures for better packing (like, I think, Ada) have to have some provision to disable that in cases when the programmer requires the structure to conform to some externally imposed layout.
I wish we could say that C does this to adhere to some principle of being predictable and obeying the programmer literally. However, that cannot be claimed with a straight face by anyone who knows anything about this language, in which you can cause undefined behavior just by giving the code a dirty look in the text editor window. What C gives you with predictable structure layout, it immediately takes away with scrambled evaluation order of function arguments and constituent subexpressions of most operators.
Anyway, one consequence of a predictable layout is that C programs can do punning among structures which share a common initial sequence of members. One form of such punning is even required by ISO C to work: when a union is made of such struct types. Related hacks not involving binding through a union, however, also broadly work in de facto practice.
Structs get written directly to disk and network. Copies of the same program would produce different output depending on the optimization strategy they were compiled with. That's vigorously not allowed.
Also, the translation unit compilation model of C would be troublesome here, if optimization settings could influence struct layout. You can't have different translation units interpreting the same struct type declaration differently.
A huge and important use of structs is to communicate with other things, like hardware, libraries, and other languages, and in in those cases it's very important that the struct matches what the other side expects. You don't want the compiler to rearrange your TCP packet, for example.
It might make sense to have a compiler extension to optimize packing for internal-only data structures, but I doubt any compilers bother. It's just another entry on the long list of things that C assumes the programmer will do themselves if it's important to them.
Then the memory layout of the struct will be different. So when you serialise it read it back it would be different, if you perhaps used a different non optimising compiler.
Aside from the ABI, file I/O, and memory mapping concerns voiced by others, it's also not always a performance optimization: Occasionally you really want two members of a struct to e.g. reside in different cachelines to avoid "false sharing" murdering your performance in multithreaded code (where multiple cores repeatedly fight over who owns / can update the cacheline in question.)
Modern compilers all have warnings you can opt into, to alert you when the compiler inserts implicit padding, if you want to ensure things get packed nicely.
I mostly just vacuum up a huge amount of material from as many sources as I can. My focus on game development might help here. A lot of it flows from understanding CPUs from a low level hardware perspective - you might be able to reverse engineer this kind of knowledge from the wikipedia articles, although I haven't tried doing so myself.
E.g. the page for "CPU cache" references:
- CPUs read/write by cacheline
- Caches need to coordinate to avoid stale data through "cache coherence protocols" (which have a cost as mentioned on their own wiki page)
"False sharing" is just the interplay of those two mechanisms in worst case scenarios and such corner cases.
About the only time I've used this knowledge of false sharing has been when implementing a work-stealing task queue system. And I suppose the few times I've written a parallel for loop of some description.
Trying to think of similar performance issues to guide you towards, a few come to mind:
1) CPU caches are basically implemented as fixed sized hashmaps with a really poor hash - the address modulo some power of two, with a fixed limit of collisions supported.
I've never actually used this knowledge, although I could see it coming up if I were working on the design of a database's in-memory storage or something.
2) Reading "write combined" memory is really bad, including implicitly reading by failing to write entire cachelines (comes up with GPU resources such as textures)
This one I'm mindful of whenever I'm porting programs to use new graphics APIs, or writing the low level systems that deal with them in the first place. I feel there's at least one more situation where write combined memory has come up for me in practice (since typical memory access is not write combined), but it escapes me at the moment. Fortunately most graphics API docs at least warn you not to read the memory they're pointing you towards, although they're not always as explicit as "memcpy entire cachelines from orbit, just to be sure."
3) Performance of atomics touching multiple cachelines is terrible, when it's even supported:
Normally I find out that this has been happening when I port a program to ARM and suddenly it crashes doing some kind of atomic operation or lock, because someone reinterpreted a char buffer instead of allocating properly, because cross-cacheline atomics are too crazy for ARM to bother implementing. Things like SSE and AVX also tend to perform... not so great, unless stuff is properly aligned for them.
EDIT: I guess fgiesen is one resource, at least, as it cropped up twice trying to google for sources for the things I'm talking about ;)
Wouldn't it make sense for the compiler to automatically optimize stuff like this? The compiler knows all about the underlying architecture the code will be running on, so it's best positioned to determine how to order data for optimal efficiency.
No as you might be poking hardware and having the compiler at best make something not work or at worst brick hardware is not good. Compilers can earn on padding, most with -Wpadding
ESR 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.
However, 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.
LOL. Okay, fair enough. I got so stuck on "but that's good advice for anybody!" that I apparently had a huge blind spot for the whack-a-doodle basis for this advice.
I really don't see how that's good advice. It's paranoia, and paranoia about something (being falsely accused of sexual assault) that very rarely happens.
It also strikes me as sexist. Every woman is a potential threat to you?
Its the current culture. Its current accepted to consider every man as a potential rapist, while for men, just the accusation of sexual misconduct is enough to ruin ones life for ever.
It is sexist, but its accepted sexist behavior. Those who would advocate for a less aggressive tone in gender politics get harassed by both camps.
Although 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.
IIRC, 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.
Unless 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).
Rust 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.
Is 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.
I 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!
The 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.
C11 §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.
If 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.
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?
It'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!).
115 comments
[ 2.9 ms ] story [ 180 ms ] threadhttps://hn.algolia.com/?query=The%20Lost%20Art%20of%20C%20St...
Blast form the past, I remember Bus Errors from Solaris days.
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.
8 byte entries, then 4 byte entries, 2 byte entries, chars/bytes, bits.
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.
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.
The code for a struct { char a; double b; } load reference on x86-64 after -O3 is:
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.It seems there are still some leftovers -- try: struct { int i:31; }; with and without __attribute__((__packed__)).
I have encountered the first often in the real world: networks are very common. I have only seen the latter one 8 bit CPUs (there they are paying a price to access bits not bytes)
I am pretty sure this could have been implemented better -- for malloc-ed and statically-allocated structs the compiler can know the alignment of the structure, so should be able to emit optimal code according to each case. Admittedly, probably a very minor improvement.
It is the feeling of surprise at the time that made me react -- this side-effect wasn't documented in GCC manual at the time, and still isn't.
We now have the attribute "aligned", so I am not sure what the code would look like for a struct {} __attribute__((__packed__,__aligned(8))).
Except ESR wrote this one. So maybe [FAUX-NOOB].
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()
https://news.ycombinator.com/item?id=6995568
https://news.ycombinator.com/item?id=9069031
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.
There are more than just a few.
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.
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...
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.
If a struct is declared like this:
then an array of this type can also be declared: 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.
6.7.2.1 para 15 of the C11 standard:
Within a structure object, the non-bit-field members and the units in which bit-fields reside have addresses that increase in the order in which they are declared. A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa.
6.7.2.1 para 17:
There may be unnamed padding at the end of a structure or union.
6.2.5 para 20:
An array type describes a contiguously allocated nonempty set of objects with a particular member object type, called the element type.
http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1570.pdf
So, on a platform with strict alignment, in order to achieve contiguous packing of structures (required by the last) and to achieve each structure member having a valid pointer (required by the first) the implementation must add enough optional padding (allowed by the middle) to make the size of the structure aligned.
> You should also be using the fixed-width numeric types.
I believe the parent is referring to the int8_t, int16_t types rather than the implementation-defined int, short, long types here.
> So, on a platform with strict alignment, in order to achieve contiguous packing of structures (required by the last) and to achieve each structure member having a valid pointer (required by the first) the implementation must add enough optional padding (allowed by the middle) to make the size of the structure aligned.
It's not in the standard per se. It's a requirement for machine code to function on certain platforms. The standard basically just says that in all cases compilers have to generate machine code that works properly. It is imposed by the designers of the processor, not the C standard.
> I believe the parent is referring to the int8_t, int16_t types rather than the implementation-defined int, short, long types here.
This is indeed what I was talking about.
The alignment requirement is platform-dependent. Some platforms can perform unaligned loads, which means an object can be allocated at any byte offset in memory. There are no requirements in the C standard for alignment other than conforming to the specific hardware.
> 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).
Yes, and in practice this depends on the compiler and the platform, which was my point.
> I'm not aware that C provides any other, currently. Though you can simulate them with libraries, of course.
None of the numeric types enumerated in the standard have a fixed size associated with them in the C standard[1]. They have minimum representation ranges, but that is it.
[1] I'm not counting IEEE754 floating-point types, since that is a standard imposed on the C standard itself.
uint32_t and friends instead of the implementation-defined unsigned int/long.
See http://pubs.opengroup.org/onlinepubs/007904975/basedefs/stdi... for many details (including things like the name for "the fastest signed integer type with at least 8 bits", which could be signed char on machines that support byte access in hardware and signed 32-bit on machines where byte addressing means loading a word, bit-bashing the new value in, and storing it back).
The optimization is present in other languages that did not start with this restriction, but it's too late for C now.
Which?
.NET is the only one I could find that appears to do some from of smart packing [1]
The new hotness languages behave like:
Go doesn't sort by size. It packs to the byte, but guarantees structures within structures will start on the 32/64bit boundary (depending on 32/64bit system) so it'll pad for them.
Rust ignores field size and just aligns to the 32bit boundary, unless you trigger `#[repr(C)]` which will pack like C. Rust doesn't give any guarantees about a structure is laid out to be perfectly honest.
C++, NIM, D.
I can find no reference on Crystal except that you can opt into C behavior. So I don't know what default is.
[1] https://msdn.microsoft.com/en-us/library/ms253935(v=vs.80).a...
It says Struct fields are aligned to to the 32/64bit boundary based on system architecture. Then you have #[repr(u8/u16/u32/u64)] which will align to 8/16/32/64 boundary.
https://doc.rust-lang.org/nomicon/repr-rust.html
The bulk of this section is describing how Rust has reserved the right to reorder and pack stuff. The first example happens to be 32-bit aligned because it contains a value that is.
You see in a lot of high performance networking code too, you just get a block of bytes off the wire, cast it to a struct and use it straight away. High risk, high reward :-)
For all I know, other languages may do just this (there's a comment farther down about Rust which appears to say this).
Languages which allow compilers to reorganize structures for better packing (like, I think, Ada) have to have some provision to disable that in cases when the programmer requires the structure to conform to some externally imposed layout.
I wish we could say that C does this to adhere to some principle of being predictable and obeying the programmer literally. However, that cannot be claimed with a straight face by anyone who knows anything about this language, in which you can cause undefined behavior just by giving the code a dirty look in the text editor window. What C gives you with predictable structure layout, it immediately takes away with scrambled evaluation order of function arguments and constituent subexpressions of most operators.
Anyway, one consequence of a predictable layout is that C programs can do punning among structures which share a common initial sequence of members. One form of such punning is even required by ISO C to work: when a union is made of such struct types. Related hacks not involving binding through a union, however, also broadly work in de facto practice.
Sure you can!
A huge and important use of structs is to communicate with other things, like hardware, libraries, and other languages, and in in those cases it's very important that the struct matches what the other side expects. You don't want the compiler to rearrange your TCP packet, for example.
It might make sense to have a compiler extension to optimize packing for internal-only data structures, but I doubt any compilers bother. It's just another entry on the long list of things that C assumes the programmer will do themselves if it's important to them.
Modern compilers all have warnings you can opt into, to alert you when the compiler inserts implicit padding, if you want to ensure things get packed nicely.
I wasn't aware of that sort of thing. any resources on learning these sorts of details of performance tuning, aside from hard-earned experience?
E.g. the page for "CPU cache" references:
- CPUs read/write by cacheline
- Caches need to coordinate to avoid stale data through "cache coherence protocols" (which have a cost as mentioned on their own wiki page)
"False sharing" is just the interplay of those two mechanisms in worst case scenarios and such corner cases.
About the only time I've used this knowledge of false sharing has been when implementing a work-stealing task queue system. And I suppose the few times I've written a parallel for loop of some description.
Trying to think of similar performance issues to guide you towards, a few come to mind:
1) CPU caches are basically implemented as fixed sized hashmaps with a really poor hash - the address modulo some power of two, with a fixed limit of collisions supported.
http://www.lshift.net/blog/2013/10/08/cpu-cache-collisions-i...
I've never actually used this knowledge, although I could see it coming up if I were working on the design of a database's in-memory storage or something.
2) Reading "write combined" memory is really bad, including implicitly reading by failing to write entire cachelines (comes up with GPU resources such as textures)
https://fgiesen.wordpress.com/2013/01/29/write-combining-is-...
This one I'm mindful of whenever I'm porting programs to use new graphics APIs, or writing the low level systems that deal with them in the first place. I feel there's at least one more situation where write combined memory has come up for me in practice (since typical memory access is not write combined), but it escapes me at the moment. Fortunately most graphics API docs at least warn you not to read the memory they're pointing you towards, although they're not always as explicit as "memcpy entire cachelines from orbit, just to be sure."
3) Performance of atomics touching multiple cachelines is terrible, when it's even supported:
https://fgiesen.wordpress.com/2014/08/18/atomics-and-content...
Normally I find out that this has been happening when I port a program to ARM and suddenly it crashes doing some kind of atomic operation or lock, because someone reinterpreted a char buffer instead of allocating properly, because cross-cacheline atomics are too crazy for ARM to bother implementing. Things like SSE and AVX also tend to perform... not so great, unless stuff is properly aligned for them.
EDIT: I guess fgiesen is one resource, at least, as it cropped up twice trying to google for sources for the things I'm talking about ;)
...so, ascending order?
(The option would be nice, though... most of the time, you don't care.)
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.
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.
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.
It also strikes me as sexist. Every woman is a potential threat to you?
It is sexist, but its accepted sexist behavior. Those who would advocate for a less aggressive tone in gender politics get harassed by both camps.
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.
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.
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.
He mentioned it in passing (and without proper syntax) in section 11.
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/
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.
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?