如何编写无分支std :: vector扫描？

Question

我想在数组上写一个简单的扫描.我有一个std::vector<int> data,我想找到元素小于9的所有数组索引,并将它们添加到结果向量.我可以用分支写这个:

for (int i = 0; i < data.size(); ++i)
    if (data[i] < 9)
        r.push_back(i);

这给出了正确答案,但我想将其与无分支版本进行比较.

使用原始数组 - 并假设它data是一个int数组,length是它中元素的数量,并且r是一个有足够空间的结果数组 - 我可以这样写:

int current_write_point = 0;
for (int i = 0; i < length; ++i){
    r[current_write_point] = i;
    current_write_point += (data[i] < 9);
}

我如何使用向量获得类​​似的行为data？

Answer 1

让我们看看实际的编译器输出:

auto scan_branch(const std::vector<int>& v)
{
  std::vector<int> res;
  int insert_index = 0;
  for(int i = 0; i < v.size(); ++i)
  {
    if (v[i] < 9)
    {
       res.push_back(i);
    } 
  }
  return res;
}

该代码显然在第26行反汇编中有一个分支.如果它大于或等于9,它只会继续下一个元素,但是如果小于9,则会为push_back执行一些可怕的代码,我们继续.没什么意外的.

auto scan_nobranch(const std::vector<int>& v)
{
  std::vector<int> res;
  res.resize(v.size());

  int insert_index = 0;
  for(int i = 0; i < v.size(); ++i)
  {
    res[insert_index] = i;
    insert_index += v[i] < 9;
  }

  res.resize(insert_index);
  return res;
}

但是,这个只有一个条件移动,你可以在反汇编的第190行看到.看起来我们有一个胜利者.由于条件移动不会导致流水线停滞,因此在此流程中没有分支(条件检查除外).