folly/gen/test/BaseBenchmark.cpp

   1 /*
   2  * Copyright 2017 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 <atomic>
  18
  19 #include <glog/logging.h>
  20
  21 #include <folly/Benchmark.h>
  22 #include <folly/gen/Base.h>
  23
  24 using namespace folly::gen;
  25 using folly::fbstring;
  26 using std::pair;
  27 using std::set;
  28 using std::vector;
  29 using std::tuple;
  30
  31 static std::atomic<int> testSize(1000);
  32 static vector<int> testVector =
  33     seq(1, testSize.load())
  34   | mapped([](int) { return rand(); })
  35   | as<vector>();
  36
  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 static vector<fbstring> strings =
  44     from(testVector)
  45   | eachTo<fbstring>()
  46   | as<vector>();
  47
  48 auto square = [](int x) { return x * x; };
  49
  50 BENCHMARK(Sum_Basic_NoGen, iters) {
  51   int limit = testSize.load();
  52   int s = 0;
  53   while (iters--) {
  54     for (int i = 0; i < limit; ++i) {
  55       s += i;
  56     }
  57   }
  58   folly::doNotOptimizeAway(s);
  59 }
  60
  61 BENCHMARK_RELATIVE(Sum_Basic_Gen, iters) {
  62   int limit = testSize.load();
  63   int s = 0;
  64   while (iters--) {
  65     s += range(0, limit) | sum;
  66   }
  67   folly::doNotOptimizeAway(s);
  68 }
  69
  70 BENCHMARK_DRAW_LINE()
  71
  72 BENCHMARK(Sum_Vector_NoGen, iters) {
  73   int s = 0;
  74   while (iters--) {
  75     for (auto& i : testVector) {
  76       s += i;
  77     }
  78   }
  79   folly::doNotOptimizeAway(s);
  80 }
  81
  82 BENCHMARK_RELATIVE(Sum_Vector_Gen, iters) {
  83   int s = 0;
  84   while (iters--) {
  85     s += from(testVector) | sum;
  86   }
  87   folly::doNotOptimizeAway(s);
  88 }
  89
  90 BENCHMARK_DRAW_LINE()
  91
  92 BENCHMARK(Member, iters) {
  93   int s = 0;
  94   while(iters--) {
  95     s += from(strings)
  96        | member(&fbstring::size)
  97        | sum;
  98   }
  99   folly::doNotOptimizeAway(s);
 100 }
 101
 102 BENCHMARK_RELATIVE(MapMember, iters) {
 103   int s = 0;
 104   while(iters--) {
 105     s += from(strings)
 106        | map([](const fbstring& x) { return x.size(); })
 107        | sum;
 108   }
 109   folly::doNotOptimizeAway(s);
 110 }
 111
 112 BENCHMARK_DRAW_LINE()
 113
 114 BENCHMARK(Count_Vector_NoGen, iters) {
 115   int s = 0;
 116   while (iters--) {
 117     for (auto& i : testVector) {
 118       if (i * 2 < rand()) {
 119         ++s;
 120       }
 121     }
 122   }
 123   folly::doNotOptimizeAway(s);
 124 }
 125
 126 BENCHMARK_RELATIVE(Count_Vector_Gen, iters) {
 127   int s = 0;
 128   while (iters--) {
 129     s += from(testVector)
 130        | filter([](int i) {
 131                   return i * 2 < rand();
 132                 })
 133        | count;
 134   }
 135   folly::doNotOptimizeAway(s);
 136 }
 137
 138 BENCHMARK_DRAW_LINE()
 139
 140 BENCHMARK(Fib_Sum_NoGen, iters) {
 141   int s = 0;
 142   while (iters--) {
 143     auto fib = [](size_t limit) -> vector<int> {
 144       vector<int> ret;
 145       int a = 0;
 146       int b = 1;
 147       for (size_t i = 0; i < limit; i += 2) {
 148         ret.push_back(a += b);
 149         ret.push_back(b += a);
 150       }
 151       return ret;
 152     };
 153     for (auto& v : fib(testSize.load())) {
 154       s += v;
 155     }
 156   }
 157   folly::doNotOptimizeAway(s);
 158 }
 159
 160 BENCHMARK_RELATIVE(Fib_Sum_Gen, iters) {
 161   int s = 0;
 162   while (iters--) {
 163     auto fib = GENERATOR(int) {
 164       int a = 0;
 165       int b = 1;
 166       for (;;) {
 167         yield(a += b);
 168         yield(b += a);
 169       }
 170     };
 171     // Early stopping implemented with exceptions.
 172     s += fib | take(testSize.load()) | sum;
 173   }
 174   folly::doNotOptimizeAway(s);
 175 }
 176
 177 BENCHMARK_RELATIVE(Fib_Sum_Gen_Limit, iters) {
 178   int s = 0;
 179   while (iters--) {
 180     size_t limit = testSize.load();
 181     auto fib = GENERATOR(int) {
 182       int a = 0;
 183       int b = 1;
 184       for (size_t i = 0; i < limit; i += 2) {
 185         yield(a += b);
 186         yield(b += a);
 187       }
 188     };
 189     // No early stopping.
 190     s += fib | sum;
 191   }
 192   folly::doNotOptimizeAway(s);
 193 }
 194
 195 struct FibYielder {
 196   template <class Yield>
 197   void operator()(Yield&& yield) const {
 198     int a = 0;
 199     int b = 1;
 200     for (;;) {
 201       yield(a += b);
 202       yield(b += a);
 203     }
 204   }
 205 };
 206
 207 BENCHMARK_RELATIVE(Fib_Sum_Gen_Static, iters) {
 208   int s = 0;
 209   while (iters--) {
 210     auto fib = generator<int>(FibYielder());
 211     s += fib | take(testSize.load()) | sum;
 212   }
 213   folly::doNotOptimizeAway(s);
 214 }
 215
 216 BENCHMARK_DRAW_LINE()
 217
 218 BENCHMARK(VirtualGen_0Virtual, iters) {
 219   int s = 0;
 220   while (iters--) {
 221     auto numbers = seq(1, 10000);
 222     auto squares = numbers | map(square);
 223     auto quads = squares | map(square);
 224     s += quads | sum;
 225   }
 226   folly::doNotOptimizeAway(s);
 227 }
 228
 229 BENCHMARK_RELATIVE(VirtualGen_1Virtual, iters) {
 230   int s = 0;
 231   while (iters--) {
 232     VirtualGen<int> numbers = seq(1, 10000);
 233     auto squares = numbers | map(square);
 234     auto quads = squares | map(square);
 235     s += quads | sum;
 236   }
 237   folly::doNotOptimizeAway(s);
 238 }
 239
 240 BENCHMARK_RELATIVE(VirtualGen_2Virtual, iters) {
 241   int s = 0;
 242   while (iters--) {
 243     VirtualGen<int> numbers = seq(1, 10000);
 244     VirtualGen<int> squares = numbers | map(square);
 245     auto quads = squares | map(square);
 246     s += quads | sum;
 247   }
 248   folly::doNotOptimizeAway(s);
 249 }
 250
 251 BENCHMARK_RELATIVE(VirtualGen_3Virtual, iters) {
 252   int s = 0;
 253   while (iters--) {
 254     VirtualGen<int> numbers = seq(1, 10000);
 255     VirtualGen<int> squares = numbers | map(square);
 256     VirtualGen<int> quads = squares | map(square);
 257     s += quads | sum;
 258   }
 259   folly::doNotOptimizeAway(s);
 260 }
 261
 262 BENCHMARK_DRAW_LINE()
 263
 264 BENCHMARK(Concat_NoGen, iters) {
 265   int s = 0;
 266   while (iters--) {
 267     for (auto& v : testVectorVector) {
 268       for (auto& i : v) {
 269         s += i;
 270       }
 271     }
 272   }
 273   folly::doNotOptimizeAway(s);
 274 }
 275
 276 BENCHMARK_RELATIVE(Concat_Gen, iters) {
 277   int s = 0;
 278   while (iters--) {
 279     s += from(testVectorVector) | rconcat | sum;
 280   }
 281   folly::doNotOptimizeAway(s);
 282 }
 283
 284 BENCHMARK_DRAW_LINE()
 285
 286 BENCHMARK(Composed_NoGen, iters) {
 287   int s = 0;
 288   while (iters--) {
 289     for (auto& i : testVector) {
 290       s += i * i;
 291     }
 292   }
 293   folly::doNotOptimizeAway(s);
 294 }
 295
 296 BENCHMARK_RELATIVE(Composed_Gen, iters) {
 297   int s = 0;
 298   auto sumSq = map(square) | sum;
 299   while (iters--) {
 300     s += from(testVector) | sumSq;
 301   }
 302   folly::doNotOptimizeAway(s);
 303 }
 304
 305 BENCHMARK_RELATIVE(Composed_GenRegular, iters) {
 306   int s = 0;
 307   while (iters--) {
 308     s += from(testVector) | map(square) | sum;
 309   }
 310   folly::doNotOptimizeAway(s);
 311 }
 312
 313 BENCHMARK_DRAW_LINE()
 314
 315 BENCHMARK(Sample, iters) {
 316   size_t s = 0;
 317   while (iters--) {
 318     auto sampler = seq(1, 10 * 1000 * 1000) | sample(1000);
 319     s += (sampler | sum);
 320   }
 321   folly::doNotOptimizeAway(s);
 322 }
 323
 324 // Results from an Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz
 325 // ============================================================================
 326 // folly/gen/test/BaseBenchmark.cpp                relative  time/iter  iters/s
 327 // ============================================================================
 328 // Sum_Basic_NoGen                                            372.39ns    2.69M
 329 // Sum_Basic_Gen                                    195.96%   190.03ns    5.26M
 330 // ----------------------------------------------------------------------------
 331 // Sum_Vector_NoGen                                           200.41ns    4.99M
 332 // Sum_Vector_Gen                                    77.14%   259.81ns    3.85M
 333 // ----------------------------------------------------------------------------
 334 // Member                                                       4.56us  219.42K
 335 // MapMember                                        400.47%     1.14us  878.73K
 336 // ----------------------------------------------------------------------------
 337 // Count_Vector_NoGen                                          13.96us   71.64K
 338 // Count_Vector_Gen                                  86.05%    16.22us   61.65K
 339 // ----------------------------------------------------------------------------
 340 // Fib_Sum_NoGen                                                2.21us  452.63K
 341 // Fib_Sum_Gen                                       23.94%     9.23us  108.36K
 342 // Fib_Sum_Gen_Static                                48.77%     4.53us  220.73K
 343 // ----------------------------------------------------------------------------
 344 // VirtualGen_0Virtual                                          9.60us  104.13K
 345 // VirtualGen_1Virtual                               28.00%    34.30us   29.15K
 346 // VirtualGen_2Virtual                               22.62%    42.46us   23.55K
 347 // VirtualGen_3Virtual                               16.96%    56.64us   17.66K
 348 // ----------------------------------------------------------------------------
 349 // Concat_NoGen                                                 2.20us  453.66K
 350 // Concat_Gen                                       109.49%     2.01us  496.70K
 351 // ----------------------------------------------------------------------------
 352 // Composed_NoGen                                             545.32ns    1.83M
 353 // Composed_Gen                                      87.94%   620.07ns    1.61M
 354 // Composed_GenRegular                               88.13%   618.74ns    1.62M
 355 // ----------------------------------------------------------------------------
 356 // Sample                                                     176.48ms     5.67
 357 // ============================================================================
 358
 359 int main(int argc, char *argv[]) {
 360   gflags::ParseCommandLineFlags(&argc, &argv, true);
 361   folly::runBenchmarks();
 362   return 0;
 363 }