The Lost Art of Structure Packing (2018)

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

by theastrowolfe • 6 years ago

112 112 6 years ago

adrianN2• 6 years ago

It would be nice if there was an annotation that just lets the compiler do all the optimization for me for the cases where I don't care about the memory layout of the struct. Just like the Rust compiler can do without repr(C)

elteto2• 6 years ago

Wait, forgive my ignorance, isn’t this the default? If you don’t care about the memory layout then won’t the compiler reorg / pad structure members to fulfill alignment?

virgilp2• 6 years ago

Pad - yes, typically. Reorg - seldom.

Chabsff• 6 years ago

The rule needs to be deterministic accross compilers, since a library can be compiled using a compiler and linked in an executable using the same header.

flohofwoe2• 6 years ago

Nope, C and C++ compilers are not allowed to reorder struct fields (AFAIK at least, I haven't seen this yet in any real world compiler), but they will add padding bytes for natural alignment (and that's where the "waste" is coming from).

IMHO there are just as many arguments for automatic reordering as there are against it (e.g. creating structs that are layed over memory mapped IO registers, or just optimizing a struct for certain cache-efficient access patterns). In my opinion it's sufficient to know about the existance of alignment-padding, and how to work around it if needed (for instance reordering the struct members manually, or using #pragma pack)

elteto2• 6 years ago

I see, thanks all.

steerablesafe2• 6 years ago

Unfortunately pointer comparison between addresses of subobjects has a defined order, so reorg is not possible.

SlowRobotAhead3• 6 years ago

A practical reason you can’t just allow the compiler to do it is if you are doing goofy things like overlaying two structures, void pointer manipulation or casting one object to the format of another because you know the first n number of elements line up anyhow, or if you’re changing specific bytes as memory manipulation and not by the object itself.

Typically if I define a 8bit as the first element, I need to be certain those 8bits are first even if that wastes three more bytes to align on the next variable.

htfy96• 6 years ago

Automatic reordering of fields is great, but sometimes people know more about how they will be used (like frequently accessed groups of fields, or leave some fields in the first 256 bytes so a u8 relative index could be used to save space), so manual reordering still exists for a reason beyond packing.

ChrisSD2• 6 years ago

I believe adrianN was suggesting that it would be useful if you could opt-in to automatic reordering on a per struct basis. Currently C doesn't give a choice other than to do it manually.

dan-robertson• 6 years ago

This is hard. If your struct definition is in a header file then the compiler needs to generate correct field offsets for anything that includes that header file, so it would need to always optimally pack structure the same way based only on the definition and not on the usage.

People will also do silly things like casting between types in ways that rely on similarly written structures having similar memory layouts. So C is probably a bad language to turn this on by default in

nly2• 6 years ago

Great idea, but you have to define these optimizations and do them deterministically, even for debug builds, all the time - otherwise you'll never have a stable ABI.

munchbunny3• 6 years ago

If you do any development that requires touching Win32, structure packing and memory alignment is still very real.

I was recently doing that in the context of improving a language’s library support for something that had to go through the OS SDK. I don’t miss the days when that stuff was the norm.

BubRoss• 6 years ago

I have done some win32 programming but haven't encountered struct packing or alignment being an issue, where does that pop up?

gambiting3• 6 years ago

I work in video games, and very recently we had a sneaky bug in one of our AAA titles(that was already out!), where(in huge simplification) we had a struct that looked like:

  struct Obj
  {
    int foo;
    bool bar;
  }

then we were storing those in a custom hashmap using these as keys, where the hashing function was basically hashing bits of each stored object, without any awareness of what's in the object.

The bug was found when someone did something like:

  void DoSomething(Obj obj)
  {
    if(!map.has(obj))
      map.add(obj, new Whatever());
  
    map[obj].blah(); //CRASH null pointer exception
  }

I was like.....well, if there is no key "obj" in the map, we insert one....and yet literally one line after it doesn't have a value for that key??? How can this be?

Well, it can be because even though the struct looks like it takes 5 bytes, in reality it's 8 bytes because it's getting padded. So a naive hashing method that just looks at bits is hashing your 5 bytes of actual data + 3 bytes of garbage, which means that two "identical" objects are very unlikely to actually produce the same hash.

C++20 now has a "hashable" concept to help with this, but it still requires the programmer to be aware of structure packing.

munchbunny3• 6 years ago

It's abstracted behind the API's data types as long as you're using C++, but in order to work with the data types you often have to maneuver around the specific packing/alignment. The Windows ETW tracing API has several examples of specific "structure packing" phenomena:

1. Arranging fields to pack things that are shorter than 4 bytes along 4 byte boundaries.

2. Manually arranging data buffers in very specific layouts (this is less about the original post, more about a different interpretation of "packing").

Aside from what I mentioned above, more commonly you will run into this in interop scenarios, such as calling C/C++ API's from C#. Thankfully those scenarios are few and far between.

joosters• 6 years ago

TLDR: When defining a struct, put the biggest items first. This works well in almost all cases.

If you need to squeeze out all padding, use compiler directives like '#pragma pack', but be aware of the performance implications.

kazinator15• 6 years ago

I've documented how GCC does bitfield packing in the TXR reference manual. Or rather, the abstract algorithm used in the FFI to replicate it.

https://www.nongnu.org/txr/txr-manpage.html#N-027D075C

This is the result of empirical investigation.

The description also covers allocation of non-bitfields (paragraph 3) and the padding of the structure (paragraph 9) which require few words.

I felt that the bitfield handling is so obscure that it had to be documented in detail. If someone is to know exactly what the layout will be, the documentation can't just be "oh, it will behave like a GCC struct". Well, what will that do? That is not adequately documented anywhere.

If I have to work with bitfields in just C, I can use that as a reference to understand what the compiler will do (at least if it's anything compatible with GCC).

carapace2• 6 years ago

That's awesome! It's the kind of detail that, when you need it you really need it, but it's often so hard to find, or locked in some proprietary deal. I can barely imagine the amount of work it must have taken to nail all that down. Congratulations, and thank you!

kazinator15• 6 years ago

I tried numerous cases, and looked at the memory, and also read and wrote the structures with FFI to make sure they match what the C compiler is putting out, and fixed bugs along the way. For big endian investiations, I borrowed the big endian PPC machine courtesy of the GCC Compile Farm project.

The details are not obvious; like the fact that a zero width bitfield like "int : 0" that appears etween two members that are not bitfields actually does something. E.g. this has size 5:

   struct {
     char c1;
     int : 0; // zero-width bit-field must be unnamed
     char c2;
   };

This is basically because c1 is de-facto considered to be 8 allocated bits out of an int-wide cell, leaving 24 bits in that cell. The int : 0 sees that a field has been partially filled and so increments to the next int-wide field (according to my documented hypothesis).

ISO C says (or did say in 1999) only this: "A bit-field declaration with no declarator, but only a colon and a width, indicates an unnamed bit-field.105) As a special case, a bit-field structure member with a width of 0 indicates that no further bit-field is to be packed into the unit in which the previous bit-field, if any, was placed."

No "further bit-field" is to be packed, but in this example there is neither a previous nor next bit field. So you might expect that there is no effect. In the GCC model of "all allocated so far are just bits", it has an effect.

Footnote 105 says just that "An unnamed bit-field structure member is useful for padding to conform to externally imposed layouts" which is more or less self-evident.

Oh wow; I just realized that the empty bit-field has an effect if it is the last member also:

   struct {  // now size 8!
     char c1;
     int : 0;
     char c2;
     int : 0;
   };

This is predicted by my documentation, but it should be spelled out in an explicit remark.

It's a useful feature of GCC bit-fields because you can conform to certain external layouts without having to use bit-fields at all, other than the zero-width ones.

not2b• 6 years ago

You could have saved time and gone to the ABI spec.

https://itanium-cxx-abi.github.io/cxx-abi/abi.html

This was originally developed as a joint effort to make compilers ABI-compatible on Itanium, but it's also used (by GCC, clang, Intel's proprietary compiler and others) on x86-64.

An old Hacker News comment said that it's from Intel; it's not, it was a joint effort with lots of work from CodeSourcery and Red Hat folks.

kazinator15• 6 years ago

The document you link to is entirely about C++, and makes numerous references to some "base (C) ABI".

"The size and alignment of a type which is a POD for the purpose of layout is as specified by the base (C) ABI"

The links in 1.5 Base Documents are old and broken.

throwaway_pdp09• 6 years ago

It's probably not talked about so much now because of the canard that memory is cheap, and because HLLs disguise things a bit too much and so mislead newbies, but to suggest it's lost is plain wrong.

saagarjha24• 6 years ago

I think the main reason is that many new languages do this for you, at the cost of not guaranteeing a particular structure member order.

WesolyKubeczek• 6 years ago

Sheesh, we're trying to be ABI-compatible over here.

garjana• 6 years ago

When I worked at a prop trading firm on a greenfield market data system this kind of optimization was very much on our minds. I assume others in this field also take care to pack structs.

Natsu2• 6 years ago

I'm sort of surprised there are no tools for this. I understand why having the compiler reorder things could be bad, though it seems like there should be room to tell the compiler it's okay to repack it for minimum space, but I don't even see any mention of a source-level tool that would just sort the items in a struct for you.

It seems like something like that could be useful rather than making programmers try to order their structs by hand.

SlowRobotAhead3• 6 years ago

If you just order top down in structures from pointers, 32s, 16s, arrays, 8s, it’s almost entirely done without thinking.

There is almost never a difference to the user what order things are structured. Although to be fair this does get tricky with unions of structure over structure.

Natsu2• 6 years ago

True, but that's the kind of drudgery that's best farmed off to computers. I see that the comment above mentions there is a tool for this that I simply wasn't aware of.

smcameron• 6 years ago

There's pahole https://lwn.net/Articles/335942/

dorianh• 6 years ago

I always assumed that in C, a given structure would always have the same memory layout, no matter what the compiler is (as long as the compilers target the same architecture of course).

I always assumed that in C++, the memory layout could change a lot between compilers (the location of the pointer to the vtable for example). Do you know if it's true, and if the layout do change, could you give an example?

saagarjha24• 6 years ago

I always assumed that in C, a given structure would always have the same memory layout, no matter what the compiler is (as long as the compilers target the same architecture of course).

Usually, but not always. In most cases there is one efficient way to pack the structure and still maintain member alignment, but there's not requirement that the amount of padding looks like this.

I always assumed that in C++, the memory layout could change a lot between compilers (the location of the pointer to the vtable for example). Do you know if it's true, and if the layout do change, could you give an example?

Yes, once you have a non-POD type the memory layout can be fairly arbitrary as you cannot really inspect it and compilers are free to lay it out as they wish.

ChrisSD2• 6 years ago

Most platforms have have system level C APIs that are exposed to userspace. When using these APIs it's necessary to layout structures as they expect. Therefore all compilers on the same platform (OS+arch) would usually produce the same layout for structs so that they are compatible.

However this isn't universally true. Some platforms might not have a well defined C ABI.

hellofunk• 6 years ago

Biggest surprise for me is learning that a pointer is a whopping eight bites! I have always mistakenly assumed they were small and just four bites.

saagarjha24• 6 years ago

It depends on the platform! On ILP64 and LP64 (and presumably P64, though I've never heard of this actually being used anywhere) they'll be 8 bytes, but not on most 32-bit architectures.

flyingfences• 6 years ago

Isn't that the _definition_ of a 32-bit (or 64-bit or 8-bit or however-many-bit) - that 32 bits is the length of a pointer?

grandinj• 6 years ago

I wrote a clang plugin to look for opportunities across a 10M line codebase and there was surprisingly little to be found. Why? Because on 64-bit Linux, the current C++ ABI mandates quite large alignment, especially once you are embedding things inside other things. Packing is still sometimes useful in speeding things up, but tends to require bitfields and flattening structs inside structs into a single struct, etc.

0xDEEPFAC• 6 years ago

Looks like what he really wants is to use Ada which has had much better support for low-level programming than C.

Example:

Word : constant := 4; -- storage element is byte, 4 bytes per word

type State is (A,M,W,P); type Mode is (Fix, Dec, Exp, Signif);

type Byte_Mask is array (0..7) of Boolean; type State_Mask is array (State) of Boolean; type Mode_Mask is array (Mode) of Boolean;

type Program_Status_Word is record System_Mask : Byte_Mask;

       Protection_Key     : Integer range 0 .. 3;

       Machine_State      : State_Mask;

       Interrupt_Cause    : Interruption_Code;

       Ilc                : Integer range 0 .. 3;

       Cc                 : Integer range 0 .. 3;

       Program_Mask       : Mode_Mask;

       Inst_Address       : Address;

 end record;

 for Program_Status_Word use

   record
       System_Mask      at 0*Word range 0  .. 7;

       Protection_Key   at 0*Word range 10 .. 11; -- bits 8,9 unused

       Machine_State    at 0*Word range 12 .. 15;

       Interrupt_Cause  at 0*Word range 16 .. 31;

       Ilc              at 1*Word range 0  .. 1;  -- second word

       Cc               at 1*Word range 2  .. 3;

       Program_Mask     at 1*Word range 4  .. 7;

       Inst_Address     at 1*Word range 8  .. 31;

   end record;

 for Program_Status_Word'Size use 8*System.Storage_Unit;

 for Program_Status_Word'Alignment use 8;

More info: https://www.adaic.org/resources/add_content/standards/05aarm...

SlowRobotAhead3• 6 years ago

I use C for embedded. I do the “lost art” of structure packing all the time. I don’t want ada.

I’m not sure why “use a different language” is such a common reply to any language specific discussion.

samatman• 6 years ago

For all its somewhat fussy verbosity, Ada really impresses me every time this sort of thing comes up.

I keep hoping the Zig developer will do a deep dive on Ada and bring over more of this kind of precise control. A language where I have this kind of control over layout, but can still spell `end record;` as `}`, is ideal for some projects I have in mind.

The Lost Art of Structure Packing (2018)

Related Stories