C语言 为什么我的线程合并排序比基本递归合并排序慢?

Question

我是一名学生，我需要使用线程实现MergeSort。当我测试程序时，与递归排序相比，使用线程排序需要相同或更多的时间。

我们得到了带有基本 MergeSort 的预制文件，我不允许更改 merge(( 或 mergesort(( 功能，但我需要实现 submergeSortThreads((。 我正在用信号量计算线程(用户决定在排序过程中将创建多少线程(，没有信号量数组无法正确排序，因为我认为竞争条件......

我正在运行该程序并从文件中读取数字，使用以下命令：

$ time cat rand_stevila.bin | ./mergeSort 10000

线程运行(n == 允许的最大线程数(：

$ time cat rand_stevila.bin | ./mergeSort 10000 -t -n 5

以下是代码的一些部分，它们对问题很重要：

sem_t *sem_c;
int *polje;
unsigned int max_paralelizacij = 1000;
struct{
int *array;
int min;
int max;
void(*function)(int *, int, int, int, int);
}typedef 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);
return 0;
}

// simple recursive sort
void submergeSortSimple(int* array, int min1, int max1, int min2, int max2){
mergeSort(array, min1, max1, submergeSortSimple);
mergeSort(array, min2, max2, submergeSortSimple);
}
//function that swaps submergeSortSimple(), while sorting with threads
void submergeSortThread(int* array, int min1, int max1, int min2, int max2){
if(sem_trywait(sem_c)==-1){ //if there is already max_threads, program continues with simple sorting
mergeSort(array, min1, max1, submergeSortSimple);
mergeSort(array, min2, max2, submergeSortSimple);
return;
}
thread_args arg1;
arg1.array = array;
arg1.min = min1;
arg1.max = max1;
arg1.function = submergeSortThread;
pthread_t tid1;
pthread_create(&tid1, 0, &thread_fun, &arg1);
if(sem_trywait(sem_c)==-1){
pthread_join(tid1,NULL);
mergeSort(array, min2, max2, submergeSortSimple);
return;
}
pthread_t tid2;
thread_args arg2;
arg2.array = array;
arg2.min = min2;
arg2.max = max2;
arg2.function = submergeSortThread;
pthread_create(&tid2, 0, &thread_fun, &arg2);
pthread_join(tid1,NULL);
pthread_join(tid2,NULL);
return;            
}

// must not be changed
void mergeSort(int *array, int min, int max, void(*submergeSort)(int *, int, int, int, int) ){
int mid;
if(min < max){
mid=(min+max)/2;
submergeSort(array, min, mid, mid+1, max);
merge(array, min, mid, max);
}
}
// must not be changed
void merge(int *arr, int min,int mid,int max)
{
// drugi korak algoritma mergeSort
int *tmp = malloc((max-min+1)*sizeof(int));
int i,j,k,m;
j=min;
m=mid+1;
for(i=min; j<=mid && m<=max ; i++)
{
if(arr[j]<=arr[m])
{
tmp[i-min]=arr[j];
j++;
}        
else
{
tmp[i-min]=arr[m];
m++;
}
}
if(j>mid)
{
for(k=m; k<=max; k++)
{
tmp[i-min]=arr[k];
i++;
}
}
else
{
for(k=j; k<=mid; k++)
{
tmp[i-min]=arr[k];
i++;
}
}
for(k=min; k<=max; k++){
arr[k]=tmp[k-min];
}
free(tmp);
}
int main(int argc, char *argv[])
{
#define NO_PAR 0 
#define THREAD_PAR 2
int technique= NO_PAR;
void (*submergeSortFun)(int *, int, int, int, int);
submergeSortFun = submergeSortSimple;
while(1){
int c;
c = getopt(argc, argv, "ptn:");
if(c==-1){
break;
}
switch(c){
case 't':
technique = THREAD_PAR;
submergeSortFun = submergeSortThread;
break;
case 'n':
max_paralelizacij = atoi(optarg);                  
break;
default:
printHelp(argc, argv);
return 0;
}
}
if(technique == THREAD_PAR){
sem_unlink("/C");
sem_c = sem_open("/C", O_RDWR|O_CREAT|O_EXCL, 0660, max_paralelizacij);
if(sem_c == SEM_FAILED){
perror("Napaka pri ustvarjanju semaforja!n");
}
}
int i;
int size;
int *arr;
if(optind >= argc){
printHelp(argc, argv);
return -1;
}
size = atoi(argv[optind]);

// TODO: inicializacija za razlicne tehnike 
switch(technique){
case NO_PAR:
arr = malloc(sizeof(int)*size);
break;
case THREAD_PAR:
arr = malloc(sizeof(int)*size);
break;
}
char buffer[101];
// reading numbers from file
for(i=0; i < size; i+=1){
read(0, &arr[i], 4);
}
//measure time and sorting
clock_t start = clock();
mergeSort(arr, 0, size-1, submergeSortFun);
clock_t end = clock();
float seconds = (float)(end - start) / CLOCKS_PER_SEC;

for(i=0; i<size; i++){
printf("%d ",arr[i]);
}
printf("n");

// TODO: ciscenje za razlicnimi tehnikami
switch(technique){
case NO_PAR:
free(arr);
sem_close(sem_c);
break;
case THREAD_PAR:
free(arr);
sem_close(sem_c);
break;
}
printf("nn CAS : %fnn",seconds);
return 0;
}

Answer 1

让我们观察创建线程与递归调用函数的成本。

创建线程时，将为该线程创建并初始化单独的调用堆栈和程序计数器。

调用函数时，它会添加到当前调用堆栈的顶部。它是单个调用的单个条目。不需要单独的程序计数器。

显然，创建线程的开销远远超过调用函数。因此，尽管两种实现的运行时间顺序相同，但由于创建线程的开销很大，线程化通常较慢。使用线程的合理情况是划分大型工作负载，然后为较小的数组运行递归案例，以防止调用堆栈大小爆炸式增长。