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