Перекомпоновка данных во время компиляции?

Мне было интересно, как можно сделать макет памяти класса более эффективным в шаблонном коде. Насколько я знаю, Стандарт обязывает элементы данных класса размещаться в памяти в порядке их объявления. Возможно, компилятором может быть выполнено заполнение для выравнивания элементов данных, добавляющих ненужные данные к размеру класса. Идея состоит в том, чтобы перекомпоновывать объявления членов данных во время компиляции, чтобы минимизировать такое заполнение. Я немного искал, но не мог найти никакой информации (большую часть времени люди обсуждают упаковочные директивы компилятора, что не совсем то, что я вижу).

Во-первых, рассмотрим следующий (тривиальный, но повторяющийся и уродливый) код (тот же код на ideone.com) (вопросы находятся под кодом, не стесняйтесь пропустить прямо к ним):

#include <iostream>
#include <cstdint>

namespace so
{
template <typename Ta, typename Tb, typename Tc, std::size_t =
((sizeof(Ta) >= sizeof(Tb)) && (sizeof(Tb) >= sizeof(Tc))) ? 10 :
((sizeof(Ta) >= sizeof(Tc)) && (sizeof(Tc) >= sizeof(Tb))) ? 11 :
((sizeof(Tb) >= sizeof(Ta)) && (sizeof(Ta) >= sizeof(Tc))) ? 20 :
((sizeof(Tb) >= sizeof(Tc)) && (sizeof(Tc) >= sizeof(Ta))) ? 21 :
((sizeof(Tc) >= sizeof(Ta)) && (sizeof(Ta) >= sizeof(Tb))) ? 30 :
((sizeof(Tc) >= sizeof(Tb)) && (sizeof(Tb) >= sizeof(Ta))) ? 31 : 0>
struct foo {};

template <typename Ta, typename Tb, typename Tc>
struct foo<Ta, Tb, Tc, 10>
{
Ta a;
Tb b;
Tc c;
foo(Ta _a, Tb _b, Tc _c) : a{_a}, b{_b}, c{_c} {}
};

template <typename Ta, typename Tb, typename Tc>
struct foo<Ta, Tb, Tc, 11>
{
Ta a;
Tc c;
Tb b;
foo(Ta _a, Tb _b, Tc _c) : a{_a}, c{_c}, b{_b} {}
};

template <typename Ta, typename Tb, typename Tc>
struct foo<Ta, Tb, Tc, 20>
{
Tb b;
Ta a;
Tc c;
foo(Ta _a, Tb _b, Tc _c) : b{_b}, a{_a}, c{_c} {}
};

template <typename Ta, typename Tb, typename Tc>
struct foo<Ta, Tb, Tc, 21>
{
Tb b;
Tc c;
Ta a;
foo(Ta _a, Tb _b, Tc _c) : b{_b}, c{_c}, a{_a} {}
};

template <typename Ta, typename Tb, typename Tc>
struct foo<Ta, Tb, Tc, 30>
{
Tc c;
Ta a;
Tb b;
foo(Ta _a, Tb _b, Tc _c) : c{_c}, a{_a}, b{_b} {}
};

template <typename Ta, typename Tb, typename Tc>
struct foo<Ta, Tb, Tc, 31>
{
Tc c;
Tb b;
Ta a;
foo(Ta _a, Tb _b, Tc _c) : c{_c}, b{_b}, a{_a} {}
};

template <typename Ta, typename Tb, typename Tc>
struct bar: public foo<Ta, Tb, Tc>
{
private:
using base = foo<Ta, Tb, Tc>;
public:
bar() = default;
using base::base;
};

template <typename Ta, typename Tb, typename Tc>
struct foobar
{
Ta a;
Tb b;
Tc c;
foobar() = default;
foobar(Ta _a, Tb _b, Tc _c) : a{_a}, b{_b}, c{_c} {}
};
} //namespace so

int main()
{
so::bar<std::uint16_t, std::uint32_t, std::uint16_t> bar{1, 2, 3};
so::foobar<std::uint16_t, std::uint32_t, std::uint16_t> foobar{1, 2, 3};

std::cout << sizeof(bar) << "\t" << sizeof(foobar) << std::endl;

std::cout << bar.a << " : " << bar.b << " : " << bar.c << std::endl;
std::cout << foobar.a << " : " << foobar.b << " : " << foobar.c << std::endl;

return (0);
}

Выход программы:

8   12
1 : 2 : 3
1 : 2 : 3

Вопросы:

  1. Есть какой-то известный, независимый от компилятора способ решения такой проблемы (может быть, Boost)?
  2. Если нет, есть ли какие-то специфичные для компилятора директивы, которые будут делать это автоматически (без смещения данных, как в GCC __atribute__((packed)))?
  3. Может ли это быть сделано более общим способом (возможно, с использованием шаблонов с переменными параметрами)?

Заранее спасибо!

6

Решение

Я считаю, что у меня есть относительно простое решение для вариационных шаблонов.

Однако для реализации потребуется пара помощников, поэтому я представлю их задом наперед, чтобы вы могли вначале понять суть.

template <typename... Args>
class OptimizedLayout {
public:
template <size_t I>
auto at() -> decltype(std::get<Index<I>::value>(_storage)) {
return std::get<Index<I>::value>(_storage);
}

template <size_t I>
auto at() const -> decltype(std::get<Index<I>::value>(_storage)) {
return std::get<Index<I>::value>(_storage);
}

private:
using Indexed = /**/; // pairs of sorted Args (by decreasing size)
// and their original index in the argument list

using Storage = /*std::tuple<Indexed.first ...>*/;

template <size_t I>
using Index = /*index of element of Indexed whose .second is I*/;

Storage _storage;
}; // class OptimizedLayout

Основное преимущество заключается в том, что изменение способа упаковки элементов влияет только на то, как Indexed определяется, так что вы можете легко улучшить алгоритм. Пока я просто предоставлю эквивалент вашего шаблона.


Отказ от ответственности: следующий код не проверен, он может даже не скомпилироваться, не говоря уже о правильном результате.

I. Генерация индексов.

Объяснение можно найти на салон, мы можем использовать его для генерации пачки пар (тип, индекс). Для сортировки мы будем использовать алгоритм MPL, поэтому проще создать пакет в виде Вектор MPL.

template <std::size_t... Is>
struct indices {};

template <std::size_t N, std::size_t... Is>
struct build_indices
: build_indices<N-1, N-1, Is...> {};

template <std::size_t... Is>
struct build_indices<0, Is...> { using type = indices<Is...>; };

template <typename Tuple, typename Indices>
struct IndexedImpl;

template <typename... T, size_t... I>
struct IndexedImpl< std::tuple<T...>, indices<I...> > {
using type = boost::mpl::vector< std::pair<T, I>... >;
};

template <typename Tuple>
using Indexed =
IndexedImpl<Tuple, typename build_indices<std::tuple_size<Tuple>::value>::type>;

II. Сортировка

Для сортировки мы будем использовать Алгоритм сортировки MPL, который работает на типах.

struct GreaterSize {
template <typename T, typename U>
struct apply {
using type = boost::mpl::bool_<sizeof(T) > sizeof(U)>;
};
};

template <typename T>
struct TupleInserter {
using state = T;

template <typename Seq, typename E>
struct apply;
};

template <typename T>
template <typename... Args, typename E>
struct TupleInserter<T>::apply<std::tuple<Args...>, E> {
using type = std::tuple<Args..., E>;
};

template <typename Tuple>
using SortedSequence = boost::mpl::sort<
typename Indexed<Tuple>::type,
GreaterSize,
TupleInserter
>;

III. Вычисление класса хранения

Теперь нам нужно только вычислить класс хранения, который делается путем извлечения первого элемента каждой пары. Интересно, что сопоставление с образцом может действительно помочь здесь.

template <typename T>
struct TupleFirstExtractor;

template <typename... T, size_t... I>
struct TupleFirstExtractor<std::tuple<std::pair<T, I>...>> {
using type = std::tuple<T...>;
};

Внутривенно Вычисление решателя индекса

template <typename Tuple, size_t Needle, size_t Acc>
struct IndexFinderImpl;

template <typename H, size_t h, typename... Tail, size_t Needle, size_t Acc>
struct IndexFinderImpl<std::tuple<std::pair<H,h>, Tail...>, Needle, Acc>:
IndexFinderImpl<std::tuple<Tail...>, Needle, Acc+1> {};

template <typename H, typename... Tail, size_t Needle, size_t Acc>
struct IndexFinderImpl<std::tuple<std::pair<H, Needle>, Tail...>, Needle, Acc>:
std::integral_constant<size_t, Acc> {};

V. Собираем все вместе

А теперь мы подключаем все:

template <typename... Args>
class OptimizedLayout {
public:
template <size_t I>
auto at() -> decltype(std::get<Index<I>::value>(_storage)) {
return std::get<Index<I>::value>(_storage);
}

template <size_t I>
auto at() const -> decltype(std::get<Index<I>::value>(_storage)) {
return std::get<Index<I>::value>(_storage);
}

private:
using Indexed = typename SortedSequence<std::tuple<Args...>>::type;

using Storage = typename TupleFirstExtractor<Indexed>::type;

template <size_t I>
using Index = IndexFinderImpl<Indexed, I, 0>;

Storage _storage;
}; // class OptimizedLayout

Подсказка: я советую использовать специализированное пространство имен для хранения всех помощников. Хотя они могут быть определены в шаблоне, их легче определить снаружи, поскольку они не зависят от Args...однако вам необходимо изолировать их, чтобы избежать конфликтов с другими частями вашей программы.

5

Другие решения

Посмотрите на эту серию сообщений в блоге Р. Мартиньо Фернандеса: http://flamingdangerzone.com/cxx11/2012/07/06/optimal-tuple-i.html.

Обрисовывает в общих чертах оптимальную упаковку кортежей. Вы можете использовать такой «упакованный» кортеж в качестве хранилища данных для своего класса и предоставлять средства доступа, скрывающие get<0>() доступ к элементу стиля кортежа.

2