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