benchmark/detail/catch_stats.hpp

0001
0002 //              Copyright Catch2 Authors
0003 // Distributed under the Boost Software License, Version 1.0.
0004 //   (See accompanying file LICENSE.txt or copy at
0005 //        https://www.boost.org/LICENSE_1_0.txt)
0006
0007 // SPDX-License-Identifier: BSL-1.0
0008 // Adapted from donated nonius code.
0009
0010 #ifndef CATCH_STATS_HPP_INCLUDED
0011 #define CATCH_STATS_HPP_INCLUDED
0012
0013 #include <catch2/benchmark/catch_estimate.hpp>
0014 #include <catch2/benchmark/catch_outlier_classification.hpp>
0015
0016 #include <algorithm>
0017 #include <vector>
0018 #include <cmath>
0019
0020 namespace Catch {
0021     namespace Benchmark {
0022         namespace Detail {
0023             using sample = std::vector<double>;
0024
0025             // Used when we know we want == comparison of two doubles
0026             // to centralize warning suppression
0027             bool directCompare( double lhs, double rhs );
0028
0029             double weighted_average_quantile(int k, int q, std::vector<double>::iterator first, std::vector<double>::iterator last);
0030
0031             OutlierClassification
0032             classify_outliers( std::vector<double>::const_iterator first,
0033                                std::vector<double>::const_iterator last );
0034
0035             double mean( std::vector<double>::const_iterator first,
0036                          std::vector<double>::const_iterator last );
0037
0038             template <typename Estimator>
0039             sample jackknife(Estimator&& estimator,
0040                              std::vector<double>::iterator first,
0041                              std::vector<double>::iterator last) {
0042                 auto n = static_cast<size_t>(last - first);
0043                 auto second = first;
0044                 ++second;
0045                 sample results;
0046                 results.reserve(n);
0047
0048                 for (auto it = first; it != last; ++it) {
0049                     std::iter_swap(it, first);
0050                     results.push_back(estimator(second, last));
0051                 }
0052
0053                 return results;
0054             }
0055
0056             inline double normal_cdf(double x) {
0057                 return std::erfc(-x / std::sqrt(2.0)) / 2.0;
0058             }
0059
0060             double erfc_inv(double x);
0061
0062             double normal_quantile(double p);
0063
0064             template <typename Estimator>
0065             Estimate<double> bootstrap( double confidence_level,
0066                                         std::vector<double>::iterator first,
0067                                         std::vector<double>::iterator last,
0068                                         sample const& resample,
0069                                         Estimator&& estimator ) {
0070                 auto n_samples = last - first;
0071
0072                 double point = estimator(first, last);
0073                 // Degenerate case with a single sample
0074                 if (n_samples == 1) return { point, point, point, confidence_level };
0075
0076                 sample jack = jackknife(estimator, first, last);
0077                 double jack_mean = mean(jack.begin(), jack.end());
0078                 double sum_squares = 0, sum_cubes = 0;
0079                 for (double x : jack) {
0080                     auto difference = jack_mean - x;
0081                     auto square = difference * difference;
0082                     auto cube = square * difference;
0083                     sum_squares += square; sum_cubes += cube;
0084                 }
0085
0086                 double accel = sum_cubes / (6 * std::pow(sum_squares, 1.5));
0087                 long n = static_cast<long>(resample.size());
0088                 double prob_n = std::count_if(resample.begin(), resample.end(), [point](double x) { return x < point; }) / static_cast<double>(n);
0089                 // degenerate case with uniform samples
0090                 if ( directCompare( prob_n, 0. ) ) {
0091                     return { point, point, point, confidence_level };
0092                 }
0093
0094                 double bias = normal_quantile(prob_n);
0095                 double z1 = normal_quantile((1. - confidence_level) / 2.);
0096
0097                 auto cumn = [n]( double x ) -> long {
0098                     return std::lround( normal_cdf( x ) * static_cast<double>(n) );
0099                 };
0100                 auto a = [bias, accel](double b) { return bias + b / (1. - accel * b); };
0101                 double b1 = bias + z1;
0102                 double b2 = bias - z1;
0103                 double a1 = a(b1);
0104                 double a2 = a(b2);
0105                 auto lo = static_cast<size_t>((std::max)(cumn(a1), 0l));
0106                 auto hi = static_cast<size_t>((std::min)(cumn(a2), n - 1));
0107
0108                 return { point, resample[lo], resample[hi], confidence_level };
0109             }
0110
0111             struct bootstrap_analysis {
0112                 Estimate<double> mean;
0113                 Estimate<double> standard_deviation;
0114                 double outlier_variance;
0115             };
0116
0117             bootstrap_analysis analyse_samples(double confidence_level,
0118                                                unsigned int n_resamples,
0119                                                std::vector<double>::iterator first,
0120                                                std::vector<double>::iterator last);
0121         } // namespace Detail
0122     } // namespace Benchmark
0123 } // namespace Catch
0124
0125 #endif // CATCH_STATS_HPP_INCLUDED