8.7 Multithreading

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

/*

Basic multithreading can speed up independent local work such as stress tests, batch experiments, or
offline preprocessing. It is rarely useful in standard contest submissions, and many judges restrict
threads, so use it only when the environment allows it.

- `parallel_for(n, threads, f)` runs `f(i)` once for each `0 <= i < n`, splitting the indices among
  at most `threads` worker threads.
- `parallel_cases(cases, threads, solve)` solves independent test cases in parallel and returns the
  outputs in the original case order.

Each call to `f(i)` must be safe to run concurrently with the others. If it writes shared state, use
separate output slots or synchronization.

*/

#include <algorithm>
#include <cassert>
#include <numeric>
#include <sstream>
#include <string>
#include <thread>
#include <vector>

template<class Fun>
void parallel_for(int n, int threads, Fun f) {
  threads = std::max(1, std::min(threads, n));
  std::vector<std::thread> workers;
  workers.reserve(threads);
  for (int id = 0; id < threads; ++id) {
    workers.emplace_back([=, &f] {
      for (int i = id; i < n; i += threads) {
        f(i);
      }
    });
  }
  for (auto &worker : workers) {
    worker.join();
  }
}

template<class Case, class Solve>
std::vector<std::string> parallel_cases(const std::vector<Case> &cases, int threads, Solve solve) {
  std::vector<std::string> out(cases.size());
  parallel_for(static_cast<int>(cases.size()), threads, [&](int i) {
    std::ostringstream os;
    solve(cases[i], os);
    out[i] = os.str();
  });
  return out;
}

/*** Example Usage ***/

int main() {
  std::vector<long long> squares(1000);
  parallel_for(static_cast<int>(squares.size()), 4, [&](int i) { squares[i] = 1LL * i * i; });
  assert(squares[17] == 289);
  assert(std::accumulate(squares.begin(), squares.end(), 0LL) == 332833500);

  std::vector<int> cases = {3, 1, 4, 2};
  auto out =
      parallel_cases(cases, 2, [](int x, std::ostringstream &os) { os << x << "^2 = " << x * x; });
  assert((out == std::vector<std::string>{"3^2 = 9", "1^2 = 1", "4^2 = 16", "2^2 = 4"}));
  return 0;
}