diff options
Diffstat (limited to 'src/catch2/benchmark')
27 files changed, 1774 insertions, 0 deletions
diff --git a/src/catch2/benchmark/catch_benchmark.hpp b/src/catch2/benchmark/catch_benchmark.hpp new file mode 100644 index 0000000..d0f88cf --- /dev/null +++ b/src/catch2/benchmark/catch_benchmark.hpp @@ -0,0 +1,148 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_BENCHMARK_HPP_INCLUDED +#define CATCH_BENCHMARK_HPP_INCLUDED + +#include <catch2/catch_user_config.hpp> +#include <catch2/internal/catch_compiler_capabilities.hpp> +#include <catch2/internal/catch_context.hpp> +#include <catch2/internal/catch_move_and_forward.hpp> +#include <catch2/internal/catch_test_failure_exception.hpp> +#include <catch2/internal/catch_unique_name.hpp> +#include <catch2/interfaces/catch_interfaces_capture.hpp> +#include <catch2/interfaces/catch_interfaces_config.hpp> +#include <catch2/interfaces/catch_interfaces_registry_hub.hpp> +#include <catch2/benchmark/detail/catch_benchmark_stats.hpp> +#include <catch2/benchmark/catch_clock.hpp> +#include <catch2/benchmark/catch_environment.hpp> +#include <catch2/benchmark/catch_execution_plan.hpp> +#include <catch2/benchmark/detail/catch_estimate_clock.hpp> +#include <catch2/benchmark/detail/catch_analyse.hpp> +#include <catch2/benchmark/detail/catch_benchmark_function.hpp> +#include <catch2/benchmark/detail/catch_run_for_at_least.hpp> + +#include <algorithm> +#include <chrono> +#include <exception> +#include <string> +#include <cmath> + +namespace Catch { + namespace Benchmark { + struct Benchmark { + Benchmark(std::string&& benchmarkName) + : name(CATCH_MOVE(benchmarkName)) {} + + template <class FUN> + Benchmark(std::string&& benchmarkName , FUN &&func) + : fun(CATCH_MOVE(func)), name(CATCH_MOVE(benchmarkName)) {} + + template <typename Clock> + ExecutionPlan prepare(const IConfig &cfg, Environment env) { + auto min_time = env.clock_resolution.mean * Detail::minimum_ticks; + auto run_time = std::max(min_time, std::chrono::duration_cast<decltype(min_time)>(cfg.benchmarkWarmupTime())); + auto&& test = Detail::run_for_at_least<Clock>(std::chrono::duration_cast<IDuration>(run_time), 1, fun); + int new_iters = static_cast<int>(std::ceil(min_time * test.iterations / test.elapsed)); + return { new_iters, test.elapsed / test.iterations * new_iters * cfg.benchmarkSamples(), CATCH_MOVE(fun), std::chrono::duration_cast<FDuration>(cfg.benchmarkWarmupTime()), Detail::warmup_iterations }; + } + + template <typename Clock = default_clock> + void run() { + static_assert( Clock::is_steady, + "Benchmarking clock should be steady" ); + auto const* cfg = getCurrentContext().getConfig(); + + auto env = Detail::measure_environment<Clock>(); + + getResultCapture().benchmarkPreparing(name); + CATCH_TRY{ + auto plan = user_code([&] { + return prepare<Clock>(*cfg, env); + }); + + BenchmarkInfo info { + CATCH_MOVE(name), + plan.estimated_duration.count(), + plan.iterations_per_sample, + cfg->benchmarkSamples(), + cfg->benchmarkResamples(), + env.clock_resolution.mean.count(), + env.clock_cost.mean.count() + }; + + getResultCapture().benchmarkStarting(info); + + auto samples = user_code([&] { + return plan.template run<Clock>(*cfg, env); + }); + + auto analysis = Detail::analyse(*cfg, samples.data(), samples.data() + samples.size()); + BenchmarkStats<> stats{ CATCH_MOVE(info), CATCH_MOVE(analysis.samples), analysis.mean, analysis.standard_deviation, analysis.outliers, analysis.outlier_variance }; + getResultCapture().benchmarkEnded(stats); + } CATCH_CATCH_ANON (TestFailureException const&) { + getResultCapture().benchmarkFailed("Benchmark failed due to failed assertion"_sr); + } CATCH_CATCH_ALL{ + getResultCapture().benchmarkFailed(translateActiveException()); + // We let the exception go further up so that the + // test case is marked as failed. + std::rethrow_exception(std::current_exception()); + } + } + + // sets lambda to be used in fun *and* executes benchmark! + template <typename Fun, std::enable_if_t<!Detail::is_related<Fun, Benchmark>::value, int> = 0> + Benchmark & operator=(Fun func) { + auto const* cfg = getCurrentContext().getConfig(); + if (!cfg->skipBenchmarks()) { + fun = Detail::BenchmarkFunction(func); + run(); + } + return *this; + } + + explicit operator bool() { + return true; + } + + private: + Detail::BenchmarkFunction fun; + std::string name; + }; + } +} // namespace Catch + +#define INTERNAL_CATCH_GET_1_ARG(arg1, arg2, ...) arg1 +#define INTERNAL_CATCH_GET_2_ARG(arg1, arg2, ...) arg2 + +#define INTERNAL_CATCH_BENCHMARK(BenchmarkName, name, benchmarkIndex)\ + if( Catch::Benchmark::Benchmark BenchmarkName{name} ) \ + BenchmarkName = [&](int benchmarkIndex) + +#define INTERNAL_CATCH_BENCHMARK_ADVANCED(BenchmarkName, name)\ + if( Catch::Benchmark::Benchmark BenchmarkName{name} ) \ + BenchmarkName = [&] + +#if defined(CATCH_CONFIG_PREFIX_ALL) + +#define CATCH_BENCHMARK(...) \ + INTERNAL_CATCH_BENCHMARK(INTERNAL_CATCH_UNIQUE_NAME(CATCH2_INTERNAL_BENCHMARK_), INTERNAL_CATCH_GET_1_ARG(__VA_ARGS__,,), INTERNAL_CATCH_GET_2_ARG(__VA_ARGS__,,)) +#define CATCH_BENCHMARK_ADVANCED(name) \ + INTERNAL_CATCH_BENCHMARK_ADVANCED(INTERNAL_CATCH_UNIQUE_NAME(CATCH2_INTERNAL_BENCHMARK_), name) + +#else + +#define BENCHMARK(...) \ + INTERNAL_CATCH_BENCHMARK(INTERNAL_CATCH_UNIQUE_NAME(CATCH2_INTERNAL_BENCHMARK_), INTERNAL_CATCH_GET_1_ARG(__VA_ARGS__,,), INTERNAL_CATCH_GET_2_ARG(__VA_ARGS__,,)) +#define BENCHMARK_ADVANCED(name) \ + INTERNAL_CATCH_BENCHMARK_ADVANCED(INTERNAL_CATCH_UNIQUE_NAME(CATCH2_INTERNAL_BENCHMARK_), name) + +#endif + +#endif // CATCH_BENCHMARK_HPP_INCLUDED diff --git a/src/catch2/benchmark/catch_benchmark_all.hpp b/src/catch2/benchmark/catch_benchmark_all.hpp new file mode 100644 index 0000000..56fc7c7 --- /dev/null +++ b/src/catch2/benchmark/catch_benchmark_all.hpp @@ -0,0 +1,46 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +/** \file + * This is a convenience header for Catch2's benchmarking. It includes + * **all** of Catch2 headers related to benchmarking. + * + * Generally the Catch2 users should use specific includes they need, + * but this header can be used instead for ease-of-experimentation, or + * just plain convenience, at the cost of (significantly) increased + * compilation times. + * + * When a new header is added to either the `benchmark` folder, or to + * the corresponding internal (detail) subfolder, it should be added here. + */ + +#ifndef CATCH_BENCHMARK_ALL_HPP_INCLUDED +#define CATCH_BENCHMARK_ALL_HPP_INCLUDED + +#include <catch2/benchmark/catch_benchmark.hpp> +#include <catch2/benchmark/catch_chronometer.hpp> +#include <catch2/benchmark/catch_clock.hpp> +#include <catch2/benchmark/catch_constructor.hpp> +#include <catch2/benchmark/catch_environment.hpp> +#include <catch2/benchmark/catch_estimate.hpp> +#include <catch2/benchmark/catch_execution_plan.hpp> +#include <catch2/benchmark/catch_optimizer.hpp> +#include <catch2/benchmark/catch_outlier_classification.hpp> +#include <catch2/benchmark/catch_sample_analysis.hpp> +#include <catch2/benchmark/detail/catch_analyse.hpp> +#include <catch2/benchmark/detail/catch_benchmark_function.hpp> +#include <catch2/benchmark/detail/catch_benchmark_stats.hpp> +#include <catch2/benchmark/detail/catch_benchmark_stats_fwd.hpp> +#include <catch2/benchmark/detail/catch_complete_invoke.hpp> +#include <catch2/benchmark/detail/catch_estimate_clock.hpp> +#include <catch2/benchmark/detail/catch_measure.hpp> +#include <catch2/benchmark/detail/catch_repeat.hpp> +#include <catch2/benchmark/detail/catch_run_for_at_least.hpp> +#include <catch2/benchmark/detail/catch_stats.hpp> +#include <catch2/benchmark/detail/catch_timing.hpp> + +#endif // CATCH_BENCHMARK_ALL_HPP_INCLUDED diff --git a/src/catch2/benchmark/catch_chronometer.cpp b/src/catch2/benchmark/catch_chronometer.cpp new file mode 100644 index 0000000..92f03c9 --- /dev/null +++ b/src/catch2/benchmark/catch_chronometer.cpp @@ -0,0 +1,17 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 + +#include <catch2/benchmark/catch_chronometer.hpp> + +namespace Catch { + namespace Benchmark { + namespace Detail { + ChronometerConcept::~ChronometerConcept() = default; + } // namespace Detail + } // namespace Benchmark +} // namespace Catch diff --git a/src/catch2/benchmark/catch_chronometer.hpp b/src/catch2/benchmark/catch_chronometer.hpp new file mode 100644 index 0000000..95498e6 --- /dev/null +++ b/src/catch2/benchmark/catch_chronometer.hpp @@ -0,0 +1,77 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_CHRONOMETER_HPP_INCLUDED +#define CATCH_CHRONOMETER_HPP_INCLUDED + +#include <catch2/benchmark/catch_clock.hpp> +#include <catch2/benchmark/catch_optimizer.hpp> +#include <catch2/internal/catch_meta.hpp> +#include <catch2/internal/catch_move_and_forward.hpp> + +namespace Catch { + namespace Benchmark { + namespace Detail { + struct ChronometerConcept { + virtual void start() = 0; + virtual void finish() = 0; + virtual ~ChronometerConcept(); // = default; + + ChronometerConcept() = default; + ChronometerConcept(ChronometerConcept const&) = default; + ChronometerConcept& operator=(ChronometerConcept const&) = default; + }; + template <typename Clock> + struct ChronometerModel final : public ChronometerConcept { + void start() override { started = Clock::now(); } + void finish() override { finished = Clock::now(); } + + IDuration elapsed() const { + return std::chrono::duration_cast<std::chrono::nanoseconds>( + finished - started ); + } + + TimePoint<Clock> started; + TimePoint<Clock> finished; + }; + } // namespace Detail + + struct Chronometer { + public: + template <typename Fun> + void measure(Fun&& fun) { measure(CATCH_FORWARD(fun), is_callable<Fun(int)>()); } + + int runs() const { return repeats; } + + Chronometer(Detail::ChronometerConcept& meter, int repeats_) + : impl(&meter) + , repeats(repeats_) {} + + private: + template <typename Fun> + void measure(Fun&& fun, std::false_type) { + measure([&fun](int) { return fun(); }, std::true_type()); + } + + template <typename Fun> + void measure(Fun&& fun, std::true_type) { + Detail::optimizer_barrier(); + impl->start(); + for (int i = 0; i < repeats; ++i) invoke_deoptimized(fun, i); + impl->finish(); + Detail::optimizer_barrier(); + } + + Detail::ChronometerConcept* impl; + int repeats; + }; + } // namespace Benchmark +} // namespace Catch + +#endif // CATCH_CHRONOMETER_HPP_INCLUDED diff --git a/src/catch2/benchmark/catch_clock.hpp b/src/catch2/benchmark/catch_clock.hpp new file mode 100644 index 0000000..4068c4d --- /dev/null +++ b/src/catch2/benchmark/catch_clock.hpp @@ -0,0 +1,27 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_CLOCK_HPP_INCLUDED +#define CATCH_CLOCK_HPP_INCLUDED + +#include <chrono> + +namespace Catch { + namespace Benchmark { + using IDuration = std::chrono::nanoseconds; + using FDuration = std::chrono::duration<double, std::nano>; + + template <typename Clock> + using TimePoint = typename Clock::time_point; + + using default_clock = std::chrono::steady_clock; + } // namespace Benchmark +} // namespace Catch + +#endif // CATCH_CLOCK_HPP_INCLUDED diff --git a/src/catch2/benchmark/catch_constructor.hpp b/src/catch2/benchmark/catch_constructor.hpp new file mode 100644 index 0000000..853bd6c --- /dev/null +++ b/src/catch2/benchmark/catch_constructor.hpp @@ -0,0 +1,82 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_CONSTRUCTOR_HPP_INCLUDED +#define CATCH_CONSTRUCTOR_HPP_INCLUDED + +#include <catch2/internal/catch_move_and_forward.hpp> + +#include <type_traits> + +namespace Catch { + namespace Benchmark { + namespace Detail { + template <typename T, bool Destruct> + struct ObjectStorage + { + ObjectStorage() = default; + + ObjectStorage(const ObjectStorage& other) + { + new(&data) T(other.stored_object()); + } + + ObjectStorage(ObjectStorage&& other) + { + new(data) T(CATCH_MOVE(other.stored_object())); + } + + ~ObjectStorage() { destruct_on_exit<T>(); } + + template <typename... Args> + void construct(Args&&... args) + { + new (data) T(CATCH_FORWARD(args)...); + } + + template <bool AllowManualDestruction = !Destruct> + std::enable_if_t<AllowManualDestruction> destruct() + { + stored_object().~T(); + } + + private: + // If this is a constructor benchmark, destruct the underlying object + template <typename U> + void destruct_on_exit(std::enable_if_t<Destruct, U>* = nullptr) { destruct<true>(); } + // Otherwise, don't + template <typename U> + void destruct_on_exit(std::enable_if_t<!Destruct, U>* = nullptr) { } + +#if defined( __GNUC__ ) && __GNUC__ <= 6 +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wstrict-aliasing" +#endif + T& stored_object() { return *reinterpret_cast<T*>( data ); } + + T const& stored_object() const { + return *reinterpret_cast<T const*>( data ); + } +#if defined( __GNUC__ ) && __GNUC__ <= 6 +# pragma GCC diagnostic pop +#endif + + alignas( T ) unsigned char data[sizeof( T )]{}; + }; + } // namespace Detail + + template <typename T> + using storage_for = Detail::ObjectStorage<T, true>; + + template <typename T> + using destructable_object = Detail::ObjectStorage<T, false>; + } // namespace Benchmark +} // namespace Catch + +#endif // CATCH_CONSTRUCTOR_HPP_INCLUDED diff --git a/src/catch2/benchmark/catch_environment.hpp b/src/catch2/benchmark/catch_environment.hpp new file mode 100644 index 0000000..da3f2fa --- /dev/null +++ b/src/catch2/benchmark/catch_environment.hpp @@ -0,0 +1,29 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_ENVIRONMENT_HPP_INCLUDED +#define CATCH_ENVIRONMENT_HPP_INCLUDED + +#include <catch2/benchmark/catch_clock.hpp> +#include <catch2/benchmark/catch_outlier_classification.hpp> + +namespace Catch { + namespace Benchmark { + struct EnvironmentEstimate { + FDuration mean; + OutlierClassification outliers; + }; + struct Environment { + EnvironmentEstimate clock_resolution; + EnvironmentEstimate clock_cost; + }; + } // namespace Benchmark +} // namespace Catch + +#endif // CATCH_ENVIRONMENT_HPP_INCLUDED diff --git a/src/catch2/benchmark/catch_estimate.hpp b/src/catch2/benchmark/catch_estimate.hpp new file mode 100644 index 0000000..64383a2 --- /dev/null +++ b/src/catch2/benchmark/catch_estimate.hpp @@ -0,0 +1,25 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_ESTIMATE_HPP_INCLUDED +#define CATCH_ESTIMATE_HPP_INCLUDED + +namespace Catch { + namespace Benchmark { + template <typename Type> + struct Estimate { + Type point; + Type lower_bound; + Type upper_bound; + double confidence_interval; + }; + } // namespace Benchmark +} // namespace Catch + +#endif // CATCH_ESTIMATE_HPP_INCLUDED diff --git a/src/catch2/benchmark/catch_execution_plan.hpp b/src/catch2/benchmark/catch_execution_plan.hpp new file mode 100644 index 0000000..17ca589 --- /dev/null +++ b/src/catch2/benchmark/catch_execution_plan.hpp @@ -0,0 +1,58 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_EXECUTION_PLAN_HPP_INCLUDED +#define CATCH_EXECUTION_PLAN_HPP_INCLUDED + +#include <catch2/interfaces/catch_interfaces_config.hpp> +#include <catch2/benchmark/catch_clock.hpp> +#include <catch2/benchmark/catch_environment.hpp> +#include <catch2/benchmark/detail/catch_benchmark_function.hpp> +#include <catch2/benchmark/detail/catch_repeat.hpp> +#include <catch2/benchmark/detail/catch_run_for_at_least.hpp> + +#include <vector> + +namespace Catch { + namespace Benchmark { + struct ExecutionPlan { + int iterations_per_sample; + FDuration estimated_duration; + Detail::BenchmarkFunction benchmark; + FDuration warmup_time; + int warmup_iterations; + + template <typename Clock> + std::vector<FDuration> run(const IConfig &cfg, Environment env) const { + // warmup a bit + Detail::run_for_at_least<Clock>( + std::chrono::duration_cast<IDuration>( warmup_time ), + warmup_iterations, + Detail::repeat( []() { return Clock::now(); } ) + ); + + std::vector<FDuration> times; + const auto num_samples = cfg.benchmarkSamples(); + times.reserve( num_samples ); + for ( size_t i = 0; i < num_samples; ++i ) { + Detail::ChronometerModel<Clock> model; + this->benchmark( Chronometer( model, iterations_per_sample ) ); + auto sample_time = model.elapsed() - env.clock_cost.mean; + if ( sample_time < FDuration::zero() ) { + sample_time = FDuration::zero(); + } + times.push_back(sample_time / iterations_per_sample); + } + return times; + } + }; + } // namespace Benchmark +} // namespace Catch + +#endif // CATCH_EXECUTION_PLAN_HPP_INCLUDED diff --git a/src/catch2/benchmark/catch_optimizer.hpp b/src/catch2/benchmark/catch_optimizer.hpp new file mode 100644 index 0000000..61e6571 --- /dev/null +++ b/src/catch2/benchmark/catch_optimizer.hpp @@ -0,0 +1,78 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_OPTIMIZER_HPP_INCLUDED +#define CATCH_OPTIMIZER_HPP_INCLUDED + +#if defined(_MSC_VER) || defined(__IAR_SYSTEMS_ICC__) +# include <atomic> // atomic_thread_fence +#endif + +#include <catch2/internal/catch_move_and_forward.hpp> + +#include <type_traits> + +namespace Catch { + namespace Benchmark { +#if defined(__GNUC__) || defined(__clang__) + template <typename T> + inline void keep_memory(T* p) { + asm volatile("" : : "g"(p) : "memory"); + } + inline void keep_memory() { + asm volatile("" : : : "memory"); + } + + namespace Detail { + inline void optimizer_barrier() { keep_memory(); } + } // namespace Detail +#elif defined(_MSC_VER) || defined(__IAR_SYSTEMS_ICC__) + +#if defined(_MSVC_VER) +#pragma optimize("", off) +#elif defined(__IAR_SYSTEMS_ICC__) +// For IAR the pragma only affects the following function +#pragma optimize=disable +#endif + template <typename T> + inline void keep_memory(T* p) { + // thanks @milleniumbug + *reinterpret_cast<char volatile*>(p) = *reinterpret_cast<char const volatile*>(p); + } + // TODO equivalent keep_memory() +#if defined(_MSVC_VER) +#pragma optimize("", on) +#endif + + namespace Detail { + inline void optimizer_barrier() { + std::atomic_thread_fence(std::memory_order_seq_cst); + } + } // namespace Detail + +#endif + + template <typename T> + inline void deoptimize_value(T&& x) { + keep_memory(&x); + } + + template <typename Fn, typename... Args> + inline auto invoke_deoptimized(Fn&& fn, Args&&... args) -> std::enable_if_t<!std::is_same<void, decltype(fn(args...))>::value> { + deoptimize_value(CATCH_FORWARD(fn) (CATCH_FORWARD(args)...)); + } + + template <typename Fn, typename... Args> + inline auto invoke_deoptimized(Fn&& fn, Args&&... args) -> std::enable_if_t<std::is_same<void, decltype(fn(args...))>::value> { + CATCH_FORWARD((fn)) (CATCH_FORWARD(args)...); + } + } // namespace Benchmark +} // namespace Catch + +#endif // CATCH_OPTIMIZER_HPP_INCLUDED diff --git a/src/catch2/benchmark/catch_outlier_classification.hpp b/src/catch2/benchmark/catch_outlier_classification.hpp new file mode 100644 index 0000000..b9a1178 --- /dev/null +++ b/src/catch2/benchmark/catch_outlier_classification.hpp @@ -0,0 +1,29 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_OUTLIER_CLASSIFICATION_HPP_INCLUDED +#define CATCH_OUTLIER_CLASSIFICATION_HPP_INCLUDED + +namespace Catch { + namespace Benchmark { + struct OutlierClassification { + int samples_seen = 0; + int low_severe = 0; // more than 3 times IQR below Q1 + int low_mild = 0; // 1.5 to 3 times IQR below Q1 + int high_mild = 0; // 1.5 to 3 times IQR above Q3 + int high_severe = 0; // more than 3 times IQR above Q3 + + constexpr int total() const { + return low_severe + low_mild + high_mild + high_severe; + } + }; + } // namespace Benchmark +} // namespace Catch + +#endif // CATCH_OUTLIERS_CLASSIFICATION_HPP_INCLUDED diff --git a/src/catch2/benchmark/catch_sample_analysis.hpp b/src/catch2/benchmark/catch_sample_analysis.hpp new file mode 100644 index 0000000..aeb87d0 --- /dev/null +++ b/src/catch2/benchmark/catch_sample_analysis.hpp @@ -0,0 +1,31 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_SAMPLE_ANALYSIS_HPP_INCLUDED +#define CATCH_SAMPLE_ANALYSIS_HPP_INCLUDED + +#include <catch2/benchmark/catch_estimate.hpp> +#include <catch2/benchmark/catch_outlier_classification.hpp> +#include <catch2/benchmark/catch_clock.hpp> + +#include <vector> + +namespace Catch { + namespace Benchmark { + struct SampleAnalysis { + std::vector<FDuration> samples; + Estimate<FDuration> mean; + Estimate<FDuration> standard_deviation; + OutlierClassification outliers; + double outlier_variance; + }; + } // namespace Benchmark +} // namespace Catch + +#endif // CATCH_SAMPLE_ANALYSIS_HPP_INCLUDED diff --git a/src/catch2/benchmark/detail/catch_analyse.cpp b/src/catch2/benchmark/detail/catch_analyse.cpp new file mode 100644 index 0000000..14d7f45 --- /dev/null +++ b/src/catch2/benchmark/detail/catch_analyse.cpp @@ -0,0 +1,85 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#include <catch2/benchmark/detail/catch_analyse.hpp> +#include <catch2/benchmark/catch_clock.hpp> +#include <catch2/benchmark/catch_sample_analysis.hpp> +#include <catch2/benchmark/detail/catch_stats.hpp> +#include <catch2/interfaces/catch_interfaces_config.hpp> +#include <catch2/internal/catch_move_and_forward.hpp> + +#include <vector> + +namespace Catch { + namespace Benchmark { + namespace Detail { + SampleAnalysis analyse(const IConfig &cfg, FDuration* first, FDuration* last) { + if (!cfg.benchmarkNoAnalysis()) { + std::vector<double> samples; + samples.reserve(static_cast<size_t>(last - first)); + for (auto current = first; current != last; ++current) { + samples.push_back( current->count() ); + } + + auto analysis = Catch::Benchmark::Detail::analyse_samples( + cfg.benchmarkConfidenceInterval(), + cfg.benchmarkResamples(), + samples.data(), + samples.data() + samples.size() ); + auto outliers = Catch::Benchmark::Detail::classify_outliers( + samples.data(), samples.data() + samples.size() ); + + auto wrap_estimate = [](Estimate<double> e) { + return Estimate<FDuration> { + FDuration(e.point), + FDuration(e.lower_bound), + FDuration(e.upper_bound), + e.confidence_interval, + }; + }; + std::vector<FDuration> samples2; + samples2.reserve(samples.size()); + for (auto s : samples) { + samples2.push_back( FDuration( s ) ); + } + + return { + CATCH_MOVE(samples2), + wrap_estimate(analysis.mean), + wrap_estimate(analysis.standard_deviation), + outliers, + analysis.outlier_variance, + }; + } else { + std::vector<FDuration> samples; + samples.reserve(static_cast<size_t>(last - first)); + + FDuration mean = FDuration(0); + int i = 0; + for (auto it = first; it < last; ++it, ++i) { + samples.push_back(*it); + mean += *it; + } + mean /= i; + + return SampleAnalysis{ + CATCH_MOVE(samples), + Estimate<FDuration>{ mean, mean, mean, 0.0 }, + Estimate<FDuration>{ FDuration( 0 ), + FDuration( 0 ), + FDuration( 0 ), + 0.0 }, + OutlierClassification{}, + 0.0 + }; + } + } + } // namespace Detail + } // namespace Benchmark +} // namespace Catch diff --git a/src/catch2/benchmark/detail/catch_analyse.hpp b/src/catch2/benchmark/detail/catch_analyse.hpp new file mode 100644 index 0000000..5e3f7b0 --- /dev/null +++ b/src/catch2/benchmark/detail/catch_analyse.hpp @@ -0,0 +1,27 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_ANALYSE_HPP_INCLUDED +#define CATCH_ANALYSE_HPP_INCLUDED + +#include <catch2/benchmark/catch_clock.hpp> +#include <catch2/benchmark/catch_sample_analysis.hpp> + + +namespace Catch { + class IConfig; + + namespace Benchmark { + namespace Detail { + SampleAnalysis analyse(const IConfig &cfg, FDuration* first, FDuration* last); + } // namespace Detail + } // namespace Benchmark +} // namespace Catch + +#endif // CATCH_ANALYSE_HPP_INCLUDED diff --git a/src/catch2/benchmark/detail/catch_benchmark_function.cpp b/src/catch2/benchmark/detail/catch_benchmark_function.cpp new file mode 100644 index 0000000..66d4e61 --- /dev/null +++ b/src/catch2/benchmark/detail/catch_benchmark_function.cpp @@ -0,0 +1,23 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 + +#include <catch2/benchmark/detail/catch_benchmark_function.hpp> + +namespace Catch { + namespace Benchmark { + namespace Detail { + struct do_nothing { + void operator()() const {} + }; + + BenchmarkFunction::callable::~callable() = default; + BenchmarkFunction::BenchmarkFunction(): + f( new model<do_nothing>{ {} } ){} + } // namespace Detail + } // namespace Benchmark +} // namespace Catch diff --git a/src/catch2/benchmark/detail/catch_benchmark_function.hpp b/src/catch2/benchmark/detail/catch_benchmark_function.hpp new file mode 100644 index 0000000..a03cb11 --- /dev/null +++ b/src/catch2/benchmark/detail/catch_benchmark_function.hpp @@ -0,0 +1,88 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_BENCHMARK_FUNCTION_HPP_INCLUDED +#define CATCH_BENCHMARK_FUNCTION_HPP_INCLUDED + +#include <catch2/benchmark/catch_chronometer.hpp> +#include <catch2/internal/catch_meta.hpp> +#include <catch2/internal/catch_unique_ptr.hpp> +#include <catch2/internal/catch_move_and_forward.hpp> + +#include <type_traits> + +namespace Catch { + namespace Benchmark { + namespace Detail { + template <typename T, typename U> + struct is_related + : std::is_same<std::decay_t<T>, std::decay_t<U>> {}; + + /// We need to reinvent std::function because every piece of code that might add overhead + /// in a measurement context needs to have consistent performance characteristics so that we + /// can account for it in the measurement. + /// Implementations of std::function with optimizations that aren't always applicable, like + /// small buffer optimizations, are not uncommon. + /// This is effectively an implementation of std::function without any such optimizations; + /// it may be slow, but it is consistently slow. + struct BenchmarkFunction { + private: + struct callable { + virtual void call(Chronometer meter) const = 0; + virtual ~callable(); // = default; + + callable() = default; + callable(callable&&) = default; + callable& operator=(callable&&) = default; + }; + template <typename Fun> + struct model : public callable { + model(Fun&& fun_) : fun(CATCH_MOVE(fun_)) {} + model(Fun const& fun_) : fun(fun_) {} + + void call(Chronometer meter) const override { + call(meter, is_callable<Fun(Chronometer)>()); + } + void call(Chronometer meter, std::true_type) const { + fun(meter); + } + void call(Chronometer meter, std::false_type) const { + meter.measure(fun); + } + + Fun fun; + }; + + public: + BenchmarkFunction(); + + template <typename Fun, + std::enable_if_t<!is_related<Fun, BenchmarkFunction>::value, int> = 0> + BenchmarkFunction(Fun&& fun) + : f(new model<std::decay_t<Fun>>(CATCH_FORWARD(fun))) {} + + BenchmarkFunction( BenchmarkFunction&& that ) noexcept: + f( CATCH_MOVE( that.f ) ) {} + + BenchmarkFunction& + operator=( BenchmarkFunction&& that ) noexcept { + f = CATCH_MOVE( that.f ); + return *this; + } + + void operator()(Chronometer meter) const { f->call(meter); } + + private: + Catch::Detail::unique_ptr<callable> f; + }; + } // namespace Detail + } // namespace Benchmark +} // namespace Catch + +#endif // CATCH_BENCHMARK_FUNCTION_HPP_INCLUDED diff --git a/src/catch2/benchmark/detail/catch_benchmark_stats.hpp b/src/catch2/benchmark/detail/catch_benchmark_stats.hpp new file mode 100644 index 0000000..3633bc9 --- /dev/null +++ b/src/catch2/benchmark/detail/catch_benchmark_stats.hpp @@ -0,0 +1,48 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +#ifndef CATCH_BENCHMARK_STATS_HPP_INCLUDED +#define CATCH_BENCHMARK_STATS_HPP_INCLUDED + +#include <catch2/benchmark/catch_estimate.hpp> +#include <catch2/benchmark/catch_outlier_classification.hpp> +// The fwd decl & default specialization needs to be seen by VS2017 before +// BenchmarkStats itself, or VS2017 will report compilation error. +#include <catch2/benchmark/detail/catch_benchmark_stats_fwd.hpp> + +#include <string> +#include <vector> + +namespace Catch { + + struct BenchmarkInfo { + std::string name; + double estimatedDuration; + int iterations; + unsigned int samples; + unsigned int resamples; + double clockResolution; + double clockCost; + }; + + // We need to keep template parameter for backwards compatibility, + // but we also do not want to use the template paraneter. + template <class Dummy> + struct BenchmarkStats { + BenchmarkInfo info; + + std::vector<Benchmark::FDuration> samples; + Benchmark::Estimate<Benchmark::FDuration> mean; + Benchmark::Estimate<Benchmark::FDuration> standardDeviation; + Benchmark::OutlierClassification outliers; + double outlierVariance; + }; + + +} // end namespace Catch + +#endif // CATCH_BENCHMARK_STATS_HPP_INCLUDED diff --git a/src/catch2/benchmark/detail/catch_benchmark_stats_fwd.hpp b/src/catch2/benchmark/detail/catch_benchmark_stats_fwd.hpp new file mode 100644 index 0000000..2ccc25d --- /dev/null +++ b/src/catch2/benchmark/detail/catch_benchmark_stats_fwd.hpp @@ -0,0 +1,23 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +#ifndef CATCH_BENCHMARK_STATS_FWD_HPP_INCLUDED +#define CATCH_BENCHMARK_STATS_FWD_HPP_INCLUDED + +#include <catch2/benchmark/catch_clock.hpp> + +namespace Catch { + + // We cannot forward declare the type with default template argument + // multiple times, so it is split out into a separate header so that + // we can prevent multiple declarations in dependees + template <typename Duration = Benchmark::FDuration> + struct BenchmarkStats; + +} // end namespace Catch + +#endif // CATCH_BENCHMARK_STATS_FWD_HPP_INCLUDED diff --git a/src/catch2/benchmark/detail/catch_complete_invoke.hpp b/src/catch2/benchmark/detail/catch_complete_invoke.hpp new file mode 100644 index 0000000..4dff4b7 --- /dev/null +++ b/src/catch2/benchmark/detail/catch_complete_invoke.hpp @@ -0,0 +1,58 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_COMPLETE_INVOKE_HPP_INCLUDED +#define CATCH_COMPLETE_INVOKE_HPP_INCLUDED + +#include <catch2/internal/catch_meta.hpp> +#include <catch2/internal/catch_move_and_forward.hpp> + +namespace Catch { + namespace Benchmark { + namespace Detail { + template <typename T> + struct CompleteType { using type = T; }; + template <> + struct CompleteType<void> { struct type {}; }; + + template <typename T> + using CompleteType_t = typename CompleteType<T>::type; + + template <typename Result> + struct CompleteInvoker { + template <typename Fun, typename... Args> + static Result invoke(Fun&& fun, Args&&... args) { + return CATCH_FORWARD(fun)(CATCH_FORWARD(args)...); + } + }; + template <> + struct CompleteInvoker<void> { + template <typename Fun, typename... Args> + static CompleteType_t<void> invoke(Fun&& fun, Args&&... args) { + CATCH_FORWARD(fun)(CATCH_FORWARD(args)...); + return {}; + } + }; + + // invoke and not return void :( + template <typename Fun, typename... Args> + CompleteType_t<FunctionReturnType<Fun, Args...>> complete_invoke(Fun&& fun, Args&&... args) { + return CompleteInvoker<FunctionReturnType<Fun, Args...>>::invoke(CATCH_FORWARD(fun), CATCH_FORWARD(args)...); + } + + } // namespace Detail + + template <typename Fun> + Detail::CompleteType_t<FunctionReturnType<Fun>> user_code(Fun&& fun) { + return Detail::complete_invoke(CATCH_FORWARD(fun)); + } + } // namespace Benchmark +} // namespace Catch + +#endif // CATCH_COMPLETE_INVOKE_HPP_INCLUDED diff --git a/src/catch2/benchmark/detail/catch_estimate_clock.hpp b/src/catch2/benchmark/detail/catch_estimate_clock.hpp new file mode 100644 index 0000000..6da24ce --- /dev/null +++ b/src/catch2/benchmark/detail/catch_estimate_clock.hpp @@ -0,0 +1,127 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_ESTIMATE_CLOCK_HPP_INCLUDED +#define CATCH_ESTIMATE_CLOCK_HPP_INCLUDED + +#include <catch2/benchmark/catch_clock.hpp> +#include <catch2/benchmark/catch_environment.hpp> +#include <catch2/benchmark/detail/catch_stats.hpp> +#include <catch2/benchmark/detail/catch_measure.hpp> +#include <catch2/benchmark/detail/catch_run_for_at_least.hpp> +#include <catch2/benchmark/catch_clock.hpp> +#include <catch2/internal/catch_unique_ptr.hpp> + +#include <algorithm> +#include <vector> +#include <cmath> + +namespace Catch { + namespace Benchmark { + namespace Detail { + template <typename Clock> + std::vector<double> resolution(int k) { + const size_t points = static_cast<size_t>( k + 1 ); + // To avoid overhead from the branch inside vector::push_back, + // we allocate them all and then overwrite. + std::vector<TimePoint<Clock>> times(points); + for ( auto& time : times ) { + time = Clock::now(); + } + + std::vector<double> deltas; + deltas.reserve(static_cast<size_t>(k)); + for ( size_t idx = 1; idx < points; ++idx ) { + deltas.push_back( static_cast<double>( + ( times[idx] - times[idx - 1] ).count() ) ); + } + + return deltas; + } + + constexpr auto warmup_iterations = 10000; + constexpr auto warmup_time = std::chrono::milliseconds(100); + constexpr auto minimum_ticks = 1000; + constexpr auto warmup_seed = 10000; + constexpr auto clock_resolution_estimation_time = std::chrono::milliseconds(500); + constexpr auto clock_cost_estimation_time_limit = std::chrono::seconds(1); + constexpr auto clock_cost_estimation_tick_limit = 100000; + constexpr auto clock_cost_estimation_time = std::chrono::milliseconds(10); + constexpr auto clock_cost_estimation_iterations = 10000; + + template <typename Clock> + int warmup() { + return run_for_at_least<Clock>(warmup_time, warmup_seed, &resolution<Clock>) + .iterations; + } + template <typename Clock> + EnvironmentEstimate estimate_clock_resolution(int iterations) { + auto r = run_for_at_least<Clock>(clock_resolution_estimation_time, iterations, &resolution<Clock>) + .result; + return { + FDuration(mean(r.data(), r.data() + r.size())), + classify_outliers(r.data(), r.data() + r.size()), + }; + } + template <typename Clock> + EnvironmentEstimate estimate_clock_cost(FDuration resolution) { + auto time_limit = (std::min)( + resolution * clock_cost_estimation_tick_limit, + FDuration(clock_cost_estimation_time_limit)); + auto time_clock = [](int k) { + return Detail::measure<Clock>([k] { + for (int i = 0; i < k; ++i) { + volatile auto ignored = Clock::now(); + (void)ignored; + } + }).elapsed; + }; + time_clock(1); + int iters = clock_cost_estimation_iterations; + auto&& r = run_for_at_least<Clock>(clock_cost_estimation_time, iters, time_clock); + std::vector<double> times; + int nsamples = static_cast<int>(std::ceil(time_limit / r.elapsed)); + times.reserve(static_cast<size_t>(nsamples)); + for ( int s = 0; s < nsamples; ++s ) { + times.push_back( static_cast<double>( + ( time_clock( r.iterations ) / r.iterations ) + .count() ) ); + } + return { + FDuration(mean(times.data(), times.data() + times.size())), + classify_outliers(times.data(), times.data() + times.size()), + }; + } + + template <typename Clock> + Environment measure_environment() { +#if defined(__clang__) +# pragma clang diagnostic push +# pragma clang diagnostic ignored "-Wexit-time-destructors" +#endif + static Catch::Detail::unique_ptr<Environment> env; +#if defined(__clang__) +# pragma clang diagnostic pop +#endif + if (env) { + return *env; + } + + auto iters = Detail::warmup<Clock>(); + auto resolution = Detail::estimate_clock_resolution<Clock>(iters); + auto cost = Detail::estimate_clock_cost<Clock>(resolution.mean); + + env = Catch::Detail::make_unique<Environment>( Environment{resolution, cost} ); + return *env; + } + } // namespace Detail + } // namespace Benchmark +} // namespace Catch + +#endif // CATCH_ESTIMATE_CLOCK_HPP_INCLUDED diff --git a/src/catch2/benchmark/detail/catch_measure.hpp b/src/catch2/benchmark/detail/catch_measure.hpp new file mode 100644 index 0000000..a804907 --- /dev/null +++ b/src/catch2/benchmark/detail/catch_measure.hpp @@ -0,0 +1,32 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_MEASURE_HPP_INCLUDED +#define CATCH_MEASURE_HPP_INCLUDED + +#include <catch2/benchmark/detail/catch_complete_invoke.hpp> +#include <catch2/benchmark/detail/catch_timing.hpp> +#include <catch2/internal/catch_move_and_forward.hpp> + +namespace Catch { + namespace Benchmark { + namespace Detail { + template <typename Clock, typename Fun, typename... Args> + TimingOf<Fun, Args...> measure(Fun&& fun, Args&&... args) { + auto start = Clock::now(); + auto&& r = Detail::complete_invoke(CATCH_FORWARD(fun), CATCH_FORWARD(args)...); + auto end = Clock::now(); + auto delta = end - start; + return { delta, CATCH_FORWARD(r), 1 }; + } + } // namespace Detail + } // namespace Benchmark +} // namespace Catch + +#endif // CATCH_MEASURE_HPP_INCLUDED diff --git a/src/catch2/benchmark/detail/catch_repeat.hpp b/src/catch2/benchmark/detail/catch_repeat.hpp new file mode 100644 index 0000000..08c0337 --- /dev/null +++ b/src/catch2/benchmark/detail/catch_repeat.hpp @@ -0,0 +1,36 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_REPEAT_HPP_INCLUDED +#define CATCH_REPEAT_HPP_INCLUDED + +#include <type_traits> +#include <catch2/internal/catch_move_and_forward.hpp> + +namespace Catch { + namespace Benchmark { + namespace Detail { + template <typename Fun> + struct repeater { + void operator()(int k) const { + for (int i = 0; i < k; ++i) { + fun(); + } + } + Fun fun; + }; + template <typename Fun> + repeater<std::decay_t<Fun>> repeat(Fun&& fun) { + return { CATCH_FORWARD(fun) }; + } + } // namespace Detail + } // namespace Benchmark +} // namespace Catch + +#endif // CATCH_REPEAT_HPP_INCLUDED diff --git a/src/catch2/benchmark/detail/catch_run_for_at_least.cpp b/src/catch2/benchmark/detail/catch_run_for_at_least.cpp new file mode 100644 index 0000000..3ebdcc0 --- /dev/null +++ b/src/catch2/benchmark/detail/catch_run_for_at_least.cpp @@ -0,0 +1,31 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 + +#include <catch2/benchmark/detail/catch_run_for_at_least.hpp> +#include <catch2/internal/catch_enforce.hpp> + +#include <exception> + +namespace Catch { + namespace Benchmark { + namespace Detail { + struct optimized_away_error : std::exception { + const char* what() const noexcept override; + }; + + const char* optimized_away_error::what() const noexcept { + return "could not measure benchmark, maybe it was optimized away"; + } + + void throw_optimized_away_error() { + Catch::throw_exception(optimized_away_error{}); + } + + } // namespace Detail + } // namespace Benchmark +} // namespace Catch diff --git a/src/catch2/benchmark/detail/catch_run_for_at_least.hpp b/src/catch2/benchmark/detail/catch_run_for_at_least.hpp new file mode 100644 index 0000000..4dfa8bb --- /dev/null +++ b/src/catch2/benchmark/detail/catch_run_for_at_least.hpp @@ -0,0 +1,65 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_RUN_FOR_AT_LEAST_HPP_INCLUDED +#define CATCH_RUN_FOR_AT_LEAST_HPP_INCLUDED + +#include <catch2/benchmark/catch_clock.hpp> +#include <catch2/benchmark/catch_chronometer.hpp> +#include <catch2/benchmark/detail/catch_measure.hpp> +#include <catch2/benchmark/detail/catch_complete_invoke.hpp> +#include <catch2/benchmark/detail/catch_timing.hpp> +#include <catch2/internal/catch_meta.hpp> +#include <catch2/internal/catch_move_and_forward.hpp> + +#include <type_traits> + +namespace Catch { + namespace Benchmark { + namespace Detail { + template <typename Clock, typename Fun> + TimingOf<Fun, int> measure_one(Fun&& fun, int iters, std::false_type) { + return Detail::measure<Clock>(fun, iters); + } + template <typename Clock, typename Fun> + TimingOf<Fun, Chronometer> measure_one(Fun&& fun, int iters, std::true_type) { + Detail::ChronometerModel<Clock> meter; + auto&& result = Detail::complete_invoke(fun, Chronometer(meter, iters)); + + return { meter.elapsed(), CATCH_MOVE(result), iters }; + } + + template <typename Clock, typename Fun> + using run_for_at_least_argument_t = std::conditional_t<is_callable<Fun(Chronometer)>::value, Chronometer, int>; + + + [[noreturn]] + void throw_optimized_away_error(); + + template <typename Clock, typename Fun> + TimingOf<Fun, run_for_at_least_argument_t<Clock, Fun>> + run_for_at_least(IDuration how_long, + const int initial_iterations, + Fun&& fun) { + auto iters = initial_iterations; + while (iters < (1 << 30)) { + auto&& Timing = measure_one<Clock>(fun, iters, is_callable<Fun(Chronometer)>()); + + if (Timing.elapsed >= how_long) { + return { Timing.elapsed, CATCH_MOVE(Timing.result), iters }; + } + iters *= 2; + } + throw_optimized_away_error(); + } + } // namespace Detail + } // namespace Benchmark +} // namespace Catch + +#endif // CATCH_RUN_FOR_AT_LEAST_HPP_INCLUDED diff --git a/src/catch2/benchmark/detail/catch_stats.cpp b/src/catch2/benchmark/detail/catch_stats.cpp new file mode 100644 index 0000000..2a5a2e0 --- /dev/null +++ b/src/catch2/benchmark/detail/catch_stats.cpp @@ -0,0 +1,393 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#include <catch2/benchmark/detail/catch_stats.hpp> + +#include <catch2/internal/catch_compiler_capabilities.hpp> +#include <catch2/internal/catch_floating_point_helpers.hpp> +#include <catch2/internal/catch_random_number_generator.hpp> +#include <catch2/internal/catch_uniform_integer_distribution.hpp> + +#include <algorithm> +#include <cassert> +#include <cmath> +#include <cstddef> +#include <numeric> +#include <random> + + +#if defined(CATCH_CONFIG_USE_ASYNC) +#include <future> +#endif + +namespace Catch { + namespace Benchmark { + namespace Detail { + namespace { + + template <typename URng, typename Estimator> + static sample + resample( URng& rng, + unsigned int resamples, + double const* first, + double const* last, + Estimator& estimator ) { + auto n = static_cast<size_t>( last - first ); + Catch::uniform_integer_distribution<size_t> dist( 0, n - 1 ); + + sample out; + out.reserve( resamples ); + std::vector<double> resampled; + resampled.reserve( n ); + for ( size_t i = 0; i < resamples; ++i ) { + resampled.clear(); + for ( size_t s = 0; s < n; ++s ) { + resampled.push_back( first[dist( rng )] ); + } + const auto estimate = + estimator( resampled.data(), resampled.data() + resampled.size() ); + out.push_back( estimate ); + } + std::sort( out.begin(), out.end() ); + return out; + } + + static double outlier_variance( Estimate<double> mean, + Estimate<double> stddev, + int n ) { + double sb = stddev.point; + double mn = mean.point / n; + double mg_min = mn / 2.; + double sg = (std::min)( mg_min / 4., sb / std::sqrt( n ) ); + double sg2 = sg * sg; + double sb2 = sb * sb; + + auto c_max = [n, mn, sb2, sg2]( double x ) -> double { + double k = mn - x; + double d = k * k; + double nd = n * d; + double k0 = -n * nd; + double k1 = sb2 - n * sg2 + nd; + double det = k1 * k1 - 4 * sg2 * k0; + return static_cast<int>( -2. * k0 / + ( k1 + std::sqrt( det ) ) ); + }; + + auto var_out = [n, sb2, sg2]( double c ) { + double nc = n - c; + return ( nc / n ) * ( sb2 - nc * sg2 ); + }; + + return (std::min)( var_out( 1 ), + var_out( + (std::min)( c_max( 0. ), + c_max( mg_min ) ) ) ) / + sb2; + } + + static double erf_inv( double x ) { + // Code accompanying the article "Approximating the erfinv + // function" in GPU Computing Gems, Volume 2 + double w, p; + + w = -log( ( 1.0 - x ) * ( 1.0 + x ) ); + + if ( w < 6.250000 ) { + w = w - 3.125000; + p = -3.6444120640178196996e-21; + p = -1.685059138182016589e-19 + p * w; + p = 1.2858480715256400167e-18 + p * w; + p = 1.115787767802518096e-17 + p * w; + p = -1.333171662854620906e-16 + p * w; + p = 2.0972767875968561637e-17 + p * w; + p = 6.6376381343583238325e-15 + p * w; + p = -4.0545662729752068639e-14 + p * w; + p = -8.1519341976054721522e-14 + p * w; + p = 2.6335093153082322977e-12 + p * w; + p = -1.2975133253453532498e-11 + p * w; + p = -5.4154120542946279317e-11 + p * w; + p = 1.051212273321532285e-09 + p * w; + p = -4.1126339803469836976e-09 + p * w; + p = -2.9070369957882005086e-08 + p * w; + p = 4.2347877827932403518e-07 + p * w; + p = -1.3654692000834678645e-06 + p * w; + p = -1.3882523362786468719e-05 + p * w; + p = 0.0001867342080340571352 + p * w; + p = -0.00074070253416626697512 + p * w; + p = -0.0060336708714301490533 + p * w; + p = 0.24015818242558961693 + p * w; + p = 1.6536545626831027356 + p * w; + } else if ( w < 16.000000 ) { + w = sqrt( w ) - 3.250000; + p = 2.2137376921775787049e-09; + p = 9.0756561938885390979e-08 + p * w; + p = -2.7517406297064545428e-07 + p * w; + p = 1.8239629214389227755e-08 + p * w; + p = 1.5027403968909827627e-06 + p * w; + p = -4.013867526981545969e-06 + p * w; + p = 2.9234449089955446044e-06 + p * w; + p = 1.2475304481671778723e-05 + p * w; + p = -4.7318229009055733981e-05 + p * w; + p = 6.8284851459573175448e-05 + p * w; + p = 2.4031110387097893999e-05 + p * w; + p = -0.0003550375203628474796 + p * w; + p = 0.00095328937973738049703 + p * w; + p = -0.0016882755560235047313 + p * w; + p = 0.0024914420961078508066 + p * w; + p = -0.0037512085075692412107 + p * w; + p = 0.005370914553590063617 + p * w; + p = 1.0052589676941592334 + p * w; + p = 3.0838856104922207635 + p * w; + } else { + w = sqrt( w ) - 5.000000; + p = -2.7109920616438573243e-11; + p = -2.5556418169965252055e-10 + p * w; + p = 1.5076572693500548083e-09 + p * w; + p = -3.7894654401267369937e-09 + p * w; + p = 7.6157012080783393804e-09 + p * w; + p = -1.4960026627149240478e-08 + p * w; + p = 2.9147953450901080826e-08 + p * w; + p = -6.7711997758452339498e-08 + p * w; + p = 2.2900482228026654717e-07 + p * w; + p = -9.9298272942317002539e-07 + p * w; + p = 4.5260625972231537039e-06 + p * w; + p = -1.9681778105531670567e-05 + p * w; + p = 7.5995277030017761139e-05 + p * w; + p = -0.00021503011930044477347 + p * w; + p = -0.00013871931833623122026 + p * w; + p = 1.0103004648645343977 + p * w; + p = 4.8499064014085844221 + p * w; + } + return p * x; + } + + static double + standard_deviation( double const* first, double const* last ) { + auto m = Catch::Benchmark::Detail::mean( first, last ); + double variance = + std::accumulate( first, + last, + 0., + [m]( double a, double b ) { + double diff = b - m; + return a + diff * diff; + } ) / + static_cast<double>( last - first ); + return std::sqrt( variance ); + } + + static sample jackknife( double ( *estimator )( double const*, + double const* ), + double* first, + double* last ) { + const auto second = first + 1; + sample results; + results.reserve( static_cast<size_t>( last - first ) ); + + for ( auto it = first; it != last; ++it ) { + std::iter_swap( it, first ); + results.push_back( estimator( second, last ) ); + } + + return results; + } + + + } // namespace + } // namespace Detail + } // namespace Benchmark +} // namespace Catch + +namespace Catch { + namespace Benchmark { + namespace Detail { + + double weighted_average_quantile( int k, + int q, + double* first, + double* last ) { + auto count = last - first; + double idx = static_cast<double>((count - 1) * k) / static_cast<double>(q); + int j = static_cast<int>(idx); + double g = idx - j; + std::nth_element(first, first + j, last); + auto xj = first[j]; + if ( Catch::Detail::directCompare( g, 0 ) ) { + return xj; + } + + auto xj1 = *std::min_element(first + (j + 1), last); + return xj + g * (xj1 - xj); + } + + OutlierClassification + classify_outliers( double const* first, double const* last ) { + std::vector<double> copy( first, last ); + + auto q1 = weighted_average_quantile( 1, 4, copy.data(), copy.data() + copy.size() ); + auto q3 = weighted_average_quantile( 3, 4, copy.data(), copy.data() + copy.size() ); + auto iqr = q3 - q1; + auto los = q1 - ( iqr * 3. ); + auto lom = q1 - ( iqr * 1.5 ); + auto him = q3 + ( iqr * 1.5 ); + auto his = q3 + ( iqr * 3. ); + + OutlierClassification o; + for ( ; first != last; ++first ) { + const double t = *first; + if ( t < los ) { + ++o.low_severe; + } else if ( t < lom ) { + ++o.low_mild; + } else if ( t > his ) { + ++o.high_severe; + } else if ( t > him ) { + ++o.high_mild; + } + ++o.samples_seen; + } + return o; + } + + double mean( double const* first, double const* last ) { + auto count = last - first; + double sum = 0.; + while (first != last) { + sum += *first; + ++first; + } + return sum / static_cast<double>(count); + } + + double normal_cdf( double x ) { + return std::erfc( -x / std::sqrt( 2.0 ) ) / 2.0; + } + + double erfc_inv(double x) { + return erf_inv(1.0 - x); + } + + double normal_quantile(double p) { + static const double ROOT_TWO = std::sqrt(2.0); + + double result = 0.0; + assert(p >= 0 && p <= 1); + if (p < 0 || p > 1) { + return result; + } + + result = -erfc_inv(2.0 * p); + // result *= normal distribution standard deviation (1.0) * sqrt(2) + result *= /*sd * */ ROOT_TWO; + // result += normal disttribution mean (0) + return result; + } + + Estimate<double> + bootstrap( double confidence_level, + double* first, + double* last, + sample const& resample, + double ( *estimator )( double const*, double const* ) ) { + auto n_samples = last - first; + + double point = estimator( first, last ); + // Degenerate case with a single sample + if ( n_samples == 1 ) + return { point, point, point, confidence_level }; + + sample jack = jackknife( estimator, first, last ); + double jack_mean = + mean( jack.data(), jack.data() + jack.size() ); + double sum_squares = 0, sum_cubes = 0; + for ( double x : jack ) { + auto difference = jack_mean - x; + auto square = difference * difference; + auto cube = square * difference; + sum_squares += square; + sum_cubes += cube; + } + + double accel = sum_cubes / ( 6 * std::pow( sum_squares, 1.5 ) ); + long n = static_cast<long>( resample.size() ); + double prob_n = static_cast<double>( + std::count_if( resample.begin(), + resample.end(), + [point]( double x ) { return x < point; } )) / + static_cast<double>( n ); + // degenerate case with uniform samples + if ( Catch::Detail::directCompare( prob_n, 0. ) ) { + return { point, point, point, confidence_level }; + } + + double bias = normal_quantile( prob_n ); + double z1 = normal_quantile( ( 1. - confidence_level ) / 2. ); + + auto cumn = [n]( double x ) -> long { + return std::lround( normal_cdf( x ) * + static_cast<double>( n ) ); + }; + auto a = [bias, accel]( double b ) { + return bias + b / ( 1. - accel * b ); + }; + double b1 = bias + z1; + double b2 = bias - z1; + double a1 = a( b1 ); + double a2 = a( b2 ); + auto lo = static_cast<size_t>( (std::max)( cumn( a1 ), 0l ) ); + auto hi = + static_cast<size_t>( (std::min)( cumn( a2 ), n - 1 ) ); + + return { point, resample[lo], resample[hi], confidence_level }; + } + + bootstrap_analysis analyse_samples(double confidence_level, + unsigned int n_resamples, + double* first, + double* last) { + auto mean = &Detail::mean; + auto stddev = &standard_deviation; + +#if defined(CATCH_CONFIG_USE_ASYNC) + auto Estimate = [=](double(*f)(double const*, double const*)) { + std::random_device rd; + auto seed = rd(); + return std::async(std::launch::async, [=] { + SimplePcg32 rng( seed ); + auto resampled = resample(rng, n_resamples, first, last, f); + return bootstrap(confidence_level, first, last, resampled, f); + }); + }; + + auto mean_future = Estimate(mean); + auto stddev_future = Estimate(stddev); + + auto mean_estimate = mean_future.get(); + auto stddev_estimate = stddev_future.get(); +#else + auto Estimate = [=](double(*f)(double const* , double const*)) { + std::random_device rd; + auto seed = rd(); + SimplePcg32 rng( seed ); + auto resampled = resample(rng, n_resamples, first, last, f); + return bootstrap(confidence_level, first, last, resampled, f); + }; + + auto mean_estimate = Estimate(mean); + auto stddev_estimate = Estimate(stddev); +#endif // CATCH_USE_ASYNC + + auto n = static_cast<int>(last - first); // seriously, one can't use integral types without hell in C++ + double outlier_variance = Detail::outlier_variance(mean_estimate, stddev_estimate, n); + + return { mean_estimate, stddev_estimate, outlier_variance }; + } + } // namespace Detail + } // namespace Benchmark +} // namespace Catch diff --git a/src/catch2/benchmark/detail/catch_stats.hpp b/src/catch2/benchmark/detail/catch_stats.hpp new file mode 100644 index 0000000..3bea612 --- /dev/null +++ b/src/catch2/benchmark/detail/catch_stats.hpp @@ -0,0 +1,60 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_STATS_HPP_INCLUDED +#define CATCH_STATS_HPP_INCLUDED + +#include <catch2/benchmark/catch_estimate.hpp> +#include <catch2/benchmark/catch_outlier_classification.hpp> + +#include <vector> + +namespace Catch { + namespace Benchmark { + namespace Detail { + using sample = std::vector<double>; + + double weighted_average_quantile( int k, + int q, + double* first, + double* last ); + + OutlierClassification + classify_outliers( double const* first, double const* last ); + + double mean( double const* first, double const* last ); + + double normal_cdf( double x ); + + double erfc_inv(double x); + + double normal_quantile(double p); + + Estimate<double> + bootstrap( double confidence_level, + double* first, + double* last, + sample const& resample, + double ( *estimator )( double const*, double const* ) ); + + struct bootstrap_analysis { + Estimate<double> mean; + Estimate<double> standard_deviation; + double outlier_variance; + }; + + bootstrap_analysis analyse_samples(double confidence_level, + unsigned int n_resamples, + double* first, + double* last); + } // namespace Detail + } // namespace Benchmark +} // namespace Catch + +#endif // CATCH_STATS_HPP_INCLUDED diff --git a/src/catch2/benchmark/detail/catch_timing.hpp b/src/catch2/benchmark/detail/catch_timing.hpp new file mode 100644 index 0000000..da56719 --- /dev/null +++ b/src/catch2/benchmark/detail/catch_timing.hpp @@ -0,0 +1,31 @@ + +// Copyright Catch2 Authors +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// https://www.boost.org/LICENSE_1_0.txt) + +// SPDX-License-Identifier: BSL-1.0 +// Adapted from donated nonius code. + +#ifndef CATCH_TIMING_HPP_INCLUDED +#define CATCH_TIMING_HPP_INCLUDED + +#include <catch2/benchmark/catch_clock.hpp> +#include <catch2/benchmark/detail/catch_complete_invoke.hpp> + +#include <type_traits> + +namespace Catch { + namespace Benchmark { + template <typename Result> + struct Timing { + IDuration elapsed; + Result result; + int iterations; + }; + template <typename Func, typename... Args> + using TimingOf = Timing<Detail::CompleteType_t<FunctionReturnType<Func, Args...>>>; + } // namespace Benchmark +} // namespace Catch + +#endif // CATCH_TIMING_HPP_INCLUDED |