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 #include "folly/experimental/StringGen.h"
  19 #include "folly/experimental/FileGen.h"
  20 #include "folly/String.h"
  21
  22 #include <atomic>
  23 #include <thread>
  24
  25 #include <glog/logging.h>
  26
  27 #include "folly/Benchmark.h"
  28
  29 using namespace folly;
  30 using namespace folly::gen;
  31 using std::ostream;
  32 using std::pair;
  33 using std::set;
  34 using std::vector;
  35 using std::tuple;
  36
  37 static std::atomic<int> testSize(1000);
  38 static vector<int> testVector =
  39     seq(1, testSize.load())
  40   | mapped([](int) { return rand(); })
  41   | as<vector>();
  42 static vector<vector<int>> testVectorVector =
  43     seq(1, 100)
  44   | map([](int i) {
  45       return seq(1, i) | as<vector>();
  46     })
  47   | as<vector>();
  48
  49 auto square = [](int x) { return x * x; };
  50 auto add = [](int a, int b) { return a + b; };
  51 auto multiply = [](int a, int b) { return a * b; };
  52
  53 BENCHMARK(Sum_Basic_NoGen, iters) {
  54   int limit = testSize.load();
  55   int s = 0;
  56   while (iters--) {
  57     for (int i = 0; i < limit; ++i) {
  58       s += i;
  59     }
  60   }
  61   folly::doNotOptimizeAway(s);
  62 }
  63
  64 BENCHMARK_RELATIVE(Sum_Basic_Gen, iters) {
  65   int limit = testSize.load();
  66   int s = 0;
  67   while (iters--) {
  68     s += range(0, limit) | sum;
  69   }
  70   folly::doNotOptimizeAway(s);
  71 }
  72
  73 BENCHMARK_DRAW_LINE()
  74
  75 BENCHMARK(Sum_Vector_NoGen, iters) {
  76   int s = 0;
  77   while (iters--) {
  78     for (auto& i : testVector) {
  79       s += i;
  80     }
  81   }
  82   folly::doNotOptimizeAway(s);
  83 }
  84
  85 BENCHMARK_RELATIVE(Sum_Vector_Gen, iters) {
  86   int s = 0;
  87   while (iters--) {
  88     s += from(testVector) | sum;
  89   }
  90   folly::doNotOptimizeAway(s);
  91 }
  92
  93 BENCHMARK_DRAW_LINE()
  94
  95 BENCHMARK(Count_Vector_NoGen, iters) {
  96   int s = 0;
  97   while (iters--) {
  98     for (auto& i : testVector) {
  99       if (i * 2 < rand()) {
 100         ++s;
 101       }
 102     }
 103   }
 104   folly::doNotOptimizeAway(s);
 105 }
 106
 107 BENCHMARK_RELATIVE(Count_Vector_Gen, iters) {
 108   int s = 0;
 109   while (iters--) {
 110     s += from(testVector)
 111        | filter([](int i) {
 112                   return i * 2 < rand();
 113                 })
 114        | count;
 115   }
 116   folly::doNotOptimizeAway(s);
 117 }
 118
 119 BENCHMARK_DRAW_LINE()
 120
 121 BENCHMARK(Fib_Sum_NoGen, iters) {
 122   int s = 0;
 123   while (iters--) {
 124     auto fib = [](int limit) -> vector<int> {
 125       vector<int> ret;
 126       int a = 0;
 127       int b = 1;
 128       for (int i = 0; i * 2 < limit; ++i) {
 129         ret.push_back(a += b);
 130         ret.push_back(b += a);
 131       }
 132       return ret;
 133     };
 134     for (auto& v : fib(testSize.load())) {
 135       s += v;
 136     }
 137   }
 138   folly::doNotOptimizeAway(s);
 139 }
 140
 141 BENCHMARK_RELATIVE(Fib_Sum_Gen, iters) {
 142   int s = 0;
 143   while (iters--) {
 144     auto fib = GENERATOR(int) {
 145       int a = 0;
 146       int b = 1;
 147       for (;;) {
 148         yield(a += b);
 149         yield(b += a);
 150       }
 151     };
 152     s += fib | take(testSize.load()) | sum;
 153   }
 154   folly::doNotOptimizeAway(s);
 155 }
 156
 157 struct FibYielder {
 158   template<class Yield>
 159   void operator()(Yield&& yield) const {
 160     int a = 0;
 161     int b = 1;
 162     for (;;) {
 163       yield(a += b);
 164       yield(b += a);
 165     }
 166   }
 167 };
 168
 169 BENCHMARK_RELATIVE(Fib_Sum_Gen_Static, iters) {
 170   int s = 0;
 171   while (iters--) {
 172     auto fib = generator<int>(FibYielder());
 173     s += fib | take(testSize.load()) | sum;
 174   }
 175   folly::doNotOptimizeAway(s);
 176 }
 177
 178 BENCHMARK_DRAW_LINE()
 179
 180 BENCHMARK(VirtualGen_0Virtual, iters) {
 181   int s = 0;
 182   while (iters--) {
 183     auto numbers = seq(1, 10000);
 184     auto squares = numbers | map(square);
 185     auto quads = squares | map(square);
 186     s += quads | sum;
 187   }
 188   folly::doNotOptimizeAway(s);
 189 }
 190
 191 BENCHMARK_RELATIVE(VirtualGen_1Virtual, iters) {
 192   int s = 0;
 193   while (iters--) {
 194     VirtualGen<int> numbers = seq(1, 10000);
 195     auto squares = numbers | map(square);
 196     auto quads = squares | map(square);
 197     s += quads | sum;
 198   }
 199   folly::doNotOptimizeAway(s);
 200 }
 201
 202 BENCHMARK_RELATIVE(VirtualGen_2Virtual, iters) {
 203   int s = 0;
 204   while (iters--) {
 205     VirtualGen<int> numbers = seq(1, 10000);
 206     VirtualGen<int> squares = numbers | map(square);
 207     auto quads = squares | map(square);
 208     s += quads | sum;
 209   }
 210   folly::doNotOptimizeAway(s);
 211 }
 212
 213 BENCHMARK_RELATIVE(VirtualGen_3Virtual, iters) {
 214   int s = 0;
 215   while (iters--) {
 216     VirtualGen<int> numbers = seq(1, 10000);
 217     VirtualGen<int> squares = numbers | map(square);
 218     VirtualGen<int> quads = squares | map(square);
 219     s += quads | sum;
 220   }
 221   folly::doNotOptimizeAway(s);
 222 }
 223
 224 BENCHMARK_DRAW_LINE()
 225
 226 BENCHMARK(Concat_NoGen, iters) {
 227   int s = 0;
 228   while (iters--) {
 229     for (auto& v : testVectorVector) {
 230       for (auto& i : v) {
 231         s += i;
 232       }
 233     }
 234   }
 235   folly::doNotOptimizeAway(s);
 236 }
 237
 238 BENCHMARK_RELATIVE(Concat_Gen, iters) {
 239   int s = 0;
 240   while (iters--) {
 241     s += from(testVectorVector) | rconcat | sum;
 242   }
 243   folly::doNotOptimizeAway(s);
 244 }
 245
 246 BENCHMARK_DRAW_LINE()
 247
 248 BENCHMARK(Composed_NoGen, iters) {
 249   int s = 0;
 250   while (iters--) {
 251     for (auto& i : testVector) {
 252       s += i * i;
 253     }
 254   }
 255   folly::doNotOptimizeAway(s);
 256 }
 257
 258 BENCHMARK_RELATIVE(Composed_Gen, iters) {
 259   int s = 0;
 260   auto sumSq = map(square) | sum;
 261   while (iters--) {
 262     s += from(testVector) | sumSq;
 263   }
 264   folly::doNotOptimizeAway(s);
 265 }
 266
 267 BENCHMARK_RELATIVE(Composed_GenRegular, iters) {
 268   int s = 0;
 269   while (iters--) {
 270     s += from(testVector) | map(square) | sum;
 271   }
 272   folly::doNotOptimizeAway(s);
 273 }
 274
 275 BENCHMARK_DRAW_LINE()
 276
 277 namespace {
 278
 279 const char* const kLine = "The quick brown fox jumped over the lazy dog.\n";
 280 const size_t kLineCount = 10000;
 281 std::string bigLines;
 282 const size_t kSmallLineSize = 17;
 283 std::vector<std::string> smallLines;
 284
 285 void initStringResplitterBenchmark() {
 286   bigLines.reserve(kLineCount * strlen(kLine));
 287   for (size_t i = 0; i < kLineCount; ++i) {
 288     bigLines += kLine;
 289   }
 290   size_t remaining = bigLines.size();
 291   size_t pos = 0;
 292   while (remaining) {
 293     size_t n = std::min(kSmallLineSize, remaining);
 294     smallLines.push_back(bigLines.substr(pos, n));
 295     pos += n;
 296     remaining -= n;
 297   }
 298 }
 299
 300 size_t len(folly::StringPiece s) { return s.size(); }
 301
 302 }  // namespace
 303
 304 BENCHMARK(StringResplitter_Big, iters) {
 305   size_t s = 0;
 306   while (iters--) {
 307     s += from({bigLines}) | resplit('\n') | map(&len) | sum;
 308   }
 309   folly::doNotOptimizeAway(s);
 310 }
 311
 312 BENCHMARK_RELATIVE(StringResplitter_Small, iters) {
 313   size_t s = 0;
 314   while (iters--) {
 315     s += from(smallLines) | resplit('\n') | map(&len) | sum;
 316   }
 317   folly::doNotOptimizeAway(s);
 318 }
 319
 320 BENCHMARK_DRAW_LINE()
 321
 322 BENCHMARK(StringSplit_Old, iters) {
 323   size_t s = 0;
 324   std::string line(kLine);
 325   while (iters--) {
 326     std::vector<StringPiece> parts;
 327     split(' ', line, parts);
 328     s += parts.size();
 329   }
 330   folly::doNotOptimizeAway(s);
 331 }
 332
 333
 334 BENCHMARK_RELATIVE(StringSplit_Gen_Vector, iters) {
 335   size_t s = 0;
 336   StringPiece line(kLine);
 337   while (iters--) {
 338     s += (split(line, ' ') | as<vector>()).size();
 339   }
 340   folly::doNotOptimizeAway(s);
 341 }
 342
 343 BENCHMARK_DRAW_LINE()
 344
 345 BENCHMARK(StringSplit_Old_ReuseVector, iters) {
 346   size_t s = 0;
 347   std::string line(kLine);
 348   std::vector<StringPiece> parts;
 349   while (iters--) {
 350     parts.clear();
 351     split(' ', line, parts);
 352     s += parts.size();
 353   }
 354   folly::doNotOptimizeAway(s);
 355 }
 356
 357 BENCHMARK_RELATIVE(StringSplit_Gen_ReuseVector, iters) {
 358   size_t s = 0;
 359   StringPiece line(kLine);
 360   std::vector<StringPiece> parts;
 361   while (iters--) {
 362     parts.clear();
 363     split(line, ' ') | appendTo(parts);
 364     s += parts.size();
 365   }
 366   folly::doNotOptimizeAway(s);
 367 }
 368
 369 BENCHMARK_RELATIVE(StringSplit_Gen, iters) {
 370   size_t s = 0;
 371   StringPiece line(kLine);
 372   while (iters--) {
 373     s += split(line, ' ') | count;
 374   }
 375   folly::doNotOptimizeAway(s);
 376 }
 377
 378 BENCHMARK_RELATIVE(StringSplit_Gen_Take, iters) {
 379   size_t s = 0;
 380   StringPiece line(kLine);
 381   while (iters--) {
 382     s += split(line, ' ') | take(10) | count;
 383   }
 384   folly::doNotOptimizeAway(s);
 385 }
 386
 387 BENCHMARK_DRAW_LINE()
 388
 389 BENCHMARK(ByLine_Pipes, iters) {
 390   std::thread thread;
 391   int rfd;
 392   int wfd;
 393   BENCHMARK_SUSPEND {
 394     int p[2];
 395     CHECK_ERR(::pipe(p));
 396     rfd = p[0];
 397     wfd = p[1];
 398     thread = std::thread([wfd, iters] {
 399       char x = 'x';
 400       PCHECK(::write(wfd, &x, 1) == 1);  // signal startup
 401       FILE* f = fdopen(wfd, "w");
 402       PCHECK(f);
 403       for (int i = 1; i <= iters; ++i) {
 404         fprintf(f, "%d\n", i);
 405       }
 406       fclose(f);
 407     });
 408     char buf;
 409     PCHECK(::read(rfd, &buf, 1) == 1);  // wait for startup
 410   }
 411
 412   auto s = byLine(rfd) | eachTo<int64_t>() | sum;
 413   folly::doNotOptimizeAway(s);
 414
 415   BENCHMARK_SUSPEND {
 416     ::close(rfd);
 417     CHECK_EQ(s, int64_t(iters) * (iters + 1) / 2);
 418     thread.join();
 419   }
 420 }
 421
 422 // Results from a dual core Xeon L5520 @ 2.27GHz:
 423 //
 424 // ============================================================================
 425 // folly/experimental/test/GenBenchmark.cpp        relative  time/iter  iters/s
 426 // ============================================================================
 427 // Sum_Basic_NoGen                                            293.77ns    3.40M
 428 // Sum_Basic_Gen                                    100.24%   293.08ns    3.41M
 429 // ----------------------------------------------------------------------------
 430 // Sum_Vector_NoGen                                           199.09ns    5.02M
 431 // Sum_Vector_Gen                                    98.57%   201.98ns    4.95M
 432 // ----------------------------------------------------------------------------
 433 // Count_Vector_NoGen                                          12.40us   80.66K
 434 // Count_Vector_Gen                                 103.07%    12.03us   83.13K
 435 // ----------------------------------------------------------------------------
 436 // Fib_Sum_NoGen                                                3.65us  274.29K
 437 // Fib_Sum_Gen                                       41.95%     8.69us  115.06K
 438 // Fib_Sum_Gen_Static                                86.10%     4.23us  236.15K
 439 // ----------------------------------------------------------------------------
 440 // VirtualGen_0Virtual                                         10.10us   99.03K
 441 // VirtualGen_1Virtual                               29.67%    34.04us   29.38K
 442 // VirtualGen_2Virtual                               20.53%    49.19us   20.33K
 443 // VirtualGen_3Virtual                               15.22%    66.36us   15.07K
 444 // ----------------------------------------------------------------------------
 445 // Concat_NoGen                                                 2.33us  428.35K
 446 // Concat_Gen                                        85.36%     2.74us  365.62K
 447 // ----------------------------------------------------------------------------
 448 // Composed_NoGen                                             552.78ns    1.81M
 449 // Composed_Gen                                     100.48%   550.14ns    1.82M
 450 // Composed_GenRegular                              100.60%   549.50ns    1.82M
 451 // ----------------------------------------------------------------------------
 452 // StringResplitter_Big                                       118.40us    8.45K
 453 // StringResplitter_Small                            12.96%   913.23us    1.10K
 454 // ----------------------------------------------------------------------------
 455 // StringSplit_Old                                            567.61ns    1.76M
 456 // StringSplit_Gen_Vector                           146.52%   387.41ns    2.58M
 457 // ----------------------------------------------------------------------------
 458 // StringSplit_Old_ReuseVector                                 74.90ns   13.35M
 459 // StringSplit_Gen_ReuseVector                      112.29%    66.71ns   14.99M
 460 // StringSplit_Gen                                  122.42%    61.18ns   16.34M
 461 // StringSplit_Gen_Take                             134.49%    55.70ns   17.95M
 462 // ----------------------------------------------------------------------------
 463 // ByLine_Pipes                                               131.18ns    7.62M
 464 // ============================================================================
 465
 466 int main(int argc, char *argv[]) {
 467   google::ParseCommandLineFlags(&argc, &argv, true);
 468   initStringResplitterBenchmark();
 469   runBenchmarks();
 470   return 0;
 471 }