Optimally packing a recursively templated struct without loss of alignment

Question

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:

• reordering of fields t1, t2, t3, t4
• addition of filler fields
• gcc attribute packed on payload
• maybe others?

I 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.

Pinnatifid

I'm not seeing it. If you reorder the way you described, but don't add packed, what's the problem? Using it in another type would not give any misaligned fields, since the compiler would fix that with padding already. – Gurley

BTW, why do you force alignment on your struct? If your types are four chars, you want a size of 4, don't you? That can't require an alignment of 8. – Gurley

@hvd four_tuple<Foo::payload,int,int,int> can achieve a size of 32 with no misalignment if properly packed. If you don't add packed, it will have a size of 40. – Pinnatifid

@hvd Solving my problem guarantees only that the leaves will be aligned relative to the four_tuple. If a particular instance of the four_tuple is misaligned, all bets are off. That's why I align 8. – Pinnatifid

#18975630 has a detailed discussion of compile-time re-ordering to optimize packing. The answer also refers to rmf.io/cxx11/optimal-tuple-i which discusses tuple data layout. – Reprovable

@Pinnatifid No, four_tuple<Foo::payload,int,int,int> can't achieve a size of 32. Foo::payload can't have a size smaller than 24 (using your platform's sizes) if you want to guarantee alignment, and you need three more ints. There's no way to re-use the padding in a member. – Gurley

@Pinnatifid Consider by the way that if you make Foo packed, then an array Foo[2] will have at least one misaligned element, and you say you want to avoid misaligned elements, right? – Gurley

@hvd I'm referring to the reordered Foo (double, double, char, char). Its (packed) payload can fit in 18 without misalignment. I say "without misalignment" assuming it is used only within the context of a template parameter of four_tuple - the payload struct is not meant to be publicly visible (I should make this clearer in my post). Also, Foo is not declared packed precisely so things like Foo[2] will work. – Pinnatifid

@Reprovable Thanks for the links. I will take a look. I think the fact that my payload inner class is not well-aligned "publicly" will make it so I can't use the link's solution out-of-the-box, but hopefully it will not take great effort to adapt it. – Pinnatifid

Answer 1

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.

Gurley

Thanks for the work. This doesn't compile for me but I think I get the idea. If I understand it correctly, it still won't be optimal in the sense that tuple4<tuple4<8,4,4,2>, tuple4<2,4,8,8>, 8, 8> will use filler space, while a naive packed implementation without reordering will not use filler and satisfy the requirement of no misalignment on the primitive types. (Here, 2=int16_t, 4=int32_t, 8=int64_t). But it should work better than anything else I have. – Pinnatifid

@Pinnatifid It compiles with GCC 4.9 and higher, 4.8 if you change conditional_t<...> to conditional<...>::type. Yes, you're right, it won't be optimal in your example. Since packed can only drop trailing padding if you want to maintain alignment to the start of the object, tuple4<2,4,8,8> gets re-ordered to tuple4<8,8,4,2>, at which point your preferred layout stops being possible. I don't see a way around that, sorry. – Gurley

I can imagine in theory if the tuple4::payload type has 8 static bools corresponding to whether it can be offset by {0, 1, 2, 3, 4, 5, 6, 7} bytes, then a meta-algorithm can incorporate that in an exhaustive search. But some cleverness would be needed to trim the search space. – Pinnatifid

@Pinnatifid Basically, you'd end up with an alignment requirement of 8*N+2, which is tricky and won't play well with any compiler built-in alignment functionality. But what else may be problematic is that the ideal layout of a tuple can't be determined without considering its containing tuple (if any): given tuple4<tuple4<2,8,8,8>,tuple4<2,8,8,8>,8,8>: you'd ideally want that to be ordered as 8,8,8,2,2,8,8,8,8,8, but that means the first tuple4<2,8,8,8> and the second tuple4<2,8,8,8> would not have the same layout. – Gurley

You're right, payload layout must be fixed regardless of context. So this seems like the best solution. – Pinnatifid