Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Lost Art of C Structure Packing (2014)

catb.org

Post reply on HN
Print view View original

51–60 of 116 posts

Re: The Lost Art of C Structure Packing (2014)

#51

Post by to3m »

Grishnakh wrote: post #49
kazinator wrote: post #31

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…

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.

The C rules don't permit it. Putting fields in the order specified is not the worst possible default.

(The option would be nice, though... most of the time, you don't care.)

Re: The Lost Art of C Structure Packing (2014)

#52

Post by gaius »

dysoco wrote: post #41
kazinator wrote: post #31

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…

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?

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.

Re: The Lost Art of C Structure Packing (2014)

#53

Post by valarauca1 »

Arnavion wrote: post #42
dysoco wrote: post #41

Earlier quoted context omitted.

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 language spec prevents it from doing so for ABI reasons. The optimization is present in other languages that did not start with this restriction, but it's too late for C now.

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

Re: The Lost Art of C Structure Packing (2014)

#54

Post by kazinator »

vonmoltke wrote: post #38
kazinator wrote: post #31

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…

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

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

Re: The Lost Art of C Structure Packing (2014)

#55

Post by kazinator »

dysoco wrote: post #41
kazinator wrote: post #31

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…

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?

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.

Re: The Lost Art of C Structure Packing (2014)

#56

Post by blaisio »

ThatGeoGuy wrote: post #40

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 anyth…

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.

Re: The Lost Art of C Structure Packing (2014)

#57

Post by blaisio »

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.

Re: The Lost Art of C Structure Packing (2014)

#58

Post by blaisio »

throwanem wrote: post #45
kazinator wrote: post #31

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…

> reverse descending order ...so, ascending order?

What they mean is put the largest fields at the top and the smallest fields at the bottom.

Re: The Lost Art of C Structure Packing (2014)

#59

Post by jevinskie »

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!

http://git.kernel.org/cgit/devel/pahole/pahole.git/log/

Post reply on HN