I have a struct of 4 fields of types that come from template parameters:
template <typename T1, typename T2, typename T3, typename T4>
struct __attribute__((aligned(8))) four_tuple {
typedef struct {
T1 t1;
T2 t2;
T3 t3;
T4 t4;
} payload;
payload p;
};
Each type T1, T2, T3, and T4, is guaranteed to be a primitive type or a four_tuple<...>::payload type. The guarantees are recursive - you can think of the struct as encoding a quadtree whose leaf nodes are primitive types.
My goal is for the struct to have minimum possible sizeof, subject to the condition that all of the leaf nodes are properly aligned. The tools allowed for the optimization are class template specializations using:
t1, t2, t3, t4packed on payloadI feel like there is a clever solution to this problem using enable_if and SFINAE. Can anyone find it?
To illustrate the problem, if we use the above implementation as-is using Foo = four_tuple<char,double,char,double>, we'll have a size of 32 for the payload and overall. If we simply declare the payload packed, the double's will not be well-aligned. A template specialization that reorders the fields in decreasing order (here, double, double, char, char) will give a payload and overall size of 24. But the extra 6 bytes it uses are wasteful, as can be seen by considering using Bar = four_tuple<Foo::payload,int,int,int>. With optimal packing Bar could fit in 32 bytes, but with this scheme it would require 40. Bluntly applying field-reordering with packed will result in misaligned int's in Bar - some filler is needed.
I know that in general restructuring the memory layout of a struct's fields can have performance implications due to cache considerations, and that in general those implications will be at least as significant as any potential gains from better packing. I'd like to explore the tradeoffs, though, and I can't really do that properly in my context without solving this problem.
The big problem in your nested tuple case is that you want to have a field of type four_tuple<char,double,char,double>::payload, aligned as if it is a four_tuple<char,double,char,double>, but without requiring the container type to inherit its alignment. This is complicated. Doing this is possible, but it makes your code highly unportable to anything other than GCC. I guess that's okay since you suggest a GCC extension in your question already. The basic idea is that bit-fields can be used to insert padding to ensure an alignment:
struct __attribute__((packed)) S {
char c; // at offset 0
int i; // at offset 1, not aligned
int : 0;
int j; // at offset 8, aligned
int : 0;
int k; // at offset 12, no extra padding between j and k
};
int is of course a very specific type with a very specific alignment, and you need a dynamically determined alignment. Luckily, GCC allows bit-fields of type char, which generally only enforce byte alignment, to be combined with alignas, ensuring arbitrary alignment.
With that done, you can check all 24 possible field orderings and select the payload that gives the lowest total size. I made the payload a global type and gave it an additional template parameter to indicate the field order. This allows tuple4<T1, T2, T3, T4> to check tuple4_payload<T1, T2, T3, T4, 1234>, tuple4_payload<T1, T2, T3, T4, 1243>, etc. in order and pick whichever is best.
template <typename...> struct smallest;
template <typename...T> using smallest_t = typename smallest<T...>::type;
template <typename T> struct smallest<T> { using type = T; };
template <typename T, typename...Ts> struct smallest<T, Ts...> { using type = std::conditional_t<sizeof(T) <= sizeof(smallest_t<Ts...>), T, smallest_t<Ts...>>; };
template <typename T1, typename T2, typename T3, typename T4> struct tuple4;
template <typename T1, typename T2, typename T3, typename T4, int fieldOrder> struct tuple4_payload;
template <typename T1, typename T2, typename T3, typename T4> struct tuple4_simple { T1 t1; T2 t2; T3 t3; T4 t4; };
template <typename T> struct extract_payload { using type = T; };
template <typename...T> struct extract_payload<tuple4<T...>> { using type = typename tuple4<T...>::payload; };
template <typename T> using extract_payload_t = typename extract_payload<T>::type;
#define PERMS \
PERM(1,2,3,4) PERM(1,2,4,3) PERM(1,3,2,4) PERM(1,3,4,2) PERM(1,4,2,3) PERM(1,4,3,2) \
PERM(2,1,3,4) PERM(2,1,4,3) PERM(2,3,1,4) PERM(2,3,4,1) PERM(2,4,1,3) PERM(2,4,3,1) \
PERM(3,1,2,4) PERM(3,1,4,2) PERM(3,2,1,4) PERM(3,2,4,1) PERM(3,4,1,2) PERM(3,4,2,1) \
PERM(4,1,2,3) PERM(4,1,3,2) PERM(4,2,1,3) PERM(4,2,3,1) PERM(4,3,1,2) PERM(4,3,2,1)
#define PERM(a,b,c,d) \
template <typename T1, typename T2, typename T3, typename T4> \
struct __attribute__((packed)) tuple4_payload<T1, T2, T3, T4, a##b##c##d> { \
char : 0 alignas(T##a); extract_payload_t<T##a> t##a; \
char : 0 alignas(T##b); extract_payload_t<T##b> t##b; \
char : 0 alignas(T##c); extract_payload_t<T##c> t##c; \
char : 0 alignas(T##d); extract_payload_t<T##d> t##d; \
};
PERMS
#undef PERM
#define PERM(a,b,c,d) , tuple4_payload<T1, T2, T3, T4, a##b##c##d>
template <typename, typename...T> using tuple4_smallest_payload_t = smallest_t<T...>;
template <typename T1, typename T2, typename T3, typename T4>
struct alignas(tuple4_simple<T1, T2, T3, T4>) tuple4 : tuple4_smallest_payload_t<void PERMS> {
using payload = tuple4_smallest_payload_t<void PERMS>;
};
#undef PERM
In your case, you would use this as tuple4<int, tuple4<char, double, char, double>, int, int>. Note that even though the payload type is not mentioned explicitly here, it will still be used for the t2 member.