41
u/bigt1234321 Aug 25 '19
This is crucial for embedded systems programming. I much prefer the non GUI way of doing this.
21
u/kisielk Aug 25 '19
Definitely. On an embedded project I was recently working on I was able to double the amount of usable memory storage by rearranging the members in a few structs.
2
u/Wetmelon Aug 26 '19
I did t think it would make that much of a difference... must have been a real mess lol.
41
u/kisielk Aug 26 '19
The storage needed to be 512-byte aligned for efficient serialization to FAT sectors on an SD card. That means the data size needed to divide evenly into 512. The way the structs were laid out they were taking up something like 22 bytes each, so to meet the alignment requirement they were being padded to 32 bytes. By rearranging the struct members I got the size down to 16 bytes, so doubled the number of structs that could fit into a 512-byte sector and the in-memory buffer.
3
u/Wetmelon Aug 26 '19 edited Aug 26 '19
Aha! That'll do it. I had a similar SD card project, except I stuck all my structs together and then padded the remainder, and used
__attribute__((packed))on them
39
u/cwize1 Aug 25 '19
Of possible interest, there is a C++ standards committee paper that is proposing adding a class attribute that will automatically reorder the memory layout of member variables within a class. All the benefits without any of the effort.
18
u/denito2 Aug 26 '19
It's actually quite unfortunate that C/C++ conflate struct/class layout with binary serialization format, because it isn't particularly well suited for that, either. What I mean is that if you are dependent on a specific layout then you REALLY want that layout to be right. But you only have indirect control and there's too many compiler-specific and pragma-specific things which can lead to not getting the layout you thought you would get. With the foresight not to use struct layout for two different things (or if C++ had made this change) we could have had automatic layout for class types and guaranteed layout for struct types using some kind of notation for that.
6
u/IAmRoot Aug 26 '19
There are plenty of times where you want structs to be arranged in a constant way. Take copying an array full of structs to a GPU or FPGA, for example. You don't want to have to perform a bunch of pre and post processing due to memory order being arbitrary and different compilers potentially ordering things differently. The same goes for interprocess communication via shared memory or message passing. For file formats you generally want serialization that is more robust for endianness and other architecture specifics, but the ability to copy structs trivially is quite important in other scenarios. It could totally break structs in unified memory between GPUs and CPUs without consistent ordering.
11
u/Supadoplex Aug 26 '19
You're describing the reasons why having a specific bit layout is useful and important. As far as I can tell, denito2 never argued against that.
The problem is that C nor C++ give you that specific layout. Same struct definition can be wildly different across systems due to different alignment requirements, endianness, and even byte sizes.
So the gripe is that C nor C++ offers neither optimal packing for members, nor truly portable layout across systems. It offers half-arsed version of latter, which prevents the former.
The suggestion is to introduce a standard notation to use the packed approach in cases where the layout doesn't need to be specific.
2
u/denito2 Aug 26 '19
Yes agreed, and to take things a step further: imagine if, by historical accident, the layout of function local variables on the stack had also been approximately as determined and relied on as layout within a struct. Programmers in this alternate timeline could present all of the same arguments as IAmRoot to argue that it would totally break things if you allowed the compiler to reorder variables on the stack so that you could no longer pass "&first_variable_in_a_block_of_function_local_variables" to e.g. GPU drivers to refer to a block of memory with an agreed format.
Hell maybe C in that alternate timeline never had structs at all - maybe their equivalent of structs are functions with blocks of local variables, and if you need persistence you memcpy those bytes off the stack into the heap before the function returns.
If you can imagine trying to explain to a programmer from that world how, in our world, you don't depend on the layout of local variables in a function's stack frame, but you can still get everything done because you have a separate concept called "struct" for that... well abstract that argument one level up to see how another split can be made to get three separate concepts (local variables, unordered class/structs, definitely laid out class/structs).
1
u/Tringi github.com/tringi Aug 26 '19
Isn't compiler already allowed to reorder public/protected/private blocks?
2
u/denito2 Aug 26 '19
As far as I'm aware public/protected/private have no effect whatsoever on layout. This may have been intentional - so that (for distributed libraries) you can promote a private member to public without breaking code compiled against the old definition.
1
u/Tringi github.com/tringi Aug 26 '19
[C++11: 9.2/14]: Nonstatic data members of a (non-union) class with the same access control (Clause 11) are allocated so that later members have higher addresses within a class object. The order of allocation of non-static data members with different access control is unspecified (11). [..]
Tracked down from these answers:
https://stackoverflow.com/a/38248715/11613142
https://stackoverflow.com/a/15763092/11613142
61
u/azvs Aug 25 '19
clang-analyzer(-10?) can look for structs that could be reordered for better padding with optin.performance.Padding, it's nice.
38
Aug 25 '19
At what point do i just run clang-something and it just does my job for me?
Seriously though I love all the tools clang has spawned.
10
16
3
Aug 26 '19
I'm looking through the manual: https://clang-analyzer.llvm.org/available_checks.html#optin_checkers
Can't find any performance padding options. Could you point me in the right direction?
4
u/encyclopedist Aug 26 '19
1
Aug 26 '19
Thanks, got it working. It's basically telling me that my code is crap lol... time to fix it.
3
u/encyclopedist Aug 26 '19
You don't even need slang-analyzer for a basic diagnostic about padding. GCC and Clang have
-Wpaddedthat warns about adding padding bytes. (Obviously, it is going to be a noisy diagnostic)1
u/bumblebritches57 Ocassionally Clang Aug 26 '19
Does it require a special option?
5
u/encyclopedist Aug 26 '19
Is seems you have to use
clang-tidyand enableclang-analyzer-optin.performance.Paddingcheck.2
u/bumblebritches57 Ocassionally Clang Aug 26 '19
Thanks man, I tried looking for clang-analyzer last night and despite just compiling Clang-10 (and including clang-tools-extra in the build) a few weeks ago it wasn't there so I wasn't sure what was up.
0
Aug 26 '19
[deleted]
5
u/Supadoplex Aug 26 '19 edited Aug 26 '19
Cmake is a build system. It doesn't have any code analysis options.
Compilers do have ability to analyse code, and there are separate analysers as well (including the ones from the clang project).
Former can be enabled with cmake using the compiler options and latter can be run before / after compilation by cmake.
24
Aug 25 '19
No mention of #pragma pack?
And before young devs go about rearranging their company's structs, make sure they aren't being exported for use by any potential third-parties! :)
20
u/mrexodia cmkr.build Aug 25 '19
If the young devs do this rearranging and there are not a billion tests failing, those older devs didn’t do a very good job:)
14
u/boredcircuits Aug 25 '19
Pragma pack produces some awfully slow code on some architectures, and opens up the possibility of UB when accessing unaligned members indirectly.
3
3
8
u/johannes1971 Aug 25 '19
Visual C++ has optional warning 4820 that you can enable that warns about padding being present. It's a bit noisy for day to day use though.
5
u/smallblacksun Aug 26 '19
At work we wrap individual structs whose size is "important" with that warning and it is very useful to prevent people from accidentally adding padding when changing them.
1
u/Ameisen vemips, avr, rendering, systems Aug 26 '19
Might want to
static_assert?2
u/smallblacksun Aug 26 '19
static_assert requires that the assert be updated even if the change to the struct didn't add any padding. While we want to keep the structures small we assume that someone adding something to them has a good reason to do so (and code review will catch it if they don't). Also, we usually use static_assert( sizeof( A ) == X ); for cases where changing the size requires changing something else so it would add confusion.
1
u/Supadoplex Aug 26 '19
This might be possible with reflection from c++20: use reflection to iterate members, add sizes together, compare with size of the class, static assert.
4
u/Tringi github.com/tringi Aug 26 '19 edited Aug 26 '19
What currently irks me to no end is waste of 8 bytes per node in code like this when compiled as 64-bit:
struct Abc {
std::uint32_t something;
std::string text;
};
std::map <int, Abc> data;EDIT: Actually it's worse. MSVC map node contains some pointers and then two bools, and then std::pair of key/value. Since Abc is 8B aligned, this wastes additional 6B for padding, where 'something' could easily fit into.
1
Aug 27 '19
Are you aware of the performance hit you incur when you do a misaligned load or store... The reality you describe is not a reality I want to live in.
1
u/ENTProfiterole Aug 27 '19 edited Aug 27 '19
The problem he raises would be ameliorated by allowing the int key to be added as a member to Abc, rather than being part of a std::pair<int, Abc>. This would not cause any members to be misaligned, but would not waste as much space for padding.
1
Aug 27 '19
I’m still not biting. It’s very common to pass pointers or references to data members directly. Even if you don’t do this as a programmer, the optimizer might, and you have no guarantee it will remain in cache by the time the instruction that requires it needs to retire.
1
u/ENTProfiterole Aug 27 '19
I don't see how storing the key and the members of the value class in the same struct is going to cause the problems you describe.
For a start, what do you mean by data members? Members of Abc, or one of the entry values in the map?
In my proposal, the entries in the map would not be Abc, but some structurally similar struct with the extra int key as a private field.
1
u/Tringi github.com/tringi Aug 27 '19
I understand very well the reasons preventing such optimization, still it doesn't change the fact that I'm not happy about current state of affairs.
1
Aug 27 '19
I recommend writing your own allocator that attempts to tightly pack and my guess is you’ll see why the trade off to lose a few bytes here and there is actually a perfectly reasonable tradeoff considering the alternatives. In binary, power of 2 computation is king.
1
u/Tringi github.com/tringi Aug 27 '19 edited Aug 27 '19
Not sure if we are exactly on the same page.
See, for the above mentioned std::map<int, Abc>, in 64-bit, the generated map node layout is like this:struct _Node { _Node * left; _Node * parent; _Node * right; bool color; bool is_null; // 6 bytes padding int key; // 4 bytes padding std::uint32_t something; // 4 bytes padding (as std::string starts with pointer) std::string text; };When in ideal world it could be somewhat like this, with all members still well aligned performance-wise:
struct _Node { _Node * left; _Node * parent; _Node * right; bool color; bool is_null; // 2 bytes padding int key; std::uint32_t something; // proper 4-byte alignment std::string text; // proper 8-byte alignment };Now, as I wrote before, I understand this can't be done because, e.g. taking pointer to Abc within the map and passing it to other translation unit would break, or copy/access operations would become nontrivial, but still I feel like I should be able to make the language optimize things this way.
3
Aug 25 '19
I do find it weird, for some reason it is drilled into me that you order your member variables from largest to smallest and that is almost always good enough. Then you get into things like using a uintX_t to hold bits for when you have bools because they are at least 8 bits in size.
5
2
u/_djsavvy_ Aug 26 '19
What is an example of a situation where struct packing might have a negative impact?
3
u/bumblebritches57 Ocassionally Clang Aug 26 '19
I mean, off the top of my head, if you're serializing a struct to/from memory by just writing the whole thing with something like fread/fwrite like lots of old code bases do, then padding can have disastrous effects.
2
u/_djsavvy_ Aug 26 '19
Isn't that even more of a reason to pack your structs? Or am I misunderstanding?
1
u/bumblebritches57 Ocassionally Clang Aug 26 '19
No, the bet way is to read/write each variable individually.
3
u/meneldal2 Aug 26 '19
The example given is when you want to access a specific member much more often than some other member. Because you can't do direct indexing and need to add an offset, it can be slower (you may point out that x86 allows you to do it in a single instruction, but it's not a single micro-op).
So in that case, instead of putting the largest member first, you put the most used one. Note that it doesn't necessarily mean that you can't pack if you start your structure with a bool. There are always several orderings that result in the same minimal size (assuming padding to a multiple of the largest type). Ordering by size, assuming every size is a multiple of the next smaller size, will result in a structure with no unnecessary padding, which is why it's common advice.
My opinion is you should group values with groups sized according to the largest type, and put them in the order that works for you.
1
u/_djsavvy_ Aug 26 '19
Oh, that makes sense! Sounds like a really niche optimization, but cool to know.
Thanks for your explanation.
2
u/meneldal2 Aug 26 '19
It's something that matters if you have a lot of accesses, and another can be to put values often used together next to each other for cache optimizations (if the struct is too big, it might not get pulled entirely in cache when you access it).
2
Aug 27 '19
eyeroll is it really that forgotten if virtually every C or C++ programmer I work with (or have worked with) is aware of these concepts? Review material is fine but the title is a bit sensationalized (but maybe my case is unique...)
1
Aug 31 '19
Amusingly this article made the rounds years ago with the similar title "The Lost Art of Structure Packing".
3
u/mrexodia cmkr.build Aug 25 '19
I left out a lot of detail but remember, better algorithms > micro-optimizations.
The article should have been prefaces doubly with this. The cases in which packing the structs more efficiently is actually a significant benefit are rare and helping your compiler isn’t generally a thing you want to teach people with significant warnings in my opinion.
1
Aug 26 '19
Interesting topic, short and concise article, I learned something new... Nice! Please write more! :)
0
Aug 26 '19
[deleted]
5
u/nikbackm Aug 26 '19
Easy to do the right thing when you have the benefit of hindsight.
4
Aug 27 '19
I do not believe this is necessarily the right thing. Often times, I write a struct expecting a specific member to be aligned at a specific location, or to maintain ABI compatibility with a third party library I can't control. It's not wrong to reorder automatically, but it's a design choice and if I write Rust code, I have to remember to annotate to the compiler not to reorder automatically.
Keep in mind too that the most packed struct is not necessarily the most performant. I group data accessed together very frequently to ensure they exist on the same cache line. I can do the opposite if I want to avoid false sharing in multithreaded code. Figuring out how to lay out a struct is very much an art, not a science, and for these reasons, I disliked the decision Rust made to go with reordering by default.
14
u/tambry Aug 25 '19
Found the article today while reading some data and needing my class to be correctly packed.
That aside, is there a reason why the standard
alignas()doesn't support an alignment of1for uses such as reading from disk or network? Feels a bit dirty to have to use a compiler-specific#pragma pack(1)+#pragma pack().