Move HistogramPercentileCounter to rtc_base from RecieveStatisticProxy.
This should be a separate utility class, rather than internal thing in
ReceiveStatisticsProxy.
Bug: webrtc:8347
Change-Id: I9c8238e625999dba5776d6038c819732d07e9656
Reviewed-on: https://webrtc-review.googlesource.com/7609
Commit-Queue: Ilya Nikolaevskiy <ilnik@webrtc.org>
Reviewed-by: Karl Wiberg <kwiberg@webrtc.org>
Reviewed-by: Erik Språng <sprang@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#20267}diff --git a/rtc_base/BUILD.gn b/rtc_base/BUILD.gn
index 8d93870..0646fb3 100644
--- a/rtc_base/BUILD.gn
+++ b/rtc_base/BUILD.gn
@@ -137,6 +137,8 @@
"flags.h",
"format_macros.h",
"function_view.h",
+ "histogram_percentile_counter.cc",
+ "histogram_percentile_counter.h",
"ignore_wundef.h",
"location.cc",
"location.h",
@@ -895,6 +897,7 @@
"event_unittest.cc",
"file_unittest.cc",
"function_view_unittest.cc",
+ "histogram_percentile_counter_unittest.cc",
"logging_unittest.cc",
"md5digest_unittest.cc",
"mod_ops_unittest.cc",
diff --git a/rtc_base/histogram_percentile_counter.cc b/rtc_base/histogram_percentile_counter.cc
new file mode 100644
index 0000000..959e11d
--- /dev/null
+++ b/rtc_base/histogram_percentile_counter.cc
@@ -0,0 +1,79 @@
+/*
+ * Copyright (c) 2017 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/histogram_percentile_counter.h"
+
+#include <algorithm>
+#include <cmath>
+
+#include "rtc_base/checks.h"
+
+namespace rtc {
+HistogramPercentileCounter::HistogramPercentileCounter(
+ uint32_t long_tail_boundary)
+ : histogram_low_(size_t{long_tail_boundary}),
+ long_tail_boundary_(long_tail_boundary),
+ total_elements_(0),
+ total_elements_low_(0) {}
+
+HistogramPercentileCounter::~HistogramPercentileCounter() = default;
+
+void HistogramPercentileCounter::Add(const HistogramPercentileCounter& other) {
+ for (uint32_t value = 0; value < other.long_tail_boundary_; ++value) {
+ Add(value, other.histogram_low_[value]);
+ }
+ for (const auto& it : histogram_high_) {
+ Add(it.first, it.second);
+ }
+}
+
+void HistogramPercentileCounter::Add(uint32_t value, size_t count) {
+ if (value < long_tail_boundary_) {
+ histogram_low_[value] += count;
+ total_elements_low_ += count;
+ } else {
+ histogram_high_[value] += count;
+ }
+ total_elements_ += count;
+}
+
+void HistogramPercentileCounter::Add(uint32_t value) {
+ Add(value, 1);
+}
+
+rtc::Optional<uint32_t> HistogramPercentileCounter::GetPercentile(
+ float fraction) {
+ RTC_CHECK_LE(fraction, 1.0);
+ RTC_CHECK_GE(fraction, 0.0);
+ if (total_elements_ == 0)
+ return rtc::Optional<uint32_t>();
+ size_t elements_to_skip = static_cast<size_t>(
+ std::max(0.0f, std::ceil(total_elements_ * fraction) - 1));
+ if (elements_to_skip >= total_elements_)
+ elements_to_skip = total_elements_ - 1;
+ if (elements_to_skip < total_elements_low_) {
+ for (uint32_t value = 0; value < long_tail_boundary_; ++value) {
+ if (elements_to_skip < histogram_low_[value])
+ return rtc::Optional<uint32_t>(value);
+ elements_to_skip -= histogram_low_[value];
+ }
+ } else {
+ elements_to_skip -= total_elements_low_;
+ for (const auto& it : histogram_high_) {
+ if (elements_to_skip < it.second)
+ return rtc::Optional<uint32_t>(it.first);
+ elements_to_skip -= it.second;
+ }
+ }
+ RTC_NOTREACHED();
+ return rtc::Optional<uint32_t>();
+}
+
+} // namespace rtc
diff --git a/rtc_base/histogram_percentile_counter.h b/rtc_base/histogram_percentile_counter.h
new file mode 100644
index 0000000..5769fb0
--- /dev/null
+++ b/rtc_base/histogram_percentile_counter.h
@@ -0,0 +1,43 @@
+/*
+ * Copyright (c) 2017 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_HISTOGRAM_PERCENTILE_COUNTER_H_
+#define RTC_BASE_HISTOGRAM_PERCENTILE_COUNTER_H_
+
+#include <stdint.h>
+#include <map>
+#include <vector>
+
+#include "api/optional.h"
+
+namespace rtc {
+// Calculates percentiles on the stream of data. Use |Add| methods to add new
+// values. Use |GetPercentile| to get percentile of the currently added values.
+class HistogramPercentileCounter {
+ public:
+ // Values below |long_tail_boundary| are stored as the histogram in an array.
+ // Values above - in a map.
+ explicit HistogramPercentileCounter(uint32_t long_tail_boundary);
+ ~HistogramPercentileCounter();
+ void Add(uint32_t value);
+ void Add(uint32_t value, size_t count);
+ void Add(const HistogramPercentileCounter& other);
+ // Argument should be from 0 to 1.
+ rtc::Optional<uint32_t> GetPercentile(float fraction);
+
+ private:
+ std::vector<size_t> histogram_low_;
+ std::map<uint32_t, size_t> histogram_high_;
+ const uint32_t long_tail_boundary_;
+ size_t total_elements_;
+ size_t total_elements_low_;
+};
+} // namespace rtc
+#endif // RTC_BASE_HISTOGRAM_PERCENTILE_COUNTER_H_
diff --git a/rtc_base/histogram_percentile_counter_unittest.cc b/rtc_base/histogram_percentile_counter_unittest.cc
new file mode 100644
index 0000000..4943123
--- /dev/null
+++ b/rtc_base/histogram_percentile_counter_unittest.cc
@@ -0,0 +1,43 @@
+/*
+ * Copyright 2017 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/histogram_percentile_counter.h"
+
+#include <utility>
+#include <vector>
+
+#include "test/gtest.h"
+
+TEST(HistogramPercentileCounterTest, ReturnsCorrectPercentiles) {
+ rtc::HistogramPercentileCounter counter(10);
+ const std::vector<int> kTestValues = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
+ 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
+
+ EXPECT_FALSE(counter.GetPercentile(0.5f));
+ // Pairs of {fraction, percentile value} computed by hand
+ // for |kTestValues|.
+ const std::vector<std::pair<float, uint32_t>> kTestPercentiles = {
+ {0.0f, 1}, {0.01f, 1}, {0.5f, 10}, {0.9f, 18},
+ {0.95f, 19}, {0.99f, 20}, {1.0f, 20}};
+ for (int value : kTestValues) {
+ counter.Add(value);
+ }
+ for (const auto& test_percentile : kTestPercentiles) {
+ EXPECT_EQ(test_percentile.second,
+ counter.GetPercentile(test_percentile.first).value_or(0));
+ }
+}
+
+TEST(HistogramPercentileCounterTest, HandlesEmptySequence) {
+ rtc::HistogramPercentileCounter counter(10);
+ EXPECT_FALSE(counter.GetPercentile(0.5f));
+ counter.Add(1u);
+ EXPECT_TRUE(counter.GetPercentile(0.5f));
+}