folly/experimental/test/GenBenchmark.cpp

   1 /*
   2  * Copyright 2012 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 "folly/experimental/Gen.h"
  18
  19 #include <glog/logging.h>
  20 #include <atomic>
  21
  22 #include "folly/Benchmark.h"
  23
  24 using namespace folly;
  25 using namespace folly::gen;
  26 using std::ostream;
  27 using std::pair;
  28 using std::set;
  29 using std::vector;
  30 using std::tuple;
  31
  32 static std::atomic<int> testSize(1000);
  33 static vector<int> testVector =
  34     seq(1, testSize.load())
  35   | mapped([](int) { return rand(); })
  36   | as<vector>();
  37 static vector<vector<int>> testVectorVector =
  38     seq(1, 100)
  39   | map([](int i) {
  40       return seq(1, i) | as<vector>();
  41     })
  42   | as<vector>();
  43
  44 auto square = [](int x) { return x * x; };
  45 auto add = [](int a, int b) { return a + b; };
  46 auto multiply = [](int a, int b) { return a * b; };
  47
  48 BENCHMARK(Sum_Basic_NoGen, iters) {
  49   int limit = testSize.load();
  50   int s = 0;
  51   while (iters--) {
  52     for (int i = 0; i < limit; ++i) {
  53       s += i;
  54     }
  55   }
  56   folly::doNotOptimizeAway(s);
  57 }
  58
  59 BENCHMARK_RELATIVE(Sum_Basic_Gen, iters) {
  60   int limit = testSize.load();
  61   int s = 0;
  62   while (iters--) {
  63     s += range(0, limit) | sum;
  64   }
  65   folly::doNotOptimizeAway(s);
  66 }
  67
  68 BENCHMARK_DRAW_LINE()
  69
  70 BENCHMARK(Sum_Vector_NoGen, iters) {
  71   int s = 0;
  72   while (iters--) {
  73     for (auto& i : testVector) {
  74       s += i;
  75     }
  76   }
  77   folly::doNotOptimizeAway(s);
  78 }
  79
  80 BENCHMARK_RELATIVE(Sum_Vector_Gen, iters) {
  81   int s = 0;
  82   while (iters--) {
  83     s += from(testVector) | sum;
  84   }
  85   folly::doNotOptimizeAway(s);
  86 }
  87
  88 BENCHMARK_DRAW_LINE()
  89
  90 BENCHMARK(Count_Vector_NoGen, iters) {
  91   int s = 0;
  92   while (iters--) {
  93     for (auto& i : testVector) {
  94       if (i * 2 < rand()) {
  95         ++s;
  96       }
  97     }
  98   }
  99   folly::doNotOptimizeAway(s);
 100 }
 101
 102 BENCHMARK_RELATIVE(Count_Vector_Gen, iters) {
 103   int s = 0;
 104   while (iters--) {
 105     s += from(testVector)
 106        | filter([](int i) {
 107                   return i * 2 < rand();
 108                 })
 109        | count;
 110   }
 111   folly::doNotOptimizeAway(s);
 112 }
 113
 114 BENCHMARK_DRAW_LINE()
 115
 116 BENCHMARK(Fib_Sum_NoGen, iters) {
 117   int s = 0;
 118   while (iters--) {
 119     auto fib = [](int limit) -> vector<int> {
 120       vector<int> ret;
 121       int a = 0;
 122       int b = 1;
 123       for (int i = 0; i * 2 < limit; ++i) {
 124         ret.push_back(a += b);
 125         ret.push_back(b += a);
 126       }
 127       return ret;
 128     };
 129     for (auto& v : fib(testSize.load())) {
 130       s += v;
 131       v = s;
 132     }
 133   }
 134   folly::doNotOptimizeAway(s);
 135 }
 136
 137 BENCHMARK_RELATIVE(Fib_Sum_Gen, iters) {
 138   int s = 0;
 139   while (iters--) {
 140     auto fib = GENERATOR(int, {
 141       int a = 0;
 142       int b = 1;
 143       for (;;) {
 144         yield(a += b);
 145         yield(b += a);
 146       }
 147     });
 148     s += fib | take(testSize.load()) | sum;
 149   }
 150   folly::doNotOptimizeAway(s);
 151 }
 152
 153 struct FibYielder {
 154   template<class Yield>
 155   void operator()(Yield&& yield) const {
 156     int a = 0;
 157     int b = 1;
 158     for (;;) {
 159       yield(a += b);
 160       yield(b += a);
 161     }
 162   }
 163 };
 164
 165 BENCHMARK_RELATIVE(Fib_Sum_Gen_Static, iters) {
 166   int s = 0;
 167   while (iters--) {
 168     auto fib = generator<int>(FibYielder());
 169     s += fib | take(30) | sum;
 170   }
 171   folly::doNotOptimizeAway(s);
 172 }
 173
 174 BENCHMARK_DRAW_LINE()
 175
 176 BENCHMARK(VirtualGen_0Virtual, iters) {
 177   int s = 0;
 178   while (iters--) {
 179     auto numbers = seq(1, 10000);
 180     auto squares = numbers | map(square);
 181     auto quads = squares | map(square);
 182     s += quads | sum;
 183   }
 184   folly::doNotOptimizeAway(s);
 185 }
 186
 187 BENCHMARK_RELATIVE(VirtualGen_1Virtual, iters) {
 188   int s = 0;
 189   while (iters--) {
 190     VirtualGen<int> numbers = seq(1, 10000);
 191     auto squares = numbers | map(square);
 192     auto quads = squares | map(square);
 193     s += quads | sum;
 194   }
 195   folly::doNotOptimizeAway(s);
 196 }
 197
 198 BENCHMARK_RELATIVE(VirtualGen_2Virtual, iters) {
 199   int s = 0;
 200   while (iters--) {
 201     VirtualGen<int> numbers = seq(1, 10000);
 202     VirtualGen<int> squares = numbers | map(square);
 203     auto quads = squares | map(square);
 204     s += quads | sum;
 205   }
 206   folly::doNotOptimizeAway(s);
 207 }
 208
 209 BENCHMARK_RELATIVE(VirtualGen_3Virtual, iters) {
 210   int s = 0;
 211   while (iters--) {
 212     VirtualGen<int> numbers = seq(1, 10000);
 213     VirtualGen<int> squares = numbers | map(square);
 214     VirtualGen<int> quads = squares | map(square);
 215     s += quads | sum;
 216   }
 217   folly::doNotOptimizeAway(s);
 218 }
 219
 220 BENCHMARK_DRAW_LINE()
 221
 222 BENCHMARK(Concat_NoGen, iters) {
 223   int s = 0;
 224   while (iters--) {
 225     for (auto& v : testVectorVector) {
 226       for (auto& i : v) {
 227         s += i;
 228       }
 229     }
 230   }
 231   folly::doNotOptimizeAway(s);
 232 }
 233
 234 BENCHMARK_RELATIVE(Concat_Gen, iters) {
 235   int s = 0;
 236   while (iters--) {
 237     s += from(testVectorVector) | rconcat | sum;
 238   }
 239   folly::doNotOptimizeAway(s);
 240 }
 241
 242 // Results from a dual core Xeon L5520 @ 2.27GHz:
 243 //
 244 // ============================================================================
 245 // folly/experimental/test/GenBenchmark.cpp        relative  time/iter  iters/s
 246 // ============================================================================
 247 // Sum_Basic_NoGen                                            301.60ns    3.32M
 248 // Sum_Basic_Gen                                    103.20%   292.24ns    3.42M
 249 // ----------------------------------------------------------------------------
 250 // Sum_Vector_NoGen                                           200.33ns    4.99M
 251 // Sum_Vector_Gen                                    99.44%   201.45ns    4.96M
 252 // ----------------------------------------------------------------------------
 253 // Count_Vector_NoGen                                          19.07fs   52.43T
 254 // Count_Vector_Gen                                 166.67%    11.44fs   87.38T
 255 // ----------------------------------------------------------------------------
 256 // Fib_Sum_NoGen                                                4.15us  241.21K
 257 // Fib_Sum_Gen                                       48.75%     8.50us  117.58K
 258 // Fib_Sum_Gen_Static                               113.24%     3.66us  273.16K
 259 // ----------------------------------------------------------------------------
 260 // VirtualGen_0Virtual                                         10.05us   99.48K
 261 // VirtualGen_1Virtual                               29.63%    33.93us   29.47K
 262 // VirtualGen_2Virtual                               20.47%    49.09us   20.37K
 263 // VirtualGen_3Virtual                               15.30%    65.68us   15.23K
 264 // ----------------------------------------------------------------------------
 265 // Concat_NoGen                                                 2.34us  427.15K
 266 // Concat_Gen                                        90.04%     2.60us  384.59K
 267 // ============================================================================
 268
 269 int main(int argc, char *argv[]) {
 270   google::ParseCommandLineFlags(&argc, &argv, true);
 271   runBenchmarks();
 272   return 0;
 273 }