qs.cpp

#include <chrono>
#include <cstdint>
#include <functional>
#include <thread>
#include <iomanip>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>

int64_t rnd_state = 0;
int64_t rnd() { rnd_state = (rnd_state * 13 + 37) % 1000000000000037ll; return rnd_state; }

void check(const std::vector<int64_t> &v) {
    for (size_t i = 0; i < v.size() - 1; ++i) { if (v[i] > v[i + 1]) { throw "Unsorted vector!"; } }
}

int partition(std::vector<int64_t> &v, int s, int e) {
    int64_t x = v[s];
    int i = s + 1, j = e - 1;
    while (j >= i) {
        if (v[i] <= x) { v[i - 1] = v[i]; ++i; continue; }
        if (v[j] >= x) { --j; continue; }
        v[i - 1] = v[j];
        v[j] = v[i];
        ++i; --j;
    }
    v[j] = x;
    return j;
}

void qs_vector(std::vector<int64_t> &v, int s, int e) {
    sort(v.begin(), v.end());
}

void qs_singlethread(std::vector<int64_t> &v, int s, int e) {
    if ((e - s) <= 1) { return; }
    int p = partition(v, s, e);
    qs_singlethread(v, s, p);
    qs_singlethread(v, p + 1, e);
}

void qs_multithread_impl(std::vector<int64_t> *v, int s, int e, int depth) {
    if ((e - s) <= 1) { return; }
    int p = partition(*v, s, e);
    if (depth > 0) {
        std::thread thread(qs_multithread_impl, v, p + 1, e, depth - 1);
        qs_multithread_impl(v, s, p, depth - 1);
        thread.join();
    } else {
        qs_singlethread(*v, s, p);
        qs_singlethread(*v, p + 1, e);
    }
}

void qs_multithread(std::vector<int64_t> &v, int s, int e) {
    qs_multithread_impl(&v, s, e, 7);
}

void bench(
    int count,
    int size,
    std::string msg,
    const std::function<void(std::vector<int64_t>&, int, int)> fn
) {
    std::chrono::high_resolution_clock::duration total_time(0);
    std::vector<int64_t> v(size);
    for (int t = 0; t < count; ++t) {
        generate(v.begin(), v.end(), rnd);
        auto start_time = std::chrono::high_resolution_clock::now();
        fn(v, 0, size);
        total_time += std::chrono::high_resolution_clock::now() - start_time;
        check(v);
    }
    auto average_time = std::chrono::duration_cast<std::chrono::microseconds>(total_time / count);
    std::cout << msg << ": " << std::setw(6) << std::setprecision(3) << average_time.count() << "us"
        << std::endl;
}

int main() {
    bench(10, 1000000, "single", qs_singlethread);
    bench(10, 1000000, "stdlib", qs_vector);
    bench(10, 1000000, "mthrea", qs_multithread);
}

result.txt

$ clang++ -Wall -std=c++14 -pthread -g -O3 -o qs qs.cpp && ./qs
single:  80846us
stdlib:  69573us
mthrea:  24378us