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));
+}
diff --git a/video/receive_statistics_proxy.cc b/video/receive_statistics_proxy.cc
index 6e61032..d4bdc6d 100644
--- a/video/receive_statistics_proxy.cc
+++ b/video/receive_statistics_proxy.cc
@@ -821,69 +821,4 @@
frame_counts.delta_frames += other.frame_counts.delta_frames;
interframe_delay_percentiles.Add(other.interframe_delay_percentiles);
}
-
-ReceiveStatisticsProxy::HistogramPercentileCounter::HistogramPercentileCounter(
- size_t long_tail_boundary)
- : histogram_low_(long_tail_boundary),
- long_tail_boundary_(long_tail_boundary),
- total_elements_(0),
- total_elements_low_(0) {}
-
-void ReceiveStatisticsProxy::HistogramPercentileCounter::Add(
- const HistogramPercentileCounter& other) {
- uint32_t value;
- for (value = 0; value < other.long_tail_boundary_; ++value) {
- Add(value, other.histogram_low_[value]);
- }
- for (auto it = other.histogram_high_.begin();
- it != other.histogram_high_.end(); ++it) {
- Add(it->first, it->second);
- }
-}
-
-void ReceiveStatisticsProxy::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 ReceiveStatisticsProxy::HistogramPercentileCounter::Add(uint32_t value) {
- Add(value, 1);
-}
-
-rtc::Optional<uint32_t>
-ReceiveStatisticsProxy::HistogramPercentileCounter::GetPercentile(
- float fraction) {
- RTC_CHECK_LE(fraction, 1);
- RTC_CHECK_GE(fraction, 0);
- if (total_elements_ == 0)
- return rtc::Optional<uint32_t>();
- int elements_to_skip =
- static_cast<int>(std::ceil(total_elements_ * fraction)) - 1;
- if (elements_to_skip < 0)
- elements_to_skip = 0;
- if (elements_to_skip >= static_cast<int>(total_elements_))
- elements_to_skip = total_elements_ - 1;
- if (elements_to_skip < static_cast<int>(total_elements_low_)) {
- for (uint32_t value = 0; value < long_tail_boundary_; ++value) {
- elements_to_skip -= histogram_low_[value];
- if (elements_to_skip < 0)
- return rtc::Optional<uint32_t>(value);
- }
- } else {
- elements_to_skip -= total_elements_low_;
- for (auto it = histogram_high_.begin(); it != histogram_high_.end(); ++it) {
- elements_to_skip -= it->second;
- if (elements_to_skip < 0)
- return rtc::Optional<uint32_t>(it->first);
- }
- }
- RTC_NOTREACHED();
- return rtc::Optional<uint32_t>();
-}
} // namespace webrtc
diff --git a/video/receive_statistics_proxy.h b/video/receive_statistics_proxy.h
index 9d4c231..e874ddc 100644
--- a/video/receive_statistics_proxy.h
+++ b/video/receive_statistics_proxy.h
@@ -21,6 +21,7 @@
#include "common_video/include/frame_callback.h"
#include "modules/video_coding/include/video_coding_defines.h"
#include "rtc_base/criticalsection.h"
+#include "rtc_base/histogram_percentile_counter.h"
#include "rtc_base/moving_max_counter.h"
#include "rtc_base/rate_statistics.h"
#include "rtc_base/ratetracker.h"
@@ -95,25 +96,6 @@
// Implements CallStatsObserver.
void OnRttUpdate(int64_t avg_rtt_ms, int64_t max_rtt_ms) override;
- class HistogramPercentileCounter {
- public:
- // Values below |long_tail_boundary| are stored in the array.
- // Values above - in the map.
- explicit HistogramPercentileCounter(size_t long_tail_boundary);
- 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 size_t long_tail_boundary_;
- size_t total_elements_;
- size_t total_elements_low_;
- };
-
private:
struct SampleCounter {
SampleCounter() : sum(0), num_samples(0) {}
@@ -146,7 +128,7 @@
SampleCounter received_height;
SampleCounter qp_counter;
FrameCounts frame_counts;
- HistogramPercentileCounter interframe_delay_percentiles;
+ rtc::HistogramPercentileCounter interframe_delay_percentiles;
};
void UpdateHistograms() RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_);
diff --git a/video/receive_statistics_proxy_unittest.cc b/video/receive_statistics_proxy_unittest.cc
index df4305b..83dffb7 100644
--- a/video/receive_statistics_proxy_unittest.cc
+++ b/video/receive_statistics_proxy_unittest.cc
@@ -999,26 +999,4 @@
"WebRTC.Video.InterframeDelayInMs.ExperimentGroup0"));
}
}
-
-TEST_F(ReceiveStatisticsProxyTest, PercentileCounterReturnsCorrectPercentiles) {
- ReceiveStatisticsProxy::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}};
- size_t i;
- for (i = 0; i < kTestValues.size(); ++i) {
- counter.Add(kTestValues[i]);
- }
- for (i = 0; i < kTestPercentiles.size(); ++i) {
- EXPECT_EQ(kTestPercentiles[i].second,
- counter.GetPercentile(kTestPercentiles[i].first).value_or(0));
- }
-}
-
} // namespace webrtc