{"id":110069,"date":"2024-07-31T07:00:00","date_gmt":"2024-07-31T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=110069"},"modified":"2024-07-31T10:03:45","modified_gmt":"2024-07-31T17:03:45","slug":"20240731-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20240731-00\/?p=110069","title":{"rendered":"How to compress out interior padding in a std::pair<\/CODE> and why you don’t want to"},"content":{"rendered":"

My survey of many popular STL types began with std::pair<\/code><\/a>, and in the comments, Jan Ringo\u0161 noted that the layout of a std::pair<\/code> could result in padding between the two elements that could be recovered from padding within one of the elements.<\/p>\n

struct bulky\r\n{\r\n    uint16_t a;\r\n    void* b;\r\n};\r\n<\/pre>\n
If you assume 64-bit pointers and natural alignment, then the bulky<\/code> structure contains 2 bytes for a<\/code>, then 6 bytes of padding to reach the next aligned pointer boundary, and then 8 bytes for b<\/code>.<\/p>\n\n\n\n\n
00<\/tt><\/td>\n01<\/tt><\/td>\n02<\/tt><\/td>\n03<\/tt><\/td>\n04<\/tt><\/td>\n05<\/tt><\/td>\n06<\/tt><\/td>\n07<\/tt><\/td>\n08<\/tt><\/td>\n09<\/tt><\/td>\n0A<\/tt><\/td>\n0B<\/tt><\/td>\n0C<\/tt><\/td>\n0D<\/tt><\/td>\n0E<\/tt><\/td>\n0F<\/tt><\/td>\n<\/tr>\n
a<\/tt><\/td>\n\u00a0<\/td>\nb<\/tt><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
This padding is unavoidable for bulky<\/code> on its own, since you need to get b<\/code> aligned on a pointer boundary, and the entire structure needs to be 8-byte aligned so that you can have an array of bulky<\/code> objects.<\/p>\n
But what if we put it inside a std::pair<lithe, bulky><\/code>, where lithe<\/code> is something like this:<\/p>\n
struct lithe\r\n{\r\n    uint16_t v;\r\n};\r\n\r\nstd::pair<lithe, bulky> p;\r\n<\/pre>\n
This produces the following std::pair<\/code>:<\/p>\n\n\n\n\n\n\n\n
00<\/tt><\/td>\n01<\/tt><\/td>\n02<\/tt><\/td>\n03<\/tt><\/td>\n04<\/tt><\/td>\n05<\/tt><\/td>\n06<\/tt><\/td>\n07<\/tt><\/td>\n08<\/tt><\/td>\n09<\/tt><\/td>\n0A<\/tt><\/td>\n0B<\/tt><\/td>\n0C<\/tt><\/td>\n0D<\/tt><\/td>\n0E<\/tt><\/td>\n0F<\/tt><\/td>\n10<\/tt><\/td>\n11<\/tt><\/td>\n12<\/tt><\/td>\n13<\/tt><\/td>\n14<\/tt><\/td>\n15<\/tt><\/td>\n16<\/tt><\/td>\n17<\/tt><\/td>\n<\/tr>\n
v<\/tt><\/td>\n\u00a0<\/td>\na<\/tt><\/td>\n\u00a0<\/td>\nb<\/tt><\/td>\n<\/tr>\n
\u00a0<\/td>\n<\/tr>\n
\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n<\/tr>\n
first<\/tt><\/td>\n\u00a0<\/td>\nsecond<\/tt><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
In order to ensure that the bulky<\/code> starts on a pointer-aligned boundary, there are 6 bytes of padding after the first<\/code>‘s uint16_t<\/code>, bringing the total size of the pair to 24 bytes. On the other hand, if we represented the same data in a single structure:<\/p>\n
struct pair_lithe_with_bulky\r\n{\r\n    uint16_t v;\r\n    uint16_t a;\r\n    void* b;\r\n};\r\n<\/pre>\n
then the result would be much smaller since we could coalesce the padding.<\/p>\n\n\n\n\n\n\n\n
00<\/tt><\/td>\n01<\/tt><\/td>\n02<\/tt><\/td>\n03<\/tt><\/td>\n04<\/tt><\/td>\n05<\/tt><\/td>\n06<\/tt><\/td>\n07<\/tt><\/td>\n08<\/tt><\/td>\n09<\/tt><\/td>\n0A<\/tt><\/td>\n0B<\/tt><\/td>\n0C<\/tt><\/td>\n0D<\/tt><\/td>\n0E<\/tt><\/td>\n0F<\/tt><\/td>\n<\/tr>\n
v<\/tt><\/td>\na<\/tt><\/td>\n\u00a0<\/td>\nb<\/tt><\/td>\n<\/tr>\n
\u00a0<\/td>\n<\/tr>\n
\u00a0<\/td>\n\u00a0<\/td>\n<\/tr>\n
first<\/tt><\/td>\nquasi-second<\/tt><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Could there be a way to tell C++, “Hey, I know you need to put padding in this bulky<\/code> structure, but if this structure is a subobject of another structure, just lay out the members as if they were all part of one big structure”?<\/p>\n
I mean, you could propose anything.<\/p>\n
The problem with this idea is that if you try to access p.second<\/code>, you don’t get a normal bulky<\/code>, but rather a wacked-out version of bulky<\/code> that has a misaligned<\/i> pointer, and whose size is not a multiple of its alignment.<\/p>\n\n\n\n\n\n\n\n
00<\/tt><\/td>\n01<\/tt><\/td>\n02<\/tt><\/td>\n03<\/tt><\/td>\n04<\/tt><\/td>\n05<\/tt><\/td>\n06<\/tt><\/td>\n07<\/tt><\/td>\n08<\/tt><\/td>\n09<\/tt><\/td>\n0A<\/tt><\/td>\n0B<\/tt><\/td>\n0C<\/tt><\/td>\n0D<\/tt><\/td>\n<\/tr>\n
a<\/tt><\/td>\n\u00a0<\/td>\nb<\/tt><\/td>\n<\/tr>\n
\u00a0<\/td>\n<\/tr>\n
\u00a0<\/td>\n<\/tr>\n
quasi-second<\/tt><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
This bizarro-world version of bulky<\/code> cannot be put in an array since it would misalign the subsequent element. And since its layout and size aren’t the same as that of a normal bulky<\/code>, its type wouldn’t be the same as that of a normal bulky<\/code>. It would have to be a “misaligned by 2 bulky<\/code>” (which would need to have a name like [[header_offset(2)]] bulky<\/code>). Now you have to decide what std::pair<lithe, bulky>::second_type<\/code> is. Is it bulky<\/code>? Or is it [[header_offset(2)]] bulky<\/code>? Either choice you make is going to create confusion, because they will cause one or the other of the following to be false:<\/p>\n
\/\/ given p of type std::pair<T, U>\r\nstd::is_same_v<U, std::pair<T, U>::second_type>>\r\nstd::is_same_v<U, decltype(p.second)>\r\n<\/pre>\n
But wait, there’s still more to fret over.<\/p>\n
Consider this slightly fatter version of lithe<\/code>:<\/p>\n
struct medium\r\n{\r\n    uint32_t v;\r\n    uint16_t w;\r\n};\r\n<\/pre>\n
The normal layout of the std::pair<\/code> would be this:<\/p>\n\n\n\n\n\n\n\n
00<\/tt><\/td>\n01<\/tt><\/td>\n02<\/tt><\/td>\n03<\/tt><\/td>\n04<\/tt><\/td>\n05<\/tt><\/td>\n06<\/tt><\/td>\n07<\/tt><\/td>\n08<\/tt><\/td>\n09<\/tt><\/td>\n0A<\/tt><\/td>\n0B<\/tt><\/td>\n0C<\/tt><\/td>\n0D<\/tt><\/td>\n0E<\/tt><\/td>\n0F<\/tt><\/td>\n10<\/tt><\/td>\n11<\/tt><\/td>\n12<\/tt><\/td>\n13<\/tt><\/td>\n14<\/tt><\/td>\n15<\/tt><\/td>\n16<\/tt><\/td>\n17<\/tt><\/td>\n<\/tr>\n
v<\/tt><\/td>\nw<\/tt><\/td>\n\u00a0<\/td>\na<\/tt><\/td>\n\u00a0<\/td>\nb<\/tt><\/td>\n<\/tr>\n
\u00a0<\/td>\n<\/tr>\n
\u00a0<\/td>\n\u00a0<\/td>\n<\/tr>\n
first<\/tt><\/td>\nsecond<\/tt><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
If you try to squeeze out the padding, you end up with this quite compact structure:<\/p>\n\n\n\n\n\n\n\n
00<\/tt><\/td>\n01<\/tt><\/td>\n02<\/tt><\/td>\n03<\/tt><\/td>\n04<\/tt><\/td>\n05<\/tt><\/td>\n06<\/tt><\/td>\n07<\/tt><\/td>\n08<\/tt><\/td>\n09<\/tt><\/td>\n0A<\/tt><\/td>\n0B<\/tt><\/td>\n0C<\/tt><\/td>\n0D<\/tt><\/td>\n0E<\/tt><\/td>\n0F<\/tt><\/td>\n<\/tr>\n
v<\/tt><\/td>\nw<\/tt><\/td>\na<\/tt><\/td>\nb<\/tt><\/td>\n<\/tr>\n
\u00a0<\/td>\n<\/tr>\n
\u00a0<\/td>\n\u00a0<\/td>\n<\/tr>\n
first<\/tt><\/td>\nsecond<\/tt><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
This is even more confusing because the embedded medium<\/code> structure is also not a normal medium<\/code> structure: It lacks the trail padding and has a size that is not a multiple of its alignment. The compiler cannot optimize<\/p>\n
extern medium special;\r\np.first = special; \/\/ make the first part special\r\n<\/pre>\n
to a memcpy(&p.first, &special, sizeof(medium))<\/code> because that would accidentally overwrite the a<\/code> hiding inside the trail padding. It would have to be memcpy(&p.first, &special, sizeof(medium) - trail_padding_size)<\/code> to avoid overwriting data hiding in the trail padding.<\/p>\n
You might think to solve the need for a header_offset<\/code> attribute for alternate layouts by putting the lithe<\/code> inside<\/i> the padding of the bulky<\/code>, assuming it fits.<\/p>\n\n\n\n\n\n\n\n\n
\u00a0<\/td>\nfirst<\/tt><\/td>\n\u00a0<\/td>\n<\/tr>\n
00<\/tt><\/td>\n01<\/tt><\/td>\n02<\/tt><\/td>\n03<\/tt><\/td>\n04<\/tt><\/td>\n05<\/tt><\/td>\n06<\/tt><\/td>\n07<\/tt><\/td>\n08<\/tt><\/td>\n09<\/tt><\/td>\n0A<\/tt><\/td>\n0B<\/tt><\/td>\n0C<\/tt><\/td>\n0D<\/tt><\/td>\n0E<\/tt><\/td>\n0F<\/tt><\/td>\n<\/tr>\n
a<\/tt><\/td>\nv<\/tt><\/td>\n\u00a0<\/td>\nb<\/tt><\/td>\n<\/tr>\n
\u00a0<\/td>\n<\/tr>\n
\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n<\/tr>\n
sec<\/tt>\u2026<\/td>\n\u00a0<\/td>\n\u2026ond<\/tt><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Great! Now, all the structures are normal-sized and normally-aligned.<\/p>\n
Now you have a problem with this:<\/p>\n
p.second = bulky{}; \/\/ clear out the second part\r\n<\/pre>\n
In order for this to work, the compiler cannot optimize the assignment to a memcpy<\/code> because that would accidentally overwrite the first<\/code> embedded in the internal padding.<\/p>\n
If you are really keen on squeezing out the padding, you can do it by setting custom packing for the bulky<\/code> structure.<\/p>\n
#include <pshpack4.h>\r\nstruct bulky\r\n{\r\n    uint16_t a;\r\n    void* b;\r\n};\r\n#include <poppack.h>\r\n<\/pre>\n
Overriding normal packing to 4-byte alignment means that you get this layout for bulky, which matches the “quasi-second<\/code>” we discovered earlier.<\/p>\n\n\n\n\n
00<\/tt><\/td>\n01<\/tt><\/td>\n02<\/tt><\/td>\n03<\/tt><\/td>\n04<\/tt><\/td>\n05<\/tt><\/td>\n06<\/tt><\/td>\n07<\/tt><\/td>\n08<\/tt><\/td>\n09<\/tt><\/td>\n0A<\/tt><\/td>\n0B<\/tt><\/td>\n<\/tr>\n
a<\/tt><\/td>\n\u00a0<\/td>\nb<\/tt><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Hooray! This  pairs nicely<\/a> with lithe<\/code>:<\/p>\n\n\n\n\n\n\n\n
00<\/tt><\/td>\n01<\/tt><\/td>\n02<\/tt><\/td>\n03<\/tt><\/td>\n04<\/tt><\/td>\n05<\/tt><\/td>\n06<\/tt><\/td>\n07<\/tt><\/td>\n08<\/tt><\/td>\n09<\/tt><\/td>\n0A<\/tt><\/td>\n0B<\/tt><\/td>\n0C<\/tt><\/td>\n0D<\/tt><\/td>\n0E<\/tt><\/td>\n0F<\/tt><\/td>\n<\/tr>\n
v<\/tt><\/td>\n\u00a0<\/td>\na<\/tt><\/td>\n\u00a0<\/td>\nb<\/tt><\/td>\n<\/tr>\n
\u00a0<\/td>\n<\/tr>\n
\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n<\/tr>\n
first<\/tt><\/td>\n\u00a0<\/td>\nquasi-second<\/tt><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
The downside of this is that systems that are alignment sensitive will have to load the b<\/code> as an unaligned value, which  tends to be rather expensive<\/a>. It’s not quite as bad as byte alignment, since we can often load it in just two steps instead of eight, but it’s still worse than a straight load.<\/p>\n
In general, this sort of tight memory optimization does save you memory, but it costs you in code flexibility (a vector of bulky<\/code> objects is not going to be fun), and it can cost you in runtime costs (on alignment-sensitive platforms).<\/p>\n
Bonus chatter<\/b>: The introduction of [[no_unique_address]]<\/code> in C++20 makes things more complicated. Base classes and members with the [[no_unique_address]]<\/code> attribute are permitted to overlap. A common use for this is to extend the so-called empty base optimization to empty members, thereby avoiding the need for the complex dance employed by  compressed pairs<\/a>.<\/p>\n
But another use for [[no_unique_address]]<\/code> is to allow overlap between non-empty objects, specifically, to allow one type to hide inside the padding of another. In practice, compilers that take advantage of it\u00b2 limit themselves to reusing tail padding, so that they can still use memcpy<\/code> to assign two objects (just with a smaller object size).<\/p>\n
In other words, it is legal for a compiler to do this:<\/p>\n
struct part1\r\n{\r\n    void* ptr;\r\n    int16_t a;\r\n};\r\n\r\nstruct part2\r\n{\r\n    int32_t b;\r\n};\r\n\r\nstruct combined\r\n{\r\n    [[no_unique_address]] part1 p1;\r\n    [[no_unique_address]] part2 p2;\r\n};\r\n<\/pre>\n\n\n\n\n\n\n\n\n\n
00<\/tt><\/td>\n01<\/tt><\/td>\n02<\/tt><\/td>\n03<\/tt><\/td>\n04<\/tt><\/td>\n05<\/tt><\/td>\n06<\/tt><\/td>\n07<\/tt><\/td>\n08<\/tt><\/td>\n09<\/tt><\/td>\n0A<\/tt><\/td>\n0B<\/tt><\/td>\n0C<\/tt><\/td>\n0D<\/tt><\/td>\n0E<\/tt><\/td>\n0F<\/tt><\/td>\n<\/tr>\n
ptr<\/tt><\/td>\na<\/tt><\/td>\n\u00a0<\/td>\nb<\/tt><\/td>\n<\/tr>\n
\u00a0<\/td>\n<\/tr>\n
\u00a0<\/td>\n\u00a0<\/td>\n<\/tr>\n
\u00a0<\/td>\np2<\/tt><\/td>\n<\/tr>\n
\u00a0<\/td>\n<\/tr>\n
p1<\/tt><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
To avoid damaging any data hiding in the tail padding, copying a part1<\/code> copies only 10 bytes instead of 16. This is not too heavy a burden on the compiler, since avoiding tail padding is easier than avoiding internal padding.<\/p>\n
\u00b2 The Microsoft Visual C++ compiler  does not take advantage of [[no_unique_address]]<\/code> for ABI compatibility reasons<\/a>. You have to say [[msvc::no_unique_address]]<\/code> with the understanding that you are accepting the ABI break and promise not to mix code compiled in C++17 mode with code compiled in C++20 mode.<\/p>\n","protected":false},"excerpt":{"rendered":"
Context-sensitive layout means you get a different structure each time you use it.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-110069","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Context-sensitive layout means you get a different structure each time you use it.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/110069","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=110069"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/110069\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=110069"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=110069"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=110069"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}