SoA/AoS 内存布局的 C++ 零成本抽象
C++ zero-cost abstraction for SoA/AoS memory layouts
假设我有一段使用结构数组 (AoS) 内存布局的大型代码。我想在 C++ 中构建一个零成本抽象，它允许我以尽可能少的重构工作在 AoS 和 SoA 之间切换。
例如，使用 class 访问成员函数
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.;
我可以在其中 select 使用 "SoA" 或 "AoS" 模板参数的内存布局。我的问题是：这样的东西存在于某处吗？如果没有，最好如何实施？
要实现你想要的，你只需要使你的新结构可迭代。请原谅我的 Java 行话，我在 C++ 中所说的 iterable 的意思只是您应该在 class 中创建名为 begin 和 end。这些应该 return 一个重载了 (pre)++ 或 ++(post) 的迭代器对象，以及 *(pointer) 运算符。
另一种方式是这样的：
Why use non-member begin and end functions in C++11?
现在，您只需交换容器类型，for-range 循环仍按应有的方式工作。
我实现了一个通用的解决方案，我将在下面解释它（这将是一个很长的post）。这当然不是唯一可能的答案，收集反馈会很棒。我把这个解决方案的完整代码放在这里 https://github.com/crosetto/SoAvsAoS
我们创建了两个助手 classes，它们给定一个项目，根据标签模板参数生成容器类型作为元组向量或向量元组。我们称此 class 为 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;
此 class 将仅包含与容器交互的静态成员函数（例如提取元素、插入、调整大小等）。我们写了两个模板特化。第一个（琐碎的）结构数组情况：
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(); }
};
...只是转发。我们对数组结构的情况做同样的事情。
注意：下面的代码有几点需要说明。
它将所有类型包装在一个 ref_wrap 类型中，即 "decorated" std::reference_wrapper。这是因为我们希望将元素作为左值引用进行访问，以便能够更改它们的值。使用常规参考我们会遇到麻烦，例如类型包含任何引用。值得注意的一件事是，在 AoS 情况下 DataLayoutPolicy::value_type 是引用，而在 SoA 情况下是 ref_wrap 类型的值。
我们 return 按值新建一个包含 ref_wrap 个值的元组。这出奇地好，因为编译器正在优化所有副本，而且在 C++17 中甚至更好（returned 元组是一个 'prvalue'），因为添加了有保证的副本省略符合标准：不复制元组，即使 std::tuple 和 std::reference_wrapper 没有 copy/move 构造函数，此代码也能正常工作。
我们使用 std::integer 序列来静态展开参数包：这很丑陋，但是 "the way" 从 C++14 开始就可以做到这一点（在 C++11 中必须使用模板递归来实现相同的目的）。参数包还没有 "for_each" 这样的东西。
我们使用 C++17 折叠表达式多次调用函数 returning 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
}
};
所以现在这段代码非常清楚地展示了如何构建这种抽象。我们在下面展示了使用它的可能策略。我们使用 DataLayoutPolicy 和通用 TItem 类型
定义 policy_t 类型
template <template <typename T> class TContainer, DataLayout TDataLayout, typename TItem>
using policy_t = DataLayoutPolicy<TContainer, TDataLayout, TItem>;
容器class 将大部分调用转发给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 的成员函数时，我们必须依赖编译器优化以使我们的抽象成为 "zero-cost"：我们不想调用 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循环中设置一个brakpoint，单步执行汇编指令（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 [=21=]x610,%rsi
0x400b0b <main(int, char**)+203> add [=21=]xffffffffffffffff,%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 [=22=]x20,%rsi
0x400bcb <main(int, char**)+331> add [=22=]x8,%rbx
0x400bcf <main(int, char**)+335> jne 0x400b60 <main(int, char**)+224>
我们看到循环由 Clang（版本 6.0.0）展开和向量化，地址增量为 0x20，与项目结构中存在的数据成员数量无关。
假设我有一段使用结构数组 (AoS) 内存布局的大型代码。我想在 C++ 中构建一个零成本抽象，它允许我以尽可能少的重构工作在 AoS 和 SoA 之间切换。 例如，使用 class 访问成员函数
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.;
我可以在其中 select 使用 "SoA" 或 "AoS" 模板参数的内存布局。我的问题是：这样的东西存在于某处吗？如果没有，最好如何实施？
要实现你想要的，你只需要使你的新结构可迭代。请原谅我的 Java 行话，我在 C++ 中所说的 iterable 的意思只是您应该在 class 中创建名为 begin 和 end。这些应该 return 一个重载了 (pre)++ 或 ++(post) 的迭代器对象，以及 *(pointer) 运算符。
另一种方式是这样的： Why use non-member begin and end functions in C++11?
现在，您只需交换容器类型，for-range 循环仍按应有的方式工作。
我实现了一个通用的解决方案，我将在下面解释它（这将是一个很长的post）。这当然不是唯一可能的答案，收集反馈会很棒。我把这个解决方案的完整代码放在这里 https://github.com/crosetto/SoAvsAoS
我们创建了两个助手 classes，它们给定一个项目，根据标签模板参数生成容器类型作为元组向量或向量元组。我们称此 class 为 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;
此 class 将仅包含与容器交互的静态成员函数（例如提取元素、插入、调整大小等）。我们写了两个模板特化。第一个（琐碎的）结构数组情况：
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(); }
};
...只是转发。我们对数组结构的情况做同样的事情。
注意：下面的代码有几点需要说明。
它将所有类型包装在一个 ref_wrap 类型中，即 "decorated" std::reference_wrapper。这是因为我们希望将元素作为左值引用进行访问，以便能够更改它们的值。使用常规参考我们会遇到麻烦，例如类型包含任何引用。值得注意的一件事是，在 AoS 情况下 DataLayoutPolicy::value_type 是引用，而在 SoA 情况下是 ref_wrap 类型的值。
我们 return 按值新建一个包含 ref_wrap 个值的元组。这出奇地好，因为编译器正在优化所有副本，而且在 C++17 中甚至更好（returned 元组是一个 'prvalue'），因为添加了有保证的副本省略符合标准：不复制元组，即使 std::tuple 和 std::reference_wrapper 没有 copy/move 构造函数，此代码也能正常工作。
我们使用 std::integer 序列来静态展开参数包：这很丑陋，但是 "the way" 从 C++14 开始就可以做到这一点（在 C++11 中必须使用模板递归来实现相同的目的）。参数包还没有 "for_each" 这样的东西。
我们使用 C++17 折叠表达式多次调用函数 returning 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
}
};
所以现在这段代码非常清楚地展示了如何构建这种抽象。我们在下面展示了使用它的可能策略。我们使用 DataLayoutPolicy 和通用 TItem 类型
定义 policy_t 类型template <template <typename T> class TContainer, DataLayout TDataLayout, typename TItem>
using policy_t = DataLayoutPolicy<TContainer, TDataLayout, TItem>;
容器class 将大部分调用转发给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 的成员函数时，我们必须依赖编译器优化以使我们的抽象成为 "zero-cost"：我们不想调用 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循环中设置一个brakpoint，单步执行汇编指令（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 [=21=]x610,%rsi
0x400b0b <main(int, char**)+203> add [=21=]xffffffffffffffff,%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 [=22=]x20,%rsi
0x400bcb <main(int, char**)+331> add [=22=]x8,%rbx
0x400bcf <main(int, char**)+335> jne 0x400b60 <main(int, char**)+224>
我们看到循环由 Clang（版本 6.0.0）展开和向量化，地址增量为 0x20，与项目结构中存在的数据成员数量无关。