How to set number of threads in C++

Question

I have written the following multi-threaded program for multi-threaded sorting using std::sort. In my program grainSize is a parameter. Since grainSize or the number of threads which can spawn is a system dependent feature. Therefore, I am not getting what should be the optimal value to which I should set the grainSize to? I work on Linux?

 int compare(const char*,const char*)
{
   //some complex user defined logic    
}
void multThreadedSort(vector<unsigned>::iterator data, int len, int grainsize)
{
    if(len < grainsize) 
    {
        std::sort(data, data + len, compare);
    }
    else
    {
        auto future = std::async(multThreadedSort, data, len/2, grainsize);

        multThreadedSort(data + len/2, len/2, grainsize); // No need to spawn another thread just to block the calling thread which would do nothing.

        future.wait();

        std::inplace_merge(data, data + len/2, data + len, compare);
    }
}

int main(int argc, char** argv) {

    vector<unsigned> items;
    int grainSize=10;
    multThreadedSort(items.begin(),items.size(),grainSize);
    std::sort(items.begin(),items.end(),CompareSorter(compare));
    return 0;
}

I need to perform multi-threaded sorting. So, that for sorting large vectors I can take advantage of multiple cores present in today's processor. If anyone is aware of an efficient algorithm then please do share.

I dont know why the value returned by multiThreadedSort() is not sorted, do you see some logical error in it, then please let me know about the same

Answer 1

This gives you the optimal number of threads (such as the number of cores):

unsigned int nThreads = std::thread::hardware_concurrency();

As you wrote it, your effective thread number is not equal to grainSize : it will depend on list size, and will potentially be much more than grainSize.

Just replace grainSize by :

unsigned int grainSize= std::max(items.size()/nThreads, 40);

The 40 is arbitrary but is there to avoid starting threads for sorting to few items which will be suboptimal (the time starting the thread will be larger than sorting the few items). It may be optimized by trial-and-error, and is potentially larger than 40.

You have at least a bug there:

multThreadedSort(data + len/2, len/2, grainsize);

If len is odd (for instance 9), you do not include the last item in the sort. Replace by:

multThreadedSort(data + len/2, len-(len/2), grainsize);