Visual Studio 2017 updateでサポートされた「C++17のparallel algorithms」

#pragma once

#include <algorithm>
#include <vector>
#include <stdexcept>

class prime_judge {
private:
  std::vector<int> primes_;
public:
  prime_judge(int N) {
    primes_.push_back(2);
    // 奇数 3, 5, 7 ... に対し
    for ( int n = 3; n <= N; n += 2 ) {
      // primes＿の中に n を割り切る数がなければ
      if ( std::none_of(primes_.begin(), primes_.end(),
           [n](int p) { return n%p == 0;}) ) {
        // nは素数だからprimes_に追加する
        primes_.push_back(n);
      }
    }
  }

  // nが素数ならtrueを返す
  bool operator()(int n) const {
    if ( n > primes_.back()*primes_.back() ) {
      throw std::domain_error("too big to determine.");
    }
    if ( n < 2 ) return false;
      return binary_search(primes_.begin(), primes_.end(), n)
          || std::none_of(primes_.begin(), primes_.end(),
                          [n](int p) { return n%p == 0;});
  }
};

#include "prime_judge.h"

#include <iostream>
#include <numeric>
#include <algorithm>

template<typename Iterator>
size_t count_seq(Iterator first, Iterator last, const prime_judge& judge) {
  return std::count_if(first, last, judge);
}

int main() {
  using namespace std;
  prime_judge judge(1000);

  vector<int> data(100000);
  iota(data.begin(), data.end(), 1); // data を 1, 2 ... 99999 で埋める

  size_t count = count_seq(data.begin(), data.end(), judge); 
  cout << count << " primes found.\n";
}

#pragma once
#include <chrono>

template<typename Function>
long long measure(Function fun, int repeat =1) {
  using namespace std::chrono;
  auto start = high_resolution_clock::now();
  while ( repeat-- ) fun();
  auto stop = high_resolution_clock::now();
  return duration_cast<microseconds>(stop - start).count();
}

#include "prime_judge.h"
#include "measure.h"

#include <iostream>
#include <iomanip>
#include <numeric>
#include <algorithm>

/*
 * 順次処理
 */
template<typename Iterator>
size_t count_seq(Iterator first, Iterator last, const prime_judge& judge) {
  return std::count_if(first, last, judge);
}

/*
 * 自前でスレッド分割
 */
#include <thread>
#include <future>
#include <iterator>

template<typename Iterator>
size_t count_par_byhand(Iterator first, Iterator last, const prime_judge& judge) {
  // 物理的に並行動作可能なスレッド数
  unsigned int num_threads = std::thread::hardware_concurrency();

  // 1つのスレッドが受け持つtask数
  size_t step = std::distance(first, last) / num_threads;

  std::vector<std::future<size_t>> futures(num_threads);
  auto count_prime = [&](Iterator f, Iterator l) -> size_t {
                       return std::count_if(f, l, judge);
                     };

  Iterator tfirst = first;
  Iterator tlast;
  for ( unsigned int i = 0; i < num_threads; ++i ) {
    tlast = ( i+1 == num_threads ) ? last : std::next(tfirst, step);
    futures[i] = std::async(count_prime, tfirst, tlast); // スレッド起動
    tfirst = tlast;
  }

  // 各スレッドで求めた数を積算する
  size_t count = 0;
  for ( auto& fut : futures ) { 
    count += fut.get(); 
  }
  return count;
}

/*
 * Parallel Patterns Library
 */
#include <ppl.h>
#include <atomic>

template<typename Iterator>
size_t count_par_ppl(Iterator first, Iterator last, const prime_judge& judge) {
  std::atomic<size_t> count = 0;
  concurrency::parallel_for_each(first, last, 
                                 [&](int n) { // nが素数ならcount+1
                                   if ( judge(n) ) {
                                     ++count;
                                   }
                                 });
  return count;
}

/*
 * C++17 parallel algorithms
 */
#include <execution>

template<typename Iterator>
size_t count_par_cpp17(Iterator first, Iterator last, const prime_judge& judge) {
  return count_if(std::execution::par, first, last, judge);
}

/*--------------------------------------------------*/

void run() {
  using namespace std;
  prime_judge judge(1000);

  vector<int> data(100000);
  iota(data.begin(), data.end(), 1);

  size_t count;
  long long par_dur;
  long long seq_dur;
  auto percent_change = [](long long o, long long n) { return (o-n)*100/n; };

  cout << "sequential:             ";
  seq_dur = 
    measure([&]() { 
              count = count_seq(data.begin(), data.end(), judge); 
            });
  cout << count << " primes found in " << seq_dur << "[us]\n";

  cout << "parallelism by hand:    ";
  par_dur = measure([&]() { 
                      count = count_par_byhand(data.begin(), data.end(), judge); 
                    });
  cout << count << " primes found in " << par_dur << "[us] " 
       << setw(3) << percent_change(seq_dur, par_dur) << "%\n";

  cout << "Parallel Patterns Lib.: ";
  par_dur = measure([&]() { 
                      count = count_par_ppl(data.begin(), data.end(), judge); 
                    });
  cout << count << " primes found in " << par_dur << "[us] " 
       << setw(3) << percent_change(seq_dur, par_dur) << "%\n";

  cout << "c++17 parallel algo.:   ";
  par_dur = measure([&]() { 
                      count = count_par_cpp17(data.begin(), data.end(), judge); 
                    });
  cout << count << " primes found in " << par_dur << "[us] " 
       << setw(3) << percent_change(seq_dur, par_dur) << "%\n";

  cout << endl;
}

int main() {
  run(); run(); run(); run(); run();
  run(); run(); run(); run(); run();
}