CODEWITHSUNDEEP
c++multithreadingsorting
Will
Will

Reputation: 11

Negligible Perfomance Boost from p_thread c++

I've been using Mac OS gcc 4.2.1 and Eclipse to write a program that sorts numbers using a simple merge sort. I've tested the sort extensively and I know it works, and I thought, maybe somewhat naively, that because of the way the algorithm divides up the list, I could simply have a thread sort half and the main thread sort half, and then it would take half the time, but unfortunately, it doesn't seem to be working.

Here's the main code: 

    float x = clock(); //timing
    int half = (int)size/2; // size is the length of the list

    status = pthread_create(thready,NULL,voidSort,(void *)datay); //start the thread sorting

    sortStep(testArray,tempList,half,0,half); //sort using the main thread 

    int join = pthread_join(*thready,&someptr); //wait for the thread to finish

    mergeStep(testArray,tempList,0,half,half-1); //merge the two sublists

    if (status != 0) { std::cout << "Could not create thread.\nError: " << status << "\n";  }

    if (join != 0) { std::cout << "Could not create thread.\nError: " << status << "\n";  }

    float y = clock() - x; //timing

sortStep is the main sorting function, mergeStep is used to merge two sublists within one array (it uses a placeholder array to switch the numbers around), and voidSort is a function I use to pass a struct containing all the arguments for sortStep to the thread. I feel like maybe the main thread is waiting until the new thread is done, but I'm not sure how to overcome that. I'm extremely, unimaginably grateful for any and all help, thank you in advanced!

EDIT: Here's the merge step

void mergeStep (int *array,int *tempList,int start, int lengthOne, int lengthTwo) //the merge step of a merge sort
{
int i = start;
int j = i+lengthOne;
int k = 0; // index for the entire templist

while (k < lengthOne+lengthTwo) // a C++ while loop
{
    if (i - start == lengthOne)
    { //list one exhausted
        for (int n = 0; n+j < lengthTwo+lengthOne+start;n++ ) //add the rest
        {
            tempList[k++] = array[j+n];
        }
        break;
    }

    if (j-(lengthOne+lengthTwo)-start == 0)
    {//list two exhausted
        for (int n = i; n < start+lengthOne;n++ ) //add the rest
        {
            tempList[k++] = array[n];
        }
        break;
    }

    if (array[i] > array[j]) // figure out which variable should go first
    {
        tempList[k] = array[j++];
    }

    else
    {
        tempList[k] = array[i++];
    }
    k++;
}

for (int s = 0; s < lengthOne+lengthTwo;s++) // add the templist into the original
{
    array[start+s] = tempList[s];
}
}

-Will

Upvotes: 0

Views: 60

Answers (1)

Surt
Surt

Reputation: 16099

The overhead of creating threads is quite large, so unless you have a large amount (to be determined) of data to sort your better off sorting it in the main thread.

The mergeStep also counts against the part of the code that can't be palletized, remember Amdahl's law.

If you don't have a coarsening step as the last part of you sortStep when you get below 8-16 elements much of your performance will go up in function calls. The coarsening step will have to be done by a simpler sort, insertion sort or sorting network.

Unless you have a large enough sorting the actual timing could drown in measuring uncertainty.

Upvotes: 1

Related Questions