Multi-threaded merge sort

Question

Below is the code for merge sort using multithreading. Will this code run for large number of inputs? Does any other part of the code need changing?

#include<iostream>
#include<thread>
#include<mutex>
#include<vector>
#include<functional>
#include<fstream>
std::mutex mut;

void merge(std::vector<int>& vec,int s,int mid,int e){
    std::vector<int> lvec,rvec;
    for(int i=s;i<=e;i++){
        mut.lock();
        if(i<=mid)
            lvec.push_back(vec[i]);
        else
            rvec.push_back(vec[i]);
        mut.unlock();
    }
    int a=0,b=0,c=s;
    while(a<lvec.size()&&b<rvec.size()){
        if(lvec[a]<rvec[b]){
            vec[c++]=lvec[a++];
        }
        else
            vec[c++]=rvec[b++];
    }
        while(a<lvec.size()){
        vec[c++]=lvec[a++];
    }
    while(b<rvec.size()){
        vec[c++]=rvec[b++];
    }
}
void mergeSort(std::vector<int>& vec,int s,int e){
    if(s>=e)
        return;
    int mid=(s+e)/2;
    std::thread th1(std::bind(mergeSort,std::ref(vec),s,mid));
    std::thread th2(std::bind(mergeSort,std::ref(vec),mid+1,e));
    th1.join();
    th2.join();
    merge(vec,s,mid,e);
}

Answer 1

Summary

Because the number of threads that a system can create is finite, if your data set is large enough eventually the thread constructor will throw an exception (system_error) when a thread cannot be created. There is also a performance hit when creating a thread, so making threads for very small intervals is counterproductive.

merge

When copying elements into the local vectors lvec and rvec, you are copying elements sequentially. Using one loop to copy all the elements adds extra overhead and is unnecessary. You can use two loops (and reserve memory space for each), use an appropriate vector constructor (that takes a pair of iterators), or use the insert function to block copy elements from one vector to another. Reserving space for the vector, instead of allowing it to grow, will reduce the contention in the memory allocator (which is not concurrent, creating a bottleneck when two threads both try to allocate memory).

Since you are writing to local vectors, and reading from a region of vec that is only being read by the current thread, the mutex is unnecessary.

To avoid repeated calculation of the size, store lvec.size() and rvec.size() in local variables. Or you can use iterators for all vector accesses. The two loops that finish copying the tail elements from lvec or rvec can use vector's insert function.

There is also some inconsistent indentation in the code, and inconsistent use of braces for single-line if/else blocks.

There may be a slight performance hit if multiple threads are writing to elements in vec that are near each other (that share a cache line), but this should be rare and with appropriate choice of range to not create threads (see below) should be avoidable.

mergesort

Thread creation is expensive, and the number of threads available in a system is finite. Once the number of running threads exceeds the number available in hardware, there is no performance gain from creating more (and usually a slight hit).

Therefore, once the interval to sort is small enough (64 or 128 elements), make recursive calls directly, rather than create threads for them. Also including an upper limit on the number of threads to create would avoid the penalty of creating threads that will not execute right away. Determination of appropriate values for these limits would require experimentation to check the effect on the performance.

Answer 2

Limiting the number of threads spawned

As already mentioned, there is a limit to how many threads can be spawned, but it also doesn't make sense for CPU-bound workloads to spawn much more threads than the number of hardware threads that your system has. You can query the number of hardware threads using std::thread::hardware_concurrency().

There are many ways you could ensure the number of threads spawned is limited, but in this case I think the appropriate thing to do is to limit thread spawning to a certain recursion depth of mergeSort(). Every level of recursion doubles the number of running threads, so if you pass the number of currently running threads as a parameter to mergeSort(), it will be able to track this. For example:

void mergeSort(std::vector<int>& vec, int s, int e, unsigned int cur_threads = 1) {
    if(s >= e)
        return;
    int mid = (s + e) / 2;

    static const unsigned int max_threads = std::thread::hardware_concurrency();

    if (cur_threads < max_threads) {
        std::thread thr(mergeSort, std::ref(vec), s, mid, cur_threads * 2);
        // No need to create a second thread if we are going to block anyway
        mergeSort(std::ref(vec), mid + 1, e, cur_threads * 2);
        thr.join();
    } else {
        mergeSort(std::ref(vec), s, mid, cur_threads);
        mergeSort(std::ref(vec), mid + 1, e, cur_thread);
    }

    merge(vec, s, mid, e);
}

Answer 3

There are a few things to do:

1. Perform all the standard optimizations also common for single-threaded merge-sort:

   1. Switch to intro-sort below a threshold.

   2. Ensure only a single scratch-buffer is ever allocated per thread, all those allocate/deallocate operations are a monumental waste of time.

2. Limit threads. When all the cores are hard at work, adding more threads slows everything down.

3. Get rid of the locking. Currently, you don't need any. All the global lock does is removing the concurrency you so enthusiastically introduced. I would be astounded if it doesn't lower the throughput below that of single-threading the code (remove lock, call synchronously instead of starting threads).

Answer 4

    std::vector<int> lvec,rvec;
    for(int i=s;i<=e;i++){
        mut.lock();
        if(i<=mid)
            lvec.push_back(vec[i]);
        else
            rvec.push_back(vec[i]);
        mut.unlock();
    }

You are locking each push_back to the vectors defined as local variables. How can other threads be manipulating the same vectors?

It's also using a global mutex for all threads, which will pretty much destroy any threading benefit.

Use a scoped lock rather than direct lock and unlock calls.

Don't repeat the whole thing when only a variable changes: Break out the choice of lvec or rvec in the condition, and then have one copy of the expression that uses it. E.g.

auto& side= i<=mid ? lvec : rvec;
side.push_back(vec[i]);

But looking at that when I typed it, I realized that you are choosing based on i not the value (vec[i]). i is just counting up. So you should just copy the first half of vec to left as one statement and copy the other half to right as one statement. That can be further improved: if you copy off right to another vector, then just call vec.resize to turn it into what you wanted in left, with no copying needed.

Your leftover is doing the same thing: just copy the entire rest of lvec or rvec with a single call each. Don't write a loop.

Your create two new threads and then immediately join them. That means that the original thread is doing nothing, and is just wasted overhead of having created it. You have two parallel things to do; put half in a new thread and do the other half in this thread. This will have the identical effect, but without the overhead of more thread creation/joining.

Finally, nobody ever sorts a simple vector of int. Make your code useable for real work by making it a template argument. You can use int in your testing, but the code is ready to use with other types.

Also, if you look at the standard algorithms, sort, stable_sort, etc. are defined to take iterators, and are not limited to std::vector. You are passing in index positions (as int, not as the type that vector actually uses for indexing) to allow sorting part of a vector, as this is needed by your recursive approach. But it works more naturally if you just used begin/end iterators, and don't need to pass the collection at all.

That is, make the signature look like std::sort.
I suggest you review what's in the algorithm header so you're familiar with what's in there, and can reach for those instead of writing loops from scratch for simple operations.