folly/Benchmark.h

   1 /*
   2  * Copyright 2013 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/Preprocessor.h" // for FB_ANONYMOUS_VARIABLE
  21 #include <cassert>
  22 #include <ctime>
  23 #include <boost/function_types/function_arity.hpp>
  24 #include <functional>
  25 #include <glog/logging.h>
  26 #include <gflags/gflags.h>
  27 #include <limits>
  28
  29 DECLARE_bool(benchmark);
  30
  31
  32 namespace folly {
  33
  34 /**
  35  * Runs all benchmarks defined. Usually put in main().
  36  */
  37 void runBenchmarks();
  38
  39 /**
  40  * Runs all benchmarks defined if and only if the --benchmark flag has
  41  * been passed to the program. Usually put in main().
  42  */
  43 inline bool runBenchmarksOnFlag() {
  44   if (FLAGS_benchmark) {
  45     runBenchmarks();
  46   }
  47   return FLAGS_benchmark;
  48 }
  49
  50 namespace detail {
  51
  52 /**
  53  * This is the clock ID used for measuring time. On older kernels, the
  54  * resolution of this clock will be very coarse, which will cause the
  55  * benchmarks to fail.
  56  */
  57 enum Clock { DEFAULT_CLOCK_ID = CLOCK_REALTIME };
  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<uint64_t(unsigned int)>);
  66
  67 /**
  68  * Takes the difference between two timespec values. end is assumed to
  69  * occur after start.
  70  */
  71 inline uint64_t timespecDiff(timespec end, timespec start) {
  72   if (end.tv_sec == start.tv_sec) {
  73     assert(end.tv_nsec >= start.tv_nsec);
  74     return end.tv_nsec - start.tv_nsec;
  75   }
  76   assert(end.tv_sec > start.tv_sec &&
  77          end.tv_sec - start.tv_sec <
  78          std::numeric_limits<uint64_t>::max() / 1000000000UL);
  79   return (end.tv_sec - start.tv_sec) * 1000000000UL
  80     + end.tv_nsec - start.tv_nsec;
  81 }
  82
  83 /**
  84  * Takes the difference between two sets of timespec values. The first
  85  * two come from a high-resolution clock whereas the other two come
  86  * from a low-resolution clock. The crux of the matter is that
  87  * high-res values may be bogus as documented in
  88  * http://linux.die.net/man/3/clock_gettime. The trouble is when the
  89  * running process migrates from one CPU to another, which is more
  90  * likely for long-running processes. Therefore we watch for high
  91  * differences between the two timings.
  92  *
  93  * This function is subject to further improvements.
  94  */
  95 inline uint64_t timespecDiff(timespec end, timespec start,
  96                              timespec endCoarse, timespec startCoarse) {
  97   auto fine = timespecDiff(end, start);
  98   auto coarse = timespecDiff(endCoarse, startCoarse);
  99   if (coarse - fine >= 1000000) {
 100     // The fine time is in all likelihood bogus
 101     return coarse;
 102   }
 103   return fine;
 104 }
 105
 106 } // namespace detail
 107
 108 /**
 109  * Supporting type for BENCHMARK_SUSPEND defined below.
 110  */
 111 struct BenchmarkSuspender {
 112   BenchmarkSuspender() {
 113     CHECK_EQ(0, clock_gettime(detail::DEFAULT_CLOCK_ID, &start));
 114   }
 115
 116   BenchmarkSuspender(const BenchmarkSuspender &) = delete;
 117   BenchmarkSuspender(BenchmarkSuspender && rhs) {
 118     start = rhs.start;
 119     rhs.start.tv_nsec = rhs.start.tv_sec = 0;
 120   }
 121
 122   BenchmarkSuspender& operator=(const BenchmarkSuspender &) = delete;
 123   BenchmarkSuspender& operator=(BenchmarkSuspender && rhs) {
 124     if (start.tv_nsec > 0 || start.tv_sec > 0) {
 125       tally();
 126     }
 127     start = rhs.start;
 128     rhs.start.tv_nsec = rhs.start.tv_sec = 0;
 129     return *this;
 130   }
 131
 132   ~BenchmarkSuspender() {
 133     if (start.tv_nsec > 0 || start.tv_sec > 0) {
 134       tally();
 135     }
 136   }
 137
 138   void dismiss() {
 139     assert(start.tv_nsec > 0 || start.tv_sec > 0);
 140     tally();
 141     start.tv_nsec = start.tv_sec = 0;
 142   }
 143
 144   void rehire() {
 145     assert(start.tv_nsec == 0 || start.tv_sec == 0);
 146     CHECK_EQ(0, clock_gettime(detail::DEFAULT_CLOCK_ID, &start));
 147   }
 148
 149   /**
 150    * This helps the macro definition. To get around the dangers of
 151    * operator bool, returns a pointer to member (which allows no
 152    * arithmetic).
 153    */
 154   operator int BenchmarkSuspender::*() const {
 155     return nullptr;
 156   }
 157
 158   /**
 159    * Accumulates nanoseconds spent outside benchmark.
 160    */
 161   typedef uint64_t NanosecondsSpent;
 162   static NanosecondsSpent nsSpent;
 163
 164 private:
 165   void tally() {
 166     timespec end;
 167     CHECK_EQ(0, clock_gettime(detail::DEFAULT_CLOCK_ID, &end));
 168     nsSpent += detail::timespecDiff(end, start);
 169     start = end;
 170   }
 171
 172   timespec start;
 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 exactly one parameter of type unsigned, and the benchmark
 179  * uses it with counter semantics (iteration occurs inside the
 180  * function).
 181  */
 182 template <typename Lambda>
 183 typename std::enable_if<
 184   boost::function_types::function_arity<decltype(&Lambda::operator())>::value
 185   == 2
 186 >::type
 187 addBenchmark(const char* file, const char* name, Lambda&& lambda) {
 188   auto execute = [=](unsigned int times) -> uint64_t {
 189     BenchmarkSuspender::nsSpent = 0;
 190     timespec start, end;
 191
 192     // CORE MEASUREMENT STARTS
 193     auto const r1 = clock_gettime(detail::DEFAULT_CLOCK_ID, &start);
 194     lambda(times);
 195     auto const r2 = clock_gettime(detail::DEFAULT_CLOCK_ID, &end);
 196     // CORE MEASUREMENT ENDS
 197
 198     CHECK_EQ(0, r1);
 199     CHECK_EQ(0, r2);
 200
 201     return detail::timespecDiff(end, start) - BenchmarkSuspender::nsSpent;
 202   };
 203
 204   detail::addBenchmarkImpl(file, name,
 205                            std::function<uint64_t(unsigned int)>(execute));
 206 }
 207
 208 /**
 209  * Adds a benchmark. Usually not called directly but instead through
 210  * the macro BENCHMARK defined below. The lambda function involved
 211  * must take zero parameters, and the benchmark calls it repeatedly
 212  * (iteration occurs outside the function).
 213  */
 214 template <typename Lambda>
 215 typename std::enable_if<
 216   boost::function_types::function_arity<decltype(&Lambda::operator())>::value
 217   == 1
 218 >::type
 219 addBenchmark(const char* file, const char* name, Lambda&& lambda) {
 220   addBenchmark(file, name, [=](unsigned int times) {
 221       while (times-- > 0) {
 222         lambda();
 223       }
 224     });
 225 }
 226
 227 /**
 228  * Call doNotOptimizeAway(var) against variables that you use for
 229  * benchmarking but otherwise are useless. The compiler tends to do a
 230  * good job at eliminating unused variables, and this function fools
 231  * it into thinking var is in fact needed.
 232  */
 233 template <class T>
 234 void doNotOptimizeAway(T&& datum) {
 235   asm volatile("" : "+r" (datum));
 236 }
 237
 238 } // namespace folly
 239
 240 /**
 241  * Introduces a benchmark function. Used internally, see BENCHMARK and
 242  * friends below.
 243  */
 244 #define BENCHMARK_IMPL(funName, stringName, paramType, paramName)       \
 245   static void funName(paramType);                                       \
 246   static bool FB_ANONYMOUS_VARIABLE(follyBenchmarkUnused) = (           \
 247     ::folly::addBenchmark(__FILE__, stringName,                         \
 248       [](paramType paramName) { funName(paramName); }),                 \
 249     true);                                                              \
 250   static void funName(paramType paramName)
 251
 252 /**
 253  * Introduces a benchmark function. Use with either one one or two
 254  * arguments. The first is the name of the benchmark. Use something
 255  * descriptive, such as insertVectorBegin. The second argument may be
 256  * missing, or could be a symbolic counter. The counter dictates how
 257  * many internal iteration the benchmark does. Example:
 258  *
 259  * BENCHMARK(vectorPushBack) {
 260  *   vector<int> v;
 261  *   v.push_back(42);
 262  * }
 263  *
 264  * BENCHMARK(insertVectorBegin, n) {
 265  *   vector<int> v;
 266  *   FOR_EACH_RANGE (i, 0, n) {
 267  *     v.insert(v.begin(), 42);
 268  *   }
 269  * }
 270  */
 271 #define BENCHMARK(name, ...)                                    \
 272   BENCHMARK_IMPL(                                               \
 273     name,                                                       \
 274     FB_STRINGIZE(name),                                         \
 275     FB_ONE_OR_NONE(unsigned, ## __VA_ARGS__),                   \
 276     __VA_ARGS__)
 277
 278 /**
 279  * Defines a benchmark that passes a parameter to another one. This is
 280  * common for benchmarks that need a "problem size" in addition to
 281  * "number of iterations". Consider:
 282  *
 283  * void pushBack(uint n, size_t initialSize) {
 284  *   vector<int> v;
 285  *   BENCHMARK_SUSPEND {
 286  *     v.resize(initialSize);
 287  *   }
 288  *   FOR_EACH_RANGE (i, 0, n) {
 289  *    v.push_back(i);
 290  *   }
 291  * }
 292  * BENCHMARK_PARAM(pushBack, 0)
 293  * BENCHMARK_PARAM(pushBack, 1000)
 294  * BENCHMARK_PARAM(pushBack, 1000000)
 295  *
 296  * The benchmark above estimates the speed of push_back at different
 297  * initial sizes of the vector. The framework will pass 0, 1000, and
 298  * 1000000 for initialSize, and the iteration count for n.
 299  */
 300 #define BENCHMARK_PARAM(name, param)                                    \
 301   BENCHMARK_NAMED_PARAM(name, param, param)
 302
 303 /*
 304  * Like BENCHMARK_PARAM(), but allows a custom name to be specified for each
 305  * parameter, rather than using the parameter value.
 306  *
 307  * Useful when the parameter value is not a valid token for string pasting,
 308  * of when you want to specify multiple parameter arguments.
 309  *
 310  * For example:
 311  *
 312  * void addValue(uint n, int64_t bucketSize, int64_t min, int64_t max) {
 313  *   Histogram<int64_t> hist(bucketSize, min, max);
 314  *   int64_t num = min;
 315  *   FOR_EACH_RANGE (i, 0, n) {
 316  *     hist.addValue(num);
 317  *     ++num;
 318  *     if (num > max) { num = min; }
 319  *   }
 320  * }
 321  *
 322  * BENCHMARK_NAMED_PARAM(addValue, 0_to_100, 1, 0, 100)
 323  * BENCHMARK_NAMED_PARAM(addValue, 0_to_1000, 10, 0, 1000)
 324  * BENCHMARK_NAMED_PARAM(addValue, 5k_to_20k, 250, 5000, 20000)
 325  */
 326 #define BENCHMARK_NAMED_PARAM(name, param_name, ...)                    \
 327   BENCHMARK_IMPL(                                                       \
 328       FB_CONCATENATE(name, FB_CONCATENATE(_, param_name)),              \
 329       FB_STRINGIZE(name) "(" FB_STRINGIZE(param_name) ")",              \
 330       unsigned,                                                         \
 331       iters) {                                                          \
 332     name(iters, ## __VA_ARGS__);                                        \
 333   }
 334
 335 /**
 336  * Just like BENCHMARK, but prints the time relative to a
 337  * baseline. The baseline is the most recent BENCHMARK() seen in
 338  * lexical order. Example:
 339  *
 340  * // This is the baseline
 341  * BENCHMARK(insertVectorBegin, n) {
 342  *   vector<int> v;
 343  *   FOR_EACH_RANGE (i, 0, n) {
 344  *     v.insert(v.begin(), 42);
 345  *   }
 346  * }
 347  *
 348  * BENCHMARK_RELATIVE(insertListBegin, n) {
 349  *   list<int> s;
 350  *   FOR_EACH_RANGE (i, 0, n) {
 351  *     s.insert(s.begin(), 42);
 352  *   }
 353  * }
 354  *
 355  * Any number of relative benchmark can be associated with a
 356  * baseline. Another BENCHMARK() occurrence effectively establishes a
 357  * new baseline.
 358  */
 359 #define BENCHMARK_RELATIVE(name, ...)                           \
 360   BENCHMARK_IMPL(                                               \
 361     name,                                                       \
 362     "%" FB_STRINGIZE(name),                                     \
 363     FB_ONE_OR_NONE(unsigned, ## __VA_ARGS__),                   \
 364     __VA_ARGS__)
 365
 366 /**
 367  * A combination of BENCHMARK_RELATIVE and BENCHMARK_PARAM.
 368  */
 369 #define BENCHMARK_RELATIVE_PARAM(name, param)                           \
 370   BENCHMARK_RELATIVE_NAMED_PARAM(name, param, param)
 371
 372 /**
 373  * A combination of BENCHMARK_RELATIVE and BENCHMARK_NAMED_PARAM.
 374  */
 375 #define BENCHMARK_RELATIVE_NAMED_PARAM(name, param_name, ...)           \
 376   BENCHMARK_IMPL(                                                       \
 377       FB_CONCATENATE(name, FB_CONCATENATE(_, param_name)),              \
 378       "%" FB_STRINGIZE(name) "(" FB_STRINGIZE(param_name) ")",          \
 379       unsigned,                                                         \
 380       iters) {                                                          \
 381     name(iters, ## __VA_ARGS__);                                        \
 382   }
 383
 384 /**
 385  * Draws a line of dashes.
 386  */
 387 #define BENCHMARK_DRAW_LINE()                                   \
 388   static bool FB_ANONYMOUS_VARIABLE(follyBenchmarkUnused) = (   \
 389     ::folly::addBenchmark(__FILE__, "-", []() { }),             \
 390     true);
 391
 392 /**
 393  * Allows execution of code that doesn't count torward the benchmark's
 394  * time budget. Example:
 395  *
 396  * BENCHMARK_START_GROUP(insertVectorBegin, n) {
 397  *   vector<int> v;
 398  *   BENCHMARK_SUSPEND {
 399  *     v.reserve(n);
 400  *   }
 401  *   FOR_EACH_RANGE (i, 0, n) {
 402  *     v.insert(v.begin(), 42);
 403  *   }
 404  * }
 405  */
 406 #define BENCHMARK_SUSPEND                               \
 407   if (auto FB_ANONYMOUS_VARIABLE(BENCHMARK_SUSPEND) =   \
 408       ::folly::BenchmarkSuspender()) {}                 \
 409   else
 410
 411 #endif // FOLLY_BENCHMARK_H_