Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 376 lines (338 sloc) 11.806 kb
27494a2 @jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
1 /*
2 * Copyright 2012 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 namespace folly {
32
33 /**
34 * Runs all benchmarks defined. Usually put in main().
35 */
36 void runBenchmarks();
37
38 /**
39 * Runs all benchmarks defined if and only if the --benchmark flag has
40 * been passed to the program. Usually put in main().
41 */
42 inline bool runBenchmarksOnFlag() {
43 if (FLAGS_benchmark) {
44 runBenchmarks();
45 }
46 return FLAGS_benchmark;
47 }
48
49 namespace detail {
50
51 /**
52 * This is the clock ID used for measuring time. On older kernels, the
53 * resolution of this clock will be very coarse, which will cause the
54 * benchmarks to fail.
55 */
56 enum Clock { DEFAULT_CLOCK_ID = CLOCK_REALTIME };
57
58 /**
59 * Adds a benchmark wrapped in a std::function. Only used
60 * internally. Pass by value is intentional.
61 */
62 void addBenchmarkImpl(const char* file,
63 const char* name,
64 std::function<uint64_t(unsigned int)>);
65
66 /**
67 * Takes the difference between two timespec values. end is assumed to
68 * occur after start.
69 */
70 inline uint64_t timespecDiff(timespec end, timespec start) {
71 if (end.tv_sec == start.tv_sec) {
72 assert(end.tv_nsec >= start.tv_nsec);
73 return end.tv_nsec - start.tv_nsec;
74 }
75 assert(end.tv_sec > start.tv_sec &&
76 end.tv_sec - start.tv_sec <
77 std::numeric_limits<uint64_t>::max() / 1000000000UL);
78 return (end.tv_sec - start.tv_sec) * 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(detail::DEFAULT_CLOCK_ID, &start));
113 }
114
115 BenchmarkSuspender(const BenchmarkSuspender &) = delete;
116 BenchmarkSuspender(BenchmarkSuspender && rhs) {
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(detail::DEFAULT_CLOCK_ID, &start));
146 }
147
148 /**
149 * This helps the macro definition. To get around the dangers of
150 * operator bool, returns a pointer to member (which allows no
151 * arithmetic).
152 */
153 operator int BenchmarkSuspender::*() const {
154 return nullptr;
155 }
156
157 /**
158 * Accumulates nanoseconds spent outside benchmark.
159 */
160 typedef uint64_t NanosecondsSpent;
161 static NanosecondsSpent nsSpent;
162
163 private:
164 void tally() {
165 timespec end;
166 CHECK_EQ(0, clock_gettime(detail::DEFAULT_CLOCK_ID, &end));
167 nsSpent += detail::timespecDiff(end, start);
168 start = end;
169 }
170
171 timespec start;
172 };
173
174 /**
175 * Adds a benchmark. Usually not called directly but instead through
176 * the macro BENCHMARK defined below. The lambda function involved
177 * must take exactly one parameter of type unsigned, and the benchmark
178 * uses it with counter semantics (iteration occurs inside the
179 * function).
180 */
181 template <typename Lambda>
182 typename std::enable_if<
183 boost::function_types::function_arity<decltype(&Lambda::operator())>::value
184 == 2
185 >::type
186 addBenchmark(const char* file, const char* name, Lambda&& lambda) {
187 auto execute = [=](unsigned int times) {
188 BenchmarkSuspender::nsSpent = 0;
189 timespec start, end;
190
191 // CORE MEASUREMENT STARTS
192 CHECK_EQ(0, clock_gettime(detail::DEFAULT_CLOCK_ID, &start));
193 lambda(times);
194 CHECK_EQ(0, clock_gettime(detail::DEFAULT_CLOCK_ID, &end));
195 // CORE MEASUREMENT ENDS
196
197 return detail::timespecDiff(end, start) - BenchmarkSuspender::nsSpent;
198 };
199
200 detail::addBenchmarkImpl(file, name,
201 std::function<uint64_t(unsigned int)>(execute));
202 }
203
204 /**
205 * Adds a benchmark. Usually not called directly but instead through
206 * the macro BENCHMARK defined below. The lambda function involved
207 * must take zero parameters, and the benchmark calls it repeatedly
208 * (iteration occurs outside the function).
209 */
210 template <typename Lambda>
211 typename std::enable_if<
212 boost::function_types::function_arity<decltype(&Lambda::operator())>::value
213 == 1
214 >::type
215 addBenchmark(const char* file, const char* name, Lambda&& lambda) {
216 addBenchmark(file, name, [=](unsigned int times) {
217 while (times-- > 0) {
218 lambda();
219 }
220 });
221 }
222
223 /**
224 * Call doNotOptimizeAway(var) against variables that you use for
225 * benchmarking but otherwise are useless. The compiler tends to do a
226 * good job at eliminating unused variables, and this function fools
227 * it into thinking var is in fact needed.
228 */
229 template <class T>
230 void doNotOptimizeAway(T&& datum) {
231 asm volatile("" : "+r" (datum));
232 }
233
234 } // namespace folly
235
236 /**
237 * Introduces a benchmark function. Used internally, see BENCHMARK and
238 * friends below.
239 */
240 #define BENCHMARK_IMPL(funName, stringName, paramType, paramName) \
241 static void funName(paramType); \
242 static bool FB_ANONYMOUS_VARIABLE(follyBenchmarkUnused) = ( \
243 ::folly::addBenchmark(__FILE__, stringName, \
244 [](paramType paramName) { funName(paramName); }), \
245 true); \
246 static void funName(paramType paramName)
247
248 /**
249 * Introduces a benchmark function. Use with either one one or two
250 * arguments. The first is the name of the benchmark. Use something
251 * descriptive, such as insertVectorBegin. The second argument may be
252 * missing, or could be a symbolic counter. The counter dictates how
253 * many internal iteration the benchmark does. Example:
254 *
255 * BENCHMARK(vectorPushBack) {
256 * vector<int> v;
257 * v.push_back(42);
258 * }
259 *
260 * BENCHMARK(insertVectorBegin, n) {
261 * vector<int> v;
262 * FOR_EACH_RANGE (i, 0, n) {
263 * v.insert(v.begin(), 42);
264 * }
265 * }
266 */
267 #define BENCHMARK(name, ...) \
268 BENCHMARK_IMPL( \
269 name, \
270 FB_STRINGIZE(name), \
271 FB_ONE_OR_NONE(unsigned, ## __VA_ARGS__), \
272 __VA_ARGS__)
273
274 /**
275 * Defines a benchmark that passes a parameter to another one. This is
276 * common for benchmarks that need a "problem size" in addition to
277 * "number of iterations". Consider:
278 *
279 * void pushBack(uint n, size_t initialSize) {
280 * vector<int> v;
281 * BENCHMARK_SUSPEND {
282 * v.resize(initialSize);
283 * }
284 * FOR_EACH_RANGE (i, 0, n) {
285 * v.push_back(i);
286 * }
287 * }
288 * BENCHMARK_PARAM(pushBack, 0)
289 * BENCHMARK_PARAM(pushBack, 1000)
290 * BENCHMARK_PARAM(pushBack, 1000000)
291 *
292 * The benchmark above estimates the speed of push_back at different
293 * initial sizes of the vector. The framework will pass 0, 1000, and
294 * 1000000 for initialSize, and the iteration count for n.
295 */
296 #define BENCHMARK_PARAM(name, param) \
297 BENCHMARK_IMPL( \
298 FB_CONCATENATE(name, FB_CONCATENATE(_, param)), \
299 FB_STRINGIZE(name) "(" FB_STRINGIZE(param) ")", \
300 unsigned, \
301 iters) { \
302 name(iters, param); \
303 }
304
305 /**
306 * Just like BENCHMARK, but prints the time relative to a
307 * baseline. The baseline is the most recent BENCHMARK() seen in
308 * lexical order. Example:
309 *
310 * // This is the baseline
311 * BENCHMARK(insertVectorBegin, n) {
312 * vector<int> v;
313 * FOR_EACH_RANGE (i, 0, n) {
314 * v.insert(v.begin(), 42);
315 * }
316 * }
317 *
318 * BENCHMARK_RELATIVE(insertListBegin, n) {
319 * list<int> s;
320 * FOR_EACH_RANGE (i, 0, n) {
321 * s.insert(s.begin(), 42);
322 * }
323 * }
324 *
325 * Any number of relative benchmark can be associated with a
326 * baseline. Another BENCHMARK() occurrence effectively establishes a
327 * new baseline.
328 */
329 #define BENCHMARK_RELATIVE(name, ...) \
330 BENCHMARK_IMPL( \
331 name, \
332 "%" FB_STRINGIZE(name), \
333 FB_ONE_OR_NONE(unsigned, ## __VA_ARGS__), \
334 __VA_ARGS__)
335
336 /**
337 * A combination of BENCHMARK_RELATIVE and BENCHMARK_PARAM.
338 */
339 #define BENCHMARK_RELATIVE_PARAM(name, param) \
340 BENCHMARK_IMPL( \
341 FB_CONCATENATE(name, FB_CONCATENATE(_, param)), \
342 "%" FB_STRINGIZE(name) "(" FB_STRINGIZE(param) ")", \
343 unsigned, \
344 iters) { \
345 name(iters, param); \
346 }
347
348 /**
349 * Draws a line of dashes.
350 */
351 #define BENCHMARK_DRAW_LINE() \
352 static bool FB_ANONYMOUS_VARIABLE(follyBenchmarkUnused) = ( \
353 ::folly::addBenchmark(__FILE__, "-", []() { }), \
354 true);
355
356 /**
357 * Allows execution of code that doesn't count torward the benchmark's
358 * time budget. Example:
359 *
360 * BENCHMARK_START_GROUP(insertVectorBegin, n) {
361 * vector<int> v;
8108795 Fix a typo in benchmark comments
Sherman Ye authored
362 * BENCHMARK_SUSPEND {
27494a2 @jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
363 * v.reserve(n);
364 * }
365 * FOR_EACH_RANGE (i, 0, n) {
366 * v.insert(v.begin(), 42);
367 * }
368 * }
369 */
370 #define BENCHMARK_SUSPEND \
371 if (auto FB_ANONYMOUS_VARIABLE(BENCHMARK_SUSPEND) = \
372 ::folly::BenchmarkSuspender()) {} \
373 else
374
375 #endif // FOLLY_BENCHMARK_H_
Something went wrong with that request. Please try again.