threads_vector.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <chrono>
#include <numeric>
#include <thread>

template<typename It, typename T>
void accumulate_block(It first, It last, T &res) {
    res = std::accumulate(first, last, res);
}

template<typename It, typename T>
T parallel_accumulate(It first, It last, T init) {
    size_t len = std::distance(first, last);

    if (len == 0) return init;

    size_t min_items_per_thread = 25;
    size_t max_threads = len / min_items_per_thread;
    size_t hardware_threads = std::thread::hardware_concurrency();

    size_t threads_n = std::min(hardware_threads != 0 ? hardware_threads : 2, max_threads);
    std::vector<T> results(threads_n);
    std::vector<std::thread> threads(threads_n - 1);

    It block_start = first;
    size_t block_size = len / threads_n;

    for (size_t i = 0; i < (threads_n - 1); ++i) {
        It block_end = block_start;
        std::advance(block_end, block_size);

        threads[i] = std::thread(
                accumulate_block<It, T>,
                block_start, block_end, std::ref(results[i])
        );
        block_start = block_end;
    }

    accumulate_block<It, T>(block_start, last, results[threads_n - 1]);

    for (std::thread &t : threads) {
        t.join();
    }

    return std::accumulate(results.begin(), results.end(), init);
}

long double avg2(std::vector<unsigned long long> const &v) {
    long long n = 0;
    long double mean = 0.0;
    for (auto x : v) {
        double delta = x - mean;
        mean += delta / ++n;
    }
    return mean;
}

int main() {
    std::vector<int> numbers(100000000);

    for (int i = 0; i < 100000000; ++i) {
        numbers[i] = i + (i % 10);
    }

    int n_runs = 100;

    std::vector<unsigned long long> runs_line(100);
    std::vector<unsigned long long> runs_threads(100);

    for (int run_n = 0; run_n < n_runs; ++run_n) {
        auto start = std::chrono::high_resolution_clock::now();
        int line_res = std::accumulate(numbers.begin(), numbers.end(), 0);
        auto stop = std::chrono::high_resolution_clock::now();
        runs_line[run_n] = std::chrono::duration_cast<std::chrono::microseconds>(stop - start).count();

        start = std::chrono::high_resolution_clock::now();
        int thread_res = parallel_accumulate(numbers.begin(), numbers.end(), 0);
        stop = std::chrono::high_resolution_clock::now();
        runs_threads[run_n] = std::chrono::duration_cast<std::chrono::microseconds>(stop - start).count();

        if (line_res != thread_res) {
            std::cout << "Oopsie";
            return 1;
        }
    }

    std::cout << "N" << "\t" << "Linear" << "\t" << "Threads" << "\n";

    for (int i = 0; i < 100; ++i) {
        std::cout << i + 1 << "\t" << runs_line[i] << "\t" << runs_threads[i] << "\n";
    }

    std::cout << "Average: " << avg2(runs_line) << "\t" << avg2(runs_threads);

}