folly/Benchmark.h

   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 #pragma once
  18
  19 #include <folly/Portability.h>
  20 #include <folly/Preprocessor.h> // for FB_ANONYMOUS_VARIABLE
  21 #include <folly/ScopeGuard.h>
  22 #include <folly/Traits.h>
  23 #include <folly/portability/GFlags.h>
  24
  25 #include <cassert>
  26 #include <chrono>
  27 #include <functional>
  28 #include <limits>
  29 #include <type_traits>
  30
  31 #include <boost/function_types/function_arity.hpp>
  32 #include <glog/logging.h>
  33
  34 DECLARE_bool(benchmark);
  35
  36 namespace folly {
  37
  38 /**
  39  * Runs all benchmarks defined. Usually put in main().
  40  */
  41 void runBenchmarks();
  42
  43 /**
  44  * Runs all benchmarks defined if and only if the --benchmark flag has
  45  * been passed to the program. Usually put in main().
  46  */
  47 inline bool runBenchmarksOnFlag() {
  48   if (FLAGS_benchmark) {
  49     runBenchmarks();
  50   }
  51   return FLAGS_benchmark;
  52 }
  53
  54 namespace detail {
  55
  56 using TimeIterPair =
  57     std::pair<std::chrono::high_resolution_clock::duration, unsigned int>;
  58 using BenchmarkFun = std::function<detail::TimeIterPair(unsigned int)>;
  59
  60 struct BenchmarkRegistration {
  61   std::string file;
  62   std::string name;
  63   BenchmarkFun func;
  64 };
  65
  66 struct BenchmarkResult {
  67   std::string file;
  68   std::string name;
  69   double timeInNs;
  70 };
  71
  72 /**
  73  * Adds a benchmark wrapped in a std::function. Only used
  74  * internally. Pass by value is intentional.
  75  */
  76 void addBenchmarkImpl(const char* file,
  77                       const char* name,
  78                       std::function<TimeIterPair(unsigned int)>);
  79
  80 } // namespace detail
  81
  82 /**
  83  * Supporting type for BENCHMARK_SUSPEND defined below.
  84  */
  85 struct BenchmarkSuspender {
  86   using Clock = std::chrono::high_resolution_clock;
  87   using TimePoint = Clock::time_point;
  88   using Duration = Clock::duration;
  89
  90   BenchmarkSuspender() {
  91     start = Clock::now();
  92   }
  93
  94   BenchmarkSuspender(const BenchmarkSuspender &) = delete;
  95   BenchmarkSuspender(BenchmarkSuspender && rhs) noexcept {
  96     start = rhs.start;
  97     rhs.start = {};
  98   }
  99
 100   BenchmarkSuspender& operator=(const BenchmarkSuspender &) = delete;
 101   BenchmarkSuspender& operator=(BenchmarkSuspender && rhs) {
 102     if (start != TimePoint{}) {
 103       tally();
 104     }
 105     start = rhs.start;
 106     rhs.start = {};
 107     return *this;
 108   }
 109
 110   ~BenchmarkSuspender() {
 111     if (start != TimePoint{}) {
 112       tally();
 113     }
 114   }
 115
 116   void dismiss() {
 117     assert(start != TimePoint{});
 118     tally();
 119     start = {};
 120   }
 121
 122   void rehire() {
 123     assert(start == TimePoint{});
 124     start = Clock::now();
 125   }
 126
 127   template <class F>
 128   auto dismissing(F f) -> typename std::result_of<F()>::type {
 129     SCOPE_EXIT { rehire(); };
 130     dismiss();
 131     return f();
 132   }
 133
 134   /**
 135    * This is for use inside of if-conditions, used in BENCHMARK macros.
 136    * If-conditions bypass the explicit on operator bool.
 137    */
 138   explicit operator bool() const {
 139     return false;
 140   }
 141
 142   /**
 143    * Accumulates time spent outside benchmark.
 144    */
 145   static Duration timeSpent;
 146
 147  private:
 148   void tally() {
 149     auto end = Clock::now();
 150     timeSpent += end - start;
 151     start = end;
 152   }
 153
 154   TimePoint start;
 155 };
 156
 157 /**
 158  * Adds a benchmark. Usually not called directly but instead through
 159  * the macro BENCHMARK defined below. The lambda function involved
 160  * must take exactly one parameter of type unsigned, and the benchmark
 161  * uses it with counter semantics (iteration occurs inside the
 162  * function).
 163  */
 164 template <typename Lambda>
 165 typename std::enable_if<
 166   boost::function_types::function_arity<decltype(&Lambda::operator())>::value
 167   == 2
 168 >::type
 169 addBenchmark(const char* file, const char* name, Lambda&& lambda) {
 170   auto execute = [=](unsigned int times) {
 171     BenchmarkSuspender::timeSpent = {};
 172     unsigned int niter;
 173
 174     // CORE MEASUREMENT STARTS
 175     auto start = std::chrono::high_resolution_clock::now();
 176     niter = lambda(times);
 177     auto end = std::chrono::high_resolution_clock::now();
 178     // CORE MEASUREMENT ENDS
 179
 180     return detail::TimeIterPair(
 181         (end - start) - BenchmarkSuspender::timeSpent, niter);
 182   };
 183
 184   detail::addBenchmarkImpl(file, name,
 185     std::function<detail::TimeIterPair(unsigned int)>(execute));
 186 }
 187
 188 /**
 189  * Adds a benchmark. Usually not called directly but instead through
 190  * the macro BENCHMARK defined below. The lambda function involved
 191  * must take zero parameters, and the benchmark calls it repeatedly
 192  * (iteration occurs outside the function).
 193  */
 194 template <typename Lambda>
 195 typename std::enable_if<
 196   boost::function_types::function_arity<decltype(&Lambda::operator())>::value
 197   == 1
 198 >::type
 199 addBenchmark(const char* file, const char* name, Lambda&& lambda) {
 200   addBenchmark(file, name, [=](unsigned int times) {
 201       unsigned int niter = 0;
 202       while (times-- > 0) {
 203         niter += lambda();
 204       }
 205       return niter;
 206     });
 207 }
 208
 209 /**
 210  * Call doNotOptimizeAway(var) to ensure that var will be computed even
 211  * post-optimization.  Use it for variables that are computed during
 212  * benchmarking but otherwise are useless. The compiler tends to do a
 213  * good job at eliminating unused variables, and this function fools it
 214  * into thinking var is in fact needed.
 215  *
 216  * Call makeUnpredictable(var) when you don't want the optimizer to use
 217  * its knowledge of var to shape the following code.  This is useful
 218  * when constant propagation or power reduction is possible during your
 219  * benchmark but not in real use cases.
 220  */
 221
 222 #ifdef _MSC_VER
 223
 224 #pragma optimize("", off)
 225
 226 inline void doNotOptimizeDependencySink(const void*) {}
 227
 228 #pragma optimize("", on)
 229
 230 template <class T>
 231 void doNotOptimizeAway(const T& datum) {
 232   doNotOptimizeDependencySink(&datum);
 233 }
 234
 235 template <typename T>
 236 void makeUnpredictable(T& datum) {
 237   doNotOptimizeDependencySink(&datum);
 238 }
 239
 240 #else
 241
 242 namespace detail {
 243 template <typename T>
 244 struct DoNotOptimizeAwayNeedsIndirect {
 245   using Decayed = typename std::decay<T>::type;
 246
 247   // First two constraints ensure it can be an "r" operand.
 248   // std::is_pointer check is because callers seem to expect that
 249   // doNotOptimizeAway(&x) is equivalent to doNotOptimizeAway(x).
 250   constexpr static bool value = !folly::IsTriviallyCopyable<Decayed>::value ||
 251       sizeof(Decayed) > sizeof(long) || std::is_pointer<Decayed>::value;
 252 };
 253 } // namespace detail
 254
 255 template <typename T>
 256 auto doNotOptimizeAway(const T& datum) -> typename std::enable_if<
 257     !detail::DoNotOptimizeAwayNeedsIndirect<T>::value>::type {
 258   // The "r" constraint forces the compiler to make datum available
 259   // in a register to the asm block, which means that it must have
 260   // computed/loaded it.  We use this path for things that are <=
 261   // sizeof(long) (they have to fit), trivial (otherwise the compiler
 262   // doesn't want to put them in a register), and not a pointer (because
 263   // doNotOptimizeAway(&foo) would otherwise be a foot gun that didn't
 264   // necessarily compute foo).
 265   //
 266   // An earlier version of this method had a more permissive input operand
 267   // constraint, but that caused unnecessary variation between clang and
 268   // gcc benchmarks.
 269   asm volatile("" ::"r"(datum));
 270 }
 271
 272 template <typename T>
 273 auto doNotOptimizeAway(const T& datum) -> typename std::enable_if<
 274     detail::DoNotOptimizeAwayNeedsIndirect<T>::value>::type {
 275   // This version of doNotOptimizeAway tells the compiler that the asm
 276   // block will read datum from memory, and that in addition it might read
 277   // or write from any memory location.  If the memory clobber could be
 278   // separated into input and output that would be preferrable.
 279   asm volatile("" ::"m"(datum) : "memory");
 280 }
 281
 282 template <typename T>
 283 auto makeUnpredictable(T& datum) -> typename std::enable_if<
 284     !detail::DoNotOptimizeAwayNeedsIndirect<T>::value>::type {
 285   asm volatile("" : "+r"(datum));
 286 }
 287
 288 template <typename T>
 289 auto makeUnpredictable(T& datum) -> typename std::enable_if<
 290     detail::DoNotOptimizeAwayNeedsIndirect<T>::value>::type {
 291   asm volatile("" ::"m"(datum) : "memory");
 292 }
 293
 294 #endif
 295
 296 struct dynamic;
 297
 298 void benchmarkResultsToDynamic(
 299     const std::vector<detail::BenchmarkResult>& data,
 300     dynamic&);
 301
 302 void benchmarkResultsFromDynamic(
 303     const dynamic&,
 304     std::vector<detail::BenchmarkResult>&);
 305
 306 void printResultComparison(
 307     const std::vector<detail::BenchmarkResult>& base,
 308     const std::vector<detail::BenchmarkResult>& test);
 309
 310 } // namespace folly
 311
 312 /**
 313  * Introduces a benchmark function. Used internally, see BENCHMARK and
 314  * friends below.
 315  */
 316 #define BENCHMARK_IMPL(funName, stringName, rv, paramType, paramName)   \
 317   static void funName(paramType);                                       \
 318   static bool FB_ANONYMOUS_VARIABLE(follyBenchmarkUnused) = (           \
 319     ::folly::addBenchmark(__FILE__, stringName,                         \
 320       [](paramType paramName) -> unsigned { funName(paramName);         \
 321                                             return rv; }),              \
 322     true);                                                              \
 323   static void funName(paramType paramName)
 324
 325 /**
 326  * Introduces a benchmark function with support for returning the actual
 327  * number of iterations. Used internally, see BENCHMARK_MULTI and friends
 328  * below.
 329  */
 330 #define BENCHMARK_MULTI_IMPL(funName, stringName, paramType, paramName) \
 331   static unsigned funName(paramType);                                   \
 332   static bool FB_ANONYMOUS_VARIABLE(follyBenchmarkUnused) = (           \
 333     ::folly::addBenchmark(__FILE__, stringName,                         \
 334       [](paramType paramName) { return funName(paramName); }),          \
 335     true);                                                              \
 336   static unsigned funName(paramType paramName)
 337
 338 /**
 339  * Introduces a benchmark function. Use with either one or two arguments.
 340  * The first is the name of the benchmark. Use something descriptive, such
 341  * as insertVectorBegin. The second argument may be missing, or could be a
 342  * symbolic counter. The counter dictates how many internal iteration the
 343  * benchmark does. Example:
 344  *
 345  * BENCHMARK(vectorPushBack) {
 346  *   vector<int> v;
 347  *   v.push_back(42);
 348  * }
 349  *
 350  * BENCHMARK(insertVectorBegin, n) {
 351  *   vector<int> v;
 352  *   FOR_EACH_RANGE (i, 0, n) {
 353  *     v.insert(v.begin(), 42);
 354  *   }
 355  * }
 356  */
 357 #define BENCHMARK(name, ...)                                    \
 358   BENCHMARK_IMPL(                                               \
 359     name,                                                       \
 360     FB_STRINGIZE(name),                                         \
 361     FB_ARG_2_OR_1(1, ## __VA_ARGS__),                           \
 362     FB_ONE_OR_NONE(unsigned, ## __VA_ARGS__),                   \
 363     __VA_ARGS__)
 364
 365 /**
 366  * Like BENCHMARK above, but allows the user to return the actual
 367  * number of iterations executed in the function body. This can be
 368  * useful if the benchmark function doesn't know upfront how many
 369  * iterations it's going to run or if it runs through a certain
 370  * number of test cases, e.g.:
 371  *
 372  * BENCHMARK_MULTI(benchmarkSomething) {
 373  *   std::vector<int> testCases { 0, 1, 1, 2, 3, 5 };
 374  *   for (int c : testCases) {
 375  *     doSomething(c);
 376  *   }
 377  *   return testCases.size();
 378  * }
 379  */
 380 #define BENCHMARK_MULTI(name, ...)                              \
 381   BENCHMARK_MULTI_IMPL(                                         \
 382     name,                                                       \
 383     FB_STRINGIZE(name),                                         \
 384     FB_ONE_OR_NONE(unsigned, ## __VA_ARGS__),                   \
 385     __VA_ARGS__)
 386
 387 /**
 388  * Defines a benchmark that passes a parameter to another one. This is
 389  * common for benchmarks that need a "problem size" in addition to
 390  * "number of iterations". Consider:
 391  *
 392  * void pushBack(uint n, size_t initialSize) {
 393  *   vector<int> v;
 394  *   BENCHMARK_SUSPEND {
 395  *     v.resize(initialSize);
 396  *   }
 397  *   FOR_EACH_RANGE (i, 0, n) {
 398  *    v.push_back(i);
 399  *   }
 400  * }
 401  * BENCHMARK_PARAM(pushBack, 0)
 402  * BENCHMARK_PARAM(pushBack, 1000)
 403  * BENCHMARK_PARAM(pushBack, 1000000)
 404  *
 405  * The benchmark above estimates the speed of push_back at different
 406  * initial sizes of the vector. The framework will pass 0, 1000, and
 407  * 1000000 for initialSize, and the iteration count for n.
 408  */
 409 #define BENCHMARK_PARAM(name, param)                                    \
 410   BENCHMARK_NAMED_PARAM(name, param, param)
 411
 412 /**
 413  * Same as BENCHMARK_PARAM, but allows one to return the actual number of
 414  * iterations that have been run.
 415  */
 416 #define BENCHMARK_PARAM_MULTI(name, param)                              \
 417   BENCHMARK_NAMED_PARAM_MULTI(name, param, param)
 418
 419 /*
 420  * Like BENCHMARK_PARAM(), but allows a custom name to be specified for each
 421  * parameter, rather than using the parameter value.
 422  *
 423  * Useful when the parameter value is not a valid token for string pasting,
 424  * of when you want to specify multiple parameter arguments.
 425  *
 426  * For example:
 427  *
 428  * void addValue(uint n, int64_t bucketSize, int64_t min, int64_t max) {
 429  *   Histogram<int64_t> hist(bucketSize, min, max);
 430  *   int64_t num = min;
 431  *   FOR_EACH_RANGE (i, 0, n) {
 432  *     hist.addValue(num);
 433  *     ++num;
 434  *     if (num > max) { num = min; }
 435  *   }
 436  * }
 437  *
 438  * BENCHMARK_NAMED_PARAM(addValue, 0_to_100, 1, 0, 100)
 439  * BENCHMARK_NAMED_PARAM(addValue, 0_to_1000, 10, 0, 1000)
 440  * BENCHMARK_NAMED_PARAM(addValue, 5k_to_20k, 250, 5000, 20000)
 441  */
 442 #define BENCHMARK_NAMED_PARAM(name, param_name, ...)                    \
 443   BENCHMARK_IMPL(                                                       \
 444       FB_CONCATENATE(name, FB_CONCATENATE(_, param_name)),              \
 445       FB_STRINGIZE(name) "(" FB_STRINGIZE(param_name) ")",              \
 446       iters,                                                            \
 447       unsigned,                                                         \
 448       iters) {                                                          \
 449     name(iters, ## __VA_ARGS__);                                        \
 450   }
 451
 452 /**
 453  * Same as BENCHMARK_NAMED_PARAM, but allows one to return the actual number
 454  * of iterations that have been run.
 455  */
 456 #define BENCHMARK_NAMED_PARAM_MULTI(name, param_name, ...)              \
 457   BENCHMARK_MULTI_IMPL(                                                 \
 458       FB_CONCATENATE(name, FB_CONCATENATE(_, param_name)),              \
 459       FB_STRINGIZE(name) "(" FB_STRINGIZE(param_name) ")",              \
 460       unsigned,                                                         \
 461       iters) {                                                          \
 462     return name(iters, ## __VA_ARGS__);                                 \
 463   }
 464
 465 /**
 466  * Just like BENCHMARK, but prints the time relative to a
 467  * baseline. The baseline is the most recent BENCHMARK() seen in
 468  * the current scope. Example:
 469  *
 470  * // This is the baseline
 471  * BENCHMARK(insertVectorBegin, n) {
 472  *   vector<int> v;
 473  *   FOR_EACH_RANGE (i, 0, n) {
 474  *     v.insert(v.begin(), 42);
 475  *   }
 476  * }
 477  *
 478  * BENCHMARK_RELATIVE(insertListBegin, n) {
 479  *   list<int> s;
 480  *   FOR_EACH_RANGE (i, 0, n) {
 481  *     s.insert(s.begin(), 42);
 482  *   }
 483  * }
 484  *
 485  * Any number of relative benchmark can be associated with a
 486  * baseline. Another BENCHMARK() occurrence effectively establishes a
 487  * new baseline.
 488  */
 489 #define BENCHMARK_RELATIVE(name, ...)                           \
 490   BENCHMARK_IMPL(                                               \
 491     name,                                                       \
 492     "%" FB_STRINGIZE(name),                                     \
 493     FB_ARG_2_OR_1(1, ## __VA_ARGS__),                           \
 494     FB_ONE_OR_NONE(unsigned, ## __VA_ARGS__),                   \
 495     __VA_ARGS__)
 496
 497 /**
 498  * Same as BENCHMARK_RELATIVE, but allows one to return the actual number
 499  * of iterations that have been run.
 500  */
 501 #define BENCHMARK_RELATIVE_MULTI(name, ...)                     \
 502   BENCHMARK_MULTI_IMPL(                                         \
 503     name,                                                       \
 504     "%" FB_STRINGIZE(name),                                     \
 505     FB_ONE_OR_NONE(unsigned, ## __VA_ARGS__),                   \
 506     __VA_ARGS__)
 507
 508 /**
 509  * A combination of BENCHMARK_RELATIVE and BENCHMARK_PARAM.
 510  */
 511 #define BENCHMARK_RELATIVE_PARAM(name, param)                           \
 512   BENCHMARK_RELATIVE_NAMED_PARAM(name, param, param)
 513
 514 /**
 515  * Same as BENCHMARK_RELATIVE_PARAM, but allows one to return the actual
 516  * number of iterations that have been run.
 517  */
 518 #define BENCHMARK_RELATIVE_PARAM_MULTI(name, param)                     \
 519   BENCHMARK_RELATIVE_NAMED_PARAM_MULTI(name, param, param)
 520
 521 /**
 522  * A combination of BENCHMARK_RELATIVE and BENCHMARK_NAMED_PARAM.
 523  */
 524 #define BENCHMARK_RELATIVE_NAMED_PARAM(name, param_name, ...)           \
 525   BENCHMARK_IMPL(                                                       \
 526       FB_CONCATENATE(name, FB_CONCATENATE(_, param_name)),              \
 527       "%" FB_STRINGIZE(name) "(" FB_STRINGIZE(param_name) ")",          \
 528       iters,                                                            \
 529       unsigned,                                                         \
 530       iters) {                                                          \
 531     name(iters, ## __VA_ARGS__);                                        \
 532   }
 533
 534 /**
 535  * Same as BENCHMARK_RELATIVE_NAMED_PARAM, but allows one to return the
 536  * actual number of iterations that have been run.
 537  */
 538 #define BENCHMARK_RELATIVE_NAMED_PARAM_MULTI(name, param_name, ...)     \
 539   BENCHMARK_MULTI_IMPL(                                                 \
 540       FB_CONCATENATE(name, FB_CONCATENATE(_, param_name)),              \
 541       "%" FB_STRINGIZE(name) "(" FB_STRINGIZE(param_name) ")",          \
 542       unsigned,                                                         \
 543       iters) {                                                          \
 544     return name(iters, ## __VA_ARGS__);                                 \
 545   }
 546
 547 /**
 548  * Draws a line of dashes.
 549  */
 550 #define BENCHMARK_DRAW_LINE()                                             \
 551   static bool FB_ANONYMOUS_VARIABLE(follyBenchmarkUnused) = (             \
 552     ::folly::addBenchmark(__FILE__, "-", []() -> unsigned { return 0; }), \
 553     true);
 554
 555 /**
 556  * Allows execution of code that doesn't count torward the benchmark's
 557  * time budget. Example:
 558  *
 559  * BENCHMARK_START_GROUP(insertVectorBegin, n) {
 560  *   vector<int> v;
 561  *   BENCHMARK_SUSPEND {
 562  *     v.reserve(n);
 563  *   }
 564  *   FOR_EACH_RANGE (i, 0, n) {
 565  *     v.insert(v.begin(), 42);
 566  *   }
 567  * }
 568  */
 569 #define BENCHMARK_SUSPEND                               \
 570   if (auto FB_ANONYMOUS_VARIABLE(BENCHMARK_SUSPEND) =   \
 571       ::folly::BenchmarkSuspender()) {}                 \
 572   else