diff options
Diffstat (limited to 'third_party/libwebrtc/api/numerics')
5 files changed, 495 insertions, 0 deletions
diff --git a/third_party/libwebrtc/api/numerics/BUILD.gn b/third_party/libwebrtc/api/numerics/BUILD.gn new file mode 100644 index 0000000000..408dc5b9f1 --- /dev/null +++ b/third_party/libwebrtc/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/third_party/libwebrtc/api/numerics/DEPS b/third_party/libwebrtc/api/numerics/DEPS new file mode 100644 index 0000000000..2d89d57557 --- /dev/null +++ b/third_party/libwebrtc/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/third_party/libwebrtc/api/numerics/samples_stats_counter.cc b/third_party/libwebrtc/api/numerics/samples_stats_counter.cc new file mode 100644 index 0000000000..4eb0cde299 --- /dev/null +++ b/third_party/libwebrtc/api/numerics/samples_stats_counter.cc @@ -0,0 +1,101 @@ +/* + * 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(size_t expected_samples_count) { + samples_.reserve(expected_samples_count); +} + +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/third_party/libwebrtc/api/numerics/samples_stats_counter.h b/third_party/libwebrtc/api/numerics/samples_stats_counter.h new file mode 100644 index 0000000000..9d72296317 --- /dev/null +++ b/third_party/libwebrtc/api/numerics/samples_stats_counter.h @@ -0,0 +1,126 @@ +/* + * 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 <map> +#include <string> +#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; + // Sample's specific metadata. + std::map<std::string, std::string> metadata; + }; + + SamplesStatsCounter(); + explicit SamplesStatsCounter(size_t expected_samples_count); + ~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 the amount of samples added into counter in O(1) time. + int64_t NumSamples() const { return stats_.Size(); } + + // 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/third_party/libwebrtc/api/numerics/samples_stats_counter_unittest.cc b/third_party/libwebrtc/api/numerics/samples_stats_counter_unittest.cc new file mode 100644 index 0000000000..1f9cabfb29 --- /dev/null +++ b/third_party/libwebrtc/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 |