folly/Benchmark.h

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