Multithread Mergesort langsamer als Singlethread Heapsort?

    • Multithread Mergesort langsamer als Singlethread Heapsort?

      Neu

      Ich gruesse euch liebe Community,
      Ich habe aktuell folgendes probiert:

      Habe mir einen Multithreadtauglichen Mergesort Algorithmus gebaut, und einen normalen Heapsort Algorithmus.
      Das Problem ist nun folgendes:

      Ich erstelle bei beiden ein Random Array mit einer Groesse von z.B. 10000.
      Ab dem Zeitpunkt wird die Zeit vom Sortiervorgang gemessen, sowohl bei Mergesort als auch Heapsort.
      Sind beides unabhaengige ausfuehrbare Dateien.

      Das Problem ist: Mergesort braucht trotz Multicore Optimierung 4 mal solange wie mein Heapsort Algorithmus.
      Woran kann das liegen?

      Einmal Mergesort

      C-Quellcode

      1. #include <pthread.h>
      2. #include <stdio.h>
      3. #include <stdlib.h>
      4. #include <time.h>
      5. #define MIN_LENGTH 4
      6. int DEBUG;
      7. typedef struct
      8. {
      9. int *array;
      10. int left;
      11. int right;
      12. int tid;
      13. } thread_data_t;
      14. int number_of_threads;
      15. pthread_mutex_t lock_number_of_threads;
      16. int my_comp(const void *larg, const void *rarg)
      17. {
      18. int l = *(int *)larg;
      19. int r = *(int *)rarg;
      20. if (l < r)
      21. {
      22. return -1;
      23. }
      24. else if (l == r)
      25. {
      26. return 0;
      27. }
      28. return 1;
      29. }
      30. void merge(int *data, int left, int right, int tid)
      31. {
      32. if (DEBUG)
      33. {
      34. printf("[%d] Merging %d to %d\n", tid, left, right);
      35. }
      36. int ctr = 0;
      37. int i = left;
      38. int mid = left + ((right - left) / 2);
      39. int j = mid + 1;
      40. int *c = (int *) malloc((right - left + 1) * sizeof(int));
      41. while (i <= mid && j <= right)
      42. {
      43. if (data[i] <= data[j])
      44. {
      45. c[ctr++] = data[i++];
      46. }
      47. else
      48. {
      49. c[ctr++] = data[j++];
      50. }
      51. }
      52. if (i == mid + 1)
      53. {
      54. while (j <= right)
      55. {
      56. c[ctr++] = data[j++];
      57. }
      58. }
      59. else
      60. {
      61. while (i <= mid)
      62. {
      63. c[ctr++] = data[i++];
      64. }
      65. }
      66. i = left;
      67. ctr = 0;
      68. while (i <= right)
      69. {
      70. data[i++] = c[ctr++];
      71. }
      72. free(c);
      73. return;
      74. }
      75. void *merge_sort_threaded(void *arg)
      76. {
      77. thread_data_t *data = (thread_data_t *) arg;
      78. int l = data->left;
      79. int r = data->right;
      80. int t = data->tid;
      81. if (r - l + 1 <= MIN_LENGTH)
      82. {
      83. if (DEBUG)
      84. {
      85. printf("[%d] Calling qsort(%d, %d).\n", t, l, r);
      86. }
      87. qsort(data->array + l, r - l + 1, sizeof(int), my_comp);
      88. }
      89. else
      90. {
      91. int m = l + ((r - l) / 2);
      92. thread_data_t data_0;
      93. data_0.left = l;
      94. data_0.right = m;
      95. data_0.array = data->array;
      96. pthread_mutex_lock(&lock_number_of_threads);
      97. data_0.tid = number_of_threads++;
      98. pthread_mutex_unlock(&lock_number_of_threads);
      99. pthread_t thread0;
      100. int rc = pthread_create(&thread0,
      101. NULL,
      102. merge_sort_threaded,
      103. &data_0);
      104. int created_thread_0 = 1;
      105. if (rc)
      106. {
      107. if (DEBUG)
      108. {
      109. printf("[%d] Failed to create thread, calling qsort.", data_0.tid);
      110. }
      111. created_thread_0 = 0;
      112. qsort(data->array + l, m - l + 1, sizeof(int), my_comp);
      113. }
      114. thread_data_t data_1;
      115. data_1.left = m + 1;
      116. data_1.right = r;
      117. data_1.array = data->array;
      118. pthread_mutex_lock(&lock_number_of_threads);
      119. data_1.tid = number_of_threads++;
      120. pthread_mutex_unlock(&lock_number_of_threads);
      121. pthread_t thread1;
      122. rc = pthread_create(&thread1,
      123. NULL,
      124. merge_sort_threaded,
      125. &data_1);
      126. int created_thread_1 = 1;
      127. if (rc)
      128. {
      129. if (DEBUG)
      130. {
      131. printf("[%d] Failed to create thread, calling qsort.", data_1.tid);
      132. }
      133. created_thread_1 = 0;
      134. qsort(data->array + m + 1, r - m, sizeof(int), my_comp);
      135. }
      136. if (created_thread_0)
      137. {
      138. pthread_join(thread0, NULL);
      139. }
      140. if (created_thread_1)
      141. {
      142. pthread_join(thread1, NULL);
      143. }
      144. merge(data->array, l, r, t);
      145. }
      146. pthread_exit(NULL);
      147. return NULL;
      148. }
      149. void merge_sort(int *array, int start, int finish)
      150. {
      151. thread_data_t data;
      152. data.array = array;
      153. data.left = start;
      154. data.right = finish;
      155. number_of_threads = 0;
      156. pthread_mutex_init(&lock_number_of_threads, NULL);
      157. data.tid = 0;
      158. pthread_t thread;
      159. int rc = pthread_create(&thread,
      160. NULL,
      161. merge_sort_threaded,
      162. &data);
      163. if (rc)
      164. {
      165. if (DEBUG)
      166. {
      167. printf("[%d] Failed to create thread, calling qsort.",
      168. data.tid);
      169. }
      170. qsort(array + start,
      171. finish - start + 1,
      172. sizeof(int),
      173. my_comp);
      174. }
      175. pthread_join(thread, NULL);
      176. return;
      177. }
      178. int main()
      179. {
      180. int size=0,loop,qrand;
      181. int *array;
      182. printf("Array-Groesse eingeben: ");
      183. scanf("%d", &size);
      184. array = (int *) malloc(size * sizeof(int));
      185. if(array != NULL)
      186. {
      187. printf("\nSpeicher ist reserviert\n");
      188. printf("\nFilling array.\n");
      189. for(loop=0;loop<size;loop++)
      190. {
      191. qrand=rand() %20;
      192. array[loop]=qrand;
      193. printf("%d",qrand);
      194. }
      195. }
      196. else printf("\nKein freier Speicher vorhanden.\n");
      197. printf("\nMerge Sort..\n");
      198. clock_t t;
      199. t = clock();
      200. merge_sort(array, 0, size - 1);
      201. for(loop=0;loop<size;loop++)
      202. {
      203. printf("%d",array[loop]);
      204. }
      205. if((size * sizeof(int)) < 1000)
      206. {
      207. printf("\n %lu Bytes wurden freigegeben\n",(size * sizeof(int)));
      208. }
      209. else if((size *sizeof(int))>=1000)
      210. {
      211. printf("\n %lu Kilobytes wurden freigegeben\n",((size * sizeof(int))/1000));
      212. }
      213. else if((size * sizeof(int))>=1000*1000)
      214. {
      215. printf("\n %lu Megabytes wurden freigegeben\n", ((size * sizeof(int))/1000*1000));
      216. }
      217. free(array);
      218. pthread_mutex_destroy(&lock_number_of_threads);
      219. t = clock() - t;
      220. printf("Sorting took %f seconds to finish \n", time_taken);
      221. return 0;
      222. }
      Alles anzeigen

      Ist es eventuell falsch implementiert?

      C-Quellcode

      1. #include <stdio.h>
      2. #include <stdlib.h>
      3. #include <time.h>
      4. void quicksort(int *A, int len);
      5. int max (int *a, int n, int i, int j, int k)
      6. {
      7. int m = i;
      8. if (j < n && a[j] > a[m]) {
      9. m = j;
      10. }
      11. if (k < n && a[k] > a[m]) {
      12. m = k;
      13. }
      14. return m;
      15. }
      16. void downheap (int *a, int n, int i)
      17. {
      18. while (1) {
      19. int j = max(a, n, i, 2 * i + 1, 2 * i + 2);
      20. if (j == i) {
      21. break;
      22. }
      23. int t = a[i];
      24. a[i] = a[j];
      25. a[j] = t;
      26. i = j;
      27. }
      28. }
      29. void heapsort (int *a, int n)
      30. {
      31. int i;
      32. for (i = (n - 2) / 2; i >= 0; i--) {
      33. downheap(a, n, i);
      34. }
      35. for (i = 0; i < n; i++) {
      36. int t = a[n - i - 1];
      37. a[n - i - 1] = a[0];
      38. a[0] = t;
      39. downheap(a, n - i - 1, 0);
      40. }
      41. }
      42. void quicksort(int *A, int len)
      43. {
      44. if (len < 2) return;
      45. int pivot = A[len / 2];
      46. int i, j;
      47. for (i = 0, j = len - 1; ; i++, j--)
      48. {
      49. while (A[i] < pivot) i++;
      50. while (A[j] > pivot) j--;
      51. if (i >= j) break;
      52. int temp = A[i];
      53. A[i] = A[j];
      54. A[j] = temp;
      55. }
      56. quicksort(A, i);
      57. quicksort(A + i, len - i);
      58. }
      59. int main()
      60. {
      61. int size=0,loop,qrand;
      62. int *array;
      63. printf("Array-Groesse eingeben: ");
      64. scanf("%d", &size);
      65. // Allocate memory
      66. array = (int *) malloc(size * sizeof(int));
      67. if(array != NULL)
      68. {
      69. printf("\nSpeicher ist reserviert\n");
      70. printf("\nFilling array.\n");
      71. for(loop=0;loop<size;loop++)
      72. {
      73. qrand=rand() %20;
      74. array[loop]=qrand;
      75. printf("%d",qrand);
      76. }
      77. }
      78. else printf("\nKein freier Speicher vorhanden.\n");
      79. printf("\nHeapsort..\n");
      80. clock_t t;
      81. t = clock();
      82. heapsort(array,size);
      83. for(loop=0;loop<size;loop++)
      84. {
      85. printf("%d",array[loop]);
      86. }
      87. if((size * sizeof(int)) < 1000)
      88. {
      89. printf("\n %lu Bytes wurden freigegeben\n",(size * sizeof(int)));
      90. }
      91. else if((size *sizeof(int))>=1000)
      92. {
      93. printf("\n %lu Kilobytes wurden freigegeben\n",((size * sizeof(int))/1000));
      94. }
      95. else if((size * sizeof(int))>=1000*1000)
      96. {
      97. printf("\n %lu Megabytes wurden freigegeben\n", ((size * sizeof(int))/1000*1000));
      98. }
      99. free(array);
      100. //Reallocate memory above
      101. t = clock() - t;
      102. double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
      103. printf("Sorting took %f seconds to finish \n", time_taken);
      104. return 0;
      105. }
      Alles anzeigen
      Verfuegbar sind 24 Threads beim System