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/api/numerics/BUILD.gn b/api/numerics/BUILD.gn
new file mode 100644
index 0000000..408dc5b
--- /dev/null
+++ b/api/numerics/BUILD.gn
@@ -0,0 +1,41 @@
+# Copyright (c) 2020 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.
+
+import("../../webrtc.gni")
+
+rtc_library("numerics") {
+ visibility = [ "*" ]
+
+ sources = [
+ "samples_stats_counter.cc",
+ "samples_stats_counter.h",
+ ]
+ deps = [
+ "..:array_view",
+ "../../rtc_base:checks",
+ "../../rtc_base:rtc_numerics",
+ "../../rtc_base:timeutils",
+ "../units:timestamp",
+ ]
+ absl_deps = [ "//third_party/abseil-cpp/absl/algorithm:container" ]
+}
+
+if (rtc_include_tests) {
+ rtc_library("numerics_unittests") {
+ visibility = [ "*" ]
+ testonly = true
+
+ sources = [ "samples_stats_counter_unittest.cc" ]
+
+ deps = [
+ ":numerics",
+ "../../test:test_support",
+ ]
+ absl_deps = [ "//third_party/abseil-cpp/absl/algorithm:container" ]
+ }
+}
diff --git a/api/numerics/DEPS b/api/numerics/DEPS
new file mode 100644
index 0000000..2d89d57
--- /dev/null
+++ b/api/numerics/DEPS
@@ -0,0 +1,6 @@
+specific_include_rules = {
+ # Some internal headers are allowed even in API headers:
+ "samples_stats_counter\.h": [
+ "+rtc_base/numerics/running_statistics.h",
+ ]
+}
diff --git a/api/numerics/samples_stats_counter.cc b/api/numerics/samples_stats_counter.cc
new file mode 100644
index 0000000..36871a6
--- /dev/null
+++ b/api/numerics/samples_stats_counter.cc
@@ -0,0 +1,97 @@
+/*
+ * 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 "api/numerics/samples_stats_counter.h"
+
+#include <algorithm>
+#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/api/numerics/samples_stats_counter.h b/api/numerics/samples_stats_counter.h
new file mode 100644
index 0000000..9387e6b
--- /dev/null
+++ b/api/numerics/samples_stats_counter.h
@@ -0,0 +1,119 @@
+/*
+ * 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 API_NUMERICS_SAMPLES_STATS_COUNTER_H_
+#define API_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:
+ webrtc_impl::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 // API_NUMERICS_SAMPLES_STATS_COUNTER_H_
diff --git a/api/numerics/samples_stats_counter_unittest.cc b/api/numerics/samples_stats_counter_unittest.cc
new file mode 100644
index 0000000..1f9cabf
--- /dev/null
+++ b/api/numerics/samples_stats_counter_unittest.cc
@@ -0,0 +1,221 @@
+/*
+ * 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 "api/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