c++ - 为什么这种搜索方法不可扩展？

Question

我想使用 openMP 并行我的搜索算法，vTree 是一个二叉搜索树，我想对每个点集应用我的搜索算法。下面是我的代码片段。两点的搜索过程完全无关，因此可以并行。尽管他们确实需要读取同一棵树，但是一旦构建，树就不会再被修改。因此它是只读的。

但是，下面的代码显示出糟糕的可扩展性，在我的 32 核平台上，速度只提高了 2 倍。是因为 vTree 被所有线程读取了吗？如果是这样，我该如何进一步优化代码？

    auto results = vector<vector<Point>>(particleNum);
    auto t3 = high_resolution_clock::now();
    double radius = 1.6;
#pragma omp parallel for
    for (decltype(points.size()) i = 0; i < points.size(); i++)
    {
        vTree.search(points[i], radius, results[i]);
    }
    auto t4 = high_resolution_clock::now();
    double searchTime = duration_cast<duration<double>>(t4 - t3).count();

search 的类型签名是

void VPTree::search(const Point& p, double radius, vector<Point>& result) const

搜索结果将放入result。

Answer 1

我最好的猜测是您正在缓存结果 vector 上的乒乓球。我假设您的“搜索”功能使用传入的结果 vector 作为放置点的位置，并且您在整个算法中使用它来插入在搜索树中遇到的邻居。每当您向该结果 vector 添加一个点时，该 vector 对象的内部数据将被修改。并且由于所有结果 vector 都打包在连续的内存中，因此不同的结果 vector 很可能占用相同的缓存行。因此，当 CPU 保持缓存一致性时，它会不断锁定相关的缓存行。

解决它的方法是使用一个内部的、临时的 vector ，你只在最后分配给结果 vector 一次(如果你使用移动语义，这可以很便宜地完成)。像这样:

void VPTree::search(const Point& p, double radius, vector<Point>& result) const {
  vector<Point> tmp_result;
  // ... add results to "tmp_result"
  result = std::move(tmp_result);
  return;
}

或者，您也可以只按值返回 vector (隐含地使用移动):

vector<Point> VPTree::search(const Point& p, double radius) const {
  vector<Point> result;
  // ... add results to "result"
  return result;
}

欢迎来到移动语义的快乐世界，它在解决这些类型的并发/缓存一致性问题方面有多么出色。

也可以想象您遇到与从所有线程访问同一棵树相关的问题，但由于它都是只读操作，我很确定即使在像 x86(和其他 Intel/AMD CPU)这应该不会造成重大问题，但我可能是错的(也许是一种“超额订阅”问题在起作用，但这是可疑的)。其他问题可能包括 OpenMP 确实会产生相当多的开销(产生线程、同步等)，这些开销必须根据您在这些并行循环中执行的实际操作的计算成本进行加权(并不总是如此)一个有利的权衡)。而且，如果您的 VPTree(我想代表“Vantage-point Tree”)没有良好的引用位置(例如，您将其实现为链接树)，那么无论您使用哪种方式，性能都会很糟糕它(正如我解释的 here )。