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