使用OpenMP实现并行快速排序性能变慢的问题排查

问题描述 #

我在快速排序中用OpenMP实现了并行部分，核心代码如下：

void quicksort_recursion(int array[], int low, int high) {
if (low < high) {
    int pivot_index = partition(array, low, high);

#pragma omp parallel sections num_threads(2)
    {
#pragma omp section
            {
            quicksort_recursion(array, low, pivot_index - 1);
            }

#pragma omp section
            {
            quicksort_recursion(array, pivot_index + 1, high);
            }
       }
    }
}

但开启OpenMP后，运行速度比串行版本慢3倍（串行耗时0.6秒，并行耗时2.18秒），调整线程数也无明显效果，编译命令为gcc -o openmp01 -fopenmp example.c。

一、性能暴跌的核心原因 #

• 线程重复创建的开销远超并行收益：每一层递归都通过#pragma omp parallel sections创建新线程组，而50万元素的递归深度可达20层左右，频繁的线程创建、销毁和资源分配开销，直接抵消甚至超过并行计算的收益。
• 负载严重不均衡：快速排序的两个子数组长度依赖pivot选择，即便用了随机pivot，仍可能出现一子数组极大、一子数组极小的情况，导致两个线程工作量差距悬殊，其中一个线程早早闲置，并行效率极低。
• 计时方式错误：使用clock()统计的是所有线程的CPU时间总和，而非实际的墙钟时间。并行版本的CPU总时间本就会高于串行，你看到的2.18秒并非真实运行耗时，而是多线程的CPU时间累加。
• 递归过深导致线程爆炸：每一层递归创建2个线程，递归到第N层时线程数会达到2^N，远超CPU核心数，操作系统需频繁切换线程，上下文切换开销急剧增加。

二、针对性解决办法 #

1. 顶层创建线程池，用task拆分任务 #

不在每一层递归创建新并行区域，而是在顶层初始化一次线程池，后续递归用#pragma omp task拆分任务，实现线程复用：

void quicksort_recursion(int array[], int low, int high) {
    if (low < high) {
        int pivot_index = partition(array, low, high);

        #pragma omp task
        quicksort_recursion(array, low, pivot_index - 1);

        #pragma omp task
        quicksort_recursion(array, pivot_index + 1, high);
    }
}

// 顶层调用时创建并行区域
void quicksort(int array[], int length)
{
    srand(time(NULL));
    #pragma omp parallel
    {
        #pragma omp single
        quicksort_recursion(array, 0, length-1);
    }
}

2. 设置递归阈值，小数组用串行排序 #

当子数组长度小于阈值（比如1000）时，并行开销大于收益，直接用串行插入排序处理：

#define THRESHOLD 1000

void quicksort_recursion(int array[], int low, int high) {
    if (high - low < THRESHOLD) {
        // 小数组串行插入排序
        for (int i = low + 1; i <= high; i++) {
            int temp = array[i];
            int j = i - 1;
            while (j >= low && array[j] > temp) {
                array[j+1] = array[j];
                j--;
            }
            array[j+1] = temp;
        }
        return;
    }
    if (low < high) {
        int pivot_index = partition(array, low, high);

        #pragma omp task
        quicksort_recursion(array, low, pivot_index - 1);

        #pragma omp task
        quicksort_recursion(array, pivot_index + 1, high);
    }
}

3. 修正计时方式，统计墙钟时间 #

改用omp_get_wtime()统计真实运行时间，避免CPU总时间的误导：

int main() {
    int a[SIZE];
    generateList(a, SIZE);
    int length = SIZE;
    double begin = omp_get_wtime(); // 替换clock()
    quicksort(a, length);

    double end = omp_get_wtime();
    double time_spent = end - begin;

    printf("\n");
    printf("Tiempo: %f", time_spent);
    return 0;
}

4. 修复partition函数的冗余代码 #

partition函数中if (pivot_index != high);多了一个分号，会导致无意义的swap操作，去掉分号即可：

int partition(int array[], int low, int high)
{
    int pivot_index = low + (rand() % (high - low)); 
    if (pivot_index != high) // 去掉后面的分号
        swap(&array[pivot_index], &array[high]);
    int pivot_value = array[high];
    int i = low;
    for (int j = low; j < high; j++)
    {
        if (array[j] <= pivot_value)
        {
            swap(&array[i], &array[j]);
            i++;
        }
    }
    swap(&array[i], &array[high]);
    return i;
}

三、优化后的完整代码 #

//
// Created by XPC on 1/12/2023.
//

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <omp.h>

#define SIZE 500000
#define THRESHOLD 1000

int generateList(int list[], int size);
void swap(int *x, int *y);
void quicksort(int array[], int length);
void quicksort_recursion(int array[], int low, int high);
int partition(int array[], int low, int high);

int generateList(int list[], int size) {
    srand(time(NULL));
    for (int i = 0; i < size; i++) {
        list[i] = rand() % 1000;
    }
}

int main() {
    int a[SIZE];
    generateList(a, SIZE);
    int length = SIZE;
    double begin = omp_get_wtime();
    quicksort(a, length);

    double end = omp_get_wtime();
    double time_spent = end - begin;

    printf("\n");
    printf("Tiempo: %f", time_spent);

    return 0;
}

void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

void quicksort(int array[], int length) {
    srand(time(NULL));
    #pragma omp parallel
    {
        #pragma omp single
        quicksort_recursion(array, 0, length-1);
    }
}

void quicksort_recursion(int array[], int low, int high) {
    if (high - low < THRESHOLD) {
        // 小数组串行插入排序
        for (int i = low + 1; i <= high; i++) {
            int temp = array[i];
            int j = i - 1;
            while (j >= low && array[j] > temp) {
                array[j+1] = array[j];
                j--;
            }
            array[j+1] = temp;
        }
        return;
    }
    if (low < high) {
        int pivot_index = partition(array, low, high);

        #pragma omp task
        quicksort_recursion(array, low, pivot_index - 1);

        #pragma omp task
        quicksort_recursion(array, pivot_index + 1, high);
    }
}

int partition(int array[], int low, int high) {
    int pivot_index = low + (rand() % (high - low));
    if (pivot_index != high)
        swap(&array[pivot_index], &array[high]);
    int pivot_value = array[high];
    int i = low;
    for (int j = low; j < high; j++) {
        if (array[j] <= pivot_value) {
            swap(&array[i], &array[j]);
            i++;
        }
    }
    swap(&array[i], &array[high]);
    return i;
}

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