Я реализовал универсальное решение, я объясню его здесь ниже (это будет длинный пост).Конечно, это не единственный возможный ответ, и было бы здорово собрать отзывы.Я разместил полный код этого решения здесь https://github.com/crosetto/SoAvsAoS
Мы создаем два вспомогательных класса, которые для данного элемента генерируют тип контейнера как вектор кортежей или кортеж векторов, в зависимости от аргумента шаблона тега.Мы называем этот класс DataLayoutPolicy, и мы собираемся использовать его, например, таким образом:
DataLayoutPolicy<std::vector, SoA, char, double, std::string>
для генерации кортежа векторов char, int и double.
enum class DataLayout { SoA, //structure of arrays
AoS //array of structures
};
template <template <typename...> class Container, DataLayout TDataLayout, typename TItem>
struct DataLayoutPolicy;
ThisКласс будет содержать только статические функции-члены для взаимодействия с контейнером (например, извлечь элемент, вставить, изменить размер и т. д.).Мы пишем две шаблонные специализации.Первый (тривиальный) для массива структур ситуации:
template <template <typename...> class Container, template<typename...> class TItem, typename... Types>
struct DataLayoutPolicy<Container, DataLayout::AoS, TItem<Types...>> {
using type = Container<TItem<Types...>>;
using value_type = TItem<Types...>&;
constexpr static value_type get( type& c_, std::size_t position_ ){ return value_type(*static_cast<TItem<Types...>*>(&c_[ position_ ])); }
constexpr static void resize( type& c_, std::size_t size_ ) { c_.resize( size_ ); }
template <typename TValue>
constexpr static void push_back( type& c_, TValue&& val_ ){ c_.push_back( val_ ); }
static constexpr std::size_t size(type& c_){ return c_.size(); }
};
... просто пересылка.Мы делаем то же самое для структуры массива case.
Примечание: в приведенном ниже коде необходимо пояснить несколько вещей.
Оборачивает все типы в тип ref_wrap, который является «оформленным» std :: reference_wrapper.Это потому, что мы хотим получить доступ к элементам как к ссылкам lvalue, чтобы иметь возможность изменять их значения.используя обычную ссылку, мы столкнемся с проблемами, если, например, Types содержит какую-либо ссылку.Стоит отметить, что в случае AoS DataLayoutPolicy :: value_type является ссылкой, а в случае SoA - значением типа ref_wrap.
мы возвращаем по значению вновь созданный кортеж ref_wrapценности.Это удивительно хорошо, потому что компилятор оптимизирует все копии, и это еще более хорошо в C ++ 17 (возвращенный кортеж - «prvalue»), потому что гарантированное разрешение копирования добавлено в стандарт: кортеж являетсяне копируется, этот код будет работать, даже если std :: tuple и std :: reference_wrapper не имеют конструктора копирования / перемещения.
мы используем последовательность std :: integer для статической развертки пакета параметров: thisнекрасиво, но это «способ» сделать это начиная с C ++ 14 (а в C ++ 11 нужно было использовать рекурсию шаблона для достижения того же).Для пакетов параметров еще нет такого понятия, как for_each.
Мы используем C ++ 17-кратные выражения для вызова функции, возвращающей void несколько раз.До C ++ 17 это было достигнуто кратко с помощью хитрых хаков.
template <typename T>
struct ref_wrap : public std::reference_wrapper<T>{
operator T&() const noexcept { return this->get(); }
ref_wrap(T& other_) : std::reference_wrapper<T>(other_){}
void operator =(T && other_) {this->get()=other_;}
};
template <template <typename...> class Container, template<typename...> class TItem, typename... Types>
struct DataLayoutPolicy<Container, DataLayout::SoA, TItem<Types...>> {
using type = std::tuple<Container<Types>...>;
using value_type = TItem<ref_wrap<Types>...>;
constexpr static value_type get( type& c_, std::size_t position_ )
{
return doGet( c_, position_, std::make_integer_sequence<unsigned, sizeof...( Types )>() ); // unrolling parameter pack
}
constexpr static void resize( type& c_, std::size_t size_ ) {
doResize( c_, size_, std::make_integer_sequence<unsigned, sizeof...( Types )>() ); // unrolling parameter pack
}
template <typename TValue>
constexpr static void push_back( type& c_, TValue&& val_ ){
doPushBack( c_, std::forward<TValue>(val_), std::make_integer_sequence<unsigned, sizeof...( Types )>() ); // unrolling parameter pack
}
static constexpr std::size_t size(type& c_){ return std::get<0>( c_ ).size(); }
private:
template <unsigned... Ids>
constexpr static auto doGet( type& c_, std::size_t position_, std::integer_sequence<unsigned, Ids...> )
{
return value_type{ ref_wrap( std::get<Ids>( c_ )[ position_ ] )... }; // guaranteed copy elision
}
template <unsigned... Ids>
constexpr static void doResize( type& c_, unsigned size_, std::integer_sequence<unsigned, Ids...> )
{
( std::get<Ids>( c_ ).resize( size_ ), ... ); //fold expressions
}
template <typename TValue, unsigned... Ids>
constexpr static void doPushBack( type& c_, TValue&& val_, std::integer_sequence<unsigned, Ids...> )
{
( std::get<Ids>( c_ ).push_back( std::get<Ids>( std::forward<TValue>( val_ ) ) ), ... ); // fold expressions
}
};
Так что теперь этот код довольно ясно показывает, как можно построить эту абстракцию.Ниже мы показываем возможную стратегию его использования.Мы определяем тип policy_t, используя DataLayoutPolicy и универсальный тип TItem
template <template <typename T> class TContainer, DataLayout TDataLayout, typename TItem>
using policy_t = DataLayoutPolicy<TContainer, TDataLayout, TItem>;
. Контейнерный класс перенаправляет большинство вызовов статических функций, определенных типом policy_t.Это может выглядеть следующим образом
template <template <typename ValueType> class TContainer, DataLayout TDataLayout, typename TItem>
struct BaseContainer
{
/*member functions like puhs_back, resize,...*/
value_type operator[]( std::size_t position_ )
{
return policy_t::get( mValues, position_ );
}
iterator begin() { return iterator( this, 0 ); }
iterator end() { return iterator( this, size() ); }
private:
typename policy_t::type mValues;
};
Теперь это не стандартный контейнер, поэтому мы должны определить итератор, чтобы использовать его в алгоритмах STL.Итератор, который мы создаем, выглядит как итератор STL для контейнера кортежа, за исключением того факта, что он должен содержать ссылку на контейнер, потому что когда мы вызываем оператор разыменования, мы хотим вызвать оператор нашего хранилища [], который статически отправляетоперация с использованием политики компоновки данных контейнера.
template <typename TContainer>
class Iterator
{
private:
using container_t = TContainer;
public:
/* ... usual iterator member functions and type definitions ...*/
template<typename TTContainer>
Iterator( TTContainer* container_, std::size_t position_ = 0 ):
mContainer( container_ )
, mIterPosition( position_ )
{
}
value_type operator*() {
return (*mContainer)[ mIterPosition ];
}
private:
container_t* mContainer = nullptr;
std::size_t mIterPosition = std::numeric_limits<std::size_t>::infinity();
};
В конечном итоге мы определяем нашу структуру данных "item": мы делаем ее декоратором std :: tuple с некоторыми конкретными функциями-членами (в данном случае только с геттерами)/setters).
template<typename ... T>
struct Item : public std::tuple<T ...>{
using std::tuple<T...>::tuple;
auto & myDouble(){return std::get<0>(*this);}
auto & myChar() {return std::get<1>(*this);}
auto & myString(){return std::get<2>(*this);}
};
Когда мы вызываем функции-члены Item, мы должны полагаться на оптимизацию компилятора, чтобы наша абстракция была «нулевой стоимостью»: мы не хотим вызывать конструктор Item,потому что мы создаем временный кортеж просто для доступа к одному из его членов каждый раз, а затем сразу же его удаляем.
, поэтому в итоге мы можем написать программу:
template<typename T>
using MyVector = std::vector<T, std::allocator<T>>;
int main(int argc, char** argv){
using container_t = BaseContainer<MyVector, DataLayout::SoA, Item<double, char, std::string, Pad> >;
container_t container_(1000);
for(auto&& i : container_){
i.myDouble()=static_cast<double>(argc);
}
и мы можемнаписать общий и эффективный код независимо от расположения памяти под ним.Осталось проверить, что это абстракция с нулевой стоимостью.Самый простой способ проверить это с помощью отладчика: скомпилировать пример с включенными символами отладки,
> clang++ -std=c++1z -O3 -g main.cpp -o test
запустите его с помощью gdb, установите точку брака в цикле for и выполните инструкции по сборке (команда layout split одновременно показывает исходный код и дизассемблированные инструкции)
> gdb test
(gdb) break main.cpp : 10 # set breakpoint inside the loop
(gdb) run # execute until the breakpoint
(gdb) layout split # show assembly and source code in 2 separate frames
(gdb) stepi # execute one instruction
Инструкциивыполняются внутри цикла в случае макета данных AoS
0x400b00 <main(int, char**)+192> movsd %xmm0,(%rsi)
0x400b04 <main(int, char**)+196> add $0x610,%rsi
0x400b0b <main(int, char**)+203> add $0xffffffffffffffff,%rcx
0x400b0f <main(int, char**)+207> jne 0x400b00 <main(int, char**)+192>
Обратите внимание, в частности, что во второй строке добавляемое смещение для вычисления адреса составляет 0x160.Это изменяется в зависимости от размера элементов данных в объекте элемента.С другой стороны, для структуры данных SoA у нас есть
0x400b60 <main(int, char**)+224> movups %xmm1,(%rdi,%rsi,8)
0x400b64 <main(int, char**)+228> movups %xmm1,0x10(%rdi,%rsi,8)
0x400b69 <main(int, char**)+233> movups %xmm1,0x20(%rdi,%rsi,8)
0x400b6e <main(int, char**)+238> movups %xmm1,0x30(%rdi,%rsi,8)
0x400b73 <main(int, char**)+243> movups %xmm1,0x40(%rdi,%rsi,8)
0x400b78 <main(int, char**)+248> movups %xmm1,0x50(%rdi,%rsi,8)
0x400b7d <main(int, char**)+253> movups %xmm1,0x60(%rdi,%rsi,8)
0x400b82 <main(int, char**)+258> movups %xmm1,0x70(%rdi,%rsi,8)
0x400b87 <main(int, char**)+263> movups %xmm1,0x80(%rdi,%rsi,8)
0x400b8f <main(int, char**)+271> movups %xmm1,0x90(%rdi,%rsi,8)
0x400b97 <main(int, char**)+279> movups %xmm1,0xa0(%rdi,%rsi,8)
0x400b9f <main(int, char**)+287> movups %xmm1,0xb0(%rdi,%rsi,8)
0x400ba7 <main(int, char**)+295> movups %xmm1,0xc0(%rdi,%rsi,8)
0x400baf <main(int, char**)+303> movups %xmm1,0xd0(%rdi,%rsi,8)
0x400bb7 <main(int, char**)+311> movups %xmm1,0xe0(%rdi,%rsi,8)
0x400bbf <main(int, char**)+319> movups %xmm1,0xf0(%rdi,%rsi,8)
0x400bc7 <main(int, char**)+327> add $0x20,%rsi
0x400bcb <main(int, char**)+331> add $0x8,%rbx
0x400bcf <main(int, char**)+335> jne 0x400b60 <main(int, char**)+224>
Мы видим, что цикл развернут и векторизован Clang (версия 6.0.0), и приращение для адреса составляет 0x20, независимо от числачленов данных, присутствующих в структуре элемента.