1 // Copyright 2015 Google Inc. All rights reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "benchmark_register.h"
16
17 #ifndef BENCHMARK_OS_WINDOWS
18 #ifndef BENCHMARK_OS_FUCHSIA
19 #include <sys/resource.h>
20 #endif
21 #include <sys/time.h>
22 #include <unistd.h>
23 #endif
24
25 #include <algorithm>
26 #include <atomic>
27 #include <cinttypes>
28 #include <condition_variable>
29 #include <cstdio>
30 #include <cstdlib>
31 #include <cstring>
32 #include <fstream>
33 #include <iostream>
34 #include <memory>
35 #include <numeric>
36 #include <sstream>
37 #include <thread>
38
39 #include "benchmark/benchmark.h"
40 #include "benchmark_api_internal.h"
41 #include "check.h"
42 #include "commandlineflags.h"
43 #include "complexity.h"
44 #include "internal_macros.h"
45 #include "log.h"
46 #include "mutex.h"
47 #include "re.h"
48 #include "statistics.h"
49 #include "string_util.h"
50 #include "timers.h"
51
52 namespace benchmark {
53
54 namespace {
55 // For non-dense Range, intermediate values are powers of kRangeMultiplier.
56 static const int kRangeMultiplier = 8;
57 // The size of a benchmark family determines is the number of inputs to repeat
58 // the benchmark on. If this is "large" then warn the user during configuration.
59 static const size_t kMaxFamilySize = 100;
60 } // end namespace
61
62 namespace internal {
63
64 //=============================================================================//
65 // BenchmarkFamilies
66 //=============================================================================//
67
68 // Class for managing registered benchmarks. Note that each registered
69 // benchmark identifies a family of related benchmarks to run.
70 class BenchmarkFamilies {
71 public:
72 static BenchmarkFamilies* GetInstance();
73
74 // Registers a benchmark family and returns the index assigned to it.
75 size_t AddBenchmark(std::unique_ptr<Benchmark> family);
76
77 // Clear all registered benchmark families.
78 void ClearBenchmarks();
79
80 // Extract the list of benchmark instances that match the specified
81 // regular expression.
82 bool FindBenchmarks(std::string re,
83 std::vector<BenchmarkInstance>* benchmarks,
84 std::ostream* Err);
85
86 private:
BenchmarkFamilies()87 BenchmarkFamilies() {}
88
89 std::vector<std::unique_ptr<Benchmark>> families_;
90 Mutex mutex_;
91 };
92
GetInstance()93 BenchmarkFamilies* BenchmarkFamilies::GetInstance() {
94 static BenchmarkFamilies instance;
95 return &instance;
96 }
97
AddBenchmark(std::unique_ptr<Benchmark> family)98 size_t BenchmarkFamilies::AddBenchmark(std::unique_ptr<Benchmark> family) {
99 MutexLock l(mutex_);
100 size_t index = families_.size();
101 families_.push_back(std::move(family));
102 return index;
103 }
104
ClearBenchmarks()105 void BenchmarkFamilies::ClearBenchmarks() {
106 MutexLock l(mutex_);
107 families_.clear();
108 families_.shrink_to_fit();
109 }
110
FindBenchmarks(std::string spec,std::vector<BenchmarkInstance> * benchmarks,std::ostream * ErrStream)111 bool BenchmarkFamilies::FindBenchmarks(
112 std::string spec, std::vector<BenchmarkInstance>* benchmarks,
113 std::ostream* ErrStream) {
114 BM_CHECK(ErrStream);
115 auto& Err = *ErrStream;
116 // Make regular expression out of command-line flag
117 std::string error_msg;
118 Regex re;
119 bool isNegativeFilter = false;
120 if (spec[0] == '-') {
121 spec.replace(0, 1, "");
122 isNegativeFilter = true;
123 }
124 if (!re.Init(spec, &error_msg)) {
125 Err << "Could not compile benchmark re: " << error_msg << std::endl;
126 return false;
127 }
128
129 // Special list of thread counts to use when none are specified
130 const std::vector<int> one_thread = {1};
131
132 int next_family_index = 0;
133
134 MutexLock l(mutex_);
135 for (std::unique_ptr<Benchmark>& family : families_) {
136 int family_index = next_family_index;
137 int per_family_instance_index = 0;
138
139 // Family was deleted or benchmark doesn't match
140 if (!family) continue;
141
142 if (family->ArgsCnt() == -1) {
143 family->Args({});
144 }
145 const std::vector<int>* thread_counts =
146 (family->thread_counts_.empty()
147 ? &one_thread
148 : &static_cast<const std::vector<int>&>(family->thread_counts_));
149 const size_t family_size = family->args_.size() * thread_counts->size();
150 // The benchmark will be run at least 'family_size' different inputs.
151 // If 'family_size' is very large warn the user.
152 if (family_size > kMaxFamilySize) {
153 Err << "The number of inputs is very large. " << family->name_
154 << " will be repeated at least " << family_size << " times.\n";
155 }
156 // reserve in the special case the regex ".", since we know the final
157 // family size.
158 if (spec == ".") benchmarks->reserve(benchmarks->size() + family_size);
159
160 for (auto const& args : family->args_) {
161 for (int num_threads : *thread_counts) {
162 BenchmarkInstance instance(family.get(), family_index,
163 per_family_instance_index, args,
164 num_threads);
165
166 const auto full_name = instance.name().str();
167 if ((re.Match(full_name) && !isNegativeFilter) ||
168 (!re.Match(full_name) && isNegativeFilter)) {
169 benchmarks->push_back(std::move(instance));
170
171 ++per_family_instance_index;
172
173 // Only bump the next family index once we've estabilished that
174 // at least one instance of this family will be run.
175 if (next_family_index == family_index) ++next_family_index;
176 }
177 }
178 }
179 }
180 return true;
181 }
182
RegisterBenchmarkInternal(Benchmark * bench)183 Benchmark* RegisterBenchmarkInternal(Benchmark* bench) {
184 std::unique_ptr<Benchmark> bench_ptr(bench);
185 BenchmarkFamilies* families = BenchmarkFamilies::GetInstance();
186 families->AddBenchmark(std::move(bench_ptr));
187 return bench;
188 }
189
190 // FIXME: This function is a hack so that benchmark.cc can access
191 // `BenchmarkFamilies`
FindBenchmarksInternal(const std::string & re,std::vector<BenchmarkInstance> * benchmarks,std::ostream * Err)192 bool FindBenchmarksInternal(const std::string& re,
193 std::vector<BenchmarkInstance>* benchmarks,
194 std::ostream* Err) {
195 return BenchmarkFamilies::GetInstance()->FindBenchmarks(re, benchmarks, Err);
196 }
197
198 //=============================================================================//
199 // Benchmark
200 //=============================================================================//
201
Benchmark(const char * name)202 Benchmark::Benchmark(const char* name)
203 : name_(name),
204 aggregation_report_mode_(ARM_Unspecified),
205 time_unit_(kNanosecond),
206 range_multiplier_(kRangeMultiplier),
207 min_time_(0),
208 iterations_(0),
209 repetitions_(0),
210 measure_process_cpu_time_(false),
211 use_real_time_(false),
212 use_manual_time_(false),
213 complexity_(oNone),
214 complexity_lambda_(nullptr),
215 setup_(nullptr),
216 teardown_(nullptr) {
217 ComputeStatistics("mean", StatisticsMean);
218 ComputeStatistics("median", StatisticsMedian);
219 ComputeStatistics("stddev", StatisticsStdDev);
220 ComputeStatistics("cv", StatisticsCV, kPercentage);
221 }
222
~Benchmark()223 Benchmark::~Benchmark() {}
224
Name(const std::string & name)225 Benchmark* Benchmark::Name(const std::string& name) {
226 SetName(name.c_str());
227 return this;
228 }
229
Arg(int64_t x)230 Benchmark* Benchmark::Arg(int64_t x) {
231 BM_CHECK(ArgsCnt() == -1 || ArgsCnt() == 1);
232 args_.push_back({x});
233 return this;
234 }
235
Unit(TimeUnit unit)236 Benchmark* Benchmark::Unit(TimeUnit unit) {
237 time_unit_ = unit;
238 return this;
239 }
240
Range(int64_t start,int64_t limit)241 Benchmark* Benchmark::Range(int64_t start, int64_t limit) {
242 BM_CHECK(ArgsCnt() == -1 || ArgsCnt() == 1);
243 std::vector<int64_t> arglist;
244 AddRange(&arglist, start, limit, range_multiplier_);
245
246 for (int64_t i : arglist) {
247 args_.push_back({i});
248 }
249 return this;
250 }
251
Ranges(const std::vector<std::pair<int64_t,int64_t>> & ranges)252 Benchmark* Benchmark::Ranges(
253 const std::vector<std::pair<int64_t, int64_t>>& ranges) {
254 BM_CHECK(ArgsCnt() == -1 || ArgsCnt() == static_cast<int>(ranges.size()));
255 std::vector<std::vector<int64_t>> arglists(ranges.size());
256 for (std::size_t i = 0; i < ranges.size(); i++) {
257 AddRange(&arglists[i], ranges[i].first, ranges[i].second,
258 range_multiplier_);
259 }
260
261 ArgsProduct(arglists);
262
263 return this;
264 }
265
ArgsProduct(const std::vector<std::vector<int64_t>> & arglists)266 Benchmark* Benchmark::ArgsProduct(
267 const std::vector<std::vector<int64_t>>& arglists) {
268 BM_CHECK(ArgsCnt() == -1 || ArgsCnt() == static_cast<int>(arglists.size()));
269
270 std::vector<std::size_t> indices(arglists.size());
271 const std::size_t total = std::accumulate(
272 std::begin(arglists), std::end(arglists), std::size_t{1},
273 [](const std::size_t res, const std::vector<int64_t>& arglist) {
274 return res * arglist.size();
275 });
276 std::vector<int64_t> args;
277 args.reserve(arglists.size());
278 for (std::size_t i = 0; i < total; i++) {
279 for (std::size_t arg = 0; arg < arglists.size(); arg++) {
280 args.push_back(arglists[arg][indices[arg]]);
281 }
282 args_.push_back(args);
283 args.clear();
284
285 std::size_t arg = 0;
286 do {
287 indices[arg] = (indices[arg] + 1) % arglists[arg].size();
288 } while (indices[arg++] == 0 && arg < arglists.size());
289 }
290
291 return this;
292 }
293
ArgName(const std::string & name)294 Benchmark* Benchmark::ArgName(const std::string& name) {
295 BM_CHECK(ArgsCnt() == -1 || ArgsCnt() == 1);
296 arg_names_ = {name};
297 return this;
298 }
299
ArgNames(const std::vector<std::string> & names)300 Benchmark* Benchmark::ArgNames(const std::vector<std::string>& names) {
301 BM_CHECK(ArgsCnt() == -1 || ArgsCnt() == static_cast<int>(names.size()));
302 arg_names_ = names;
303 return this;
304 }
305
DenseRange(int64_t start,int64_t limit,int step)306 Benchmark* Benchmark::DenseRange(int64_t start, int64_t limit, int step) {
307 BM_CHECK(ArgsCnt() == -1 || ArgsCnt() == 1);
308 BM_CHECK_LE(start, limit);
309 for (int64_t arg = start; arg <= limit; arg += step) {
310 args_.push_back({arg});
311 }
312 return this;
313 }
314
Args(const std::vector<int64_t> & args)315 Benchmark* Benchmark::Args(const std::vector<int64_t>& args) {
316 BM_CHECK(ArgsCnt() == -1 || ArgsCnt() == static_cast<int>(args.size()));
317 args_.push_back(args);
318 return this;
319 }
320
Apply(void (* custom_arguments)(Benchmark * benchmark))321 Benchmark* Benchmark::Apply(void (*custom_arguments)(Benchmark* benchmark)) {
322 custom_arguments(this);
323 return this;
324 }
325
Setup(void (* setup)(const benchmark::State &))326 Benchmark* Benchmark::Setup(void (*setup)(const benchmark::State&)) {
327 BM_CHECK(setup != nullptr);
328 setup_ = setup;
329 return this;
330 }
331
Teardown(void (* teardown)(const benchmark::State &))332 Benchmark* Benchmark::Teardown(void (*teardown)(const benchmark::State&)) {
333 BM_CHECK(teardown != nullptr);
334 teardown_ = teardown;
335 return this;
336 }
337
RangeMultiplier(int multiplier)338 Benchmark* Benchmark::RangeMultiplier(int multiplier) {
339 BM_CHECK(multiplier > 1);
340 range_multiplier_ = multiplier;
341 return this;
342 }
343
MinTime(double t)344 Benchmark* Benchmark::MinTime(double t) {
345 BM_CHECK(t > 0.0);
346 BM_CHECK(iterations_ == 0);
347 min_time_ = t;
348 return this;
349 }
350
Iterations(IterationCount n)351 Benchmark* Benchmark::Iterations(IterationCount n) {
352 BM_CHECK(n > 0);
353 BM_CHECK(IsZero(min_time_));
354 iterations_ = n;
355 return this;
356 }
357
Repetitions(int n)358 Benchmark* Benchmark::Repetitions(int n) {
359 BM_CHECK(n > 0);
360 repetitions_ = n;
361 return this;
362 }
363
ReportAggregatesOnly(bool value)364 Benchmark* Benchmark::ReportAggregatesOnly(bool value) {
365 aggregation_report_mode_ = value ? ARM_ReportAggregatesOnly : ARM_Default;
366 return this;
367 }
368
DisplayAggregatesOnly(bool value)369 Benchmark* Benchmark::DisplayAggregatesOnly(bool value) {
370 // If we were called, the report mode is no longer 'unspecified', in any case.
371 aggregation_report_mode_ = static_cast<AggregationReportMode>(
372 aggregation_report_mode_ | ARM_Default);
373
374 if (value) {
375 aggregation_report_mode_ = static_cast<AggregationReportMode>(
376 aggregation_report_mode_ | ARM_DisplayReportAggregatesOnly);
377 } else {
378 aggregation_report_mode_ = static_cast<AggregationReportMode>(
379 aggregation_report_mode_ & ~ARM_DisplayReportAggregatesOnly);
380 }
381
382 return this;
383 }
384
MeasureProcessCPUTime()385 Benchmark* Benchmark::MeasureProcessCPUTime() {
386 // Can be used together with UseRealTime() / UseManualTime().
387 measure_process_cpu_time_ = true;
388 return this;
389 }
390
UseRealTime()391 Benchmark* Benchmark::UseRealTime() {
392 BM_CHECK(!use_manual_time_)
393 << "Cannot set UseRealTime and UseManualTime simultaneously.";
394 use_real_time_ = true;
395 return this;
396 }
397
UseManualTime()398 Benchmark* Benchmark::UseManualTime() {
399 BM_CHECK(!use_real_time_)
400 << "Cannot set UseRealTime and UseManualTime simultaneously.";
401 use_manual_time_ = true;
402 return this;
403 }
404
Complexity(BigO complexity)405 Benchmark* Benchmark::Complexity(BigO complexity) {
406 complexity_ = complexity;
407 return this;
408 }
409
Complexity(BigOFunc * complexity)410 Benchmark* Benchmark::Complexity(BigOFunc* complexity) {
411 complexity_lambda_ = complexity;
412 complexity_ = oLambda;
413 return this;
414 }
415
ComputeStatistics(const std::string & name,StatisticsFunc * statistics,StatisticUnit unit)416 Benchmark* Benchmark::ComputeStatistics(const std::string& name,
417 StatisticsFunc* statistics,
418 StatisticUnit unit) {
419 statistics_.emplace_back(name, statistics, unit);
420 return this;
421 }
422
Threads(int t)423 Benchmark* Benchmark::Threads(int t) {
424 BM_CHECK_GT(t, 0);
425 thread_counts_.push_back(t);
426 return this;
427 }
428
ThreadRange(int min_threads,int max_threads)429 Benchmark* Benchmark::ThreadRange(int min_threads, int max_threads) {
430 BM_CHECK_GT(min_threads, 0);
431 BM_CHECK_GE(max_threads, min_threads);
432
433 AddRange(&thread_counts_, min_threads, max_threads, 2);
434 return this;
435 }
436
DenseThreadRange(int min_threads,int max_threads,int stride)437 Benchmark* Benchmark::DenseThreadRange(int min_threads, int max_threads,
438 int stride) {
439 BM_CHECK_GT(min_threads, 0);
440 BM_CHECK_GE(max_threads, min_threads);
441 BM_CHECK_GE(stride, 1);
442
443 for (auto i = min_threads; i < max_threads; i += stride) {
444 thread_counts_.push_back(i);
445 }
446 thread_counts_.push_back(max_threads);
447 return this;
448 }
449
ThreadPerCpu()450 Benchmark* Benchmark::ThreadPerCpu() {
451 thread_counts_.push_back(CPUInfo::Get().num_cpus);
452 return this;
453 }
454
SetName(const char * name)455 void Benchmark::SetName(const char* name) { name_ = name; }
456
ArgsCnt() const457 int Benchmark::ArgsCnt() const {
458 if (args_.empty()) {
459 if (arg_names_.empty()) return -1;
460 return static_cast<int>(arg_names_.size());
461 }
462 return static_cast<int>(args_.front().size());
463 }
464
465 //=============================================================================//
466 // FunctionBenchmark
467 //=============================================================================//
468
Run(State & st)469 void FunctionBenchmark::Run(State& st) { func_(st); }
470
471 } // end namespace internal
472
ClearRegisteredBenchmarks()473 void ClearRegisteredBenchmarks() {
474 internal::BenchmarkFamilies::GetInstance()->ClearBenchmarks();
475 }
476
CreateRange(int64_t lo,int64_t hi,int multi)477 std::vector<int64_t> CreateRange(int64_t lo, int64_t hi, int multi) {
478 std::vector<int64_t> args;
479 internal::AddRange(&args, lo, hi, multi);
480 return args;
481 }
482
CreateDenseRange(int64_t start,int64_t limit,int step)483 std::vector<int64_t> CreateDenseRange(int64_t start, int64_t limit, int step) {
484 BM_CHECK_LE(start, limit);
485 std::vector<int64_t> args;
486 for (int64_t arg = start; arg <= limit; arg += step) {
487 args.push_back(arg);
488 }
489 return args;
490 }
491
492 } // end namespace benchmark
493