third-party/folly/src/folly/gen/test/BaseBenchmark.cpp

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