CODEWITHSUNDEEP
c++multithreadingquicksort
Kroshtan
Kroshtan

Reputation: 677

Segmentation fault during multithreaded quicksort in c++

#include <iostream>
#include <algorithm>
#include <future>
#include <iterator>

using namespace std;

void qsort(int *beg, int *end)
{

    if (end - beg <= 1)
        return;

    int lhs = *beg;
    int *mid = partition(beg + 1, end, 
        [&](int arg)
        {
            return arg < lhs;
        }
    );

    swap(*beg, *(mid - 1));

    qsort(beg, mid);
    qsort(mid, end);
}

std::future<void> qsortMulti(int *beg, int *end) // SEG FAULT
{

    if (end - beg <= 1)
        return future<void>();
    int lhs = *beg;
    int *mid = partition(beg + 1, end, 
        [&](int arg)
        {
            return arg < lhs;
        }
    );

    swap(*beg, *(mid - 1));
    //spawn new thread for one side of the recursion
    auto future = async(launch::async, qsortMulti, beg, mid);
    //other side of the recursion is done in the current thread
    qsortMulti(mid, end);
    future.wait();
    inplace_merge(beg, mid, end);
}

void printArray(int *arr, size_t sz)
{
    for (size_t i = 0; i != sz; i++)
        cout << arr[i] << ' ';
    cout << endl;
}

int main()
{
    int ia[] = {5,3,6,8,4,6,2,5,2,9,7,8,4,2,6,8};
    int ia2[] = {5,3,6,8,4,6,2,5,2,9,7,8,4,2,6,8};
    size_t iaSize = 16;
    size_t ia2Size = 16;
    qsort(ia, ia + iaSize);
    printArray(ia, iaSize);
    qsortMulti(ia2, ia2 + ia2Size);
    printArray(ia2, ia2Size);
}

From the above piece of code it is clear I am simply trying to implement the same qsort function, but with multiple threads. The other questions and answers on stack overflow regarding related issue have led me to this version of the code, which leaves me with a very simple problem and related question: What is causing the multithreaded section to cause segmentation faults? To be clear: I do not require anyone to build a solution for me, I'd much rather have an indication or directions as to where to find the source of the segmentation fault, as I don't see it. Thanks in advance!

Upvotes: 0

Views: 163

Answers (1)

nh_
nh_

Reputation: 2241

In order to make std::async return an object of type std::future<T>, the function you pass to it merely has to return T. Example:

int compute() { return 42; }
std::future<int> result = std::async(&compute);

In your case that means that qsortMulti is supposed to have the signature 

void qsortMulti(int* beg, int* end);

and nothing has to be returned from it. In the code you provided, qsortMulti returns std::future<void> itself, which leads to std::async returning an object of type std::future<std::future<void>>, which is probably not what you intended. Furthermore, your function is only returning something in the case where the range is empty (in the if at the top). In all other code paths (e.g. reaching the end of the function) you are not returning anything at all, which leads to the caller accessing an uninitialized object, what may be the reason for the seg fault.

Upvotes: 2

Related Questions