folly/gen/test/ParallelBenchmark.cpp

   1 /*
   2  * Copyright 2014 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <glog/logging.h>
  18 #include <iostream>
  19 #include <array>
  20 #include <vector>
  21 #include <future>
  22
  23 #include "folly/gen/Base.h"
  24 #include "folly/gen/Parallel.h"
  25 #include "folly/gen/test/Bench.h"
  26
  27
  28 DEFINE_int32(threads,
  29              std::max(1, (int32_t) sysconf(_SC_NPROCESSORS_CONF) / 2),
  30              "Num threads.");
  31
  32 using namespace folly::gen;
  33 using std::vector;
  34
  35
  36 constexpr int kFib = 28;  // unit of work
  37 size_t fib(int n) { return n <= 1 ? 1 : fib(n - 1) + fib(n - 2); }
  38
  39 static auto add = [](int a, int b) { return a + b; };
  40 static auto mod7 = [](int i) { return i % 7; };
  41
  42 static auto isPrimeSlow = [](int n) {
  43   if (n < 2) {
  44     return false;
  45   } else if (n > 2) {
  46     for (int d = 3; d * d <= n; d += 2) {
  47       if (0 == n % d) {
  48         return false;
  49       }
  50     }
  51   }
  52   return true;
  53 };
  54
  55 static auto primes =
  56     seq(1, 1 << 20) | filter(isPrimeSlow) | as<vector>();
  57
  58 static auto isPrime = [](int n) {
  59   return !(from(primes)
  60          | until([&](int d) { return d * d > n; })
  61          | filter([&](int d) { return 0 == n % d; })
  62          | any);
  63 };
  64
  65 static auto factors = [](int n) {
  66   return from(primes)
  67        | until([&](int d) { return d * d > n; })
  68        | filter([&](int d) { return 0 == n % d; })
  69        | count;
  70 };
  71
  72 static auto factorsSlow = [](int n) {
  73   return from(primes)
  74        | filter([&](int d) { return 0 == n % d; })
  75        | count;
  76 };
  77
  78 static auto sleepyWork = [](int i) {
  79   const auto sleepyTime = std::chrono::microseconds(100);
  80   std::this_thread::sleep_for(sleepyTime);
  81   return i;
  82 };
  83
  84 static auto sleepAndWork = [](int i) {
  85   return factorsSlow(i) + sleepyWork(i);
  86 };
  87
  88 std::mutex block;
  89 static auto workAndBlock = [](int i) {
  90   int r = factorsSlow(i);
  91   {
  92     std::lock_guard<std::mutex> lock(block);
  93     return sleepyWork(i) + r;
  94   }
  95 };
  96
  97 auto start = 1 << 20;
  98 auto v = seq(start) | take(1 << 20) | as<vector>();
  99 auto small = from(v) | take(1 << 12);
 100 auto medium = from(v) | take(1 << 14);
 101 auto large = from(v) | take(1 << 18);
 102 auto huge = from(v);
 103 auto chunks = chunked(v);
 104
 105 BENCH_GEN(small | map(factorsSlow) | sum);
 106 BENCH_GEN_REL(small | parallel(map(factorsSlow)) | sum);
 107 BENCHMARK_DRAW_LINE();
 108
 109 BENCH_GEN(small | map(factors) | sum);
 110 BENCH_GEN_REL(small | parallel(map(factors)) | sum);
 111 BENCHMARK_DRAW_LINE();
 112
 113 BENCH_GEN(large | map(factors) | sum);
 114 BENCH_GEN_REL(large | parallel(map(factors)) | sum);
 115 BENCHMARK_DRAW_LINE();
 116
 117 auto ch = chunks;
 118 auto cat = concat;
 119 BENCH_GEN(huge | filter(isPrime) | count);
 120 BENCH_GEN_REL(ch | cat | filter(isPrime) | count);
 121 BENCH_GEN_REL(ch | parallel(cat | filter(isPrime)) | count);
 122 BENCH_GEN_REL(ch | parallel(cat | filter(isPrime) | sub(count)) | sum);
 123 BENCHMARK_DRAW_LINE();
 124
 125 BENCH_GEN(small | map(sleepAndWork) | sum);
 126 BENCH_GEN_REL(small | parallel(map(sleepAndWork)) | sum);
 127 BENCHMARK_DRAW_LINE();
 128
 129 const int fibs = 1000;
 130 BENCH_GEN(seq(1, fibs) | map([](int) { return fib(kFib); }) | sum);
 131 BENCH_GEN_REL(seq(1, fibs) |
 132               parallel(map([](int) { return fib(kFib); }) | sub(sum)) | sum);
 133 BENCH_GEN_REL([] {
 134   auto threads = seq(1, int(FLAGS_threads))
 135                | map([](int i) {
 136                    return std::thread([=] {
 137                      return range((i + 0) * fibs / FLAGS_threads,
 138                                   (i + 1) * fibs / FLAGS_threads) |
 139                             map([](int) { return fib(kFib); }) | sum;
 140                    });
 141                  })
 142                | as<vector>();
 143   from(threads) | [](std::thread &thread) { thread.join(); };
 144   return 1;
 145 }());
 146 BENCHMARK_DRAW_LINE();
 147
 148 #if 0
 149 ============================================================================
 150 folly/gen/test/ParallelBenchmark.cpp            relative  time/iter  iters/s
 151 ============================================================================
 152 small | map(factorsSlow) | sum                                4.59s  217.87m
 153 small | parallel(map(factorsSlow)) | sum        1588.86%   288.88ms     3.46
 154 ----------------------------------------------------------------------------
 155 small | map(factors) | sum                                   9.62ms   103.94
 156 small | parallel(map(factors)) | sum              89.15%    10.79ms    92.66
 157 ----------------------------------------------------------------------------
 158 large | map(factors) | sum                                 650.52ms     1.54
 159 large | parallel(map(factors)) | sum              53.82%      1.21s  827.41m
 160 ----------------------------------------------------------------------------
 161 huge | filter(isPrime) | count                             295.93ms     3.38
 162 ch | cat | filter(isPrime) | count                99.76%   296.64ms     3.37
 163 ch | parallel(cat | filter(isPrime)) | count     142.75%   207.31ms     4.82
 164 ch | parallel(cat | filter(isPrime) | sub(count 1538.50%    19.24ms    51.99
 165 ----------------------------------------------------------------------------
 166 small | map(sleepAndWork) | sum                               5.37s  186.18m
 167 small | parallel(map(sleepAndWork)) | sum       1840.38%   291.85ms     3.43
 168 ----------------------------------------------------------------------------
 169 seq(1, fibs) | map([](int) { return fib(kFib);                1.49s  669.53m
 170 seq(1, fibs) | parallel(map([](int) { return fi 1698.07%    87.96ms    11.37
 171 [] { auto threads = seq(1, int(FLAGS_threads))  1571.16%    95.06ms    10.52
 172 ----------------------------------------------------------------------------
 173 ============================================================================
 174 #endif
 175 int main(int argc, char *argv[]) {
 176   google::ParseCommandLineFlags(&argc, &argv, true);
 177   folly::runBenchmarks();
 178   return 0;
 179 }