ratio_bootstrap_estimator.cc | Explore in Territory

// Copyright 2024 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "testing/perf/confidence/ratio_bootstrap_estimator.h"

#define _USE_MATH_DEFINES …
#include <math.h>

#include <algorithm>
#include <memory>
#include <vector>

#ifdef UNSAFE_BUFFERS_BUILD
// Not used with untrusted inputs.
#pragma allow_unsafe_buffers
#endif

lower_bound;
min;
numeric_limits;
sort;
unique_ptr;
vector;

// Inverse normal CDF, e.g. InverseNormalCDF(0.975) ~= 1.96
// (a 95% CI will cover +/- 1.96 standard deviations from the mean).
//
// For some reason, C has erf() in its standard library, but not its inverse,
// so we have to build it ourselves (which is a bit annoying, since we only
// really want it to convert the confidence interval quantiles!). This is
// nontrivial, but fortunately, others have figured it out. This is an
// implementation of “Algorithm AS 241: The Percentage Points of the Normal
// Distribution” (Wichura), and is roughly the same as was used in GNU R
// until recently. We don't need extreme precision, so we've only used the
// version that is accurate to about seven decimal digits (the other one
// is pretty much the same, just with even more constants).
double RatioBootstrapEstimator::InverseNormalCDF(double p) { … }

namespace {

// Normal (Gaussian) CDF, e.g. NormCRF(1.96) ~= 0.975
// (+/- 1.96 standard deviations would cover a 95% CI).
double NormalCDF(double q) { … }

// Compute percentiles of the bootstrap distribution (the inverse of G).
// We estimate G by Ĝ, the bootstrap estimate of G (text above eq. 2.9
// in the paper). Note that unlike bcajack, we interpolate between values
// to get slightly better accuracy.
double ComputeBCa(const double* estimates,
                  size_t num_estimates,
                  double alpha,
                  double z0,
                  double a) { … }

// Calculate Ĝ (the fraction of estimates that are less than search-value).
double FindCDF(const double* estimates,
               size_t num_estimates,
               double search_val) { … }

}  // namespace

// Find the ratio estimate over all values except for the one at skip_index,
// i.e., leave-one-out. (If skip_index == -1 or similar, simply compute over
// all values.) This is used in the jackknife estimate for the acceleration.
double RatioBootstrapEstimator::EstimateRatioExcept(
    const vector<RatioBootstrapEstimator::Sample>& x,
    int skip_index) { … }

// Similar, for the geometric mean across all the data sets.
double RatioBootstrapEstimator::EstimateGeometricMeanExcept(
    const vector<vector<RatioBootstrapEstimator::Sample>>& x,
    int skip_index) { … }

vector<RatioBootstrapEstimator::Estimate>
RatioBootstrapEstimator::ComputeRatioEstimates(
    const vector<vector<RatioBootstrapEstimator::Sample>>& data,
    unsigned num_resamples,
    double confidence_level,
    bool compute_geometric_mean) { … }
chromium/testing/perf/confidence/ratio_bootstrap_estimator.cc
