Grok  9.5.0
nanobenchmark.h
Go to the documentation of this file.
1 // Copyright 2019 Google LLC
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 #ifndef HIGHWAY_HWY_NANOBENCHMARK_H_
16 #define HIGHWAY_HWY_NANOBENCHMARK_H_
17 
18 // Benchmarks functions of a single integer argument with realistic branch
19 // prediction hit rates. Uses a robust estimator to summarize the measurements.
20 // The precision is about 0.2%.
21 //
22 // Examples: see nanobenchmark_test.cc.
23 //
24 // Background: Microbenchmarks such as http://github.com/google/benchmark
25 // can measure elapsed times on the order of a microsecond. Shorter functions
26 // are typically measured by repeating them thousands of times and dividing
27 // the total elapsed time by this count. Unfortunately, repetition (especially
28 // with the same input parameter!) influences the runtime. In time-critical
29 // code, it is reasonable to expect warm instruction/data caches and TLBs,
30 // but a perfect record of which branches will be taken is unrealistic.
31 // Unless the application also repeatedly invokes the measured function with
32 // the same parameter, the benchmark is measuring something very different -
33 // a best-case result, almost as if the parameter were made a compile-time
34 // constant. This may lead to erroneous conclusions about branch-heavy
35 // algorithms outperforming branch-free alternatives.
36 //
37 // Our approach differs in three ways. Adding fences to the timer functions
38 // reduces variability due to instruction reordering, improving the timer
39 // resolution to about 40 CPU cycles. However, shorter functions must still
40 // be invoked repeatedly. For more realistic branch prediction performance,
41 // we vary the input parameter according to a user-specified distribution.
42 // Thus, instead of VaryInputs(Measure(Repeat(func))), we change the
43 // loop nesting to Measure(Repeat(VaryInputs(func))). We also estimate the
44 // central tendency of the measurement samples with the "half sample mode",
45 // which is more robust to outliers and skewed data than the mean or median.
46 
47 #include <stddef.h>
48 #include <stdint.h>
49 
50 // Enables sanity checks that verify correct operation at the cost of
51 // longer benchmark runs.
52 #ifndef NANOBENCHMARK_ENABLE_CHECKS
53 #define NANOBENCHMARK_ENABLE_CHECKS 0
54 #endif
55 
56 #define NANOBENCHMARK_CHECK_ALWAYS(condition) \
57  while (!(condition)) { \
58  fprintf(stderr, "Nanobenchmark check failed at line %d\n", __LINE__); \
59  abort(); \
60  }
61 
62 #if NANOBENCHMARK_ENABLE_CHECKS
63 #define NANOBENCHMARK_CHECK(condition) NANOBENCHMARK_CHECK_ALWAYS(condition)
64 #else
65 #define NANOBENCHMARK_CHECK(condition)
66 #endif
67 
68 namespace hwy {
69 
70 namespace platform {
71 
72 // Returns tick rate, useful for converting measurements to seconds. Invariant
73 // means the tick counter frequency is independent of CPU throttling or sleep.
74 // This call may be expensive, callers should cache the result.
76 
77 // Returns current timestamp [in seconds] relative to an unspecified origin.
78 // Features: monotonic (no negative elapsed time), steady (unaffected by system
79 // time changes), high-resolution (on the order of microseconds).
80 double Now();
81 
82 // Returns ticks elapsed in back to back timer calls, i.e. a function of the
83 // timer resolution (minimum measurable difference) and overhead.
84 // This call is expensive, callers should cache the result.
85 uint64_t TimerResolution();
86 
87 } // namespace platform
88 
89 // Returns 1, but without the compiler knowing what the value is. This prevents
90 // optimizing out code.
92 
93 // Input influencing the function being measured (e.g. number of bytes to copy).
94 using FuncInput = size_t;
95 
96 // "Proof of work" returned by Func to ensure the compiler does not elide it.
97 using FuncOutput = uint64_t;
98 
99 // Function to measure: either 1) a captureless lambda or function with two
100 // arguments or 2) a lambda with capture, in which case the first argument
101 // is reserved for use by MeasureClosure.
102 using Func = FuncOutput (*)(const void*, FuncInput);
103 
104 // Internal parameters that determine precision/resolution/measuring time.
105 struct Params {
106  // For measuring timer overhead/resolution. Used in a nested loop =>
107  // quadratic time, acceptable because we know timer overhead is "low".
108  // constexpr because this is used to define array bounds.
109  static constexpr size_t kTimerSamples = 256;
110 
111  // Best-case precision, expressed as a divisor of the timer resolution.
112  // Larger => more calls to Func and higher precision.
113  size_t precision_divisor = 1024;
114 
115  // Ratio between full and subset input distribution sizes. Cannot be less
116  // than 2; larger values increase measurement time but more faithfully
117  // model the given input distribution.
118  size_t subset_ratio = 2;
119 
120  // Together with the estimated Func duration, determines how many times to
121  // call Func before checking the sample variability. Larger values increase
122  // measurement time, memory/cache use and precision.
123  double seconds_per_eval = 4E-3;
124 
125  // The minimum number of samples before estimating the central tendency.
127 
128  // The mode is better than median for estimating the central tendency of
129  // skewed/fat-tailed distributions, but it requires sufficient samples
130  // relative to the width of half-ranges.
131  size_t min_mode_samples = 64;
132 
133  // Maximum permissible variability (= median absolute deviation / center).
134  double target_rel_mad = 0.002;
135 
136  // Abort after this many evals without reaching target_rel_mad. This
137  // prevents infinite loops.
138  size_t max_evals = 9;
139 
140  // Whether to print additional statistics to stdout.
141  bool verbose = true;
142 };
143 
144 // Measurement result for each unique input.
145 struct Result {
147 
148  // Robust estimate (mode or median) of duration.
149  float ticks;
150 
151  // Measure of variability (median absolute deviation relative to "ticks").
152  float variability;
153 };
154 
155 // Precisely measures the number of ticks elapsed when calling "func" with the
156 // given inputs, shuffled to ensure realistic branch prediction hit rates.
157 //
158 // "func" returns a 'proof of work' to ensure its computations are not elided.
159 // "arg" is passed to Func, or reserved for internal use by MeasureClosure.
160 // "inputs" is an array of "num_inputs" (not necessarily unique) arguments to
161 // "func". The values should be chosen to maximize coverage of "func". This
162 // represents a distribution, so a value's frequency should reflect its
163 // probability in the real application. Order does not matter; for example, a
164 // uniform distribution over [0, 4) could be represented as {3,0,2,1}.
165 // Returns how many Result were written to "results": one per unique input, or
166 // zero if the measurement failed (an error message goes to stderr).
167 size_t Measure(const Func func, const uint8_t* arg, const FuncInput* inputs,
168  const size_t num_inputs, Result* results,
169  const Params& p = Params());
170 
171 // Calls operator() of the given closure (lambda function).
172 template <class Closure>
173 static FuncOutput CallClosure(const Closure* f, const FuncInput input) {
174  return (*f)(input);
175 }
176 
177 // Same as Measure, except "closure" is typically a lambda function of
178 // FuncInput -> FuncOutput with a capture list.
179 template <class Closure>
180 static inline size_t MeasureClosure(const Closure& closure,
181  const FuncInput* inputs,
182  const size_t num_inputs, Result* results,
183  const Params& p = Params()) {
184  return Measure(reinterpret_cast<Func>(&CallClosure<Closure>),
185  reinterpret_cast<const uint8_t*>(&closure), inputs, num_inputs,
186  results, p);
187 }
188 
189 } // namespace hwy
190 
191 #endif // HIGHWAY_HWY_NANOBENCHMARK_H_
uint64_t TimerResolution()
double InvariantTicksPerSecond()
double Now()
Definition: aligned_allocator.h:23
static FuncOutput CallClosure(const Closure *f, const FuncInput input)
Definition: nanobenchmark.h:173
FuncOutput(*)(const void *, FuncInput) Func
Definition: nanobenchmark.h:102
size_t FuncInput
Definition: nanobenchmark.h:94
size_t Measure(const Func func, const uint8_t *arg, const FuncInput *inputs, const size_t num_inputs, Result *results, const Params &p=Params())
uint64_t FuncOutput
Definition: nanobenchmark.h:97
static size_t MeasureClosure(const Closure &closure, const FuncInput *inputs, const size_t num_inputs, Result *results, const Params &p=Params())
Definition: nanobenchmark.h:180
int Unpredictable1()
Definition: nanobenchmark.h:105
size_t subset_ratio
Definition: nanobenchmark.h:118
size_t precision_divisor
Definition: nanobenchmark.h:113
bool verbose
Definition: nanobenchmark.h:141
size_t min_mode_samples
Definition: nanobenchmark.h:131
static constexpr size_t kTimerSamples
Definition: nanobenchmark.h:109
size_t max_evals
Definition: nanobenchmark.h:138
double target_rel_mad
Definition: nanobenchmark.h:134
size_t min_samples_per_eval
Definition: nanobenchmark.h:126
double seconds_per_eval
Definition: nanobenchmark.h:123
Definition: nanobenchmark.h:145
float ticks
Definition: nanobenchmark.h:149
float variability
Definition: nanobenchmark.h:152
FuncInput input
Definition: nanobenchmark.h:146