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 = [](int limit) -> vector<int> {
 144       vector<int> ret;
 145       int a = 0;
 146       int b = 1;
 147       for (int i = 0; i * 2 < limit; ++i) {
 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     s += fib | take(testSize.load()) | sum;
 172   }
 173   folly::doNotOptimizeAway(s);
 174 }
 175
 176 struct FibYielder {
 177   template <class Yield>
 178   void operator()(Yield&& yield) const {
 179     int a = 0;
 180     int b = 1;
 181     for (;;) {
 182       yield(a += b);
 183       yield(b += a);
 184     }
 185   }
 186 };
 187
 188 BENCHMARK_RELATIVE(Fib_Sum_Gen_Static, iters) {
 189   int s = 0;
 190   while (iters--) {
 191     auto fib = generator<int>(FibYielder());
 192     s += fib | take(testSize.load()) | sum;
 193   }
 194   folly::doNotOptimizeAway(s);
 195 }
 196
 197 BENCHMARK_DRAW_LINE()
 198
 199 BENCHMARK(VirtualGen_0Virtual, iters) {
 200   int s = 0;
 201   while (iters--) {
 202     auto numbers = seq(1, 10000);
 203     auto squares = numbers | map(square);
 204     auto quads = squares | map(square);
 205     s += quads | sum;
 206   }
 207   folly::doNotOptimizeAway(s);
 208 }
 209
 210 BENCHMARK_RELATIVE(VirtualGen_1Virtual, iters) {
 211   int s = 0;
 212   while (iters--) {
 213     VirtualGen<int> numbers = seq(1, 10000);
 214     auto squares = numbers | map(square);
 215     auto quads = squares | map(square);
 216     s += quads | sum;
 217   }
 218   folly::doNotOptimizeAway(s);
 219 }
 220
 221 BENCHMARK_RELATIVE(VirtualGen_2Virtual, iters) {
 222   int s = 0;
 223   while (iters--) {
 224     VirtualGen<int> numbers = seq(1, 10000);
 225     VirtualGen<int> squares = numbers | map(square);
 226     auto quads = squares | map(square);
 227     s += quads | sum;
 228   }
 229   folly::doNotOptimizeAway(s);
 230 }
 231
 232 BENCHMARK_RELATIVE(VirtualGen_3Virtual, iters) {
 233   int s = 0;
 234   while (iters--) {
 235     VirtualGen<int> numbers = seq(1, 10000);
 236     VirtualGen<int> squares = numbers | map(square);
 237     VirtualGen<int> quads = squares | map(square);
 238     s += quads | sum;
 239   }
 240   folly::doNotOptimizeAway(s);
 241 }
 242
 243 BENCHMARK_DRAW_LINE()
 244
 245 BENCHMARK(Concat_NoGen, iters) {
 246   int s = 0;
 247   while (iters--) {
 248     for (auto& v : testVectorVector) {
 249       for (auto& i : v) {
 250         s += i;
 251       }
 252     }
 253   }
 254   folly::doNotOptimizeAway(s);
 255 }
 256
 257 BENCHMARK_RELATIVE(Concat_Gen, iters) {
 258   int s = 0;
 259   while (iters--) {
 260     s += from(testVectorVector) | rconcat | sum;
 261   }
 262   folly::doNotOptimizeAway(s);
 263 }
 264
 265 BENCHMARK_DRAW_LINE()
 266
 267 BENCHMARK(Composed_NoGen, iters) {
 268   int s = 0;
 269   while (iters--) {
 270     for (auto& i : testVector) {
 271       s += i * i;
 272     }
 273   }
 274   folly::doNotOptimizeAway(s);
 275 }
 276
 277 BENCHMARK_RELATIVE(Composed_Gen, iters) {
 278   int s = 0;
 279   auto sumSq = map(square) | sum;
 280   while (iters--) {
 281     s += from(testVector) | sumSq;
 282   }
 283   folly::doNotOptimizeAway(s);
 284 }
 285
 286 BENCHMARK_RELATIVE(Composed_GenRegular, iters) {
 287   int s = 0;
 288   while (iters--) {
 289     s += from(testVector) | map(square) | sum;
 290   }
 291   folly::doNotOptimizeAway(s);
 292 }
 293
 294 BENCHMARK_DRAW_LINE()
 295
 296 BENCHMARK(Sample, iters) {
 297   size_t s = 0;
 298   while (iters--) {
 299     auto sampler = seq(1, 10 * 1000 * 1000) | sample(1000);
 300     s += (sampler | sum);
 301   }
 302   folly::doNotOptimizeAway(s);
 303 }
 304
 305 // Results from an Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz
 306 // ============================================================================
 307 // folly/gen/test/BaseBenchmark.cpp                relative  time/iter  iters/s
 308 // ============================================================================
 309 // Sum_Basic_NoGen                                            372.39ns    2.69M
 310 // Sum_Basic_Gen                                    195.96%   190.03ns    5.26M
 311 // ----------------------------------------------------------------------------
 312 // Sum_Vector_NoGen                                           200.41ns    4.99M
 313 // Sum_Vector_Gen                                    77.14%   259.81ns    3.85M
 314 // ----------------------------------------------------------------------------
 315 // Member                                                       4.56us  219.42K
 316 // MapMember                                        400.47%     1.14us  878.73K
 317 // ----------------------------------------------------------------------------
 318 // Count_Vector_NoGen                                          13.96us   71.64K
 319 // Count_Vector_Gen                                  86.05%    16.22us   61.65K
 320 // ----------------------------------------------------------------------------
 321 // Fib_Sum_NoGen                                                2.21us  452.63K
 322 // Fib_Sum_Gen                                       23.94%     9.23us  108.36K
 323 // Fib_Sum_Gen_Static                                48.77%     4.53us  220.73K
 324 // ----------------------------------------------------------------------------
 325 // VirtualGen_0Virtual                                          9.60us  104.13K
 326 // VirtualGen_1Virtual                               28.00%    34.30us   29.15K
 327 // VirtualGen_2Virtual                               22.62%    42.46us   23.55K
 328 // VirtualGen_3Virtual                               16.96%    56.64us   17.66K
 329 // ----------------------------------------------------------------------------
 330 // Concat_NoGen                                                 2.20us  453.66K
 331 // Concat_Gen                                       109.49%     2.01us  496.70K
 332 // ----------------------------------------------------------------------------
 333 // Composed_NoGen                                             545.32ns    1.83M
 334 // Composed_Gen                                      87.94%   620.07ns    1.61M
 335 // Composed_GenRegular                               88.13%   618.74ns    1.62M
 336 // ----------------------------------------------------------------------------
 337 // Sample                                                     176.48ms     5.67
 338 // ============================================================================
 339
 340 int main(int argc, char *argv[]) {
 341   gflags::ParseCommandLineFlags(&argc, &argv, true);
 342   folly::runBenchmarks();
 343   return 0;
 344 }