并行与串行朴素快速排序性能不及预期的原因咨询

// 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;
}

• 缺少小粒度任务的串行降级逻辑
  并行算法的线程调度、任务拆分、同步都有固定开销，当待排序区间长度较小时（通常小于1024~4096个元素），并行带来的收益完全覆盖不了开销。上述实现对所有长度的区间都调用并行std::partition，递归到小区间时会产生大量无效的调度开销，反而比串行慢。
• 重复遍历区间带来的额外开销
  为了实现三路分区，代码对同一区间调用了两次std::partition，相当于全量遍历了两次待排序区间，不仅浪费了内存带宽，还降低了缓存命中率。可以改为单次遍历直接划分出小于、等于、大于pivot的三个区间，减少一半的遍历开销。
• 基准值选择逻辑不合理
  直接选取区间中间位置的元素作为pivot，当遇到有序、近乎有序、重复元素多的场景时，很容易出现分区极度不均衡的情况，最坏情况下时间复杂度会退化到O(n²)，这种情况下并行也无法提升性能。建议改为三数取中、随机选pivot的策略降低最坏情况的概率。
• 子任务没有并行执行
  当前实现仅在分区步骤用了并行逻辑，但左右两个子区间的排序是串行执行的，两个完全独立的子任务没有利用到并行能力。可以在区间长度足够大时，用异步任务并行执行两个子区间的排序，进一步提升并行度。
• 测试场景的局限性
  10万元素的测试规模偏小，并行收益还不足以覆盖调度开销，建议测试百万级以上的数据量才能观测到明显的并行优势。同时测试时要注意避免缓存预热带来的结果偏差，最好打乱测试顺序、多次运行取平均值。
• 标准库并行算法的实现依赖
  C标准库的并行执行策略通常依赖底层的并行运行时（比如GCC的libstdc依赖TBB），如果编译时没有链接对应的运行时、或者运行时的调度策略适配不好，也会导致并行算法性能不及预期。

• 增加阈值判断：当待排序区间长度小于设定阈值（可根据硬件环境调整为2048或4096）时，直接调用串行std::sort完成排序，不再继续递归和调用并行分区。
• 替换为单趟三路分区逻辑，减少区间遍历次数。
• 优化pivot选择策略，使用三数取中或随机pivot避免分区退化。
• 大区间的两个子排序任务用异步并行执行，小区间直接串行执行。

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