CODEWITHSUNDEEP
c++multithreadingmergesort
Paul
Paul

Reputation: 147

threaded merge sort giving invalid results

I created a merge sort that works fine for arrays of non repeating integers. I am attempting to make a multithreaded version of the same.

I am getting back invalid results.

void mergesort(int data[ ], size_t n)
{
    size_t n1; // Size of the first subarray
    size_t n2; // Size of the second subarray

    if (n > 1)
    {
        // Compute sizes of the subarrays.
        n1 = n / 2;
        n2 = n - n1;

        mergesort(data, n1);         // Sort from data[0] through data[n1-1]
        mergesort((data + n1), n2);  // Sort from data[n1] to the end

        // Merge the two sorted halves.
        merge(data, n1, n2);
    }
}

DWORD WINAPI threadedmergesort(LPVOID params)
{
    size_t n1; // Size of the first subarray
    size_t n2; // Size of the second subarray
    Params* parameters = (Params*) params;
    if (parameters->size > 1)
    {
        // Compute sizes of the subarrays.
        n1 = parameters->size / 2;
        n2 = parameters->size - n1;

        Params* p1 = new Params(parameters->dataArray, n1);
        //mergesort(data, n1);         // Sort from data[0] through data[n1-1]
        HANDLE h1 = CreateThread(NULL, 0, threadedmergesort, (LPVOID)p1, 0, NULL);
        Params* p2 = new Params(parameters->dataArray, n2);
        //mergesort((data + n1), n2);  // Sort from data[n1] to the end
        HANDLE h2 = CreateThread(NULL, 0, threadedmergesort, (LPVOID)p1, 0, NULL);
        WaitForSingleObject(h1, INFINITE);
        WaitForSingleObject(h2, INFINITE);

        // Merge the two sorted halves.
        merge(parameters->dataArray, n1, n2);
    }
    return (DWORD)0x0; //null
}

struct Params
{
    int* dataArray;
    int size;
    Params(int _dataArray[], int _size);
};
Params::Params(int _dataArray[], int _size)
{
    dataArray = _dataArray;
    size = _size;
}

Could someone comment on why I would get invalid results with the threaded version of the merge sort and what I could do to correct the problem?

Upvotes: 0

Views: 343

Answers (2)

Chris O
Chris O

Reputation: 5037

A few points to consider:

  1. Don't use CreateThread, use beginThreadEx instead, see the MSDN for more info.
  2. As TOAOGG already pointed out, you have a data race, since multiple threads are access the same memory, and you have no synchronization.
  3. You should use the OS thread pool instead of creating your own threads explicitly. Since this is a recursive algorithm, you strongly run the risk of running out of system resources for larger datasets. Each thread gets 1MB default stack size in user space (not sure but I think another 1MB in kernel space as well) so with a 32-bit process, you will quickly hit that wall. Plus, there's significant overhead with creating new threads at a fast rate, which will reduce any concurrency gains that you want here. See the SubmitThreadPoolWork and related API

Another alternative to using the thread pool API is to use OpenMP to do a parallel for loop in C++. Visual Studio 2008 and later support that options (and Intel compilers of course).

Upvotes: 0

TOAOGG
TOAOGG

Reputation: 392

Params* p1 = new Params(parameters->dataArray, n1);
//mergesort(data, n1);         // Sort from data[0] through data[n1-1]
HANDLE h1 = CreateThread(NULL, 0, threadedmergesort, (LPVOID)p1, 0, NULL);
Params* p2 = new Params(parameters->dataArray, n2);
//mergesort((data + n1), n2);  // Sort from data[n1] to the end
HANDLE h2 = CreateThread(NULL, 0, threadedmergesort, (LPVOID)p1, 0, NULL);

It looks like you're sending p1 twice to the mergesorter. So you're just sorting the first halfs of your list. Change your second parameter and everything should be correct.

My Mergesort looks like this: 

DWORD WINAPI Mergesorter::mergesort_MT(LPVOID param)
{
    Mergesort_Params* i_mergesortParams = (Mergesort_Params*)param;
    unsigned int half = i_mergesortParams->numberOfValues / 2;
    DWORD threadId[2] = {0,0};
    HANDLE h[2];
    Mergesort_Params* mergesortParams;

    if(i_mergesortParams->numberOfValues > 1)
    {
        mergesortParams = new Mergesort_Params[2];
        mergesortParams[0].l_list = i_mergesortParams->l_list;
        mergesortParams[1].l_list = i_mergesortParams->l_list + half;
        mergesortParams[0].numberOfValues = half;
        mergesortParams[1].numberOfValues = i_mergesortParams->numberOfValues - half;

        h[0] = CreateThread(0,0,mergesort_MT,(void*)&mergesortParams[0],0,&threadId[0]);
        //WaitForSingleObject(h[0],INFINITE);
        h[1] = CreateThread(0,0,mergesort_MT,(void*)&mergesortParams[1],0,&threadId[1]);        
        //WaitForSingleObject(h[1],INFINITE);
        WaitForMultipleObjects(2,h,TRUE,INFINITE);
        merge_ST(i_mergesortParams->l_list,half,i_mergesortParams->numberOfValues - half);


    }

//delete threadId;
//delete h;
//delete mergesortParams;

return 0;
}

Did you fix your problem? Now my problem is, that I'm not able to sort enough values 100000 are too much (Single-Threaded no problem) and my CPU isn't used completely (25% on my A8-3500M so just one core)

Upvotes: 1

Related Questions