Оптимальная упаковка рекурсивно-шаблонной структуры без потери выравнивания
У меня есть структура из 4 полей типов, которые приходят из параметров шаблона:
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;
};
Каждый тип T1, T2, T3, а также T4, гарантированно будет примитивным типом или four_tuple<...>::payload тип. Гарантии рекурсивны — вы можете думать о структуре как о кодирующей квадрантов чьи конечные узлы являются примитивными типами.
Моя цель — чтобы структура имела как можно меньше sizeof, при условии, что все конечные узлы правильно выровнены. Инструменты, разрешенные для оптимизации, являются специализациями шаблонов классов с использованием:
- переупорядочение полей
t1,t2,t3,t4 - добавление полей-заполнителей
- атрибут gcc
packedнаpayload - может другие?
Я чувствую, что есть разумное решение этой проблемы, используя enable_if и сфина. Кто-нибудь может найти это?
Чтобы проиллюстрировать проблему, если мы используем вышеуказанную реализацию как есть using Foo = four_tuple<char,double,char,double>у нас будет размер 32 для полезной нагрузки и в целом. Если мы просто объявим полезную нагрузку packed, doubleне будет хорошо выровнен. Специализация шаблона, которая переупорядочивает поля в порядке убывания (здесь double, double, char, char) даст полезную нагрузку и общий размер 24. Но дополнительные 6 байтов, которые он использует, расточительны, что можно увидеть, рассмотрев using Bar = four_tuple<Foo::payload,int,int,int>, С оптимальной упаковкой Bar может уместиться в 32 байта, но с этой схемой потребуется 40. Прямо применяя переупорядочение полей с packed приведет к смещению intв Bar — нужен какой-то наполнитель.
Я знаю, что в целом реструктуризация структуры памяти полей структуры может влиять на производительность из-за проблем с кэшем, и что в целом эти последствия будут как минимум такими же значительными, как и любые потенциальные выгоды от лучшей упаковки. Я хотел бы изучить компромиссы, и я не могу сделать это должным образом в моем контексте без решения этой проблемы.
Решение
Большая проблема в вашем случае вложенного кортежа состоит в том, что вы хотите иметь поле типа four_tuple<char,double,char,double>::payloadвыровнены, как будто это four_tuple<char,double,char,double>, но не требуя, чтобы тип контейнера наследовал его выравнивание. Это сложно. Это возможно, но это делает ваш код крайне непереносимым ни к чему, кроме GCC. Я думаю, это нормально, поскольку вы уже предлагаете расширение GCC в своем вопросе. Основная идея заключается в том, что битовые поля можно использовать для вставки отступов, чтобы обеспечить выравнивание:
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 Конечно, это очень специфический тип с очень специфическим выравниванием, и вам нужно динамически определенное выравнивание. К счастью, GCC допускает битовые поля типа char, которые обычно обеспечивают принудительное выравнивание байтов, для объединения с alignas, обеспечивая произвольное выравнивание.
Сделав это, вы можете проверить все 24 возможных порядка полей и выбрать полезную нагрузку, которая дает наименьший общий размер. Я сделал полезный груз глобальным типом и дал ему дополнительный параметр шаблона для указания порядка полей. Это позволяет tuple4<T1, T2, T3, T4> Проверять tuple4_payload<T1, T2, T3, T4, 1234>, tuple4_payload<T1, T2, T3, T4, 1243>и т. д. по порядку и выбирайте, что лучше.
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
В вашем случае вы бы использовали это как tuple4<int, tuple4<char, double, char, double>, int, int>, Обратите внимание, что, хотя тип полезной нагрузки здесь явно не упоминается, он все равно будет использоваться для t2 член.
Другие решения
Других решений пока нет …