c++ - 将 AoS 转换为 SoA 时处理组合爆炸

Question

假设我想将结构数组转换为数组结构，其中运行时参数指示应转换源结构的哪些成员。例如:

struct SourceElement {
  string member1;
  float member2;
  int member3;
  //More members...
};
auto source_elements = ...; //A forward-iterable range of SourceElement objects

vector<string> members1;
vector<float> members2;
vector<int> members3;

for(auto& source_element : source_elements) {
  if(member1_required) {
    members1.push_back(source_element.member1);
  }
  if(member2_required) {
    members2.push_back(source_element.member2);
  }
  if(member3_required) {
    members3.push_back(source_element.member3);
  }
  //...and so on...
}
//Some of the vectors might be empty, which I am fine with

我想摆脱循环中的条件，希望无条件代码运行得更快一些。我所知道的典型方法是简单地将条件从循环中移出，如果它只是一个条件，这会很好地工作，但是对于多个条件，这会导致组合爆炸 - 对于 N 成员 I必须编写 2^N 不同的循环体。添加新成员也需要编写大量代码。这是一个看起来如何的示例:

if(member1_required && !member2_required && !member3_required) {
  for(auto& source_element : source_elements) {
    members1.push_back(source_element.member1);
  }
} else if(member1_required && member2_required && !member3_required) {
  for(auto& source_element : source_elements) {
    members1.push_back(source_element.member1);
    members2.push_back(source_element.member2);
  }
}
//... and so on

处理此类问题的好方法是什么？理想的解决方案应具有以下特性:

• 生成的代码应尽可能接近手动解决方案(每个组合一个 for 循环)
• 添加新成员应该不费吹灰之力
• 解构源元素应该允许数据转换(例如 members1.push_back(my_conversion(source_element.member1)))。一个简单的案例:SourceElement 有一个 double 成员，但我只想存储 float 数据
• 源数据可能来自前向迭代器，因此不能假设所有数据都线性存储在内存中

Answer 1

您可以使用模板，示例(未测试):

struct DestElements
{
    vector<string> members1;
    vector<float> members2;
    vector<int> members3;
};

template<uint32_t bitMask>
DestElements copy( const SourceElement* begin, const SourceElement* end )
{
    DestElements dest;
    for( ; begin < end; begin++ )
    {
        if constexpr( bitMask & 1 )
            dest.members1.push_back( begin->member1 );
        if constexpr( bitMask & 2 )
            dest.members2.push_back( begin->member2 );
        if constexpr( bitMask & 4 )
            dest.members3.push_back( begin->member3 );
    }
    return std::move( dest );
}

using pfnCopy = DestElements( *)( const SourceElement* begin, const SourceElement* end );

static const std::array<pfnCopy, 8> dispatch =
{
    // You can do crazy C++ metaprogramming here, std::apply, std::make_index_sequence, etc.
    // When I have too large count of them, I write ~2 lines of C# in a T4 template instead.
    &copy<0>, &copy<1>, &copy<2>, &copy<3>, &copy<4>, &copy<5>, &copy<6>, &copy<7>,
};

// Usage
uint32_t mask = 0;
if( member1_required ) mask |= 1;
if( member2_required ) mask |= 2;
if( member3_required ) mask |= 4;
DestElements dest = dispatch[ mask ]( source_elements.data(),
                source_elements.data() + source_elements.size() );

显然，您需要用前向迭代器的类型替换 const 指针。

但是，我不确定这会对性能产生可衡量的影响。所有现代 CPU 都进行分支预测。这些条件在您迭代时不会改变。在第一次循环迭代后，所有这些分支都将以 100% 的准确率进行预测。