Абстракция C++ с нулевой стоимостью для макетов памяти SoA/AoS
Скажем, у меня большой код с использованием структуры памяти Array of Structures (AoS). Я хотел бы создать абстракцию с нулевой стоимостью в C++, которая позволяет мне переключаться между AoS и SoA с минимальными усилиями по рефакторингу. Например, возьмите класс с функциями доступа
struct Item{
auto& myDouble(){ return mDouble; }
auto& myChar(){ return mChar; }
auto& myString(){ return mString; }
private:
double mDouble;
char mChar;
std::string mString;
};
который используется внутри контейнера в цикле
std::vector<Item> vec_(1000);
for (auto& i : vec_)
i.myDouble()=5.;
Я хотел бы изменить первый фрагмент, в то время как второй остается похожим... например, что-то вроде
MyContainer<Item, SoA> vec_(1000)
for (auto& i : vec_)
i.myDouble()=5.;
в котором я могу выбрать макет памяти с параметрами шаблона "SoA" или "AoS". Мои вопросы: существует ли такая вещь где-нибудь? И если это не так, как это будет реализовано в лучшем случае?
2 ответа
Я реализовал общее решение, я объясню его здесь ниже (это будет длинный пост). Конечно, это не единственный возможный ответ, и было бы здорово собрать отзывы. Я разместил полный код этого решения здесь 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;
Этот класс будет содержать только статические функции-члены для взаимодействия с контейнером (например, извлечь элемент, вставить, изменить размер и т. Д.). Мы пишем две шаблонные специализации. Первый (тривиальный) для массива структур ситуации:
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 для статического развертывания пакета параметров: это уродливо, но это "способ" сделать это с 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 с некоторыми конкретными функциями-членами (в этом случае только getters / 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. Это изменяется в зависимости от размера элементов данных в объекте item. С другой стороны, для структуры данных 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, независимо от количества членов данных, присутствующих в структуре элемента.
Чтобы достичь того, чего вы хотите, вы просто должны сделать вашу новую структуру итеративной. Простите за то, что я говорю на языке Java, что я подразумеваю под итеративностью в C++, просто то, что вы должны создавать функции внутри вашего класса, называемые begin а также end, Они должны возвращать объект итератора, который имеет (pre)++ или же ++(post) перегружен, а также *(pointer) оператор.
Другой способ заключается в следующем: зачем использовать не входящие и не завершающие функции в C++11?
Теперь это позволит вам просто поменять тип контейнера, и цикл for-range будет работать так, как должен.