0
\$\begingroup\$

i had made a simple parallel sorting for my personal games. it did well so far, but i would like to get some advises about how to improve it further or perhaps there are an alternative methods for better sorting data.

#include <iostream>
#include <cassert>
#include <iomanip>
#include <functional>
#include <utility>
#include <vector>
#include <thread>
#include <future>
#include <random>
#include <algorithm>

template<typename T, typename C = std::less<T>>
void parallel_sort(T* data, std::size_t len, std::size_t grainsize, const C& comp = C())
{
    // Use grainsize instead of thread count so that we don't e.g.
    // spawn 4 threads just to sort 8 elements.
    if (len < grainsize)
    {
        std::sort(data, data + len, comp);
    }
    else
    {
        auto future = std::async(parallel_sort<T, C>, data, len / 2, grainsize, comp);

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

        future.wait();

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


int main()
{
    auto eval = [](auto fun) {
        const auto t1 = std::chrono::high_resolution_clock::now();
        const auto [name, result] = fun();
        result();
        const auto t2 = std::chrono::high_resolution_clock::now();
        const std::chrono::duration<double, std::milli> ms = t2 - t1;
        std::cout << std::fixed << std::setprecision(1) << name << " took " << ms.count() << " ms\n";
    };

    using ints_t = std::vector<int>;
    ints_t ints(200); // *Not* ints{200}!
    std::generate(std::begin(ints), std::end(ints), std::rand);
    {
        ints_t l{ ints };
        eval([&l] { return std::pair{ "parallel_sort",
            [&l] { return parallel_sort(l.data(), l.size(), l.size() / std::thread::hardware_concurrency()); } }; });
        assert(std::is_sorted(std::begin(l), std::end(l)));
    }
    {
        ints_t l{ ints };
        eval([&l] { return std::pair{ "std::sort",
            [&l] { return std::sort(std::begin(l), std::end(l)); } }; });
        assert(std::is_sorted(std::begin(l), std::end(l)));
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.