folly/Benchmark.h

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