Multithread Mergesort langsamer als Singlethread Heapsort?

Sub Royal · 19. Juni 2017

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

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>




#define MIN_LENGTH 4


int DEBUG;


typedef struct 
{
    int *array;
    int left;
    int right;
    int tid;
} thread_data_t;


int number_of_threads;
pthread_mutex_t lock_number_of_threads;


int my_comp(const void *larg, const void *rarg) 
{
    int l = *(int *)larg;
    int r = *(int *)rarg;
    if (l < r) 
	{
        return -1;
    } 
	else if (l == r) 
	{
        return 0;
    }
    return 1;
}


void merge(int *data, int left, int right, int tid) 
{
    if (DEBUG) 
	{
        printf("[%d] Merging %d to %d\n", tid, left, right);
    }
    int ctr = 0;
    int i = left;
    int mid = left + ((right - left) / 2);
    int j = mid + 1;
    int *c = (int *) malloc((right - left + 1) * sizeof(int));
    while (i <= mid && j <= right) 
	{
        if (data[i] <= data[j]) 
		{
            c[ctr++] =  data[i++];
        } 
		else 
		{
            c[ctr++] =  data[j++];
        }
    }
    if (i == mid + 1) 
	{
        while (j <= right) 
		{
            c[ctr++] = data[j++];
        }
    } 
	else 
	{
        while (i <= mid) 
		{
            c[ctr++] = data[i++];
        }
    }
    i = left;
    ctr = 0;
    while (i <= right) 
	{
        data[i++] = c[ctr++];
    }
    free(c);
    return;
}


void *merge_sort_threaded(void *arg) 
{
    thread_data_t *data = (thread_data_t *) arg;
    int l = data->left;
    int r = data->right;
    int t = data->tid;
    if (r - l + 1 <= MIN_LENGTH) 
	{
        if (DEBUG) 
		{
            printf("[%d] Calling qsort(%d, %d).\n", t, l, r);
        }
        qsort(data->array + l, r - l + 1, sizeof(int), my_comp);
    }
	else 
	{
        int m = l + ((r - l) / 2);
        thread_data_t data_0;
        data_0.left = l;
        data_0.right = m;
        data_0.array = data->array;
        pthread_mutex_lock(&lock_number_of_threads);
            data_0.tid = number_of_threads++;
        pthread_mutex_unlock(&lock_number_of_threads);
        pthread_t thread0;
        int rc = pthread_create(&thread0,
                                NULL,
                                merge_sort_threaded,
                                &data_0);
        int created_thread_0 = 1;
        if (rc) 
		{
            if (DEBUG) 
			{
                printf("[%d] Failed to create thread, calling qsort.", data_0.tid);
            }
            created_thread_0 = 0;
            qsort(data->array + l, m - l + 1, sizeof(int), my_comp);
        }
        thread_data_t data_1;
        data_1.left = m + 1;
        data_1.right = r;
        data_1.array = data->array;
        pthread_mutex_lock(&lock_number_of_threads);
            data_1.tid = number_of_threads++;
        pthread_mutex_unlock(&lock_number_of_threads);
        pthread_t thread1;
        rc = pthread_create(&thread1,
                            NULL,
                            merge_sort_threaded,
                            &data_1);
        int created_thread_1 = 1;
        if (rc) 
		{
            if (DEBUG) 
			{
                printf("[%d] Failed to create thread, calling qsort.", data_1.tid);
            }
            created_thread_1 = 0;
            qsort(data->array + m + 1, r - m, sizeof(int), my_comp);
        }
        if (created_thread_0) 
		{
            pthread_join(thread0, NULL);
        }
        if (created_thread_1) 
		{
            pthread_join(thread1, NULL);
        }
        merge(data->array, l, r, t);
    }
    pthread_exit(NULL);
    return NULL;
}


void merge_sort(int *array, int start, int finish) 
{
    thread_data_t data;
    data.array = array;
    data.left = start;
    data.right = finish;


    number_of_threads = 0;
    pthread_mutex_init(&lock_number_of_threads, NULL);
    data.tid = 0;
    pthread_t thread;
    int rc = pthread_create(&thread,
                            NULL,
                            merge_sort_threaded,
                            &data);
    if (rc) 
	{
        if (DEBUG) 
		{
            printf("[%d] Failed to create thread, calling qsort.",
                   data.tid);
        }
        qsort(array + start,
              finish - start + 1,
              sizeof(int),
              my_comp);
    }
    pthread_join(thread, NULL);
    return;
}




int main()
    {
        int size=0,loop,qrand;
        int *array;
        printf("Array-Groesse eingeben: ");
        scanf("%d", &size);
        array = (int *) malloc(size * sizeof(int));
        if(array != NULL)
        {
            printf("\nSpeicher ist reserviert\n");
            printf("\nFilling array.\n");
    	for(loop=0;loop<size;loop++)
    	{
                qrand=rand() %20;
                array[loop]=qrand;
                printf("%d",qrand);
    	}
        }
        else printf("\nKein freier Speicher vorhanden.\n");


	printf("\nMerge Sort..\n");
		clock_t t;
		t = clock();
          merge_sort(array, 0, size - 1);
        for(loop=0;loop<size;loop++)
        {
            printf("%d",array[loop]);
        }
	if((size * sizeof(int)) < 1000)
	{
        printf("\n %lu Bytes wurden freigegeben\n",(size * sizeof(int)));
	}
	else if((size *sizeof(int))>=1000)
	{
	printf("\n %lu Kilobytes wurden freigegeben\n",((size * sizeof(int))/1000));
	}
	else if((size * sizeof(int))>=1000*1000)
	{
	printf("\n %lu Megabytes wurden freigegeben\n", ((size * sizeof(int))/1000*1000));
	}
        free(array);
		pthread_mutex_destroy(&lock_number_of_threads);
	t = clock() - t;
	printf("Sorting took %f seconds to finish \n", time_taken);
        return 0;
    }

Alles anzeigen

Ist es eventuell falsch implementiert?

C

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


void quicksort(int *A, int len);




int max (int *a, int n, int i, int j, int k) 
{
    int m = i;
    if (j < n && a[j] > a[m]) {
        m = j;
    }
    if (k < n && a[k] > a[m]) {
        m = k;
    }
    return m;
}
void downheap (int *a, int n, int i) 
{
    while (1) {
        int j = max(a, n, i, 2 * i + 1, 2 * i + 2);
        if (j == i) {
            break;
        }
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
        i = j;
    }
}
void heapsort (int *a, int n) 
{
    int i;
    for (i = (n - 2) / 2; i >= 0; i--) {
        downheap(a, n, i);
    }
    for (i = 0; i < n; i++) {
        int t = a[n - i - 1];
        a[n - i - 1] = a[0];
        a[0] = t;
        downheap(a, n - i - 1, 0);
    }
}
void quicksort(int *A, int len)
{
  if (len < 2) return;
  int pivot = A[len / 2];
  int i, j;
  for (i = 0, j = len - 1; ; i++, j--)
  {
    while (A[i] < pivot) i++;
    while (A[j] > pivot) j--;
    if (i >= j) break;
    int temp = A[i];
    A[i]     = A[j];
    A[j]     = temp;
  }
  quicksort(A, i);
  quicksort(A + i, len - i);
}








    int main()
    {
        int size=0,loop,qrand;
        int *array;
        printf("Array-Groesse eingeben: ");
        scanf("%d", &size);
        // Allocate memory
        array = (int *) malloc(size * sizeof(int));
        if(array != NULL)
        {
            printf("\nSpeicher ist reserviert\n");
            printf("\nFilling array.\n");
    	for(loop=0;loop<size;loop++)
    	{
                qrand=rand() %20;
                array[loop]=qrand;
                printf("%d",qrand);
    	}
        }
        else printf("\nKein freier Speicher vorhanden.\n");


	printf("\nHeapsort..\n");
	clock_t t;
				t = clock();
        heapsort(array,size);
        for(loop=0;loop<size;loop++)
        {
            printf("%d",array[loop]);
        }
	if((size * sizeof(int)) < 1000)
	{
        printf("\n %lu Bytes wurden freigegeben\n",(size * sizeof(int)));
	}
	else if((size *sizeof(int))>=1000)
	{
	printf("\n %lu Kilobytes wurden freigegeben\n",((size * sizeof(int))/1000));
	}
	else if((size * sizeof(int))>=1000*1000)
	{
	printf("\n %lu Megabytes wurden freigegeben\n", ((size * sizeof(int))/1000*1000));
	}
        free(array);
	//Reallocate memory above	
		t = clock() - t;
	double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
	printf("Sorting took %f seconds to finish \n", time_taken);
        return 0;
    }

Alles anzeigen

Verfuegbar sind 24 Threads beim System

Hybris · 20. Juni 2017

Ich glaube du hast es falsch programmiert. Ich würde vorher splitten, diese Teile auf deine Threads verteilen, joinen und zum Schluss mergen.

Sub Royal · 2. Juli 2017

Gute Idee, werde ich mal probieren

breadfish.de 12. März 2022