Variadic Struct is Bloated, Extra Padding Being Added At The End of the Struct-CodePudding

I have been following this tutorial for creating a variadic structure, which is nearly identical to another tutorial on creating a rudimentary tuple from scratch. Unfortunately when I analyze the variadic structure it seems very inefficient. The size of the structure seems bloated as in the struct's size does not seem to match its variable layout. It doesn't seem like byte alignment is the issue since actual tuples do not seem to suffer from this effect so I was wondering how they get around it, or what I am doing wrong in my struct.

Below is the code I have been using to test the variadic struct:

#include <iostream>
#include <tuple>
#include <array>

template<typename ... T>
struct DataStructure
{
};

template<typename T>
struct DataStructure<T> {
    DataStructure(const T& first) : first(first)
    {}

    DataStructure() {}

    T first;
};

template<typename T, typename ... Rest>
struct DataStructure<T, Rest ...>
{
    DataStructure(const T& first, const Rest& ... rest)
        : first(first)
        , rest(rest...)
    {}

    DataStructure() {}
    
    T first;
    [[no_unique_address]] DataStructure<Rest ... > rest;
};

struct test1 {
    int one;
    float two;
};

struct test2 {
    double three;
    float two;
    int one;
};

int main()
{
    std::cout << "Size of test1 with double: " << sizeof(test1) << std::endl;
    std::cout << "Offset of test1 with double: " << offsetof(test1, one) << " | " << offsetof(test1, two) << std::endl;
    std::cout << std::endl;

    typedef DataStructure<int32_t, float> def;
    std::cout << "Size of DataStructure<int32_t, float> w/o Double: " << sizeof(def) << std::endl;
    std::cout << "Offset of DataStructure<int32_t, float> w/o Double: " << offsetof(def, first) << " | " << offsetof(def, rest.first) << std::endl;
    std::cout << std::endl;

    std::cout << "Size of test2 with double: " << sizeof(test2) << std::endl;
    std::cout << "Offset of test2 with double: " << offsetof(test2, one) << "(int32) | " << offsetof(test2, two) << "(float) | " << offsetof(test2, three) << "(double)" << std::endl;
    std::cout << std::endl;

    typedef DataStructure<double, float, int32_t> defDouble;
    std::cout << "Size of DataStructure<double, float, int32_t>: " << sizeof(defDouble) << std::endl;
    std::cout << "Offset of DataStructure<double, float, int32_t>: " << offsetof(defDouble, rest.rest.first) << "(int32) | " << offsetof(defDouble, rest.first) << "(float) | " << offsetof(defDouble, first) << "(double)" << std::endl;
    std::cout << std::endl;

    std::tuple<int32_t, float, double> tp;
    std::cout << "Size of tuple with double (gcc compiled tuple reverses parameter layout in memory): " << sizeof(tp) << std::endl;
    std::cout << "Offset of tuple with double: " << (long)&std::get<0>(tp) - (long)&tp << "(int32) | " << (long)&std::get<1>(tp) - (long)&tp << "(float) | " << (long)&std::get<2>(tp) - (long)&tp << "(double)" << std::endl;
    std::cout << std::endl;

    std::cout << "Size of no parameter DataStructure<>: " << sizeof(DataStructure<>) << std::endl;

    typedef DataStructure<int32_t, float, double> defDoubleNormal;
    std::cout << "Size of DataStructure<int32_t, float, double>: " << sizeof(defDoubleNormal) << std::endl;
    std::cout << "Offset of DataStructure<int32_t, float, double>: " << offsetof(defDoubleNormal, first) << "(int32) | " << offsetof(defDoubleNormal, rest.first) << "(float) | " << offsetof(defDoubleNormal, rest.rest.first) << "(double)" << std::endl;
    std::cout << std::endl;

    std::tuple<double, float, int32_t> tp2;
    std::cout << "Size of tuple with double (gcc compiled tuple reverses parameter layout in memory): " << sizeof(tp) << std::endl;
    std::cout << "Offset of tuple with double: " << (long)&std::get<0>(tp2) - (long)&tp2 << "(double) | " << (long)&std::get<1>(tp2) - (long)&tp2 << "(float) | " << (long)&std::get<2>(tp2) - (long)&tp2 << "(int32)" << std::endl;
    std::cout << std::endl;

    std::array<defDouble, 2> arr;
    std::cout << "Array DataStructure<double, float, int32_t> Offsets: [0] - " << (long)&arr[0] - (long)&arr << ", [1] - " << (long)&arr[1] - (long)&arr;
}

The code above prints:

Size of test1 with double: 8
Offset of test1 with double: 0 | 4

Size of DataStructure<int32_t, float> w/o Double: 8
Offset of DataStructure<int32_t, float> w/o Double: 0 | 4

Size of test2 with double: 16
Offset of test2 with double: 12(int32) | 8(float) | 0(double)

Size of DataStructure<double, float, int32_t>: 16
Offset of DataStructure<double, float, int32_t>: 12(int32) | 8(float) | 0(double)

Size of tuple with double (gcc compiled tuple reverses parameter layout in memory): 16
Offset of tuple with double: 12(int32) | 8(float) | 0(double)

Size of no parameter DataStructure<>: 1
Size of DataStructure<int32_t, float, double>: 24
Offset of DataStructure<int32_t, float, double>: 0(int32) | 8(float) | 16(double)

Size of tuple with double (gcc compiled tuple reverses parameter layout in memory): 16
Offset of tuple with double: 8(double) | 4(float) | 0(int32)

Array DataStructure<double, float, int32_t> Offsets: [0] - 0, [1] - 16

I reversed the order of the template arguments between the DataStructure with double and the tuple because the tuple I was using internally reverses the order of the members (this is an unspecified implementation detail of tuple and is how gcc was implementing it); this way both member layouts are in the same order with the double starting at offset 0 followed by their float and finally their int32. That layout can be seen visually in the test2 struct What we can see is that the appropriate size of the structure as shown with "test2" is 16 and that the offsets of the members is 0 for the double, 8 for the float, and 12 for the int32. The tuple shows the same thing albeit with the member order reversed having the double at 0 the float at 8, the int32 at 12 and an overall size of 16 bytes. These same offsets are found in the DataStructure with double; the double is at offset 0 the float is at 8 and the int32 at 12 but this time the overall size is 24 bytes and I cannot understand what is being padded at the end of the structure or why. I know that doubles need to be 8 byte aligned but that shouldn't be a problem here and clearly isn't as shown in the case of the tuple and test2.

CodePudding user response：

Even an empty class needs space to store itself, the minimum size of a class is therefore 1. As your no argument DataStructure class is empty and a member it takes up space and causes the rest of the members to take more space to allow for alignment. Making the base non-empty fixes the issue:

template<typename ... T>
struct DataStructure;

template<typename T>
struct DataStructure<T>
{
    DataStructure(const T& first)
        : first(first)
    {}

    T first;
};

template<typename T, typename ... Rest>
struct DataStructure<T, Rest ...>
{
    DataStructure(const T& first, const Rest& ... rest)
        : first(first)
        , rest(rest...)
    {}
    
    T first;
    DataStructure<Rest ... > rest;
};

This still introduces extra padding in the case of DataStructure<int32_t, float, double>. This is because your code essentially produces:

struct A
{
    double a;
};

struct B
{
    A a;
    float b;
};

struct C
{
    B b;
    int32_t c;
};

The compiler will try to always put the double on a multiple of 8 bytes, as B needs 12 bytes the compiler pads this to 16 bytes to that in an array of B, a is always aligned to 8 bytes. sizeof(B) will therefore be 16 leading to sizeof(C) being 24.

I think std::tuple is generally implemented using base classes rather than members. Changing your implementation to do this too fixes this padding issue:

template<typename ... T>
struct DataStructure;

template<typename T>
struct DataStructure<T>
{
    DataStructure(const T& first)
        : first(first)
    {}

    T first;
};

template<typename T, typename ... Rest>
struct DataStructure<T, Rest ...>: DataStructure<Rest ... >
{
    DataStructure(const T& first, const Rest& ... rest)
        : first(first), DataStructure<Rest ... >(rest...)
    {}
    
    T first;
};