Move SampleStatsCounter to public API
Bug: None
Change-Id: I8956f6febbb1caf71e951d212d57746fe1ec5eb2
Reviewed-on: https://webrtc-review.googlesource.com/c/src/+/184506
Commit-Queue: Artem Titov <titovartem@webrtc.org>
Reviewed-by: Karl Wiberg <kwiberg@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#32142}
diff --git a/rtc_base/numerics/math_utils.h b/rtc_base/numerics/math_utils.h
index 4bf48e22..0f1d51b 100644
--- a/rtc_base/numerics/math_utils.h
+++ b/rtc_base/numerics/math_utils.h
@@ -8,14 +8,16 @@
* be found in the AUTHORS file in the root of the source tree.
*/
-#ifndef RTC_BASE_NUMERICS_MATH_UTILS_H_
-#define RTC_BASE_NUMERICS_MATH_UTILS_H_
+#ifndef API_NUMERICS_MATH_UTILS_H_
+#define API_NUMERICS_MATH_UTILS_H_
#include <limits>
#include <type_traits>
#include "rtc_base/checks.h"
+namespace webrtc {
+namespace webrtc_impl {
// Given two numbers |x| and |y| such that x >= y, computes the difference
// x - y without causing undefined behavior due to signed overflow.
template <typename T>
@@ -67,4 +69,7 @@
return std::numeric_limits<T>::min();
}
-#endif // RTC_BASE_NUMERICS_MATH_UTILS_H_
+} // namespace webrtc_impl
+} // namespace webrtc
+
+#endif // API_NUMERICS_MATH_UTILS_H_
diff --git a/rtc_base/numerics/running_statistics.h b/rtc_base/numerics/running_statistics.h
index 4a3516d..bbcc7e2 100644
--- a/rtc_base/numerics/running_statistics.h
+++ b/rtc_base/numerics/running_statistics.h
@@ -8,8 +8,8 @@
* be found in the AUTHORS file in the root of the source tree.
*/
-#ifndef RTC_BASE_NUMERICS_RUNNING_STATISTICS_H_
-#define RTC_BASE_NUMERICS_RUNNING_STATISTICS_H_
+#ifndef API_NUMERICS_RUNNING_STATISTICS_H_
+#define API_NUMERICS_RUNNING_STATISTICS_H_
#include <algorithm>
#include <cmath>
@@ -20,6 +20,7 @@
#include "rtc_base/numerics/math_utils.h"
namespace webrtc {
+namespace webrtc_impl {
// tl;dr: Robust and efficient online computation of statistics,
// using Welford's method for variance. [1]
@@ -154,6 +155,7 @@
double cumul_ = 0; // Variance * size_, sometimes noted m2.
};
+} // namespace webrtc_impl
} // namespace webrtc
-#endif // RTC_BASE_NUMERICS_RUNNING_STATISTICS_H_
+#endif // API_NUMERICS_RUNNING_STATISTICS_H_
diff --git a/rtc_base/numerics/running_statistics_unittest.cc b/rtc_base/numerics/running_statistics_unittest.cc
index 26dc713..d593f3f 100644
--- a/rtc_base/numerics/running_statistics_unittest.cc
+++ b/rtc_base/numerics/running_statistics_unittest.cc
@@ -21,6 +21,7 @@
// Tests were copied from samples_stats_counter_unittest.cc.
namespace webrtc {
+namespace webrtc_impl {
namespace {
RunningStatistics<double> CreateStatsFilledWithIntsFrom1ToN(int n) {
@@ -55,8 +56,6 @@
constexpr int SIZE_FOR_MERGE = 5;
-} // namespace
-
TEST(RunningStatistics, FullSimpleTest) {
auto stats = CreateStatsFilledWithIntsFrom1ToN(100);
@@ -192,4 +191,6 @@
RunningStatisticsTest,
::testing::Range(0, SIZE_FOR_MERGE + 1));
+} // namespace
+} // namespace webrtc_impl
} // namespace webrtc
diff --git a/rtc_base/numerics/sample_stats.h b/rtc_base/numerics/sample_stats.h
index f634741..39af1c6 100644
--- a/rtc_base/numerics/sample_stats.h
+++ b/rtc_base/numerics/sample_stats.h
@@ -10,10 +10,10 @@
#ifndef RTC_BASE_NUMERICS_SAMPLE_STATS_H_
#define RTC_BASE_NUMERICS_SAMPLE_STATS_H_
+#include "api/numerics/samples_stats_counter.h"
#include "api/units/data_rate.h"
#include "api/units/time_delta.h"
#include "api/units/timestamp.h"
-#include "rtc_base/numerics/samples_stats_counter.h"
namespace webrtc {
template <typename T>
diff --git a/rtc_base/numerics/samples_stats_counter.cc b/rtc_base/numerics/samples_stats_counter.cc
deleted file mode 100644
index 9b98a31..0000000
--- a/rtc_base/numerics/samples_stats_counter.cc
+++ /dev/null
@@ -1,96 +0,0 @@
-/*
- * Copyright (c) 2018 The WebRTC project authors. All Rights Reserved.
- *
- * Use of this source code is governed by a BSD-style license
- * that can be found in the LICENSE file in the root of the source
- * tree. An additional intellectual property rights grant can be found
- * in the file PATENTS. All contributing project authors may
- * be found in the AUTHORS file in the root of the source tree.
- */
-
-#include "rtc_base/numerics/samples_stats_counter.h"
-
-#include <cmath>
-
-#include "absl/algorithm/container.h"
-#include "rtc_base/time_utils.h"
-
-namespace webrtc {
-
-SamplesStatsCounter::SamplesStatsCounter() = default;
-SamplesStatsCounter::~SamplesStatsCounter() = default;
-SamplesStatsCounter::SamplesStatsCounter(const SamplesStatsCounter&) = default;
-SamplesStatsCounter& SamplesStatsCounter::operator=(
- const SamplesStatsCounter&) = default;
-SamplesStatsCounter::SamplesStatsCounter(SamplesStatsCounter&&) = default;
-SamplesStatsCounter& SamplesStatsCounter::operator=(SamplesStatsCounter&&) =
- default;
-
-void SamplesStatsCounter::AddSample(double value) {
- AddSample(StatsSample{value, Timestamp::Micros(rtc::TimeMicros())});
-}
-
-void SamplesStatsCounter::AddSample(StatsSample sample) {
- stats_.AddSample(sample.value);
- samples_.push_back(sample);
- sorted_ = false;
-}
-
-void SamplesStatsCounter::AddSamples(const SamplesStatsCounter& other) {
- stats_.MergeStatistics(other.stats_);
- samples_.insert(samples_.end(), other.samples_.begin(), other.samples_.end());
- sorted_ = false;
-}
-
-double SamplesStatsCounter::GetPercentile(double percentile) {
- RTC_DCHECK(!IsEmpty());
- RTC_CHECK_GE(percentile, 0);
- RTC_CHECK_LE(percentile, 1);
- if (!sorted_) {
- absl::c_sort(samples_, [](const StatsSample& a, const StatsSample& b) {
- return a.value < b.value;
- });
- sorted_ = true;
- }
- const double raw_rank = percentile * (samples_.size() - 1);
- double int_part;
- double fract_part = std::modf(raw_rank, &int_part);
- size_t rank = static_cast<size_t>(int_part);
- if (fract_part >= 1.0) {
- // It can happen due to floating point calculation error.
- rank++;
- fract_part -= 1.0;
- }
-
- RTC_DCHECK_GE(rank, 0);
- RTC_DCHECK_LT(rank, samples_.size());
- RTC_DCHECK_GE(fract_part, 0);
- RTC_DCHECK_LT(fract_part, 1);
- RTC_DCHECK(rank + fract_part == raw_rank);
-
- const double low = samples_[rank].value;
- const double high = samples_[std::min(rank + 1, samples_.size() - 1)].value;
- return low + fract_part * (high - low);
-}
-
-SamplesStatsCounter operator*(const SamplesStatsCounter& counter,
- double value) {
- SamplesStatsCounter out;
- for (const auto& sample : counter.GetTimedSamples()) {
- out.AddSample(
- SamplesStatsCounter::StatsSample{sample.value * value, sample.time});
- }
- return out;
-}
-
-SamplesStatsCounter operator/(const SamplesStatsCounter& counter,
- double value) {
- SamplesStatsCounter out;
- for (const auto& sample : counter.GetTimedSamples()) {
- out.AddSample(
- SamplesStatsCounter::StatsSample{sample.value / value, sample.time});
- }
- return out;
-}
-
-} // namespace webrtc
diff --git a/rtc_base/numerics/samples_stats_counter.h b/rtc_base/numerics/samples_stats_counter.h
deleted file mode 100644
index a4ec443..0000000
--- a/rtc_base/numerics/samples_stats_counter.h
+++ /dev/null
@@ -1,119 +0,0 @@
-/*
- * Copyright (c) 2018 The WebRTC project authors. All Rights Reserved.
- *
- * Use of this source code is governed by a BSD-style license
- * that can be found in the LICENSE file in the root of the source
- * tree. An additional intellectual property rights grant can be found
- * in the file PATENTS. All contributing project authors may
- * be found in the AUTHORS file in the root of the source tree.
- */
-
-#ifndef RTC_BASE_NUMERICS_SAMPLES_STATS_COUNTER_H_
-#define RTC_BASE_NUMERICS_SAMPLES_STATS_COUNTER_H_
-
-#include <vector>
-
-#include "api/array_view.h"
-#include "api/units/timestamp.h"
-#include "rtc_base/checks.h"
-#include "rtc_base/numerics/running_statistics.h"
-
-namespace webrtc {
-
-// This class extends RunningStatistics by providing GetPercentile() method,
-// while slightly adapting the interface.
-class SamplesStatsCounter {
- public:
- struct StatsSample {
- double value;
- Timestamp time;
- };
-
- SamplesStatsCounter();
- ~SamplesStatsCounter();
- SamplesStatsCounter(const SamplesStatsCounter&);
- SamplesStatsCounter& operator=(const SamplesStatsCounter&);
- SamplesStatsCounter(SamplesStatsCounter&&);
- SamplesStatsCounter& operator=(SamplesStatsCounter&&);
-
- // Adds sample to the stats in amortized O(1) time.
- void AddSample(double value);
- void AddSample(StatsSample sample);
-
- // Adds samples from another counter.
- void AddSamples(const SamplesStatsCounter& other);
-
- // Returns if there are any values in O(1) time.
- bool IsEmpty() const { return samples_.empty(); }
-
- // Returns min in O(1) time. This function may not be called if there are no
- // samples.
- double GetMin() const {
- RTC_DCHECK(!IsEmpty());
- return *stats_.GetMin();
- }
- // Returns max in O(1) time. This function may not be called if there are no
- // samples.
- double GetMax() const {
- RTC_DCHECK(!IsEmpty());
- return *stats_.GetMax();
- }
- // Returns average in O(1) time. This function may not be called if there are
- // no samples.
- double GetAverage() const {
- RTC_DCHECK(!IsEmpty());
- return *stats_.GetMean();
- }
- // Returns variance in O(1) time. This function may not be called if there are
- // no samples.
- double GetVariance() const {
- RTC_DCHECK(!IsEmpty());
- return *stats_.GetVariance();
- }
- // Returns standard deviation in O(1) time. This function may not be called if
- // there are no samples.
- double GetStandardDeviation() const {
- RTC_DCHECK(!IsEmpty());
- return *stats_.GetStandardDeviation();
- }
- // Returns percentile in O(nlogn) on first call and in O(1) after, if no
- // additions were done. This function may not be called if there are no
- // samples.
- //
- // |percentile| has to be in [0; 1]. 0 percentile is the min in the array and
- // 1 percentile is the max in the array.
- double GetPercentile(double percentile);
- // Returns array view with all samples added into counter. There are no
- // guarantees of order, so samples can be in different order comparing to in
- // which they were added into counter. Also return value will be invalidate
- // after call to any non const method.
- rtc::ArrayView<const StatsSample> GetTimedSamples() const { return samples_; }
- std::vector<double> GetSamples() const {
- std::vector<double> out;
- out.reserve(samples_.size());
- for (const auto& sample : samples_) {
- out.push_back(sample.value);
- }
- return out;
- }
-
- private:
- RunningStatistics<double> stats_;
- std::vector<StatsSample> samples_;
- bool sorted_ = false;
-};
-
-// Multiply all sample values on |value| and return new SamplesStatsCounter
-// with resulted samples. Doesn't change origin SamplesStatsCounter.
-SamplesStatsCounter operator*(const SamplesStatsCounter& counter, double value);
-inline SamplesStatsCounter operator*(double value,
- const SamplesStatsCounter& counter) {
- return counter * value;
-}
-// Divide all sample values on |value| and return new SamplesStatsCounter with
-// resulted samples. Doesn't change origin SamplesStatsCounter.
-SamplesStatsCounter operator/(const SamplesStatsCounter& counter, double value);
-
-} // namespace webrtc
-
-#endif // RTC_BASE_NUMERICS_SAMPLES_STATS_COUNTER_H_
diff --git a/rtc_base/numerics/samples_stats_counter_unittest.cc b/rtc_base/numerics/samples_stats_counter_unittest.cc
deleted file mode 100644
index 1221e9b..0000000
--- a/rtc_base/numerics/samples_stats_counter_unittest.cc
+++ /dev/null
@@ -1,221 +0,0 @@
-/*
- * Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
- *
- * Use of this source code is governed by a BSD-style license
- * that can be found in the LICENSE file in the root of the source
- * tree. An additional intellectual property rights grant can be found
- * in the file PATENTS. All contributing project authors may
- * be found in the AUTHORS file in the root of the source tree.
- */
-
-#include "rtc_base/numerics/samples_stats_counter.h"
-
-#include <math.h>
-
-#include <random>
-#include <vector>
-
-#include "absl/algorithm/container.h"
-#include "test/gtest.h"
-
-namespace webrtc {
-namespace {
-
-SamplesStatsCounter CreateStatsFilledWithIntsFrom1ToN(int n) {
- std::vector<double> data;
- for (int i = 1; i <= n; i++) {
- data.push_back(i);
- }
- absl::c_shuffle(data, std::mt19937(std::random_device()()));
-
- SamplesStatsCounter stats;
- for (double v : data) {
- stats.AddSample(v);
- }
- return stats;
-}
-
-// Add n samples drawn from uniform distribution in [a;b].
-SamplesStatsCounter CreateStatsFromUniformDistribution(int n,
- double a,
- double b) {
- std::mt19937 gen{std::random_device()()};
- std::uniform_real_distribution<> dis(a, b);
-
- SamplesStatsCounter stats;
- for (int i = 1; i <= n; i++) {
- stats.AddSample(dis(gen));
- }
- return stats;
-}
-
-class SamplesStatsCounterTest : public ::testing::TestWithParam<int> {};
-
-constexpr int SIZE_FOR_MERGE = 10;
-
-} // namespace
-
-TEST(SamplesStatsCounterTest, FullSimpleTest) {
- SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(100);
-
- EXPECT_TRUE(!stats.IsEmpty());
- EXPECT_DOUBLE_EQ(stats.GetMin(), 1.0);
- EXPECT_DOUBLE_EQ(stats.GetMax(), 100.0);
- EXPECT_NEAR(stats.GetAverage(), 50.5, 1e-6);
- for (int i = 1; i <= 100; i++) {
- double p = i / 100.0;
- EXPECT_GE(stats.GetPercentile(p), i);
- EXPECT_LT(stats.GetPercentile(p), i + 1);
- }
-}
-
-TEST(SamplesStatsCounterTest, VarianceAndDeviation) {
- SamplesStatsCounter stats;
- stats.AddSample(2);
- stats.AddSample(2);
- stats.AddSample(-1);
- stats.AddSample(5);
-
- EXPECT_DOUBLE_EQ(stats.GetAverage(), 2.0);
- EXPECT_DOUBLE_EQ(stats.GetVariance(), 4.5);
- EXPECT_DOUBLE_EQ(stats.GetStandardDeviation(), sqrt(4.5));
-}
-
-TEST(SamplesStatsCounterTest, FractionPercentile) {
- SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(5);
-
- EXPECT_DOUBLE_EQ(stats.GetPercentile(0.5), 3);
-}
-
-TEST(SamplesStatsCounterTest, TestBorderValues) {
- SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(5);
-
- EXPECT_GE(stats.GetPercentile(0.01), 1);
- EXPECT_LT(stats.GetPercentile(0.01), 2);
- EXPECT_DOUBLE_EQ(stats.GetPercentile(1.0), 5);
-}
-
-TEST(SamplesStatsCounterTest, VarianceFromUniformDistribution) {
- // Check variance converge to 1/12 for [0;1) uniform distribution.
- // Acts as a sanity check for NumericStabilityForVariance test.
- SamplesStatsCounter stats = CreateStatsFromUniformDistribution(1e6, 0, 1);
-
- EXPECT_NEAR(stats.GetVariance(), 1. / 12, 1e-3);
-}
-
-TEST(SamplesStatsCounterTest, NumericStabilityForVariance) {
- // Same test as VarianceFromUniformDistribution,
- // except the range is shifted to [1e9;1e9+1).
- // Variance should also converge to 1/12.
- // NB: Although we lose precision for the samples themselves, the fractional
- // part still enjoys 22 bits of mantissa and errors should even out,
- // so that couldn't explain a mismatch.
- SamplesStatsCounter stats =
- CreateStatsFromUniformDistribution(1e6, 1e9, 1e9 + 1);
-
- EXPECT_NEAR(stats.GetVariance(), 1. / 12, 1e-3);
-}
-
-TEST_P(SamplesStatsCounterTest, AddSamples) {
- int data[SIZE_FOR_MERGE] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
- // Split the data in different partitions.
- // We have 11 distinct tests:
- // * Empty merged with full sequence.
- // * 1 sample merged with 9 last.
- // * 2 samples merged with 8 last.
- // [...]
- // * Full merged with empty sequence.
- // All must lead to the same result.
- SamplesStatsCounter stats0, stats1;
- for (int i = 0; i < GetParam(); ++i) {
- stats0.AddSample(data[i]);
- }
- for (int i = GetParam(); i < SIZE_FOR_MERGE; ++i) {
- stats1.AddSample(data[i]);
- }
- stats0.AddSamples(stats1);
-
- EXPECT_EQ(stats0.GetMin(), 0);
- EXPECT_EQ(stats0.GetMax(), 9);
- EXPECT_DOUBLE_EQ(stats0.GetAverage(), 4.5);
- EXPECT_DOUBLE_EQ(stats0.GetVariance(), 8.25);
- EXPECT_DOUBLE_EQ(stats0.GetStandardDeviation(), sqrt(8.25));
- EXPECT_DOUBLE_EQ(stats0.GetPercentile(0.1), 0.9);
- EXPECT_DOUBLE_EQ(stats0.GetPercentile(0.5), 4.5);
- EXPECT_DOUBLE_EQ(stats0.GetPercentile(0.9), 8.1);
-}
-
-TEST(SamplesStatsCounterTest, MultiplyRight) {
- SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(10);
-
- EXPECT_TRUE(!stats.IsEmpty());
- EXPECT_DOUBLE_EQ(stats.GetMin(), 1.0);
- EXPECT_DOUBLE_EQ(stats.GetMax(), 10.0);
- EXPECT_DOUBLE_EQ(stats.GetAverage(), 5.5);
-
- SamplesStatsCounter multiplied_stats = stats * 10;
- EXPECT_TRUE(!multiplied_stats.IsEmpty());
- EXPECT_DOUBLE_EQ(multiplied_stats.GetMin(), 10.0);
- EXPECT_DOUBLE_EQ(multiplied_stats.GetMax(), 100.0);
- EXPECT_DOUBLE_EQ(multiplied_stats.GetAverage(), 55.0);
- EXPECT_EQ(multiplied_stats.GetSamples().size(), stats.GetSamples().size());
-
- // Check that origin stats were not modified.
- EXPECT_TRUE(!stats.IsEmpty());
- EXPECT_DOUBLE_EQ(stats.GetMin(), 1.0);
- EXPECT_DOUBLE_EQ(stats.GetMax(), 10.0);
- EXPECT_DOUBLE_EQ(stats.GetAverage(), 5.5);
-}
-
-TEST(SamplesStatsCounterTest, MultiplyLeft) {
- SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(10);
-
- EXPECT_TRUE(!stats.IsEmpty());
- EXPECT_DOUBLE_EQ(stats.GetMin(), 1.0);
- EXPECT_DOUBLE_EQ(stats.GetMax(), 10.0);
- EXPECT_DOUBLE_EQ(stats.GetAverage(), 5.5);
-
- SamplesStatsCounter multiplied_stats = 10 * stats;
- EXPECT_TRUE(!multiplied_stats.IsEmpty());
- EXPECT_DOUBLE_EQ(multiplied_stats.GetMin(), 10.0);
- EXPECT_DOUBLE_EQ(multiplied_stats.GetMax(), 100.0);
- EXPECT_DOUBLE_EQ(multiplied_stats.GetAverage(), 55.0);
- EXPECT_EQ(multiplied_stats.GetSamples().size(), stats.GetSamples().size());
-
- // Check that origin stats were not modified.
- EXPECT_TRUE(!stats.IsEmpty());
- EXPECT_DOUBLE_EQ(stats.GetMin(), 1.0);
- EXPECT_DOUBLE_EQ(stats.GetMax(), 10.0);
- EXPECT_DOUBLE_EQ(stats.GetAverage(), 5.5);
-}
-
-TEST(SamplesStatsCounterTest, Divide) {
- SamplesStatsCounter stats;
- for (int i = 1; i <= 10; i++) {
- stats.AddSample(i * 10);
- }
-
- EXPECT_TRUE(!stats.IsEmpty());
- EXPECT_DOUBLE_EQ(stats.GetMin(), 10.0);
- EXPECT_DOUBLE_EQ(stats.GetMax(), 100.0);
- EXPECT_DOUBLE_EQ(stats.GetAverage(), 55.0);
-
- SamplesStatsCounter divided_stats = stats / 10;
- EXPECT_TRUE(!divided_stats.IsEmpty());
- EXPECT_DOUBLE_EQ(divided_stats.GetMin(), 1.0);
- EXPECT_DOUBLE_EQ(divided_stats.GetMax(), 10.0);
- EXPECT_DOUBLE_EQ(divided_stats.GetAverage(), 5.5);
- EXPECT_EQ(divided_stats.GetSamples().size(), stats.GetSamples().size());
-
- // Check that origin stats were not modified.
- EXPECT_TRUE(!stats.IsEmpty());
- EXPECT_DOUBLE_EQ(stats.GetMin(), 10.0);
- EXPECT_DOUBLE_EQ(stats.GetMax(), 100.0);
- EXPECT_DOUBLE_EQ(stats.GetAverage(), 55.0);
-}
-
-INSTANTIATE_TEST_SUITE_P(SamplesStatsCounterTests,
- SamplesStatsCounterTest,
- ::testing::Range(0, SIZE_FOR_MERGE + 1));
-
-} // namespace webrtc