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

61–70 of 116 posts

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

#61

Post by blaisio »

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.

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.

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

#62

Post by kazinator »

gaius wrote: post #52
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?

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 */
    }

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

#63

Post by blaisio »

samfisher83 wrote: post #15

You can kind of do this is in C# with StructLayoutAttribute. One of the few high level languages you can do it with.

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.

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

#64

Post by Grishnakh »

gaius wrote: post #52
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?

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.

Well if we were making an all-new C-like language, we could just add a compiler directive which prevents optimization for cases like this.

For all I know, other languages may do just this (there's a comment farther down about Rust which appears to say this).

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

#65

Post by nwmcsween »

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.

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

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

#66

Post by david-given »

kazinator wrote: post #54
vonmoltke wrote: post #38

Earlier quoted context omitted.

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

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.

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.

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

#67

Post by qwertyuiop924 »

andrepd wrote: post #47
qwertyuiop924 wrote: post #36

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.

Offtopic. His opinions on open source politics are little matter to his technical insights. I can appreciate Hitler's paintings, etc etc.

...Which is why despite that, I still think this article is good, and said so.

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

#68

Post by superuser2 »

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?

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.

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

#69

Post by vonmoltke »

kazinator wrote: post #54
vonmoltke wrote: post #38

Earlier quoted context omitted.

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

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

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

#70

Post by dmit »

cheez wrote: post #37
tedunangst wrote: post #34

Earlier quoted context omitted.

That doesn't make it a lost art. I've no clue how to make wine (something to do with grapes?) but I don't describe it as a lost art.

Most programmers would have known this a few years ago. Programmers today don't. So, it is a lost art.

There are more people alive who know this in the year 2016 than at any prior point in history.
Post reply on HN