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.
The Lost Art of Structure Packing (2018)
21–30 of 120 posts
Re: The Lost Art of Structure Packing (2018)
#22I'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).
Re: The Lost Art of Structure Packing (2018)
#23It'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.
Re: The Lost Art of Structure Packing (2018)
#24Earlier quoted context omitted.
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?
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 str…
Yes, the C and C++ standards could have allowed the compiler to reorder structs, but that would have lead to even more of those undefined behavior situation that people complain so much about.
People do quite often rely on the first struct element being at the start of the struct. Memcpy:ing directly between structs and network/disk is also common, but naughty. Both struct padding and endianness already break that.
Re: The Lost Art of Structure Packing (2018)
#25When 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.
Re: The Lost Art of Structure Packing (2018)
#26Earlier 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…
> C++20 now has a "hashable" concept to help with this I'm sorry, you can easily solve this problem in K&R C from 1979.
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 hashmap that is generic and you don't want to write/specify a hashing function for keys on map initialization, then what you're likely to end up doing is ensuring that keys are initialized consistently, providing key size on map initialization, and simply performing a hash on the key as though it were a buffer of bytes.
Suggesting that this is somehow any more fragile than anything else in C or that templates should be used instead, which is an absurd comment since templates do not exist in C, is ridiculous. This comment is replying to a comment about how solutions to this problem have existed since K&R C--and they have. You don't need templates to not ignore UB, although if you are using C++ you can certainly use templates (and also take advantage of the stronger type system) to work around issues like this.
The point is that avoiding undefined behavior in C/C++ hashmap implementations is not something that has only recently become possible. C solutions may be more fragile, but that doesn't stop them from being "correct" in that will yield correct behavior unless an error is made elsewhere. Code that makes assumptions about the values of padding without explicitly setting those values is NOT correct and for anyone who works in a language like C/C++ regularly, that should be obvious.
Re: The Lost Art of Structure Packing (2018)
#27Earlier quoted context omitted.
> C++20 now has a "hashable" concept to help with this I'm sorry, you can easily solve this problem in K&R C from 1979.
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…
I don’t think memset is required to zero out padding bytes. The correct way to do this is to only access non-padding bytes.
Re: The Lost Art of Structure Packing (2018)
#28It'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.
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.
Re: The Lost Art of Structure Packing (2018)
#29Earlier quoted context omitted.
> C++20 now has a "hashable" concept to help with this I'm sorry, you can easily solve this problem in K&R C from 1979.
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…
Wrong answer. This is brittle and relies on the memory always being initialized correctly and will be prone to all sorts of issues in the wild. Better is just either templatize on the key type or store the size on the map.
Re: The Lost Art of Structure Packing (2018)
#30Earlier 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…
Wrong answer. This is brittle and relies on the memory always being initialized correctly and will be prone to all sorts of issues in the wild. Better is just either templatize on the key type or store the size on the map.
The answer is wrong more because it relies on padding bytes having consistent values than a lack of templating.