为何基于线程的归并排序比基础递归归并排序更慢？

作为同行，我来帮你梳理下线程版归并排序没达到预期性能的核心问题，以及对应的优化方案：

核心问题梳理 #

你的线程版代码之所以性能没提升甚至更慢，主要是这几个关键问题导致的：

• 信号量未正确释放：只获取信号量但没在任务完成后释放，很快就会耗尽信号量，后续任务只能退回到递归版，还平白承担了线程创建的开销
• 线程参数传递有风险：传递栈上的局部变量给线程，线程还没读取参数，当前函数就可能返回，导致参数被覆盖，引发排序错误或额外损耗
• 线程创建粒度太细：小数组排序的收益远抵不上线程创建/切换的开销，反而拖慢整体速度
• 时间测量方式有误：clock()统计的是所有线程的总CPU时间，不是实际流逝的墙上时间，线程版总CPU时间必然比单线程高，但实际耗时应该更短

改进后的关键代码实现 #

下面是修正后的核心代码，我会标注每个修改点的作用：

1. 调整线程参数结构体与线程函数 #

新增信号量传递，确保线程完成后释放信号量，同时改用堆分配参数避免栈变量覆盖：

typedef struct{
    int *array;
    int min;
    int max;
    void(*function)(int *, int, int, int, int);
    sem_t *sem; // 新增：传递信号量指针，用于线程完成后释放
} thread_args;

void* thread_fun(void* args){
    thread_args *thr_arg = (thread_args*)args;
    mergeSort(thr_arg->array, thr_arg->min, thr_arg->max, thr_arg->function);
    sem_post(thr_arg->sem); // 线程完成排序后释放信号量
    free(args); // 释放堆上的参数内存
    return NULL;
}

2. 优化submergeSortThread函数 #

添加数组大小阈值控制线程创建粒度，修正信号量使用逻辑：

// 新增：根据硬件环境调整这个阈值，子数组小于该值时用递归
#define MIN_THREAD_SIZE 1000

void submergeSortThread(int* array, int min1, int max1, int min2, int max2){
    int size1 = max1 - min1 + 1;
    int size2 = max2 - min2 + 1;

    // 子数组太小，直接用递归，避免线程开销
    if(size1 < MIN_THREAD_SIZE || size2 < MIN_THREAD_SIZE){
        mergeSort(array, min1, max1, submergeSortSimple);
        mergeSort(array, min2, max2, submergeSortSimple);
        return;
    }

    // 处理第一个子数组：尝试获取信号量并创建线程
    pthread_t tid1 = 0;
    int got_sem1 = 0;
    if(sem_wait(sem_c) == 0){ // 用sem_wait替代sem_trywait，确保获取到信号量再创建线程
        got_sem1 = 1;
        thread_args *arg1 = malloc(sizeof(thread_args));
        arg1->array = array;
        arg1->min = min1;
        arg1->max = max1;
        arg1->function = submergeSortThread;
        arg1->sem = sem_c;
        pthread_create(&tid1, NULL, thread_fun, arg1);
    } else {
        mergeSort(array, min1, max1, submergeSortSimple);
    }

    // 处理第二个子数组
    pthread_t tid2 = 0;
    int got_sem2 = 0;
    if(sem_wait(sem_c) == 0){
        got_sem2 = 1;
        thread_args *arg2 = malloc(sizeof(thread_args));
        arg2->array = array;
        arg2->min = min2;
        arg2->max = max2;
        arg2->function = submergeSortThread;
        arg2->sem = sem_c;
        pthread_create(&tid2, NULL, thread_fun, arg2);
    } else {
        mergeSort(array, min2, max2, submergeSortSimple);
    }

    // 等待已创建的线程完成
    if(got_sem1) pthread_join(tid1, NULL);
    if(got_sem2) pthread_join(tid2, NULL);
}

3. 修正主函数的时间测量与资源清理 #

改用墙上时间测量，完善信号量清理逻辑：

int main(int argc, char *argv[]) {
    // ... 其他原有代码保持不变 ...

    // 计时并排序：用CLOCK_MONOTONIC测量实际流逝的墙上时间
    struct timespec start, end;
    clock_gettime(CLOCK_MONOTONIC, &start);
    mergeSort(arr, 0, size-1, submergeSortFun);
    clock_gettime(CLOCK_MONOTONIC, &end);
    double seconds = (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1e9;

    // ... 输出排序结果 ...

    // 资源清理：修正单线程分支的错误，完善线程版信号量清理
    switch(technique){
        case NO_PAR:
            free(arr);
            break; // 单线程时sem_c未初始化，不需要close
        case THREAD_PAR:
            free(arr);
            sem_close(sem_c);
            sem_unlink("/C"); // 删除命名信号量，避免残留资源
            break;
    }

    printf("\n\n CAS : %lf\n\n", seconds);
    return 0;
}

优化效果说明 #

1. 信号量循环利用：线程完成后释放信号量，保证最大线程数的限制有效，真正发挥并行优势
2. 避免参数覆盖问题：堆分配线程参数，确保线程能安全读取任务信息
3. 平衡线程开销与收益：只对足够大的子数组创建线程，避免小任务的线程开销浪费
4. 准确测量性能：墙上时间能真实反映多线程带来的速度提升，不会被总CPU时间误导

你可以根据自己的硬件配置调整MIN_THREAD_SIZE的值，找到最适合的线程创建粒度，这样线程版归并排序在大数据量下应该能明显快于递归版。

内容的提问来源于stack exchange，提问作者Aljaž Gornik