| //===-- Benchmark function --------------------------------------*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| // This file mainly defines a `Benchmark` function. |
| // |
| // The benchmarking process is as follows: |
| // - We start by measuring the time it takes to run the function |
| // `InitialIterations` times. This is called a Sample. From this we can derive |
| // the time it took to run a single iteration. |
| // |
| // - We repeat the previous step with a greater number of iterations to lower |
| // the impact of the measurement. We can derive a more precise estimation of the |
| // runtime for a single iteration. |
| // |
| // - Each sample gives a more accurate estimation of the runtime for a single |
| // iteration but also takes more time to run. We stop the process when: |
| // * The measure stabilize under a certain precision (Epsilon), |
| // * The overall benchmarking time is greater than MaxDuration, |
| // * The overall sample count is greater than MaxSamples, |
| // * The last sample used more than MaxIterations iterations. |
| // |
| // - We also makes sure that the benchmark doesn't run for a too short period of |
| // time by defining MinDuration and MinSamples. |
| |
| #ifndef LLVM_LIBC_UTILS_BENCHMARK_BENCHMARK_H |
| #define LLVM_LIBC_UTILS_BENCHMARK_BENCHMARK_H |
| |
| #include "benchmark/benchmark.h" |
| #include "llvm/ADT/ArrayRef.h" |
| #include "llvm/ADT/Optional.h" |
| #include "llvm/ADT/SmallVector.h" |
| #include <array> |
| #include <chrono> |
| #include <cmath> |
| #include <cstdint> |
| |
| namespace llvm { |
| namespace libc_benchmarks { |
| |
| using Duration = std::chrono::duration<double>; |
| |
| enum class BenchmarkLog { |
| None, // Don't keep the internal state of the benchmark. |
| Last, // Keep only the last batch. |
| Full // Keep all iterations states, useful for testing or debugging. |
| }; |
| |
| // An object to configure the benchmark stopping conditions. |
| // See documentation at the beginning of the file for the overall algorithm and |
| // meaning of each field. |
| struct BenchmarkOptions { |
| // The minimum time for which the benchmark is running. |
| Duration MinDuration = std::chrono::seconds(0); |
| // The maximum time for which the benchmark is running. |
| Duration MaxDuration = std::chrono::seconds(10); |
| // The number of iterations in the first sample. |
| uint32_t InitialIterations = 1; |
| // The maximum number of iterations for any given sample. |
| uint32_t MaxIterations = 10000000; |
| // The minimum number of samples. |
| uint32_t MinSamples = 4; |
| // The maximum number of samples. |
| uint32_t MaxSamples = 1000; |
| // The benchmark will stop if the relative difference between the current and |
| // the last estimation is less than epsilon. This is 1% by default. |
| double Epsilon = 0.01; |
| // The number of iterations grows exponentially between each sample. |
| // Must be greater or equal to 1. |
| double ScalingFactor = 1.4; |
| BenchmarkLog Log = BenchmarkLog::None; |
| }; |
| |
| // The state of a benchmark. |
| enum class BenchmarkStatus { |
| Running, |
| MaxDurationReached, |
| MaxIterationsReached, |
| MaxSamplesReached, |
| PrecisionReached, |
| }; |
| |
| // The internal state of the benchmark, useful to debug, test or report |
| // statistics. |
| struct BenchmarkState { |
| size_t LastSampleIterations; |
| Duration LastBatchElapsed; |
| BenchmarkStatus CurrentStatus; |
| Duration CurrentBestGuess; // The time estimation for a single run of `foo`. |
| double ChangeRatio; // The change in time estimation between previous and |
| // current samples. |
| }; |
| |
| // A lightweight result for a benchmark. |
| struct BenchmarkResult { |
| BenchmarkStatus TerminationStatus = BenchmarkStatus::Running; |
| Duration BestGuess = {}; |
| llvm::Optional<llvm::SmallVector<BenchmarkState, 16>> MaybeBenchmarkLog; |
| }; |
| |
| // Stores information about a cache in the host memory system. |
| struct CacheInfo { |
| std::string Type; // e.g. "Instruction", "Data", "Unified". |
| int Level; // 0 is closest to processing unit. |
| int Size; // In bytes. |
| int NumSharing; // The number of processing units (Hyper-Threading Thread) |
| // with which this cache is shared. |
| }; |
| |
| // Stores information about the host. |
| struct HostState { |
| std::string CpuName; // returns a string compatible with the -march option. |
| double CpuFrequency; // in Hertz. |
| std::vector<CacheInfo> Caches; |
| |
| static HostState get(); |
| }; |
| |
| namespace internal { |
| |
| struct Measurement { |
| size_t Iterations = 0; |
| Duration Elapsed = {}; |
| }; |
| |
| // Updates the estimation of the elapsed time for a single iteration. |
| class RefinableRuntimeEstimation { |
| Duration TotalTime = {}; |
| size_t TotalIterations = 0; |
| |
| public: |
| Duration update(const Measurement &M) { |
| assert(M.Iterations > 0); |
| // Duration is encoded as a double (see definition). |
| // `TotalTime` and `M.Elapsed` are of the same magnitude so we don't expect |
| // loss of precision due to radically different scales. |
| TotalTime += M.Elapsed; |
| TotalIterations += M.Iterations; |
| return TotalTime / TotalIterations; |
| } |
| }; |
| |
| // This class tracks the progression of the runtime estimation. |
| class RuntimeEstimationProgression { |
| RefinableRuntimeEstimation RRE; |
| |
| public: |
| Duration CurrentEstimation = {}; |
| |
| // Returns the change ratio between our best guess so far and the one from the |
| // new measurement. |
| double computeImprovement(const Measurement &M) { |
| const Duration NewEstimation = RRE.update(M); |
| const double Ratio = fabs(((CurrentEstimation / NewEstimation) - 1.0)); |
| CurrentEstimation = NewEstimation; |
| return Ratio; |
| } |
| }; |
| |
| } // namespace internal |
| |
| // Measures the runtime of `foo` until conditions defined by `Options` are met. |
| // |
| // To avoid measurement's imprecisions we measure batches of `foo`. |
| // The batch size is growing by `ScalingFactor` to minimize the effect of |
| // measuring. |
| // |
| // Note: The benchmark is not responsible for serializing the executions of |
| // `foo`. It is not suitable for measuring, very small & side effect free |
| // functions, as the processor is free to execute several executions in |
| // parallel. |
| // |
| // - Options: A set of parameters controlling the stopping conditions for the |
| // benchmark. |
| // - foo: The function under test. It takes one value and returns one value. |
| // The input value is used to randomize the execution of `foo` as part of a |
| // batch to mitigate the effect of the branch predictor. Signature: |
| // `ProductType foo(ParameterProvider::value_type value);` |
| // The output value is a product of the execution of `foo` and prevents the |
| // compiler from optimizing out foo's body. |
| // - ParameterProvider: An object responsible for providing a range of |
| // `Iterations` values to use as input for `foo`. The `value_type` of the |
| // returned container has to be compatible with `foo` argument. |
| // Must implement one of: |
| // `Container<ParameterType> generateBatch(size_t Iterations);` |
| // `const Container<ParameterType>& generateBatch(size_t Iterations);` |
| // - Clock: An object providing the current time. Must implement: |
| // `std::chrono::time_point now();` |
| template <typename Function, typename ParameterProvider, |
| typename BenchmarkClock = const std::chrono::high_resolution_clock> |
| BenchmarkResult benchmark(const BenchmarkOptions &Options, |
| ParameterProvider &PP, Function foo, |
| BenchmarkClock &Clock = BenchmarkClock()) { |
| BenchmarkResult Result; |
| internal::RuntimeEstimationProgression REP; |
| Duration TotalBenchmarkDuration = {}; |
| size_t Iterations = std::max(Options.InitialIterations, uint32_t(1)); |
| size_t Samples = 0; |
| if (Options.ScalingFactor < 1.0) |
| report_fatal_error("ScalingFactor should be >= 1"); |
| if (Options.Log != BenchmarkLog::None) |
| Result.MaybeBenchmarkLog.emplace(); |
| for (;;) { |
| // Request a new Batch of size `Iterations`. |
| const auto &Batch = PP.generateBatch(Iterations); |
| |
| // Measuring this Batch. |
| const auto StartTime = Clock.now(); |
| for (const auto Parameter : Batch) { |
| const auto Production = foo(Parameter); |
| benchmark::DoNotOptimize(Production); |
| } |
| const auto EndTime = Clock.now(); |
| const Duration Elapsed = EndTime - StartTime; |
| |
| // Updating statistics. |
| ++Samples; |
| TotalBenchmarkDuration += Elapsed; |
| const double ChangeRatio = REP.computeImprovement({Iterations, Elapsed}); |
| Result.BestGuess = REP.CurrentEstimation; |
| |
| // Stopping condition. |
| if (TotalBenchmarkDuration >= Options.MinDuration && |
| Samples >= Options.MinSamples && ChangeRatio < Options.Epsilon) |
| Result.TerminationStatus = BenchmarkStatus::PrecisionReached; |
| else if (Samples >= Options.MaxSamples) |
| Result.TerminationStatus = BenchmarkStatus::MaxSamplesReached; |
| else if (TotalBenchmarkDuration >= Options.MaxDuration) |
| Result.TerminationStatus = BenchmarkStatus::MaxDurationReached; |
| else if (Iterations >= Options.MaxIterations) |
| Result.TerminationStatus = BenchmarkStatus::MaxIterationsReached; |
| |
| if (Result.MaybeBenchmarkLog) { |
| auto &BenchmarkLog = *Result.MaybeBenchmarkLog; |
| if (Options.Log == BenchmarkLog::Last && !BenchmarkLog.empty()) |
| BenchmarkLog.pop_back(); |
| BenchmarkState BS; |
| BS.LastSampleIterations = Iterations; |
| BS.LastBatchElapsed = Elapsed; |
| BS.CurrentStatus = Result.TerminationStatus; |
| BS.CurrentBestGuess = Result.BestGuess; |
| BS.ChangeRatio = ChangeRatio; |
| BenchmarkLog.push_back(BS); |
| } |
| |
| if (Result.TerminationStatus != BenchmarkStatus::Running) |
| return Result; |
| |
| if (Options.ScalingFactor > 1 && |
| Iterations * Options.ScalingFactor == Iterations) |
| report_fatal_error( |
| "`Iterations *= ScalingFactor` is idempotent, increase ScalingFactor " |
| "or InitialIterations."); |
| |
| Iterations *= Options.ScalingFactor; |
| } |
| } |
| |
| // Interprets `Array` as a circular buffer of `Size` elements. |
| template <typename T> class CircularArrayRef { |
| llvm::ArrayRef<T> Array; |
| size_t Size; |
| |
| public: |
| using value_type = T; |
| using reference = T &; |
| using const_reference = const T &; |
| using difference_type = ssize_t; |
| using size_type = size_t; |
| |
| class const_iterator |
| : public std::iterator<std::input_iterator_tag, T, ssize_t> { |
| llvm::ArrayRef<T> Array; |
| size_t Index; |
| size_t Offset; |
| |
| public: |
| explicit const_iterator(llvm::ArrayRef<T> Array, size_t Index = 0) |
| : Array(Array), Index(Index), Offset(Index % Array.size()) {} |
| const_iterator &operator++() { |
| ++Index; |
| ++Offset; |
| if (Offset == Array.size()) |
| Offset = 0; |
| return *this; |
| } |
| bool operator==(const_iterator Other) const { return Index == Other.Index; } |
| bool operator!=(const_iterator Other) const { return !(*this == Other); } |
| const T &operator*() const { return Array[Offset]; } |
| }; |
| |
| CircularArrayRef(llvm::ArrayRef<T> Array, size_t Size) |
| : Array(Array), Size(Size) { |
| assert(Array.size() > 0); |
| } |
| |
| const_iterator begin() const { return const_iterator(Array); } |
| const_iterator end() const { return const_iterator(Array, Size); } |
| }; |
| |
| // A convenient helper to produce a CircularArrayRef from an ArrayRef. |
| template <typename T> |
| CircularArrayRef<T> cycle(llvm::ArrayRef<T> Array, size_t Size) { |
| return {Array, Size}; |
| } |
| |
| // Creates an std::array which storage size is constrained under `Bytes`. |
| template <typename T, size_t Bytes> |
| using ByteConstrainedArray = std::array<T, Bytes / sizeof(T)>; |
| |
| // A convenient helper to produce a CircularArrayRef from a |
| // ByteConstrainedArray. |
| template <typename T, size_t N> |
| CircularArrayRef<T> cycle(const std::array<T, N> &Container, size_t Size) { |
| return {llvm::ArrayRef<T>(Container.cbegin(), Container.cend()), Size}; |
| } |
| |
| // Makes sure the binary was compiled in release mode and that frequency |
| // governor is set on performance. |
| void checkRequirements(); |
| |
| } // namespace libc_benchmarks |
| } // namespace llvm |
| |
| #endif // LLVM_LIBC_UTILS_BENCHMARK_BENCHMARK_H |