Introduce stats calculator.
It accumulate sample values inside it and provide API to calc
min/max/avg and percentiles. Current implementation will do it
in O(nlogn) time and planned to be used in the test code after
all time sensitive operations and also assume not too big amount
of data inside.
Bug: webrtc:10138
Change-Id: I262c4b9ca538c19463888b6d6bcdaa7e8c3caa68
Reviewed-on: https://webrtc-review.googlesource.com/c/116284
Commit-Queue: Artem Titov <titovartem@webrtc.org>
Reviewed-by: Karl Wiberg <kwiberg@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#26214}diff --git a/rtc_base/BUILD.gn b/rtc_base/BUILD.gn
index 896e5d8..f350028 100644
--- a/rtc_base/BUILD.gn
+++ b/rtc_base/BUILD.gn
@@ -689,6 +689,8 @@
"numerics/moving_average.h",
"numerics/moving_median_filter.h",
"numerics/percentile_filter.h",
+ "numerics/samples_stats_counter.cc",
+ "numerics/samples_stats_counter.h",
"numerics/sequence_number_util.h",
]
deps = [
@@ -1402,6 +1404,7 @@
"numerics/moving_average_unittest.cc",
"numerics/moving_median_filter_unittest.cc",
"numerics/percentile_filter_unittest.cc",
+ "numerics/samples_stats_counter_unittest.cc",
"numerics/sequence_number_util_unittest.cc",
]
deps = [
diff --git a/rtc_base/numerics/samples_stats_counter.cc b/rtc_base/numerics/samples_stats_counter.cc
new file mode 100644
index 0000000..ac07734
--- /dev/null
+++ b/rtc_base/numerics/samples_stats_counter.cc
@@ -0,0 +1,64 @@
+/*
+ * 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 <algorithm>
+#include <cmath>
+
+namespace webrtc {
+
+SamplesStatsCounter::SamplesStatsCounter() = default;
+SamplesStatsCounter::~SamplesStatsCounter() = default;
+SamplesStatsCounter::SamplesStatsCounter(SamplesStatsCounter&) = default;
+SamplesStatsCounter::SamplesStatsCounter(SamplesStatsCounter&&) = default;
+
+void SamplesStatsCounter::AddSample(double value) {
+ samples_.push_back(value);
+ sorted_ = false;
+ if (value > max_) {
+ max_ = value;
+ }
+ if (value < min_) {
+ min_ = value;
+ }
+ sum_ += value;
+}
+
+double SamplesStatsCounter::GetPercentile(double percentile) {
+ RTC_DCHECK(!IsEmpty());
+ RTC_CHECK_GE(percentile, 0);
+ RTC_CHECK_LE(percentile, 1);
+ if (!sorted_) {
+ std::sort(samples_.begin(), samples_.end());
+ 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];
+ const double high = samples_[std::min(rank + 1, samples_.size() - 1)];
+ return low + fract_part * (high - low);
+}
+
+} // namespace webrtc
diff --git a/rtc_base/numerics/samples_stats_counter.h b/rtc_base/numerics/samples_stats_counter.h
new file mode 100644
index 0000000..8849503
--- /dev/null
+++ b/rtc_base/numerics/samples_stats_counter.h
@@ -0,0 +1,70 @@
+/*
+ * 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 <limits>
+#include <vector>
+
+#include "rtc_base/checks.h"
+
+namespace webrtc {
+
+class SamplesStatsCounter {
+ public:
+ SamplesStatsCounter();
+ ~SamplesStatsCounter();
+ SamplesStatsCounter(SamplesStatsCounter&);
+ SamplesStatsCounter(SamplesStatsCounter&&);
+
+ // Adds sample to the stats in amortized O(1) time.
+ void AddSample(double value);
+
+ // 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 min_;
+ }
+ // Returns max in O(1) time. This function may not be called if there are no
+ // samples.
+ double GetMax() const {
+ RTC_DCHECK(!IsEmpty());
+ return max_;
+ }
+ // Returns average in O(1) time. This function may not be called if there are
+ // no samples.
+ double GetAverage() const {
+ RTC_DCHECK(!IsEmpty());
+ return sum_ / samples_.size();
+ }
+ // 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);
+
+ private:
+ std::vector<double> samples_;
+ double min_ = std::numeric_limits<double>::max();
+ double max_ = std::numeric_limits<double>::min();
+ double sum_ = 0;
+ bool sorted_ = false;
+};
+
+} // 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
new file mode 100644
index 0000000..713b5f9
--- /dev/null
+++ b/rtc_base/numerics/samples_stats_counter_unittest.cc
@@ -0,0 +1,64 @@
+/*
+ * 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 <algorithm>
+#include <vector>
+
+#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);
+ }
+ std::random_shuffle(data.begin(), data.end());
+
+ SamplesStatsCounter stats;
+ for (double v : data) {
+ stats.AddSample(v);
+ }
+ return stats;
+}
+} // namespace
+
+TEST(SamplesStatsCounter, FullSimpleTest) {
+ SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(100);
+
+ ASSERT_TRUE(!stats.IsEmpty());
+ ASSERT_DOUBLE_EQ(stats.GetMin(), 1.0);
+ ASSERT_DOUBLE_EQ(stats.GetMax(), 100.0);
+ ASSERT_DOUBLE_EQ(stats.GetAverage(), 50.5);
+ ASSERT_DOUBLE_EQ(stats.GetPercentile(0), 1);
+ for (int i = 1; i <= 100; i++) {
+ double p = i / 100.0;
+ ASSERT_GE(stats.GetPercentile(p), i);
+ ASSERT_LT(stats.GetPercentile(p), i + 1);
+ }
+}
+
+TEST(SamplesStatsCounter, FractionPercentile) {
+ SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(5);
+
+ ASSERT_DOUBLE_EQ(stats.GetPercentile(0.5), 3);
+}
+
+TEST(SamplesStatsCounter, TestBorderValues) {
+ SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(5);
+
+ ASSERT_GE(stats.GetPercentile(0.01), 1);
+ ASSERT_LT(stats.GetPercentile(0.01), 2);
+ ASSERT_DOUBLE_EQ(stats.GetPercentile(1.0), 5);
+}
+
+} // namespace webrtc