folly/gen/test/ParallelBenchmark.cpp

   1 /*
   2  * Copyright 2014-present 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 <array>
  18 #include <future>
  19 #include <iostream>
  20 #include <vector>
  21
  22 #include <glog/logging.h>
  23
  24 #include <folly/gen/Base.h>
  25 #include <folly/gen/Parallel.h>
  26 #include <folly/gen/test/Bench.h>
  27
  28
  29 DEFINE_int32(threads,
  30              std::max(1, (int32_t) sysconf(_SC_NPROCESSORS_CONF) / 2),
  31              "Num threads.");
  32
  33 using namespace folly::gen;
  34 using std::vector;
  35
  36
  37 constexpr int kFib = 28;  // unit of work
  38 size_t fib(int n) { return n <= 1 ? 1 : fib(n - 1) + fib(n - 2); }
  39
  40 static auto isPrimeSlow = [](int n) {
  41   if (n < 2) {
  42     return false;
  43   } else if (n > 2) {
  44     for (int d = 3; d * d <= n; d += 2) {
  45       if (0 == n % d) {
  46         return false;
  47       }
  48     }
  49   }
  50   return true;
  51 };
  52
  53 static auto primes =
  54     seq(1, 1 << 20) | filter(isPrimeSlow) | as<vector>();
  55
  56 static auto isPrime = [](int n) {
  57   return from(primes)
  58          | until([&](int d) { return d * d > n; })
  59          | filter([&](int d) { return 0 == n % d; })
  60          | isEmpty;
  61 };
  62
  63 static auto factors = [](int n) {
  64   return from(primes)
  65        | until([&](int d) { return d * d > n; })
  66        | filter([&](int d) { return 0 == n % d; })
  67        | count;
  68 };
  69
  70 static auto factorsSlow = [](int n) {
  71   return from(primes)
  72        | filter([&](int d) { return 0 == n % d; })
  73        | count;
  74 };
  75
  76 static auto sleepyWork = [](int i) {
  77   const auto sleepyTime = std::chrono::microseconds(100);
  78   std::this_thread::sleep_for(sleepyTime);
  79   return i;
  80 };
  81
  82 static auto sleepAndWork = [](int i) {
  83   return factorsSlow(i) + sleepyWork(i);
  84 };
  85
  86 auto start = 1 << 20;
  87 auto v = seq(start) | take(1 << 20) | as<vector>();
  88 auto small = from(v) | take(1 << 12);
  89 auto medium = from(v) | take(1 << 14);
  90 auto large = from(v) | take(1 << 18);
  91 auto huge = from(v);
  92 auto chunks = chunked(v);
  93
  94 BENCH_GEN(small | map(factorsSlow) | sum);
  95 BENCH_GEN_REL(small | parallel(map(factorsSlow)) | sum);
  96 BENCHMARK_DRAW_LINE();
  97
  98 BENCH_GEN(small | map(factors) | sum);
  99 BENCH_GEN_REL(small | parallel(map(factors)) | sum);
 100 BENCHMARK_DRAW_LINE();
 101
 102 BENCH_GEN(large | map(factors) | sum);
 103 BENCH_GEN_REL(large | parallel(map(factors)) | sum);
 104 BENCHMARK_DRAW_LINE();
 105
 106 auto ch = chunks;
 107 auto cat = concat;
 108 BENCH_GEN(huge | filter(isPrime) | count);
 109 BENCH_GEN_REL(ch | cat | filter(isPrime) | count);
 110 BENCH_GEN_REL(ch | parallel(cat | filter(isPrime)) | count);
 111 BENCH_GEN_REL(ch | parallel(cat | filter(isPrime) | sub(count)) | sum);
 112 BENCHMARK_DRAW_LINE();
 113
 114 BENCH_GEN(small | map(sleepAndWork) | sum);
 115 BENCH_GEN_REL(small | parallel(map(sleepAndWork)) | sum);
 116 BENCHMARK_DRAW_LINE();
 117
 118 const int fibs = 1000;
 119 BENCH_GEN(seq(1, fibs) | map([](int) { return fib(kFib); }) | sum);
 120 BENCH_GEN_REL(seq(1, fibs) |
 121               parallel(map([](int) { return fib(kFib); }) | sub(sum)) | sum);
 122 BENCH_GEN_REL([] {
 123   auto threads = seq(1, int(FLAGS_threads))
 124                | map([](int i) {
 125                    return std::thread([=] {
 126                      return range((i + 0) * fibs / FLAGS_threads,
 127                                   (i + 1) * fibs / FLAGS_threads) |
 128                             map([](int) { return fib(kFib); }) | sum;
 129                    });
 130                  })
 131                | as<vector>();
 132   from(threads) | [](std::thread &thread) { thread.join(); };
 133   return 1;
 134 }());
 135 BENCHMARK_DRAW_LINE();
 136
 137 #if 0
 138 ============================================================================
 139 folly/gen/test/ParallelBenchmark.cpp            relative  time/iter  iters/s
 140 ============================================================================
 141 small | map(factorsSlow) | sum                                4.59s  217.87m
 142 small | parallel(map(factorsSlow)) | sum        1588.86%   288.88ms     3.46
 143 ----------------------------------------------------------------------------
 144 small | map(factors) | sum                                   9.62ms   103.94
 145 small | parallel(map(factors)) | sum              89.15%    10.79ms    92.66
 146 ----------------------------------------------------------------------------
 147 large | map(factors) | sum                                 650.52ms     1.54
 148 large | parallel(map(factors)) | sum              53.82%      1.21s  827.41m
 149 ----------------------------------------------------------------------------
 150 huge | filter(isPrime) | count                             295.93ms     3.38
 151 ch | cat | filter(isPrime) | count                99.76%   296.64ms     3.37
 152 ch | parallel(cat | filter(isPrime)) | count     142.75%   207.31ms     4.82
 153 ch | parallel(cat | filter(isPrime) | sub(count 1538.50%    19.24ms    51.99
 154 ----------------------------------------------------------------------------
 155 small | map(sleepAndWork) | sum                               5.37s  186.18m
 156 small | parallel(map(sleepAndWork)) | sum       1840.38%   291.85ms     3.43
 157 ----------------------------------------------------------------------------
 158 seq(1, fibs) | map([](int) { return fib(kFib);                1.49s  669.53m
 159 seq(1, fibs) | parallel(map([](int) { return fi 1698.07%    87.96ms    11.37
 160 [] { auto threads = seq(1, int(FLAGS_threads))  1571.16%    95.06ms    10.52
 161 ----------------------------------------------------------------------------
 162 ============================================================================
 163 #endif
 164 int main(int argc, char *argv[]) {
 165   gflags::ParseCommandLineFlags(&argc, &argv, true);
 166   folly::runBenchmarks();
 167   return 0;
 168 }