c - 为什么我的合并排序使用线程比不使用线程慢?
问题描述
我是一名学生,我需要使用线程和 fork() 在 C 中实现 Mergesort 程序。没有并行化的实施是由学校助理预先完成的。到目前为止,我实现了线程并行化,但该程序比没有线程运行它要慢得多......
我正在从预制文件中读取数字并测量时间:
$ time cat rand_stevila.bin | ./mergeSort 10000
当我用我运行的线程订购时:
$ time cat rand_stevila.bin | ./mergeSort 10000 -t
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <fcntl.h>
#include <pthread.h>
#include <unistd.h>
#include <wait.h>
void printHelp(int argc, char **argv);
void submergeSortSimple(int *array, int min1, int max1, int min2, int max2);
void submergeSortProc(int *array, int min1, int max1, int min2, int max2);
void submergeSortThread(int *array, int min1, int max1, int min2, int max2);
void mergeSort(int *array, int min, int max, void(*submergeSort)(int *, int, int, int, int));
void merge(int *arr,int min,int mid,int max);
int max_paralelizacij;
pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
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;
}
// preprosta implementacija mergeSort rekurzije,
// samo klicemo margeSort za levo in desno polovico
// v istem procesu/isti niti
void submergeSortSimple(int *array, int min1, int max1, int min2, int max2) {
mergeSort(array, min1, max1, submergeSortSimple);
mergeSort(array, min2, max2, submergeSortSimple);
}
// TODO: funkcija ki paralelizira sortiranje z uporabo procesov
// za preprosto paralelizacijo samo izvedemo vsak klic mergeSort
// funkcije v svojem procesu, in počakamo, da se klica zaključita
void submergeSortProc(int *array, int min1, int max1, int min2, int max2) {
printf("implementacija submergeSortProc manjka\n");
return;
}
// TODO: funkcija, ki paralelizira sortiranje z uporabo niti
// za preprosto paralelizacijo samo izvedemo vsak klic mergeSort
// funkcije v svoji niti, in počakamo, da se klica zaključita
void submergeSortThread(int *array, int min1, int max1, int min2, int max2) {
pthread_t tid1, tid2;
thread_args arg1,arg2;
arg1.array = array;
arg1.min = min1;
arg1.max = max1;
arg1.function = submergeSortThread;
arg2.array = array;
arg2.min = min2;
arg2.max = max2;
arg2.function = submergeSortThread;
pthread_create(&tid1, 0, &thread_fun, &arg1);
pthread_join(tid1, NULL);
pthread_create(&tid2, 0, &thread_fun, &arg2);
pthread_join(tid2, NULL);
return;
}
// mergeSort in merge funkciji
// ti dve izvajata dejansko sortiranje
// void mergeSort(int *array, int min, int max, void(*submergeSort)(int *, int, int, int, int))
//
// int *array
// kazalec na tabelo števil, ki jih urejamo
//
// int min, int max
// indeks prvega in zadnjega števila v tabeli,
// označujeta interval, ki ga sortiramo
//
// void (*submergeSort)(int *array, int min1, int max1, int min2, int max2)
// kazalec na funkcijo, ki naj kliče mergeSort za dva podintervala
// in vrne, ko sta oba intervala sortirana
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);
}
}
// void merge(int *arr, int min,int mid,int max)
//
// int *arr
// kazalec na tabelo
//
// int min, int mid, int max
// indeksi na del tabele, ki jih je potrebno združiti
// min je začetni indeks prve podtabele, mid je zadnji indeks
// prve podtabele in max je zadnji indeks druge podtabele
//
// metoda zdruzi dve sosednji sortirani podtabeli,
// tako da je nova podtabela tudi sortirana
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++) {
pthread_mutex_lock(&mtx);
if (arr[j] <= arr[m]) {
tmp[i - min] = arr[j];
j++;
} else {
tmp[i - min] = arr[m];
m++;
}
pthread_mutex_unlock(&mtx);
}
if (j > mid) {
for (k = m; k <= max; k++) {
pthread_mutex_lock(&mtx);
tmp[i - min] = arr[k];
pthread_mutex_unlock(&mtx);
i++;
}
} else {
for (k = j; k <= mid; k++) {
pthread_mutex_lock(&mtx);
tmp[i - min] = arr[k];
pthread_mutex_unlock(&mtx);
i++;
}
}
for (k = min; k <= max; k++) {
pthread_mutex_lock(&mtx);
arr[k] = tmp[k - min];
pthread_mutex_unlock(&mtx);
}
free(tmp);
}
int main(int argc, char *argv[]) {
#define NO_PAR 0
#define PROC_PAR 1
#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:");
//printf("while\n");
if (c == -1) {
break;
}
switch (c) {
case 'p':
technique = PROC_PAR;
submergeSortFun = submergeSortProc;
break;
case 't':
technique = THREAD_PAR;
submergeSortFun = submergeSortThread;
//printf("HALOOOOOO\n");
break;
case 'n':
//printf("Vrednost: %s\n",optarg);
max_paralelizacij = atoi(optarg);
//printf("Max par: %d\n",max_paralelizacij);
break;
default:
//printf("more printat\n");
printHelp(argc, argv);
return 0;
}
}
//printf("\nHIER\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 PROC_PAR:
// inicializacija za uporabo procesov
// ustvariti je potrebno deljen pomnilnik, semafor, ...
dprintf(2, "not implemented\n");
exit(-1);
break;
case THREAD_PAR:
//printf("\ntechnique\n");
arr = malloc(sizeof(int)*size);
// inicializacija za uporabo procesov
// tukaj potrebujete morebitne sinhronizacijske strukture
//dprintf(2, "not implemented\n");
//exit(-1);
break;
}
char buffer[101];
for (i = 0; i < size; i += 1) {
//printf("ines erbus\n");
// preberi binarne vrednosti
read(0, &arr[i], 4);
}
for (i = 0; i < size; i++) {
//printf("Serbus ines\n");
printf("%d ",arr[i]);
}
printf("\n\n\n\nKonec Filanja\n\n\n\n");
//printf("test\n");
mergeSort(arr, 0, size - 1, submergeSortFun);
for (i = 0; i < size; i++) {
printf("%d ",arr[i]);
}
printf("\n");
// TODO: ciscenje za razlicnimi tehnikami
switch (technique) {
case NO_PAR:
free(arr);
break;
case PROC_PAR:
dprintf(2, "not implemented\n");
exit(-1);
break;
case THREAD_PAR:
dprintf(2, "not implemented\n");
exit(-1);
break;
}
return 0;
}
void printHelp(int argc, char **argv) {
printf("uporaba\n");
printf("%s <opcija> <n>\n", argv[0]);
printf("\tn je število celih števil prebranih z standardnega vhoda\n");
printf("\tfunkcije prebere n*4 bajtov v tabelo in jih sortira\n");
printf("opcije:\n");
printf("-p\n");
printf("\tparalelizacija s pomočjo procesov\n");
printf("-t\n");
printf("\tparalelizacija s pomočjo niti\n");
}
解决方案
您创建了多个线程,但不要让它们并行运行:您应该更改submergeSortThread
为对线程创建进行分组并将等待移至最后:
pthread_create(&tid1, 0, &thread_fun, &arg1);
pthread_create(&tid2, 0, &thread_fun, &arg2);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
如果您为非常小的任务创建线程,程序可能仍然会更慢,在并行执行的好处面前,线程创建的开销变得很大。创建比系统中的内核更多的线程也应该几乎没有收益,因为只有这么多线程可以并行执行(在最好的情况下)。
最后,您应该尝试通过确保不同的线程不会同时访问相同的数据来避免使用互斥锁。这些pthread_mutex_lock(&mtx);
/pthread_mutex_unlock(&mtx);
对的开销很大。
推荐阅读
- python - 我面临语音识别中的错误
- r - 匹配字符串正则表达式完全匹配
- flutter - Flutter中最小化SliverAppBar时有没有办法看到内容?
- typescript - 如何在 TypeScript 中推断泛型的子类型?
- node.js - 将图像从 React Native 上传到 Apollo Server 不起作用?
- php - 带有ansi2html问题的PHP exec输出文本
- json - 如何在 Laravel 中返回视图并返回 json 响应?
- c# - Kafka - 序列化 JSON 时的消费者速度
- python - set_weights 函数张量流的问题
- statistics - 你如何找到翻转不公平硬币的样本空间?