c - 用于性能测量的多线程合并排序

Question

我试图比较使用单线程和多线程程序的合并排序的性能差异。使用单个线程对大小约为 50000 的数组进行排序需要 0.01 秒，而对于相同大小的数组，使用 2/4/8 线程需要 0.02-0.03 秒。我知道，差别不大，但我只是想知道多线程程序速度减慢的原因是什么？下面是单线程程序的代码(main函数的代码):

 srand(clock());            //to seed-random numbers
 readData(A,n);
 clock_t start=clock();
 mergeSort(A,0,n-1);
 clock_t end=clock();

并且，对于多线程程序:

int n=50000;        //n is the size
int no_of_threads=4;
limit S;              //structure containing array,start and end index
srand(clock());         //to seed-random numbers
generateData(&S,n);
pthread_t id[no_of_threads];
int i=0,size=0,k=n/no_of_threads;
clock_t start=clock();
for(i=0; i<no_of_threads; i++)
{
        S.start=size,S.end=size+k-1;
        pthread_create(&id[i],NULL, sorter ,&S);
        size=size + k;
}
for(i=0; i<no_of_threads; i++)
        pthread_join(id[i],NULL);
mergeSort(S.A,0,n-1);
clock_t end=clock();

排序功能:

void* sorter(void *s)
{
    limit *S=(limit*)s;
    int start=S->start,end=S->end;
    mergeSort(S->A,start,end);
}

Answer 1

你不是在分工，而是在做额外的工作。在每个线程中，当线程数为 x 时，您正在对数组的 1/x 进行排序。所有线程完成后，您再次对整个数组调用合并排序，这将递归地将数组分区直到底部并合并，忽略子部分已经排序的事实。

解决这个问题的一种方法是，您只需合并已排序的子部分，而不是再次调用 mergeSort() 函数，这可以在 O(nx)< 中完成 时间。