folly/experimental/test/GenBenchmark.cpp

   1 /*
   2  * Copyright 2013 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
  43 static vector<fbstring> testStrVector =
  44     seq(1, testSize.load())
  45   | eachTo<fbstring>()
  46   | as<vector>();
  47
  48 static vector<vector<int>> testVectorVector =
  49     seq(1, 100)
  50   | map([](int i) {
  51       return seq(1, i) | as<vector>();
  52     })
  53   | as<vector>();
  54
  55 auto square = [](int x) { return x * x; };
  56 auto add = [](int a, int b) { return a + b; };
  57 auto multiply = [](int a, int b) { return a * b; };
  58
  59 BENCHMARK(Sum_Basic_NoGen, iters) {
  60   int limit = testSize.load();
  61   int s = 0;
  62   while (iters--) {
  63     for (int i = 0; i < limit; ++i) {
  64       s += i;
  65     }
  66   }
  67   folly::doNotOptimizeAway(s);
  68 }
  69
  70 BENCHMARK_RELATIVE(Sum_Basic_Gen, iters) {
  71   int limit = testSize.load();
  72   int s = 0;
  73   while (iters--) {
  74     s += range(0, limit) | sum;
  75   }
  76   folly::doNotOptimizeAway(s);
  77 }
  78
  79 BENCHMARK_DRAW_LINE()
  80
  81 BENCHMARK(Sum_Vector_NoGen, iters) {
  82   int s = 0;
  83   while (iters--) {
  84     for (auto& i : testVector) {
  85       s += i;
  86     }
  87   }
  88   folly::doNotOptimizeAway(s);
  89 }
  90
  91 BENCHMARK_RELATIVE(Sum_Vector_Gen, iters) {
  92   int s = 0;
  93   while (iters--) {
  94     s += from(testVector) | sum;
  95   }
  96   folly::doNotOptimizeAway(s);
  97 }
  98
  99 BENCHMARK_DRAW_LINE()
 100
 101 BENCHMARK(Count_Vector_NoGen, iters) {
 102   int s = 0;
 103   while (iters--) {
 104     for (auto& i : testVector) {
 105       if (i * 2 < rand()) {
 106         ++s;
 107       }
 108     }
 109   }
 110   folly::doNotOptimizeAway(s);
 111 }
 112
 113 BENCHMARK_RELATIVE(Count_Vector_Gen, iters) {
 114   int s = 0;
 115   while (iters--) {
 116     s += from(testVector)
 117        | filter([](int i) {
 118                   return i * 2 < rand();
 119                 })
 120        | count;
 121   }
 122   folly::doNotOptimizeAway(s);
 123 }
 124
 125 BENCHMARK_DRAW_LINE()
 126
 127 BENCHMARK(Fib_Sum_NoGen, iters) {
 128   int s = 0;
 129   while (iters--) {
 130     auto fib = [](int limit) -> vector<int> {
 131       vector<int> ret;
 132       int a = 0;
 133       int b = 1;
 134       for (int i = 0; i * 2 < limit; ++i) {
 135         ret.push_back(a += b);
 136         ret.push_back(b += a);
 137       }
 138       return ret;
 139     };
 140     for (auto& v : fib(testSize.load())) {
 141       s += v;
 142     }
 143   }
 144   folly::doNotOptimizeAway(s);
 145 }
 146
 147 BENCHMARK_RELATIVE(Fib_Sum_Gen, iters) {
 148   int s = 0;
 149   while (iters--) {
 150     auto fib = GENERATOR(int) {
 151       int a = 0;
 152       int b = 1;
 153       for (;;) {
 154         yield(a += b);
 155         yield(b += a);
 156       }
 157     };
 158     s += fib | take(testSize.load()) | sum;
 159   }
 160   folly::doNotOptimizeAway(s);
 161 }
 162
 163 struct FibYielder {
 164   template<class Yield>
 165   void operator()(Yield&& yield) const {
 166     int a = 0;
 167     int b = 1;
 168     for (;;) {
 169       yield(a += b);
 170       yield(b += a);
 171     }
 172   }
 173 };
 174
 175 BENCHMARK_RELATIVE(Fib_Sum_Gen_Static, iters) {
 176   int s = 0;
 177   while (iters--) {
 178     auto fib = generator<int>(FibYielder());
 179     s += fib | take(testSize.load()) | sum;
 180   }
 181   folly::doNotOptimizeAway(s);
 182 }
 183
 184 BENCHMARK_DRAW_LINE()
 185
 186 BENCHMARK(VirtualGen_0Virtual, iters) {
 187   int s = 0;
 188   while (iters--) {
 189     auto numbers = seq(1, 10000);
 190     auto squares = numbers | map(square);
 191     auto quads = squares | map(square);
 192     s += quads | sum;
 193   }
 194   folly::doNotOptimizeAway(s);
 195 }
 196
 197 BENCHMARK_RELATIVE(VirtualGen_1Virtual, iters) {
 198   int s = 0;
 199   while (iters--) {
 200     VirtualGen<int> numbers = seq(1, 10000);
 201     auto squares = numbers | map(square);
 202     auto quads = squares | map(square);
 203     s += quads | sum;
 204   }
 205   folly::doNotOptimizeAway(s);
 206 }
 207
 208 BENCHMARK_RELATIVE(VirtualGen_2Virtual, iters) {
 209   int s = 0;
 210   while (iters--) {
 211     VirtualGen<int> numbers = seq(1, 10000);
 212     VirtualGen<int> squares = numbers | map(square);
 213     auto quads = squares | map(square);
 214     s += quads | sum;
 215   }
 216   folly::doNotOptimizeAway(s);
 217 }
 218
 219 BENCHMARK_RELATIVE(VirtualGen_3Virtual, iters) {
 220   int s = 0;
 221   while (iters--) {
 222     VirtualGen<int> numbers = seq(1, 10000);
 223     VirtualGen<int> squares = numbers | map(square);
 224     VirtualGen<int> quads = squares | map(square);
 225     s += quads | sum;
 226   }
 227   folly::doNotOptimizeAway(s);
 228 }
 229
 230 BENCHMARK_DRAW_LINE()
 231
 232 BENCHMARK(Concat_NoGen, iters) {
 233   int s = 0;
 234   while (iters--) {
 235     for (auto& v : testVectorVector) {
 236       for (auto& i : v) {
 237         s += i;
 238       }
 239     }
 240   }
 241   folly::doNotOptimizeAway(s);
 242 }
 243
 244 BENCHMARK_RELATIVE(Concat_Gen, iters) {
 245   int s = 0;
 246   while (iters--) {
 247     s += from(testVectorVector) | rconcat | sum;
 248   }
 249   folly::doNotOptimizeAway(s);
 250 }
 251
 252 BENCHMARK_DRAW_LINE()
 253
 254 BENCHMARK(Composed_NoGen, iters) {
 255   int s = 0;
 256   while (iters--) {
 257     for (auto& i : testVector) {
 258       s += i * i;
 259     }
 260   }
 261   folly::doNotOptimizeAway(s);
 262 }
 263
 264 BENCHMARK_RELATIVE(Composed_Gen, iters) {
 265   int s = 0;
 266   auto sumSq = map(square) | sum;
 267   while (iters--) {
 268     s += from(testVector) | sumSq;
 269   }
 270   folly::doNotOptimizeAway(s);
 271 }
 272
 273 BENCHMARK_RELATIVE(Composed_GenRegular, iters) {
 274   int s = 0;
 275   while (iters--) {
 276     s += from(testVector) | map(square) | sum;
 277   }
 278   folly::doNotOptimizeAway(s);
 279 }
 280
 281 BENCHMARK_DRAW_LINE()
 282
 283 BENCHMARK(Sample, iters) {
 284   size_t s = 0;
 285   while (iters--) {
 286     auto sampler = seq(1, 10 * 1000 * 1000) | sample(1000);
 287     s += (sampler | sum);
 288   }
 289   folly::doNotOptimizeAway(s);
 290 }
 291
 292 BENCHMARK_DRAW_LINE()
 293
 294 namespace {
 295
 296 const char* const kLine = "The quick brown fox jumped over the lazy dog.\n";
 297 const size_t kLineCount = 10000;
 298 std::string bigLines;
 299 const size_t kSmallLineSize = 17;
 300 std::vector<std::string> smallLines;
 301
 302 void initStringResplitterBenchmark() {
 303   bigLines.reserve(kLineCount * strlen(kLine));
 304   for (size_t i = 0; i < kLineCount; ++i) {
 305     bigLines += kLine;
 306   }
 307   size_t remaining = bigLines.size();
 308   size_t pos = 0;
 309   while (remaining) {
 310     size_t n = std::min(kSmallLineSize, remaining);
 311     smallLines.push_back(bigLines.substr(pos, n));
 312     pos += n;
 313     remaining -= n;
 314   }
 315 }
 316
 317 size_t len(folly::StringPiece s) { return s.size(); }
 318
 319 }  // namespace
 320
 321 BENCHMARK(StringResplitter_Big, iters) {
 322   size_t s = 0;
 323   while (iters--) {
 324     s += from({bigLines}) | resplit('\n') | map(&len) | sum;
 325   }
 326   folly::doNotOptimizeAway(s);
 327 }
 328
 329 BENCHMARK_RELATIVE(StringResplitter_Small, iters) {
 330   size_t s = 0;
 331   while (iters--) {
 332     s += from(smallLines) | resplit('\n') | map(&len) | sum;
 333   }
 334   folly::doNotOptimizeAway(s);
 335 }
 336
 337 BENCHMARK_DRAW_LINE()
 338
 339 BENCHMARK(StringSplit_Old, iters) {
 340   size_t s = 0;
 341   std::string line(kLine);
 342   while (iters--) {
 343     std::vector<StringPiece> parts;
 344     split(' ', line, parts);
 345     s += parts.size();
 346   }
 347   folly::doNotOptimizeAway(s);
 348 }
 349
 350
 351 BENCHMARK_RELATIVE(StringSplit_Gen_Vector, iters) {
 352   size_t s = 0;
 353   StringPiece line(kLine);
 354   while (iters--) {
 355     s += (split(line, ' ') | as<vector>()).size();
 356   }
 357   folly::doNotOptimizeAway(s);
 358 }
 359
 360 BENCHMARK_DRAW_LINE()
 361
 362 BENCHMARK(StringSplit_Old_ReuseVector, iters) {
 363   size_t s = 0;
 364   std::string line(kLine);
 365   std::vector<StringPiece> parts;
 366   while (iters--) {
 367     parts.clear();
 368     split(' ', line, parts);
 369     s += parts.size();
 370   }
 371   folly::doNotOptimizeAway(s);
 372 }
 373
 374 BENCHMARK_RELATIVE(StringSplit_Gen_ReuseVector, iters) {
 375   size_t s = 0;
 376   StringPiece line(kLine);
 377   std::vector<StringPiece> parts;
 378   while (iters--) {
 379     parts.clear();
 380     split(line, ' ') | appendTo(parts);
 381     s += parts.size();
 382   }
 383   folly::doNotOptimizeAway(s);
 384 }
 385
 386 BENCHMARK_RELATIVE(StringSplit_Gen, iters) {
 387   size_t s = 0;
 388   StringPiece line(kLine);
 389   while (iters--) {
 390     s += split(line, ' ') | count;
 391   }
 392   folly::doNotOptimizeAway(s);
 393 }
 394
 395 BENCHMARK_RELATIVE(StringSplit_Gen_Take, iters) {
 396   size_t s = 0;
 397   StringPiece line(kLine);
 398   while (iters--) {
 399     s += split(line, ' ') | take(10) | count;
 400   }
 401   folly::doNotOptimizeAway(s);
 402 }
 403
 404 BENCHMARK_DRAW_LINE()
 405
 406 BENCHMARK(StringUnsplit_Old, iters) {
 407   size_t s = 0;
 408   while (iters--) {
 409     fbstring joined;
 410     join(',', testStrVector, joined);
 411     s += joined.size();
 412   }
 413   folly::doNotOptimizeAway(s);
 414 }
 415
 416 BENCHMARK_RELATIVE(StringUnsplit_Old_ReusedBuffer, iters) {
 417   size_t s = 0;
 418   fbstring joined;
 419   while (iters--) {
 420     joined.clear();
 421     join(',', testStrVector, joined);
 422     s += joined.size();
 423   }
 424   folly::doNotOptimizeAway(s);
 425 }
 426
 427 BENCHMARK_RELATIVE(StringUnsplit_Gen, iters) {
 428   size_t s = 0;
 429   StringPiece line(kLine);
 430   while (iters--) {
 431     fbstring joined = from(testStrVector) | unsplit(',');
 432     s += joined.size();
 433   }
 434   folly::doNotOptimizeAway(s);
 435 }
 436
 437 BENCHMARK_RELATIVE(StringUnsplit_Gen_ReusedBuffer, iters) {
 438   size_t s = 0;
 439   fbstring buffer;
 440   while (iters--) {
 441     buffer.clear();
 442     from(testStrVector) | unsplit(',', &buffer);
 443     s += buffer.size();
 444   }
 445   folly::doNotOptimizeAway(s);
 446 }
 447
 448 BENCHMARK_DRAW_LINE()
 449
 450 void StringUnsplit_Gen(size_t iters, size_t joinSize) {
 451   std::vector<fbstring> v;
 452   BENCHMARK_SUSPEND {
 453     FOR_EACH_RANGE(i, 0, joinSize) {
 454       v.push_back(to<fbstring>(rand()));
 455     }
 456   }
 457   size_t s = 0;
 458   fbstring buffer;
 459   while (iters--) {
 460     buffer.clear();
 461     from(v) | unsplit(',', &buffer);
 462     s += buffer.size();
 463   }
 464   folly::doNotOptimizeAway(s);
 465 }
 466
 467 BENCHMARK_DRAW_LINE()
 468
 469 BENCHMARK_PARAM(StringUnsplit_Gen, 1000)
 470 BENCHMARK_RELATIVE_PARAM(StringUnsplit_Gen, 2000)
 471 BENCHMARK_RELATIVE_PARAM(StringUnsplit_Gen, 4000)
 472 BENCHMARK_RELATIVE_PARAM(StringUnsplit_Gen, 8000)
 473
 474 BENCHMARK_DRAW_LINE()
 475
 476 BENCHMARK(ByLine_Pipes, iters) {
 477   std::thread thread;
 478   int rfd;
 479   int wfd;
 480   BENCHMARK_SUSPEND {
 481     int p[2];
 482     CHECK_ERR(::pipe(p));
 483     rfd = p[0];
 484     wfd = p[1];
 485     thread = std::thread([wfd, iters] {
 486       char x = 'x';
 487       PCHECK(::write(wfd, &x, 1) == 1);  // signal startup
 488       FILE* f = fdopen(wfd, "w");
 489       PCHECK(f);
 490       for (int i = 1; i <= iters; ++i) {
 491         fprintf(f, "%d\n", i);
 492       }
 493       fclose(f);
 494     });
 495     char buf;
 496     PCHECK(::read(rfd, &buf, 1) == 1);  // wait for startup
 497   }
 498
 499   auto s = byLine(rfd) | eachTo<int64_t>() | sum;
 500   folly::doNotOptimizeAway(s);
 501
 502   BENCHMARK_SUSPEND {
 503     ::close(rfd);
 504     CHECK_EQ(s, int64_t(iters) * (iters + 1) / 2);
 505     thread.join();
 506   }
 507 }
 508
 509 // Results from a dual core Xeon L5520 @ 2.27GHz:
 510 //
 511 // ============================================================================
 512 // folly/experimental/test/GenBenchmark.cpp        relative  time/iter  iters/s
 513 // ============================================================================
 514 // Sum_Basic_NoGen                                            354.70ns    2.82M
 515 // Sum_Basic_Gen                                     95.88%   369.92ns    2.70M
 516 // ----------------------------------------------------------------------------
 517 // Sum_Vector_NoGen                                           211.89ns    4.72M
 518 // Sum_Vector_Gen                                    97.49%   217.35ns    4.60M
 519 // ----------------------------------------------------------------------------
 520 // Count_Vector_NoGen                                          13.93us   71.78K
 521 // Count_Vector_Gen                                 106.38%    13.10us   76.36K
 522 // ----------------------------------------------------------------------------
 523 // Fib_Sum_NoGen                                                4.54us  220.07K
 524 // Fib_Sum_Gen                                       45.81%     9.92us  100.82K
 525 // Fib_Sum_Gen_Static                               100.00%     4.54us  220.05K
 526 // ----------------------------------------------------------------------------
 527 // VirtualGen_0Virtual                                         12.03us   83.14K
 528 // VirtualGen_1Virtual                               32.89%    36.57us   27.34K
 529 // VirtualGen_2Virtual                               24.98%    48.15us   20.77K
 530 // VirtualGen_3Virtual                               17.82%    67.49us   14.82K
 531 // ----------------------------------------------------------------------------
 532 // Concat_NoGen                                                 1.92us  520.46K
 533 // Concat_Gen                                       102.79%     1.87us  534.97K
 534 // ----------------------------------------------------------------------------
 535 // Composed_NoGen                                             545.64ns    1.83M
 536 // Composed_Gen                                      99.65%   547.55ns    1.83M
 537 // Composed_GenRegular                               99.64%   547.62ns    1.83M
 538 // ----------------------------------------------------------------------------
 539 // StringResplitter_Big                                       120.88us    8.27K
 540 // StringResplitter_Small                            14.39%   839.94us    1.19K
 541 // ----------------------------------------------------------------------------
 542 // StringSplit_Old                                            421.09ns    2.37M
 543 // StringSplit_Gen_Vector                            97.73%   430.87ns    2.32M
 544 // ----------------------------------------------------------------------------
 545 // StringSplit_Old_ReuseVector                                 80.25ns   12.46M
 546 // StringSplit_Gen_ReuseVector                       98.99%    81.07ns   12.34M
 547 // StringSplit_Gen                                  117.23%    68.45ns   14.61M
 548 // StringSplit_Gen_Take                             115.23%    69.64ns   14.36M
 549 // ----------------------------------------------------------------------------
 550 // StringUnsplit_Old                                           34.45us   29.02K
 551 // StringUnsplit_Old_ReusedBuffer                   100.37%    34.33us   29.13K
 552 // StringUnsplit_Gen                                106.27%    32.42us   30.84K
 553 // StringUnsplit_Gen_ReusedBuffer                   105.61%    32.62us   30.65K
 554 // ----------------------------------------------------------------------------
 555 // ----------------------------------------------------------------------------
 556 // StringUnsplit_Gen(1000)                                     32.20us   31.06K
 557 // StringUnsplit_Gen(2000)                           49.41%    65.17us   15.34K
 558 // StringUnsplit_Gen(4000)                           22.75%   141.52us    7.07K
 559 // StringUnsplit_Gen(8000)                           11.20%   287.53us    3.48K
 560 // ----------------------------------------------------------------------------
 561 // ByLine_Pipes                                               126.58ns    7.90M
 562 // ============================================================================
 563
 564 int main(int argc, char *argv[]) {
 565   google::ParseCommandLineFlags(&argc, &argv, true);
 566   initStringResplitterBenchmark();
 567   runBenchmarks();
 568   return 0;
 569 }