如何用OpenMP创建单线程实现并行快速排序？并行版为何更慢？

需求与问题 #

我正在实现并行快速排序，核心步骤为：

• 划分输入区间；
• 当前线程处理左子区间；
• 新开单个线程处理右子区间，与左子区间并行执行。

使用OpenMP实现后，并行版本的运行速度比std::sort慢约19%，但排序结果正确。以下是我的实现代码与运行输出：

问题代码 #

#include <algorithm>
#include <chrono>
#include <iostream>
#include <omp.h>

#define N 50000000

using std::swap;
using std::cout;

typedef unsigned long long data_t;

static std::chrono::milliseconds get_millis() {
    return std::chrono::duration_cast<std::chrono::milliseconds>(
    std::chrono::system_clock::now().time_since_epoch());
}

static int partition(data_t* data, int lo, int hi) {
    data_t pivot = data[lo];
    int i = lo - 1;
    int j = hi + 1;

    while (true) {
        do i++; while (data[i] < pivot);
        do j--; while (data[j] > pivot);

        if (i >= j) return j;

        data_t temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

static void sortImpl(data_t* data,
                     int lo,
                     int hi,
                     int threads) {
    if (threads <= 1 || hi - lo < 1000) {
        std::sort(data + lo, data + hi + 1);
        return;
    }

    int pivot = partition(data, lo, hi);
    int left_threads = threads / 2;
    int right_threads = threads - left_threads;

    #pragma omp parallel shared(data) num_threads(1)
    {
        sortImpl(data,
                 lo,
                 pivot,
                 left_threads);
    }

    sortImpl(data,
             pivot + 1,
             hi,
             right_threads);
}

void psort(int n, data_t *data) {
    sortImpl(data,
             0,
             n - 1,
             omp_get_max_threads());
}

static void ssort(data_t* data, int lo, int hi) {
    if (lo < hi) {
        int pivot = partition(data, lo, hi);
        ssort(data, lo, pivot);
        ssort(data, pivot + 1, hi);
    }
}

void ssort(int n, data_t* data) {
    ssort(data, 0, n - 1);
}

int main() {
    std::cout << "Starting benchmark.\n";

    data_t* arr = new data_t[N];
    data_t* arr2 = new data_t[N];

    for (int i = 0; i < N; i++) {
        arr[i] = rand();
        arr2[i] = arr[i];
    }

    auto st = get_millis();
    psort(N, arr);
    auto et = get_millis();

    std::cout << "My parallel quicksort duration: " << et - st << "\n";

    st = get_millis();
    std::sort(arr2, arr2 + N);
    et = get_millis();

    std::cout << "std::sort duration: " << et - st << "\n";

    for (int i = 0; i < N; i++) {
        if (arr[i] != arr2[i]) {
            std::cout << arr[i] << " != " << arr2[i] << " at " << i << "\n";
            break;
        }
    }

    std::cout << "Equals: " << std::boolalpha
              << std::equal(arr2, arr2 + N, arr) << "\n";

    return 0;
}

运行输出 #

Starting benchmark.
My parallel quicksort duration: 11482ms
std::sort duration: 9651ms
Equals: true

问题分析与优化方案 #

1. 错误的并行区域使用 #

原代码中用#pragma omp parallel num_threads(1)创建单线程并行区域，这不仅无法实现有效并行，还会带来不必要的线程创建/销毁开销，是性能落后的核心原因之一。

正确的做法是使用**OpenMP任务（Task）**异步调度子区间的排序任务，利用OpenMP的线程池管理线程，避免重复创建线程的开销。

2. 基准选择的性能缺陷 #

原快排直接选择区间第一个元素作为基准，在数据有序或接近有序时会触发最坏时间复杂度（O(n²)），严重影响性能。改用三数取中选择基准，能显著降低最坏情况出现的概率，提升快排本身的性能。

3. 并行粒度与线程分配策略 #

原代码手动分配线程数的方式不够灵活，且串行阈值（hi-lo <1000）过小，会导致大量小任务被调度，增加线程调度开销。需要调整阈值，平衡并行粒度与调度成本。

优化后的代码 #

核心修改部分 #

改进的partition函数（三数取中基准）

static int partition(data_t* data, int lo, int hi) {
    // 三数取中选择基准，避免最坏情况
    int mid = lo + (hi - lo) / 2;
    
    // 排序lo、mid、hi三个位置的元素，将中位数放到lo位置作为基准
    if (data[lo] > data[mid]) swap(data[lo], data[mid]);
    if (data[lo] > data[hi]) swap(data[lo], data[hi]);
    if (data[mid] > data[hi]) swap(data[mid], data[hi]);
    swap(data[mid], data[lo]);

    data_t pivot = data[lo];
    int i = lo - 1;
    int j = hi + 1;

    while (true) {
        do i++; while (data[i] < pivot);
        do j--; while (data[j] > pivot);

        if (i >= j) return j;

        swap(data[i], data[j]);
    }
}

改进的sortImpl与psort函数（OpenMP Task调度）

static void sortImpl(data_t* data, int lo, int hi) {
    // 调整串行阈值，避免过多小任务调度开销
    if (hi - lo < 10000) {
        std::sort(data + lo, data + hi + 1);
        return;
    }

    int pivot = partition(data, lo, hi);

    // 创建异步任务处理左区间，当前线程继续处理右区间
    #pragma omp task shared(data)
    sortImpl(data, lo, pivot);

    sortImpl(data, pivot + 1, hi);

    // 等待当前任务的所有子任务完成
    #pragma omp taskwait
}

void psort(int n, data_t *data) {
    // 启动并行区域，用single指令让一个线程发起递归
    #pragma omp parallel
    {
        #pragma omp single
        sortImpl(data, 0, n - 1);
    }
}

优化效果说明 #

1. Task调度：利用OpenMP线程池管理线程，避免了频繁创建销毁线程的开销，实现了真正的并行执行。
2. 三数取中基准：大幅降低快排最坏情况出现的概率，提升了排序的整体效率。
3. 调整串行阈值：减少了任务调度的频率，平衡了并行加速比与调度成本。

优化后的并行快速排序在多核环境下的性能会超过std::sort，尤其是在数据量较大时，加速比会更明显。

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