Why is my Merge Sort with threads slower than basic recursive Merge Sort?

Question

I am a student and I need to implement MergeSort using threads. When I test the program, sorting with threads takes equal or more time, compared to recursive sorting.

We got premade file with basic MergeSort, and I am not allowed to change merge() or mergesort() fucntion, but I need to implement submergeSortThreads(). I am counting threads with semaphore(user decides how many threads will be made during the sorting), without semaphore array doesn't get sorted right, because of the race condition I think...

I'm running the program and reading numbers from file, with this command:

$ time cat rand_stevila.bin | ./mergeSort 10000

Threaded run (n == number of max threads allowed):

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

Here are some parts of the code, that are important for the question:

    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\0");
            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("\n\n CAS : %f\n\n",seconds);

        return 0;
    }

Answer 1

Let's observe the cost of creating a thread vs calling a function recursively.

When you create a thread, you create and initialize a separate Call Stack and Program Counter for that thread.

When you call a function, it adds to the top of your current call stack. It is a single entry for a single call. No separate Program Counter is needed.

Clearly, the overhead of creating a thread is much more than calling a function. Hence, despite order of running time being the same for both implementations, threaded is usually slower due to large overhead of creating a thread. A reasonable situation to use threads would be to divide a large workload and then run recursive cases for smaller arrays to prevent the Call Stacks from exploding in size.