TBB parallel_sort处理海量CGAL Point2向量性能低下的优化咨询

一、减少交点计算的冗余与同步开销 #

• 避免重复计算交点：当前代码会同时计算(i,k)和(k,i)的交点，这两个结果完全相同。修改遍历逻辑，只处理i < k的线对，直接减少一半的计算量，同时后续排序的元素数量也会大幅减少。示例修改：

  tbb::parallel_for(tbb::blocked_range<size_t>(0, lines.size()), [&](const tbb::blocked_range<size_t>& r) {
      std::vector<Point2> local_points;
      for (size_t i = r.begin(); i < r.end(); ++i) {
          for (size_t k = i + 1; k < lines.size(); ++k) {
              const auto intersection = CGAL::intersection(lines[i], lines[k]);
              if (intersection) {
                  const Point2* point = boost::get<Point2>(&*intersection);
                  if (point) {
                      local_points.push_back(*point);
                  }
              }
          }
      }
      std::lock_guard<std::mutex> lock(mtx);
      vertices.insert(vertices.end(), local_points.begin(), local_points.end());
  });
  

• 替换原子计数器为线程本地存储：原代码的std::atomic<size_t> counter会导致多线程频繁竞争缓存行，核数越多竞争越激烈。改用每个线程先把交点存在本地std::vector<Point2>，最后通过互斥锁合并到全局vector，彻底避免原子操作的开销。

二、优化排序阶段的性能 #

• 先去重再排序：大量重复交点会显著增加排序的时间和内存开销。在合并完所有线程的本地vector后，先执行去重操作：

  std::sort(vertices.begin(), vertices.end(), CGAL::Less<Point2, Point2>());
  auto last = std::unique(vertices.begin(), vertices.end());
  vertices.erase(last, vertices.end());
  

  去重后排序的数据量会大幅减少，缓解内存带宽压力。
• 调整parallel_sort的使用策略：tbb::parallel_sort在内存带宽成为瓶颈时（比如8核环境下），多线程的内存竞争会抵消并行收益。可以尝试：
  • 替换默认比较器为更轻量的自定义逻辑，避免CGAL封装的额外开销：

    auto point_compare = [](const Point2& a, const Point2& b) {
        if (a.x() != b.x()) return a.x() < b.x();
        return a.y() < b.y();
    };
    tbb::parallel_sort(vertices.begin(), vertices.end(), point_compare);
    

• 优化内存布局：Exact_predicates_exact_constructions_kernel::Point_2内部存储的是高精度有理数值，体积较大，排序时缓存命中率低。如果业务允许，可以先将点的坐标转换为更紧凑的表示（需保证排序的精确性），提升缓存利用率。

三、其他编译与运行时优化 #

• 禁用CGAL断言：发布版本中通过编译宏CGAL_NDEBUG关闭CGAL_precondition等断言，避免不必要的检查开销。
• 开启最高级别编译优化：编译时添加-O3（GCC/Clang）或/O2（MSVC）优化选项，同时确保链接TBB的release版本，让编译器充分优化代码。
• 减少预分配内存的浪费：原代码一开始预分配的内存远大于实际需求（平行无线交点），改用线程本地vector合并的方式，最后只分配实际需要的内存，提升缓存效率。

内容的提问来源于stack exchange，提问作者Toby