Benchmarking parallelized version of sort

futures.log

----- N=1
Sorting only took 10.049 seconds
Sorting+merging took 10.049 seconds
Verification hash: 4462128812807805993
----- N=2
Sorting only took 5.450 seconds
0, 1, 2
Sorting+merging took 6.038 seconds
Verification hash: 4462128812807805993
----- N=4
Sorting only took 3.129 seconds
0, 1, 2
2, 3, 4
0, 2, 4
Sorting+merging took 4.305 seconds
Verification hash: 4462128812807805993
----- N=8
Sorting only took 1.533 seconds
0, 1, 2
2, 3, 4
4, 5, 6
6, 7, 8
0, 2, 4
4, 6, 8
0, 4, 8
Sorting+merging took 3.218 seconds
Verification hash: 4462128812807805993

REAME.md

method using futures

for a in 1 2 4 8
do 
    echo ----- N=$a
    g++ -std=c++0x -g -O3 -I ~/custom/boost/ -march=native test.cpp -o test -lpthread -DNUMBEROFCHUNKS=$a
    ./test
done |& tee futures.log

method using threads.log

for a in 1 2 4 8
do echo ----- N=$a
    g++ -std=c++0x -g -O3 -I ~/custom/boost/ -march=native test.cpp -o test -lpthread -DNUMBEROFCHUNKS=$a
    ./test
done |& tee threads.log

single-threaded execution

for a in 1 2 4 8
do echo ----- N=$a
    g++ -std=c++0x -g -O3 -I ~/custom/boost/ -march=native test.cpp -o test -lpthread -DNUMBEROFCHUNKS=$a
    ./test
done |& tee single.log

single.log

----- N=1
Sorting only took 10.195 seconds
Sorting+merging took 10.195 seconds
Verification hash: 4462128812807805993
----- N=2
Sorting only took 9.699 seconds
0, 1, 2
Sorting+merging took 10.261 seconds
Verification hash: 4462128812807805993
----- N=4
Sorting only took 9.367 seconds
0, 1, 2
2, 3, 4
0, 2, 4
Sorting+merging took 10.500 seconds
Verification hash: 4462128812807805993
----- N=8
Sorting only took 8.995 seconds
0, 1, 2
2, 3, 4
4, 5, 6
6, 7, 8
0, 2, 4
4, 6, 8
0, 4, 8
Sorting+merging took 10.682 seconds
Verification hash: 4462128812807805993

test.cpp

#define BOOST_RESULT_OF_USE_DECLTYPE
#include <boost/functional/hash.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <chrono>
#include <cstdlib>
#include <future>
#include <iostream>
#include <thread>
#include <vector>
#include <iomanip>

class Timer
{
    typedef std::chrono::high_resolution_clock clock;
    clock::time_point _start;
public:
    Timer() { reset(); }
    void reset() { _start = now(); }
    double elapsed()
    {
        using namespace std::chrono;
        auto e = now() - _start;
        return duration_cast<nanoseconds>(e).count()*1.0e-9;
    }
    clock::time_point now()
    {
        return clock::now();
    }
};

void powerof2(unsigned numberofchunks)
{
    while (numberofchunks%2==0) numberofchunks/=2;
    assert(1 == numberofchunks); // must be a power of 2
}

using namespace boost::adaptors;
int main()
{
    srand(42);
    ////////////////////////////////////////
    // prepare data
    std::vector<int> v(1ul<<27);

    auto f(begin(v)), l(end(v));
    std::generate(f, l, rand);

    ////////////////////////////////////////
    // prepare ranges in N chunks
    typedef boost::iterator_range<decltype(f)> R;

    const int N = NUMBEROFCHUNKS;
    powerof2(N);
    auto const chunk = v.size()/N;

    std::array<R, N> ranges;

    for (auto i=0; i<N; ++i)
        ranges[i] = boost::make_iterator_range(f+chunk*i, f+chunk*(i+1));

    auto sort = [] (R& r) -> void { boost::sort(r); };

    Timer timer;
#if 1
    ////////////////////////////////////////
    // synchronous sort
    for (auto& r : ranges)
        sort(r);
#elif 1
    ////////////////////////////////////////
    // using joined threads
    auto threads = boost::copy_range<std::vector<std::thread>>(
                ranges | transformed([&](R& range) { return std::thread(sort, std::ref(range)); })
            );

    for (auto&th : threads)
        th.join();
#else
    ////////////////////////////////////////
    // using async futures (how many threads is up to the implementation...)
    auto futures = boost::copy_range<std::vector<std::future<void>>>(
                ranges | transformed([&](R& range) { return std::async(std::launch::async, sort, std::ref(range)); })
            );
    for (auto& fut : futures)
        fut.get();
#endif
    std::cout << "Sorting only took " << std::fixed << std::setprecision(3) << timer.elapsed() << " seconds\n";

    ////////////////////////////////////////
    // recursively inplace_merge
    // only supports N = 2^x
    for (int m = 2; m <= N; m *= 2)
        for (auto i=0; (i+m/2)<N; i += m)
        {
            std::cout << i << ", " << (i+m/2) << ", " << (i+m) << "\n";
            std::inplace_merge(
                    begin(ranges[i]), 
                    begin(ranges[i+m/2]), 
                    end(ranges[std::min(N, i+m)-1]));
        }

    std::cout << "Sorting+merging took " << std::fixed << std::setprecision(3) << timer.elapsed() << " seconds\n";

    ////////////////////////////////////////
    // print result hash (for verification)
    auto h = boost::hash_range(f,l);
    std::cout << "Verification hash: " << h << "\n";
}

threads.log

----- N=1
Sorting only took 10.033 seconds
Sorting+merging took 10.033 seconds
Verification hash: 4462128812807805993
----- N=2
Sorting only took 5.402 seconds
0, 1, 2
Sorting+merging took 5.994 seconds
Verification hash: 4462128812807805993
----- N=4
Sorting only took 2.889 seconds
0, 1, 2
2, 3, 4
0, 2, 4
Sorting+merging took 4.019 seconds
Verification hash: 4462128812807805993
----- N=8
Sorting only took 1.622 seconds
0, 1, 2
2, 3, 4
4, 5, 6
6, 7, 8
0, 2, 4
4, 6, 8
0, 4, 8
Sorting+merging took 3.389 seconds
Verification hash: 4462128812807805993