用于SoA/AoS内存布局的C++零成本抽象

Question

假设我有一个使用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"模板参数选择内存布局.我的问题是:这样的事情存在于某个地方吗？如果没有,最好如何实施？

Answer 1

我实现了一个通用的解决方案,我将在下面解释它(这将是一个很长的帖子).当然,这不是唯一可能的答案,收集反馈意见非常好.我在这里放置了这个解决方案的完整代码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(); }
};

......只是转发.我们对数组结构的情况做同样的事情.

注意:下面的代码有几点需要解释.

它包装了ref_wrap类型中的所有类型,这是一个"装饰"的std :: reference_wrapper.这是因为我们想要将元素作为左值引用来访问,以便能够更改它们的值.使用常规引用,如果例如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 fold表达式来调用多次返回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>;

容器类将大多数调用转发给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迭代器,除了它必须保存对容器的引用这一事实,因为当我们调用dereference运算符时,我们要调用我们的存储的operator [],它静态地调度使用容器的数据布局策略进行操作.

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的装饰器,带有一些特定的成员函数(在这种情况下只有getter/setter).

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循环中设置一个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    $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,与项结构中存在的数据成员的数量无关.