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

41–50 of 120 posts

Re: The Lost Art of Structure Packing (2018)

#41

Post by bregma »

gambiting wrote: post #10
BubRoss wrote: post #4

Earlier quoted context omitted.

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

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?

Re: The Lost Art of Structure Packing (2018)

#42

Post by shawxe »

scatters wrote: post #35
shawxe wrote: post #26

Earlier quoted context omitted.

Yeah, it's called memset. Not sure if this bug is supposed to be subtle or something, but if you require the padding bytes to be consistent then you need to consistently initialize your structs. Ignoring UB often leads to these sorts of bugs. EDIT: Based on some of the comments I'm getting here, it seems like some of you have never implemented a hashmap/generic interface in vanilla C and it shows. If you want a hashm…

memset, sure, then you copy the struct (return it or pass it by value) and the compiler won't bother copying the padding bytes. Or worse, an optimizing compiler will see that you're writing to padding bytes and helpfully no-op it.

First of all, there is no way the compiler is going to optimize a call to memset(&foo, 0, sizeof(foo)) when &foo is being interpreted as a void pointer. That doesn't even make sense.

Second of all, in a generic C interface keys are likely to be treated as void pointer and almost certainly are going to be moved around with memcpy etc. rather than returned/passed by value since doing so would make the interface non-generic.

Re: The Lost Art of Structure Packing (2018)

#43

Post by WesolyKubeczek »

DagAgren wrote: post #39
WesolyKubeczek wrote: post #34

Earlier quoted context omitted.

It's been 5 minutes already, why pay attention to one DagAgren and their comments?

May I present my own achievements, such as: Not being an awful racist, and not spending any of my time defending pedophile rapists?

Ah, you're one of _those_ people.

Re: The Lost Art of Structure Packing (2018)

#44

Post by dependenttypes »

shawxe wrote: post #42
scatters wrote: post #35

Earlier quoted context omitted.

memset, sure, then you copy the struct (return it or pass it by value) and the compiler won't bother copying the padding bytes. Or worse, an optimizing compiler will see that you're writing to padding bytes and helpfully no-op it.

First of all, there is no way the compiler is going to optimize a call to memset(&foo, 0, sizeof(foo)) when &foo is being interpreted as a void pointer. That doesn't even make sense. Second of all, in a generic C interface keys are likely to be treated as void pointer and almost certainly are going to be moved around with memcpy etc. rather than returned/passed by value since doing so would make the interface non-gen…

The HN markdown ate your stars.

Re: The Lost Art of Structure Packing (2018)

#45

Post by shawxe »

dependenttypes wrote: post #44
shawxe wrote: post #42

Earlier quoted context omitted.

First of all, there is no way the compiler is going to optimize a call to memset(&foo, 0, sizeof(foo)) when &foo is being interpreted as a void pointer. That doesn't even make sense. Second of all, in a generic C interface keys are likely to be treated as void pointer and almost certainly are going to be moved around with memcpy etc. rather than returned/passed by value since doing so would make the interface non-gen…

The HN markdown ate your stars.

Thanks for letting me know, should be better now! :-)

Re: The Lost Art of Structure Packing (2018)

#46

Post by Natsu »

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.

Re: The Lost Art of Structure Packing (2018)

#47

Post by kazinator »

shawxe wrote: post #45
dependenttypes wrote: post #44

Earlier quoted context omitted.

The HN markdown ate your stars.

Thanks for letting me know, should be better now! :-)

Basically, put a space after the star that you want to render verbatim, and don't try to do that in a region of text that is already italicized with stars.

E.g. "... being interpreted as a void * type."

Re: The Lost Art of Structure Packing (2018)

#48

Post by gambiting »

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?

I don't have the code in front of me, but something like

  int hash=0;
  for(int i=0;i(&obj)+i);
  return hash;
Basically hashing each byte of the memory containing the object, regardless of what the object itself represents.

We can argue whether that's a smart thing to do or not, but I wasn't in charge of implementing it - it's a relic from a codebase that's more than a decade old at this point. It's a simple hashing method that works with most types, but obviously dies horrendously in a case like this.

Re: The Lost Art of Structure Packing (2018)

#49

Post by shawxe »

kazinator wrote: post #36
shawxe wrote: post #26

Earlier quoted context omitted.

Yeah, it's called memset. Not sure if this bug is supposed to be subtle or something, but if you require the padding bytes to be consistent then you need to consistently initialize your structs. Ignoring UB often leads to these sorts of bugs. EDIT: Based on some of the comments I'm getting here, it seems like some of you have never implemented a hashmap/generic interface in vanilla C and it shows. If you want a hashm…

One solution consists of using memset to initialize the structure to zero, and using memcpy to copy it instead of structure assignment. (Problem: pass-by-value in function calls won't use memcpy; abstractly, it uses member-for-member assignment which is not required to copy padding. A function that wants to calculate the correct has has to prepare a blank object with memset, then individually assign the fields into i…

> Another solution, more along the lines of what I was thinking, is simply to associate the hash table with a hashing function which processes the type as a structure, hashing the members individually rather than as a pad of memory.

This solution is probably what I would go for in most cases as well. The most compelling reasons I can think of for going the other way would be if there were a desire to use a specific hashing function/algorithm on all keys regardless of type or if there were a desire to have keys of different types in the same map.

Re: The Lost Art of Structure Packing (2018)

#50

Post by ChrisSD »

htfy96 wrote: post #6
adrianN wrote: post #2

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)

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.

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