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

The Lost Art of Structure Packing (2018)

catb.org

Post reply on HN
Print view View original

61–70 of 120 posts

Re: The Lost Art of Structure Packing (2018)

#61

Post by saagarjha »

WesolyKubeczek wrote: post #37
saagarjha wrote: post #28

Earlier quoted context omitted.

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.

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

For interoperability concerns within the language itself, this is usually solved by making the layout algorithm deterministic or passing around the aggregate around with an invisible pointer. When interacting with other languages, typically there's an attribute to ensure that layout matches declaration order.

Re: The Lost Art of Structure Packing (2018)

#63

Post by grandinj »

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.

Re: The Lost Art of Structure Packing (2018)

#65

Post by saagarjha »

hellofunk wrote: post #62

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.

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.

Re: The Lost Art of Structure Packing (2018)

#66

Post by virgilp »

klodolph wrote: post #16
virgilp wrote: post #7

Earlier quoted context omitted.

Pad - yes, typically. Reorg - seldom.

Reorg is prohibited by C standard.

I know, it wasn't obvious to me that elteto talked exclusively about C/C++. AFAIK few -if any- compilers/VMs take it upon themselves to reorder struct members (even outside C/C++ world).

Re: The Lost Art of Structure Packing (2018)

#67

Post by Asooka »

bregma wrote: post #41
gambiting wrote: post #10

Earlier quoted context omitted.

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

If you rely on code containing undefined behaviour you're in for a world of butthurt sooner rather than later. There is no way in C++ to get at the padding bytes unless you're using undefined behaviour. How does the hash function work? Pointer aliasing using reinterpret_cast? Pointer aliasing using C-style casts? Typing punning through the old union switcheroo?

You can trivially get at the padding bytes, just cast to char pointer. Their contents are undefined and there is absolutely no guarantee that they will remain constant, but they're there.

Generally you have several possibilities for how to escape this problem, but the simplest is to just add the padding and a static assert that the sizeof the struct is what you expect.

Re: The Lost Art of Structure Packing (2018)

#68

Post by 0xDEEPFAC »

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

Re: The Lost Art of Structure Packing (2018)

#69

Post by leni536 »

virgilp wrote: post #66
klodolph wrote: post #16

Earlier quoted context omitted.

Reorg is prohibited by C standard.

I know, it wasn't obvious to me that elteto talked exclusively about C/C++. AFAIK few -if any- compilers/VMs take it upon themselves to reorder struct members (even outside C/C++ world).

Even though struct member reordering is prohibited, the order of std::tuple elements are not fixed by the standard. There could be an stdlib implementation that used this fact to reorder tuple members optimally.

AFAIK there are PoC 3rd party implementations for such tuples.

Re: The Lost Art of Structure Packing (2018)

#70

Post by carapace »

kazinator wrote: post #22

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…

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!
Post reply on HN