Do tuple implementations have an optimized layout?

Question

While reading this I was amazed on what a certain level of metaprogramming can do for your class layout. I must admit that I don't fully grasp what's the proposed optimal layout, if I had to state what I understood it would be this :

ordering class member by descending alignment i.e. the type with the greatest alignof result goes first etc

Feel free to correct me if I got this wrong (if you had a short explanation of why this happens it would be even better, I couldn't copy paste large chunks of the rationale in my question), but my question is on another topic :

Does any library implementation of std::tuple have such an optimization of layout?

If not, are there any standard algebraic data types that do so, is there another way to do this for my class apart from writing such a machinery ?

Pastille

Answer 1

No library implementation I'm aware of optimizes layout for alignment. You can use a program such as this to inspect a tuple layout:

#include <iostream>
#include <tuple>

struct empty {};

int
main()
{
    using T = std::tuple<double, int, empty, short, long>;
    T t{};
    std::cout << &t << '\n';
    std::cout << &std::get<0>(t) << '\n';
    std::cout << &std::get<1>(t) << '\n';
    std::cout << &std::get<2>(t) << '\n';
    std::cout << &std::get<3>(t) << '\n';
    std::cout << &std::get<4>(t) << '\n';
    std::cout << &t+1 << '\n';
    std::cout << sizeof(T) << '\n';
}

libc++ stores elements in order of declaration, and optimizes space away for empty members. Empty members are shunted towards the front. Sample output:

0x7fff5ccf39f8
0x7fff5ccf39f8
0x7fff5ccf3a00
0x7fff5ccf39f8
0x7fff5ccf3a04
0x7fff5ccf3a08
0x7fff5ccf3a10
24

libstdc++ stores elements in reverse order of declaration, and optimizes space away for empty members. Empty members are shunted towards the front. Sample output:

0x7ffe4fc5b2a0
0x7ffe4fc5b2b0
0x7ffe4fc5b2ac
0x7ffe4fc5b2a0
0x7ffe4fc5b2a8
0x7ffe4fc5b2a0
0x7ffe4fc5b2b8
24

VS-2015 stores elements in reverse order of declaration and does not optimize away the space for empty members. Sample output:

0306FEF4
0306FF04
0306FF00
0306FEFC
0306FEF8
0306FEF4
0306FF0C
24

In this example we see that optimizing the space away for the empty member didn't buy anything since it fits in an area of padding anyway.

There are no facilities which automate the task of reducing padding in the standard.

Doctrinal

Could you please elaborate on why ordering by descending alignment would be an optimal layout? – Pastille

@LorahAttkins: This is a heuristic that often works. It assumes that the class itself is usually maximally aligned, and so putting your maximally aligned members first guarantees no padding bytes between your maximally aligned members. Then move to your next biggest alignment members and the same logic will hold. When you run out of members, you will typically have some padding added afterwords to round up the sizeof(your_class) to a multiple of the class alignment. So sometimes the order-by-align trick will save you bytes, and sometimes it won't. It is a good tool to have in the toolbox. – Doctrinal

I should've added to my comment above: The sizeof every type is a multiple of the alignment for that type. For example there is no such thing as a type with 16 byte alignment and a sizeof 15 or 17. Its sizeof will be 16, or 32, or 48, etc. This implies that both &a and &a + 1 are pointers with alignment as least as big as alignof(a). – Doctrinal