2 * Copyright 2017 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
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>
29 #include <type_traits>
31 #include <boost/function_types/function_arity.hpp>
32 #include <glog/logging.h>
34 DECLARE_bool(benchmark);
39 * Runs all benchmarks defined. Usually put in main().
44 * Runs all benchmarks defined if and only if the --benchmark flag has
45 * been passed to the program. Usually put in main().
47 inline bool runBenchmarksOnFlag() {
48 if (FLAGS_benchmark) {
51 return FLAGS_benchmark;
57 std::pair<std::chrono::high_resolution_clock::duration, unsigned int>;
58 using BenchmarkFun = std::function<detail::TimeIterPair(unsigned int)>;
60 struct BenchmarkRegistration {
66 struct BenchmarkResult {
73 * Adds a benchmark wrapped in a std::function. Only used
74 * internally. Pass by value is intentional.
76 void addBenchmarkImpl(const char* file,
78 std::function<TimeIterPair(unsigned int)>);
83 * Supporting type for BENCHMARK_SUSPEND defined below.
85 struct BenchmarkSuspender {
86 using Clock = std::chrono::high_resolution_clock;
87 using TimePoint = Clock::time_point;
88 using Duration = Clock::duration;
90 BenchmarkSuspender() {
94 BenchmarkSuspender(const BenchmarkSuspender &) = delete;
95 BenchmarkSuspender(BenchmarkSuspender && rhs) noexcept {
100 BenchmarkSuspender& operator=(const BenchmarkSuspender &) = delete;
101 BenchmarkSuspender& operator=(BenchmarkSuspender && rhs) {
102 if (start != TimePoint{}) {
110 ~BenchmarkSuspender() {
111 if (start != TimePoint{}) {
117 assert(start != TimePoint{});
123 assert(start == TimePoint{});
124 start = Clock::now();
128 auto dismissing(F f) -> typename std::result_of<F()>::type {
129 SCOPE_EXIT { rehire(); };
135 * This is for use inside of if-conditions, used in BENCHMARK macros.
136 * If-conditions bypass the explicit on operator bool.
138 explicit operator bool() const {
143 * Accumulates time spent outside benchmark.
145 static Duration timeSpent;
149 auto end = Clock::now();
150 timeSpent += end - start;
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
164 template <typename Lambda>
165 typename std::enable_if<
166 boost::function_types::function_arity<decltype(&Lambda::operator())>::value
169 addBenchmark(const char* file, const char* name, Lambda&& lambda) {
170 auto execute = [=](unsigned int times) {
171 BenchmarkSuspender::timeSpent = {};
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
180 return detail::TimeIterPair(
181 (end - start) - BenchmarkSuspender::timeSpent, niter);
184 detail::addBenchmarkImpl(file, name,
185 std::function<detail::TimeIterPair(unsigned int)>(execute));
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).
194 template <typename Lambda>
195 typename std::enable_if<
196 boost::function_types::function_arity<decltype(&Lambda::operator())>::value
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) {
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.
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.
224 #pragma optimize("", off)
226 inline void doNotOptimizeDependencySink(const void*) {}
228 #pragma optimize("", on)
231 void doNotOptimizeAway(const T& datum) {
232 doNotOptimizeDependencySink(&datum);
235 template <typename T>
236 void makeUnpredictable(T& datum) {
237 doNotOptimizeDependencySink(&datum);
243 template <typename T>
244 struct DoNotOptimizeAwayNeedsIndirect {
245 using Decayed = typename std::decay<T>::type;
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;
253 } // namespace detail
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).
266 // An earlier version of this method had a more permissive input operand
267 // constraint, but that caused unnecessary variation between clang and
269 asm volatile("" ::"r"(datum));
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");
282 template <typename T>
283 auto makeUnpredictable(T& datum) -> typename std::enable_if<
284 !detail::DoNotOptimizeAwayNeedsIndirect<T>::value>::type {
285 asm volatile("" : "+r"(datum));
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");
298 void benchmarkResultsToDynamic(
299 const std::vector<detail::BenchmarkResult>& data,
302 void benchmarkResultsFromDynamic(
304 std::vector<detail::BenchmarkResult>&);
306 void printResultComparison(
307 const std::vector<detail::BenchmarkResult>& base,
308 const std::vector<detail::BenchmarkResult>& test);
313 * Introduces a benchmark function. Used internally, see BENCHMARK and
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); \
323 static void funName(paramType paramName)
326 * Introduces a benchmark function with support for returning the actual
327 * number of iterations. Used internally, see BENCHMARK_MULTI and friends
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); }), \
336 static unsigned funName(paramType paramName)
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:
345 * BENCHMARK(vectorPushBack) {
350 * BENCHMARK(insertVectorBegin, n) {
352 * FOR_EACH_RANGE (i, 0, n) {
353 * v.insert(v.begin(), 42);
357 #define BENCHMARK(name, ...) \
360 FB_STRINGIZE(name), \
361 FB_ARG_2_OR_1(1, ## __VA_ARGS__), \
362 FB_ONE_OR_NONE(unsigned, ## __VA_ARGS__), \
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.:
372 * BENCHMARK_MULTI(benchmarkSomething) {
373 * std::vector<int> testCases { 0, 1, 1, 2, 3, 5 };
374 * for (int c : testCases) {
377 * return testCases.size();
380 #define BENCHMARK_MULTI(name, ...) \
381 BENCHMARK_MULTI_IMPL( \
383 FB_STRINGIZE(name), \
384 FB_ONE_OR_NONE(unsigned, ## __VA_ARGS__), \
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:
392 * void pushBack(uint n, size_t initialSize) {
394 * BENCHMARK_SUSPEND {
395 * v.resize(initialSize);
397 * FOR_EACH_RANGE (i, 0, n) {
401 * BENCHMARK_PARAM(pushBack, 0)
402 * BENCHMARK_PARAM(pushBack, 1000)
403 * BENCHMARK_PARAM(pushBack, 1000000)
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.
409 #define BENCHMARK_PARAM(name, param) \
410 BENCHMARK_NAMED_PARAM(name, param, param)
413 * Same as BENCHMARK_PARAM, but allows one to return the actual number of
414 * iterations that have been run.
416 #define BENCHMARK_PARAM_MULTI(name, param) \
417 BENCHMARK_NAMED_PARAM_MULTI(name, param, param)
420 * Like BENCHMARK_PARAM(), but allows a custom name to be specified for each
421 * parameter, rather than using the parameter value.
423 * Useful when the parameter value is not a valid token for string pasting,
424 * of when you want to specify multiple parameter arguments.
428 * void addValue(uint n, int64_t bucketSize, int64_t min, int64_t max) {
429 * Histogram<int64_t> hist(bucketSize, min, max);
431 * FOR_EACH_RANGE (i, 0, n) {
432 * hist.addValue(num);
434 * if (num > max) { num = min; }
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)
442 #define BENCHMARK_NAMED_PARAM(name, param_name, ...) \
444 FB_CONCATENATE(name, FB_CONCATENATE(_, param_name)), \
445 FB_STRINGIZE(name) "(" FB_STRINGIZE(param_name) ")", \
449 name(iters, ## __VA_ARGS__); \
453 * Same as BENCHMARK_NAMED_PARAM, but allows one to return the actual number
454 * of iterations that have been run.
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) ")", \
462 return name(iters, ## __VA_ARGS__); \
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:
470 * // This is the baseline
471 * BENCHMARK(insertVectorBegin, n) {
473 * FOR_EACH_RANGE (i, 0, n) {
474 * v.insert(v.begin(), 42);
478 * BENCHMARK_RELATIVE(insertListBegin, n) {
480 * FOR_EACH_RANGE (i, 0, n) {
481 * s.insert(s.begin(), 42);
485 * Any number of relative benchmark can be associated with a
486 * baseline. Another BENCHMARK() occurrence effectively establishes a
489 #define BENCHMARK_RELATIVE(name, ...) \
492 "%" FB_STRINGIZE(name), \
493 FB_ARG_2_OR_1(1, ## __VA_ARGS__), \
494 FB_ONE_OR_NONE(unsigned, ## __VA_ARGS__), \
498 * Same as BENCHMARK_RELATIVE, but allows one to return the actual number
499 * of iterations that have been run.
501 #define BENCHMARK_RELATIVE_MULTI(name, ...) \
502 BENCHMARK_MULTI_IMPL( \
504 "%" FB_STRINGIZE(name), \
505 FB_ONE_OR_NONE(unsigned, ## __VA_ARGS__), \
509 * A combination of BENCHMARK_RELATIVE and BENCHMARK_PARAM.
511 #define BENCHMARK_RELATIVE_PARAM(name, param) \
512 BENCHMARK_RELATIVE_NAMED_PARAM(name, param, param)
515 * Same as BENCHMARK_RELATIVE_PARAM, but allows one to return the actual
516 * number of iterations that have been run.
518 #define BENCHMARK_RELATIVE_PARAM_MULTI(name, param) \
519 BENCHMARK_RELATIVE_NAMED_PARAM_MULTI(name, param, param)
522 * A combination of BENCHMARK_RELATIVE and BENCHMARK_NAMED_PARAM.
524 #define BENCHMARK_RELATIVE_NAMED_PARAM(name, param_name, ...) \
526 FB_CONCATENATE(name, FB_CONCATENATE(_, param_name)), \
527 "%" FB_STRINGIZE(name) "(" FB_STRINGIZE(param_name) ")", \
531 name(iters, ## __VA_ARGS__); \
535 * Same as BENCHMARK_RELATIVE_NAMED_PARAM, but allows one to return the
536 * actual number of iterations that have been run.
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) ")", \
544 return name(iters, ## __VA_ARGS__); \
548 * Draws a line of dashes.
550 #define BENCHMARK_DRAW_LINE() \
551 static bool FB_ANONYMOUS_VARIABLE(follyBenchmarkUnused) = ( \
552 ::folly::addBenchmark(__FILE__, "-", []() -> unsigned { return 0; }), \
556 * Allows execution of code that doesn't count torward the benchmark's
557 * time budget. Example:
559 * BENCHMARK_START_GROUP(insertVectorBegin, n) {
561 * BENCHMARK_SUSPEND {
564 * FOR_EACH_RANGE (i, 0, n) {
565 * v.insert(v.begin(), 42);
569 #define BENCHMARK_SUSPEND \
570 if (auto FB_ANONYMOUS_VARIABLE(BENCHMARK_SUSPEND) = \
571 ::folly::BenchmarkSuspender()) {} \