并行与顺序朴素快速排序

Question

我正在尝试实现快速排序，它并行运行分区排序，如下所示：

// Returns patition points as pair
template<typename ExPo, std::random_access_iterator I, std::sentinel_for<I> S,
    class Comp = std::ranges::less, class Proj = std::identity >
    requires std::sortable<I, Comp, Proj>
    std::pair<I, I> parition_points(ExPo policy, I first, S last, Comp comp = {}, Proj proj = {})
{
    auto val = *std::next(first, std::distance(first, last) / 2);
    auto mid1 = std::partition(policy, first, last, [&](const auto& cur) { return  std::invoke(comp, std::invoke(proj, cur), std::invoke(proj, val)); }); // a < b
    auto mid2 = std::partition(policy, mid1, last, [&](const auto& cur)  { return !std::invoke(comp, std::invoke(proj, val), std::invoke(proj, cur)); }); // !(b < a)-> b >=a
    return { mid1, mid2 };
}

// Quick sort
template<typename ExPo, std::random_access_iterator I, std::sentinel_for<I> S,
    class Comp = std::ranges::less, class Proj = std::identity >
    requires std::sortable<I, Comp, Proj>
    void quicksort(ExPo policy, I first, S last, Comp comp = {}, Proj proj = {})
{
    if (first == last) return;
    const auto& [mid1, mid2] = parition_points(policy, first, last, std::ref(comp), std::ref(proj));
    quicksort(policy, first, mid1, std::ref(comp), std::ref(proj));
    quicksort(policy, mid2,  last, std::ref(comp), std::ref(proj));
}


int main()
{
    auto rv1 = getRandomVector(100000);
    auto rv2 = rv1;
    auto rv3 = rv1;

    // std::sort parallel
    auto sort1 = [&rv1]() { std::sort(std::execution::par, rv1.begin(), rv1.end());};
    execute(sort1);

    // quicksort in parallel 
    auto sort2 = [&rv2]() {quicksort(std::execution::par, rv2.begin(), rv2.end()); };
    execute(sort2);

    // quicksort in sequential 
    auto sort3 = [&rv3]() {quicksort(std::execution::seq, rv3.begin(), rv3.end()); };
    execute(sort3);

    return 0;
}

这里是 Godbolt 编译器资源管理器 link 我的例子。

我期望使用并行执行策略调用 std::partition 时性能更好，但结果或多或少相似，或者在某些情况下更差。

我做错了什么？

Answer 1

首先，由于并行性，您不能使用 godbolt 来演示加速（或减速）。上次我检查时，该服务为每个程序分配了一个硬件线程。

其次，默认情况下 gcc 不进行任何并行化。那里有两个并行后端，默认情况下使用的那个被称为“串行后端”。进行真正并行化的称为“TBB 后端”，您需要安装英特尔 TBB 库才能使用它。

最后但同样重要的是，“并行快速排序”的这种特殊实现一点也不好。它只尝试并行运行 std::partition，如果有的话，这不会做太多。真正的并行快速排序运行 对快速排序 的两次递归调用是并行的，当然它不会创建超过硬件支持的线程，因为它只是纯粹的开销零增益。

我能够快速而肮脏地调整您的代码，使并行版本实际上更快。这涉及到类似

  static std::atomic<int> tc = 1;

  if (!std::is_same_v<ExPo,std::execution::parallel_policy> || last-first<32 || tc >= 8)
  {
      const auto& [mid1, mid2] = parition_points(std::execution::seq, first, last, std::ref(comp), std::ref(proj));
      quicksort(std::execution::seq, first, mid1, std::ref(comp), std::ref(proj));
      quicksort(std::execution::seq, mid2,  last, std::ref(comp), std::ref(proj));
  }
  else
  {
      ++tc;
      const auto& [mid1, mid2] = parition_points(policy, first, last, std::ref(comp), std::ref(proj));
      auto fut = std::async(std::launch::async, [&](){quicksort(policy, first, mid1, std::ref(comp), std::ref(proj));});
      quicksort(policy, mid2,  last, std::ref(comp), std::ref(proj));
      fut.wait();
      --tc;
  }

性能仍然很糟糕，但可以证明并行性带来的一些好处。

并行与顺序朴素快速排序

Parallel vs Sequential naïve quick sort

c++

quicksort

c++20