merge parallel with stl and tbb

merge_parallel.cc

#include <algorithm>
#include <cassert>
#include <chrono>
#include <execution>
#include <random>
#include <iostream>
#include <vector>
#include <benchmark/benchmark.h>

// Function to initialize random data
std::vector<unsigned long long> initializeRandomData(unsigned long long size) {
    std::vector<unsigned long long> data;
    std::mt19937 prng(std::random_device{}());
    std::uniform_int_distribution<uint64_t> zero_ull_max(0);

    for (unsigned long long i = 0; i < size; ++i) {
        data.push_back(zero_ull_max(prng));
    }

    return data;
}

// static void BM_ParallelUnSeqMerge(benchmark::State& state) {
//     std::vector<unsigned long long> left = initializeRandomData(state.range(0));
//     std::vector<unsigned long long> right = initializeRandomData(state.range(0));
//     std::sort(std::execution::par, left.begin(), left.end());
//     std::sort(std::execution::par, right.begin(), right.end());

//     for (auto _ : state) {
//         auto start = std::chrono::high_resolution_clock::now();
//         std::vector<unsigned long long> result(state.range(0) * 2);
//         std::merge(std::execution::par_unseq, left.begin(), left.end(),
//                    right.begin(), right.end(), result.begin());
//         auto end = std::chrono::high_resolution_clock::now();

//         state.SetIterationTime(std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() * 1e-9);
//     }
// }

// BENCHMARK(BM_ParallelUnSeqMerge)->Arg(16384)->Arg(16384000)->Arg(163840000);


// Benchmark function for parallel merge
static void BM_ParallelMerge(benchmark::State& state) {
    std::vector<unsigned long long> left = initializeRandomData(state.range(0));
    std::vector<unsigned long long> right = initializeRandomData(state.range(0));
    std::sort(std::execution::par, left.begin(), left.end());
    std::sort(std::execution::par, right.begin(), right.end());

    for (auto _ : state) {
        auto start = std::chrono::high_resolution_clock::now();
        std::vector<unsigned long long> result(state.range(0) * 2);
        std::merge(std::execution::par, left.begin(), left.end(),
                   right.begin(), right.end(), result.begin());
        auto end = std::chrono::high_resolution_clock::now();

        state.SetIterationTime(std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() * 1e-9);
    }
}

BENCHMARK(BM_ParallelMerge)->Arg(16384)->Arg(16384000)->Arg(163840000);

// Benchmark function for serial merge
static void BM_SerialMerge(benchmark::State& state) {
    std::vector<unsigned long long> left = initializeRandomData(state.range(0));
    std::vector<unsigned long long> right = initializeRandomData(state.range(0));
    std::sort(std::execution::seq, left.begin(), left.end());
    std::sort(std::execution::seq, right.begin(), right.end());

    for (auto _ : state) {
        auto start = std::chrono::high_resolution_clock::now();
        std::vector<unsigned long long> result(state.range(0) * 2);
        std::merge(std::execution::seq, left.begin(), left.end(),
                   right.begin(), right.end(), result.begin());
        auto end = std::chrono::high_resolution_clock::now();

        state.SetIterationTime(std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() * 1e-9);
    }
}

BENCHMARK(BM_SerialMerge)->Arg(16384)->Arg(16384000)->Arg(163840000);


BENCHMARK_MAIN();