parallel_accumulate.cpp

//
//  main.cpp
//  test
//
//  Created by alex on 18/05/2018.
//  Copyright © 2018 alex. All rights reserved.
//

#include <iostream>
#include <iomanip>

#include <list>
#include <vector>
#include <numeric>
#include <mutex>
#include <future>
#include <cmath>

int total_levels = 0;
std::vector<int> input;


//  1   2  3   4   5   6   7   8
//   \_/    \_/     \_/     \_/    level=3
//    \     /         \     /
//      ---             ---        level=2
//        \             /
//          -----------            level=1
//               |
//               -                 level=0

long twice(const std::vector<int>::iterator& begin, const std::vector<int>::iterator& end, int level) {
    
    if (level < total_levels) {
        
        auto mid = begin;
        auto dist = std::distance(begin, end);
        std::advance(mid, dist/2);

        auto f1 = std::async(twice, begin, mid, level + 1);
        auto f2 = std::async(twice, mid,   end, level + 1);
        
        return f1.get() + f2.get();
        
    } else {
        return std::accumulate(begin, end, 0);
    }
}

void calculate_levels()
{
    /*
    auto hardware = std::thread::hardware_concurrency();
    std::cout << "hardware = " << hardware << std::endl;

    auto th = hardware;
    do
    {
        total_levels += 1;
    } while (th >>= 1);
    */
    total_levels = 2;
    std::cout << "levels = " << total_levels << std::endl;
}

int main(int argc, const char * argv[]) {
    
    //std::srand(unsigned(std::time(0)));
    calculate_levels();
    
    auto parallel_fun = []{
        return twice(input.begin(), input.end(), 0);
    };
    
    auto serial_fun = []{
        return std::accumulate(input.begin(), input.end(), 0);
    };
    
    auto profile = [](std::function<long()> func) {
        auto start = std::chrono::high_resolution_clock::now();
        auto res = func();
        auto end = std::chrono::high_resolution_clock::now();
        
        assert(res > 0);
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        return duration;
    };
    
    auto interval = [&] (std::function<int()> func) {
        auto M = 60.0;
        auto t = 2.0003;
        auto sqrt_n = std::sqrt(M);
        
        std::vector<long> x(M);
        for (auto i = 0; i < M; ++i) {
            x.push_back(profile(func));
        }
        auto mean = std::accumulate(x.begin(), x.end(), 0.0) / M;
        
        auto sum = 0;
        for (auto j = 0; j < M; ++j)
        {
            sum += std::pow((x[j] - mean), 2);
        }
        
        double s = 0;
        if (sum > 0) {
            s = std::sqrt( sum / M - 1 );
        }
        
        std::cout.precision(2);
        std::cout << std::fixed
        << "[" << std::setw(9) << std::setfill(' ')  << (mean - t*s/sqrt_n )
        << "; "<< std::setw(9) << std::setfill(' ')  << (mean + t*s/sqrt_n )
        << "]" << std::endl;
    };

    auto change_input = [](long n) {
        std::cout << std::endl << "N=" << n << std::endl;
        input.clear();
        input.reserve(n);
        for (int64_t i = 0; i < n; ++i) {
            //input.push_back(std::rand() % 10);
            input.push_back(1);
        }
    };
    
    //-----------------------------------------------
    
    for (long n = 16; n < 134217728; n *= 2) {
    
         change_input(n);
         std::cout << "parallel interval = ";
         interval(parallel_fun);
         std::cout << "serial   interval = ";
         interval(serial_fun);
    }
    
    //std::cout << "par=" << parallel_fun() << std::endl << "ser=" << serial_fun() << std::endl;
    //assert(parallel_fun() == serial_fun());
    
    return 0;
}