The Lost Art of C Structure Packing (2014) • Hacker News Board

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

#21

Post by wangchow » Fri, Aug 05, 2016, 3:54 PM UTC

kbob wrote: post #6

It concerns me when a technique I've used this week is called a "lost art". I'd suggest putting a [NOOB] tag on this kind of post. Except ESR wrote this one. So maybe [FAUX-NOOB].

Not a lost art--but a dying one. Think of how many people using languages that don't care about this sort of detail.

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()

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

#22

Post by minipci1321 » Fri, Aug 05, 2016, 3:54 PM UTC

looki wrote: post #13

minipci1321 wrote: post #5

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

You mean that it reads the values into single byte registers and assembles those back into the value you want?

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.

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

#23

Post by looki » Fri, Aug 05, 2016, 4:05 PM UTC

minipci1321 wrote: post #22

looki wrote: post #13

Earlier quoted context omitted.

You mean that it reads the values into single byte registers and assembles those back into the value you want?

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.

That sounds quite horrible - today was very eye-opening on why people almost never pack structs tightly, thank you.

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

#24

Post by jcranmer » Fri, Aug 05, 2016, 4:05 PM UTC

minipci1321 wrote: post #5

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

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.

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

#25

Post by Roboprog » Fri, Aug 05, 2016, 4:09 PM UTC

jgrahamc wrote: post #3

Ah, yes. BUS ERROR: http://blog.jgc.org/2007/04/debugging-solaris-bus-error-caus...

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.

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

#26

Post by Roboprog » Fri, Aug 05, 2016, 4:14 PM UTC

Roboprog wrote: post #25

jgrahamc wrote: post #3

Ah, yes. BUS ERROR: http://blog.jgc.org/2007/04/debugging-solaris-bus-error-caus...

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)

8 byte entries, then 4 byte entries, 2 byte entries, chars/bytes, bits.

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

#27

Post by vvanders » Fri, Aug 05, 2016, 4:20 PM UTC

looki wrote: post #23

minipci1321 wrote: post #22

Earlier quoted context omitted.

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.

That sounds quite horrible - today was very eye-opening on why people almost never pack structs tightly, thank you.

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.

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

#28

Post by Roboprog » Fri, Aug 05, 2016, 4:21 PM UTC

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.

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

#29

Post by Artlav » Fri, Aug 05, 2016, 4:23 PM UTC

Huh? "Lost art"?

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

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

#30

Post by bluGill » Fri, Aug 05, 2016, 4:27 PM UTC

minipci1321 wrote: post #5

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

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)