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
  21 #include <atomic>
  22 #include <thread>
  23
  24 #include <glog/logging.h>
  25
  26 #include "folly/Benchmark.h"
  27
  28 using namespace folly;
  29 using namespace folly::gen;
  30 using std::ostream;
  31 using std::pair;
  32 using std::set;
  33 using std::vector;
  34 using std::tuple;
  35
  36 static std::atomic<int> testSize(1000);
  37 static vector<int> testVector =
  38     seq(1, testSize.load())
  39   | mapped([](int) { return rand(); })
  40   | as<vector>();
  41 static vector<vector<int>> testVectorVector =
  42     seq(1, 100)
  43   | map([](int i) {
  44       return seq(1, i) | as<vector>();
  45     })
  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(Count_Vector_NoGen, iters) {
  95   int s = 0;
  96   while (iters--) {
  97     for (auto& i : testVector) {
  98       if (i * 2 < rand()) {
  99         ++s;
 100       }
 101     }
 102   }
 103   folly::doNotOptimizeAway(s);
 104 }
 105
 106 BENCHMARK_RELATIVE(Count_Vector_Gen, iters) {
 107   int s = 0;
 108   while (iters--) {
 109     s += from(testVector)
 110        | filter([](int i) {
 111                   return i * 2 < rand();
 112                 })
 113        | count;
 114   }
 115   folly::doNotOptimizeAway(s);
 116 }
 117
 118 BENCHMARK_DRAW_LINE()
 119
 120 BENCHMARK(Fib_Sum_NoGen, iters) {
 121   int s = 0;
 122   while (iters--) {
 123     auto fib = [](int limit) -> vector<int> {
 124       vector<int> ret;
 125       int a = 0;
 126       int b = 1;
 127       for (int i = 0; i * 2 < limit; ++i) {
 128         ret.push_back(a += b);
 129         ret.push_back(b += a);
 130       }
 131       return ret;
 132     };
 133     for (auto& v : fib(testSize.load())) {
 134       s += v;
 135     }
 136   }
 137   folly::doNotOptimizeAway(s);
 138 }
 139
 140 BENCHMARK_RELATIVE(Fib_Sum_Gen, iters) {
 141   int s = 0;
 142   while (iters--) {
 143     auto fib = GENERATOR(int, {
 144       int a = 0;
 145       int b = 1;
 146       for (;;) {
 147         yield(a += b);
 148         yield(b += a);
 149       }
 150     });
 151     s += fib | take(testSize.load()) | sum;
 152   }
 153   folly::doNotOptimizeAway(s);
 154 }
 155
 156 struct FibYielder {
 157   template<class Yield>
 158   void operator()(Yield&& yield) const {
 159     int a = 0;
 160     int b = 1;
 161     for (;;) {
 162       yield(a += b);
 163       yield(b += a);
 164     }
 165   }
 166 };
 167
 168 BENCHMARK_RELATIVE(Fib_Sum_Gen_Static, iters) {
 169   int s = 0;
 170   while (iters--) {
 171     auto fib = generator<int>(FibYielder());
 172     s += fib | take(testSize.load()) | sum;
 173   }
 174   folly::doNotOptimizeAway(s);
 175 }
 176
 177 BENCHMARK_DRAW_LINE()
 178
 179 BENCHMARK(VirtualGen_0Virtual, iters) {
 180   int s = 0;
 181   while (iters--) {
 182     auto numbers = seq(1, 10000);
 183     auto squares = numbers | map(square);
 184     auto quads = squares | map(square);
 185     s += quads | sum;
 186   }
 187   folly::doNotOptimizeAway(s);
 188 }
 189
 190 BENCHMARK_RELATIVE(VirtualGen_1Virtual, iters) {
 191   int s = 0;
 192   while (iters--) {
 193     VirtualGen<int> numbers = seq(1, 10000);
 194     auto squares = numbers | map(square);
 195     auto quads = squares | map(square);
 196     s += quads | sum;
 197   }
 198   folly::doNotOptimizeAway(s);
 199 }
 200
 201 BENCHMARK_RELATIVE(VirtualGen_2Virtual, iters) {
 202   int s = 0;
 203   while (iters--) {
 204     VirtualGen<int> numbers = seq(1, 10000);
 205     VirtualGen<int> 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_3Virtual, iters) {
 213   int s = 0;
 214   while (iters--) {
 215     VirtualGen<int> numbers = seq(1, 10000);
 216     VirtualGen<int> squares = numbers | map(square);
 217     VirtualGen<int> quads = squares | map(square);
 218     s += quads | sum;
 219   }
 220   folly::doNotOptimizeAway(s);
 221 }
 222
 223 BENCHMARK_DRAW_LINE()
 224
 225 BENCHMARK(Concat_NoGen, iters) {
 226   int s = 0;
 227   while (iters--) {
 228     for (auto& v : testVectorVector) {
 229       for (auto& i : v) {
 230         s += i;
 231       }
 232     }
 233   }
 234   folly::doNotOptimizeAway(s);
 235 }
 236
 237 BENCHMARK_RELATIVE(Concat_Gen, iters) {
 238   int s = 0;
 239   while (iters--) {
 240     s += from(testVectorVector) | rconcat | sum;
 241   }
 242   folly::doNotOptimizeAway(s);
 243 }
 244
 245 BENCHMARK_DRAW_LINE()
 246
 247 BENCHMARK(Composed_NoGen, iters) {
 248   int s = 0;
 249   while (iters--) {
 250     for (auto& i : testVector) {
 251       s += i * i;
 252     }
 253   }
 254   folly::doNotOptimizeAway(s);
 255 }
 256
 257 BENCHMARK_RELATIVE(Composed_Gen, iters) {
 258   int s = 0;
 259   auto sumSq = map(square) | sum;
 260   while (iters--) {
 261     s += from(testVector) | sumSq;
 262   }
 263   folly::doNotOptimizeAway(s);
 264 }
 265
 266 BENCHMARK_RELATIVE(Composed_GenRegular, iters) {
 267   int s = 0;
 268   while (iters--) {
 269     s += from(testVector) | map(square) | sum;
 270   }
 271   folly::doNotOptimizeAway(s);
 272 }
 273
 274 BENCHMARK_DRAW_LINE()
 275
 276 namespace {
 277
 278 const char* const kLine = "The quick brown fox jumped over the lazy dog.\n";
 279 const size_t kLineCount = 10000;
 280 std::string bigLines;
 281 const size_t kSmallLineSize = 17;
 282 std::vector<std::string> smallLines;
 283
 284 void initStringResplitterBenchmark() {
 285   bigLines.reserve(kLineCount * strlen(kLine));
 286   for (size_t i = 0; i < kLineCount; ++i) {
 287     bigLines += kLine;
 288   }
 289   size_t remaining = bigLines.size();
 290   size_t pos = 0;
 291   while (remaining) {
 292     size_t n = std::min(kSmallLineSize, remaining);
 293     smallLines.push_back(bigLines.substr(pos, n));
 294     pos += n;
 295     remaining -= n;
 296   }
 297 }
 298
 299 size_t len(folly::StringPiece s) { return s.size(); }
 300
 301 }  // namespace
 302
 303 BENCHMARK(StringResplitter_Big, iters) {
 304   size_t s = 0;
 305   while (iters--) {
 306     s += from({bigLines}) | resplit('\n') | map(&len) | sum;
 307   }
 308   folly::doNotOptimizeAway(s);
 309 }
 310
 311 BENCHMARK_RELATIVE(StringResplitter_Small, iters) {
 312   size_t s = 0;
 313   while (iters--) {
 314     s += from(smallLines) | resplit('\n') | map(&len) | sum;
 315   }
 316   folly::doNotOptimizeAway(s);
 317 }
 318
 319 BENCHMARK_DRAW_LINE()
 320
 321 BENCHMARK(ByLine_Pipes, iters) {
 322   std::thread thread;
 323   int rfd;
 324   int wfd;
 325   BENCHMARK_SUSPEND {
 326     int p[2];
 327     CHECK_ERR(::pipe(p));
 328     rfd = p[0];
 329     wfd = p[1];
 330     thread = std::thread([wfd, iters] {
 331       char x = 'x';
 332       PCHECK(::write(wfd, &x, 1) == 1);  // signal startup
 333       FILE* f = fdopen(wfd, "w");
 334       PCHECK(f);
 335       for (int i = 1; i <= iters; ++i) {
 336         fprintf(f, "%d\n", i);
 337       }
 338       fclose(f);
 339     });
 340     char buf;
 341     PCHECK(::read(rfd, &buf, 1) == 1);  // wait for startup
 342   }
 343
 344   auto s = byLine(rfd) | eachTo<int64_t>() | sum;
 345   folly::doNotOptimizeAway(s);
 346
 347   BENCHMARK_SUSPEND {
 348     ::close(rfd);
 349     CHECK_EQ(s, int64_t(iters) * (iters + 1) / 2);
 350     thread.join();
 351   }
 352 }
 353
 354 // Results from a dual core Xeon L5520 @ 2.27GHz:
 355 //
 356 // ============================================================================
 357 // folly/experimental/test/GenBenchmark.cpp        relative  time/iter  iters/s
 358 // ============================================================================
 359 // Sum_Basic_NoGen                                            301.60ns    3.32M
 360 // Sum_Basic_Gen                                    104.27%   289.24ns    3.46M
 361 // ----------------------------------------------------------------------------
 362 // Sum_Vector_NoGen                                           200.33ns    4.99M
 363 // Sum_Vector_Gen                                    99.81%   200.70ns    4.98M
 364 // ----------------------------------------------------------------------------
 365 // Count_Vector_NoGen                                          12.37us   80.84K
 366 // Count_Vector_Gen                                 103.09%    12.00us   83.33K
 367 // ----------------------------------------------------------------------------
 368 // Fib_Sum_NoGen                                                3.66us  273.21K
 369 // Fib_Sum_Gen                                       43.06%     8.50us  117.65K
 370 // Fib_Sum_Gen_Static                                87.81%     4.17us  239.89K
 371 // ----------------------------------------------------------------------------
 372 // VirtualGen_0Virtual                                         10.04us   99.61K
 373 // VirtualGen_1Virtual                               29.59%    33.93us   29.47K
 374 // VirtualGen_2Virtual                               20.45%    49.10us   20.37K
 375 // VirtualGen_3Virtual                               15.49%    64.82us   15.43K
 376 // ----------------------------------------------------------------------------
 377 // Concat_NoGen                                                 2.50us  400.37K
 378 // Concat_Gen                                       102.50%     2.44us  410.37K
 379 // ----------------------------------------------------------------------------
 380 // Composed_NoGen                                             549.54ns    1.82M
 381 // Composed_Gen                                     101.39%   542.00ns    1.85M
 382 // Composed_GenRegular                               99.66%   551.40ns    1.81M
 383 // ============================================================================
 384
 385 int main(int argc, char *argv[]) {
 386   google::ParseCommandLineFlags(&argc, &argv, true);
 387   initStringResplitterBenchmark();
 388   runBenchmarks();
 389   return 0;
 390 }