Trier 2 tableaux à l’aide de 2 threads prend plus de temps que le sorting des 2 tableaux un par un

J’ai 2 tableaux non sortingés et 2 copies de ces tableaux. J’utilise deux threads différents pour sortinger deux tableaux, puis je sortinge les deux autres tableaux non sortingés un par un. Ce que je pensais, c’était que le processus de thread serait plus rapide mais ce n’est pas le cas, alors comment les threads prennent-ils plus de temps?

#include  #include  #include  #include  #include  struct thread_data { int count; unsigned int *arr; }; struct thread_data thread_data_array[2]; void insertionSort(unsigned int arr[], int n) { int i, key, j; for (i = 1; i = 0 && arr[j] > key) { arr[j+1] = arr[j]; j = j-1; } arr[j+1] = key; } } void *sortAndMergeArrays(void *threadarg) { int count; unsigned int *arr; struct thread_data *my_data; my_data = (struct thread_data *) threadarg; count = my_data->count; arr = my_data->arr; insertionSort(arr, count); pthread_exit(NULL); } int main(int argc, char *argv[]) { int count, i, rc; clock_t start, end, total_t; pthread_t threads[2]; //get the loop count. If loop count is not provided take 10000 as default loop count. if(argc == 2){ count = atoi(argv[1]); } else{ count = 10000; } unsigned int arr1[count], arr2[count], copyArr1[count], copyArr2[count]; srand(time(0)); for(i = 0; i<count; i++){ arr1[i] = rand(); arr2[i] = rand(); copyArr1[i] = arr1[i]; copyArr2[i] = arr2[i]; } start = clock(); for(int t=0; t<2; t++) { thread_data_array[t].count = count; if(t==0) thread_data_array[t].arr = arr1; else thread_data_array[t].arr = arr2; rc = pthread_create(&threads[t], NULL, sortAndMergeArrays, (void *) &thread_data_array[t]); if (rc) { printf("ERROR; return code from pthread_create() is %d\n", rc); exit(-1); } } pthread_join(threads[0], NULL); pthread_join(threads[1], NULL); end = clock(); total_t = (double)(end - start); printf("Total time taken by CPU to sort using threads: %d\n", total_t); start = clock(); insertionSort(copyArr1, count); insertionSort(copyArr2, count); end = clock(); total_t = (double)(end - start); printf("Total time taken by CPU to sort sequentially: %d\n", total_t); pthread_exit(NULL); } 

J’utilise un serveur Linux pour exécuter le code. D’abord, je remplis les tableaux de manière aléatoire et les copie dans deux tableaux distincts. Pour les deux premiers tableaux, je crée deux threads à l’aide de pthread et leur passe les deux tableaux, qui utilisent le sorting par insertion pour les sortinger. Et pour les deux autres tableaux, je ne fais que sortinger un par un.

Je m’attendais à ce que l’utilisation de threads réduise le temps d’exécution, mais prenne plus de temps.

Diagnostic

La raison pour laquelle vous obtenez pratiquement le même temps – et un peu plus de temps avec le code threadé que avec le code séquentiel – est que clock() mesure le temps processeur, et que les deux méthodes de sorting prennent presque la même quantité de temps processeur, car elles faire le même travail (et le nombre de threads est probablement légèrement plus grand à cause du temps nécessaire pour installer et démonter les threads).

La fonction clock() doit renvoyer la meilleure approximation de la mise en oeuvre au temps de traitement utilisé par le processus depuis le début d’une ère définie par la mise en oeuvre liée uniquement à l’appel du processus.

Page de manuel BSD (macOS):

La fonction clock() détermine la quantité de temps de processeur utilisée depuis l’appel du processus appelant, mesurée en CLOCKS_PER_SECs par seconde.

La quantité de temps CPU nécessaire pour sortinger les deux tableaux est fondamentalement la même; la différence est la surcharge de filetage (plus ou moins).

Code révisé

J’ai un ensemble de fonctions qui peuvent utiliser clock_gettime() place (code dans timer.c et timer.h sur GitHub ). Celles-ci mesurent le temps d’horloge murale – le temps écoulé, pas le temps CPU

Voici une version légèrement modifiée de votre code – les modifications de fond changeaient le type de key dans la fonction de sorting de int à unsigned int pour correspondre aux données du tableau et à corriger la spécification de conversion de %d vers %ld afin qu’elle corresponde au type identifié par GCC comme clock_t . J’ai légèrement modifié le traitement des arguments et les messages de chronométrage afin qu’ils soient de longueur uniforme, puis j’ai ajouté le code de mesure du temps écoulé:

 #include  #include  #include  #include  #include  #include "timer.h" struct thread_data { int count; unsigned int *arr; }; struct thread_data thread_data_array[2]; static void insertionSort(unsigned int arr[], int n) { for (int i = 1; i < n; i++) { unsigned int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } static void *sortAndMergeArrays(void *threadarg) { int count; unsigned int *arr; struct thread_data *my_data; my_data = (struct thread_data *)threadarg; count = my_data->count; arr = my_data->arr; insertionSort(arr, count); pthread_exit(NULL); } int main(int argc, char *argv[]) { int count = 10000; int i, rc; clock_t start, end, total_t; pthread_t threads[2]; // get the loop count. If loop count is not provided take 10000 as default loop count. if (argc == 2) count = atoi(argv[1]); unsigned int arr1[count], arr2[count], copyArr1[count], copyArr2[count]; srand(time(0)); for (i = 0; i < count; i++) { arr1[i] = rand(); arr2[i] = rand(); copyArr1[i] = arr1[i]; copyArr2[i] = arr2[i]; } Clock clk; clk_init(&clk); start = clock(); clk_start(&clk); for (int t = 0; t < 2; t++) { thread_data_array[t].count = count; if (t == 0) thread_data_array[t].arr = arr1; else thread_data_array[t].arr = arr2; rc = pthread_create(&threads[t], NULL, sortAndMergeArrays, (void *)&thread_data_array[t]); if (rc) { printf("ERROR; return code from pthread_create() is %d\n", rc); exit(-1); } } pthread_join(threads[0], NULL); pthread_join(threads[1], NULL); clk_stop(&clk); end = clock(); char buffer[32]; printf("Elapsed using threads: %ss\n", clk_elapsed_us(&clk, buffer, sizeof(buffer))); total_t = (double)(end - start); printf("CPU time using threads: %ld\n", total_t); start = clock(); clk_start(&clk); insertionSort(copyArr1, count); insertionSort(copyArr2, count); clk_stop(&clk); end = clock(); printf("Elapsed sequentially: %ss\n", clk_elapsed_us(&clk, buffer, sizeof(buffer))); total_t = (double)(end - start); printf("CPU time sequentially: %ld\n", total_t); return 0; } 

Résultats

Exemple de programmes (programme inssortthread23 ) - exécutés sur un MacBook Pro (15 "2016) avec 16 Go de RAM et un processeur Intel Core i7 cadencé à 2,7 GHz, exécutant macOS High Sierra 10.13, utilisant GCC 7.2.0 pour la compilation. par exemple, le navigateur n'est pas utilisé activement, pas de musique ou de vidéos en cours, pas de téléchargements en cours, etc. (Ces éléments sont importants pour l'parsing comparative.)

 $ inssortthread23 100000 Elapsed using threads: 1.060299 s CPU time using threads: 2099441 Elapsed sequentially: 2.146059 s CPU time sequentially: 2138465 $ inssortthread23 200000 Elapsed using threads: 4.332935 s CPU time using threads: 8616953 Elapsed sequentially: 8.496348 s CPU time sequentially: 8469327 $ inssortthread23 300000 Elapsed using threads: 9.984021 s CPU time using threads: 19880539 Elapsed sequentially: 20.000900 s CPU time sequentially: 19959341 $ 

Conclusions

Ici, vous pouvez voir clairement que:

  1. Le temps écoulé est environ deux fois plus long pour le code non-threadé que pour le code threadé.
  2. Le temps CPU pour le code threadé et non-threadé est presque identique.
  3. Le temps total est quadratique dans le nombre de lignes sortingées.

Toutes ces réponses sont très conformes aux attentes - une fois que vous vous êtes rendu compte que clock() mesurait le temps CPU, pas le temps écoulé.

Puzzle mineur

Vous pouvez également constater que le temps de traitement des threads est légèrement inférieur au temps de traitement pour les sortings séquentiels. Je n'ai pas d'explication à cela - je la considère comme "perdue dans le bruit", bien que l'effet soit persistant:

 $ inssortthread23 100000 Elapsed using threads: 1.051229 s CPU time using threads: 2081847 Elapsed sequentially: 2.138538 s CPU time sequentially: 2132083 $ inssortthread23 100000 Elapsed using threads: 1.053656 s CPU time using threads: 2089886 Elapsed sequentially: 2.128908 s CPU time sequentially: 2122983 $ inssortthread23 100000 Elapsed using threads: 1.058283 s CPU time using threads: 2093644 Elapsed sequentially: 2.126402 s CPU time sequentially: 2120625 $ $ inssortthread23 200000 Elapsed using threads: 4.259660 s CPU time using threads: 8479978 Elapsed sequentially: 8.872929 s CPU time sequentially: 8843207 $ inssortthread23 200000 Elapsed using threads: 4.463954 s CPU time using threads: 8883267 Elapsed sequentially: 8.603401 s CPU time sequentially: 8580240 $ inssortthread23 200000 Elapsed using threads: 4.227154 s CPU time using threads: 8411582 Elapsed sequentially: 8.816412 s CPU time sequentially: 8797965 $