Add class which periodically computes statistics.

webrtc/video/stats_counter.cc

+/*
+ *  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 "webrtc/video/stats_counter.h"
+
+#include <algorithm>
+
+#include "webrtc/base/checks.h"
+#include "webrtc/base/logging.h"
+#include "webrtc/system_wrappers/include/clock.h"
+
+namespace webrtc {
+
+namespace {
+// Periodic time interval for processing samples.
+const int64_t kProcessIntervalMs = 2000;
+
+// Limit for the maximum number of buckets to use.
+const size_t kMaxBuckets = 250;
+}  // namespace
+
+StatsCounter::Histogram::Stats::Stats()
+    : num_samples(0),
+      min(-1),
+      max(-1),
+      average(-1),
+      percentile10(-1),
+      percentile50(-1),
+      percentile90(-1) {}
+
+// Histogram class.
+StatsCounter::Histogram::Histogram(size_t bucket_count, size_t bucket_max)
+    : bucket_count_(bucket_count),
+      bucket_max_(bucket_max),
+      bucket_size1_(bucket_count == bucket_max),

[stefan-webrtc, 2016/01/29 15:22:46]

I don't think I fully understand what this variable is based on reading its
name.

+      sum_(0) {
+  RTC_CHECK_GT(kProcessIntervalMs, 0);
+  RTC_CHECK_GT(bucket_count, 0u);
+  RTC_CHECK_GT(bucket_max, 0u);
+  RTC_CHECK_LE(bucket_count, bucket_max);
+  InitializeBuckets();
+}
+
+void StatsCounter::Histogram::InitializeBuckets() {
+  if (bucket_size1_) {
+    // Buckets created when needed.
+    return;
+  }
+  RTC_CHECK_LE(bucket_count_, kMaxBuckets);
+  double log_max = log(static_cast<double>(bucket_max_));
+  buckets_[0] = 0;    // [0, bucket min)
+  size_t cur = 1;  // bucket min
+  buckets_[cur] = 0;  // [bucket min,...)
+  for (size_t i = 2; i < bucket_count_; ++i) {
+    // cur * x^(remaining buckets) = max
+    double log_cur = log(static_cast<double>(cur));
+    double log_x = (log_max - log_cur) / (bucket_count_ - i);
+    double log_next = log_cur + log_x;

[stefan-webrtc, 2016/01/29 15:22:46]

I'm trying to follow this and I have a bit of a hard time understanding what x
is here. Is it the number of percent each bucket is supposed to increase?

Based on my computations below I think line 66 can be rewritten to
next = cur * exp(log(x)) and line 65 can be removed, is that correct? Either way
maybe we should have a comment or two here to explain the derivation?

log(max / cur) = log(x)*remaining
log(x) = log(max/cur) / remaining
log(x) = (log(max) - log(cur)) / remaining

log(cur) + log(x) = log(cur*x)
next = exp(log(cur*x)) = cur*x

+    size_t next = static_cast<size_t>(exp(log_next) + 0.5);
+    cur = (next > cur) ? next : (cur + 1);
+    buckets_[cur] = 0;  // [cur,...)
+  }
+  RTC_DCHECK(buckets_.rbegin()->first == 1 ||
+             buckets_.rbegin()->first == bucket_max_);
+}
+
+void StatsCounter::Histogram::Add(int sample) {
+  sum_ += sample;
+  ++stats_.num_samples;
+  if (stats_.num_samples == 1) {
+    stats_.min = sample;
+    stats_.max = sample;
+  }
+  stats_.min = std::min(sample, stats_.min);
+  stats_.max = std::max(sample, stats_.max);
+
+  if (sample < 0)
+    sample = 0;
+
+  AddToBucket(sample);
+}
+
+void StatsCounter::Histogram::AddToBucket(size_t sample) {
+  if (sample > bucket_max_)
+    sample = bucket_max_;
+
+  if (bucket_size1_) {
+    if (buckets_.size() == kMaxBuckets &&
+        buckets_.find(sample) == buckets_.end()) {
+      LOG(LS_WARNING) << "Max buckets reached. Sample not added " << sample;
+      return;
+    }
+    ++buckets_[sample];
+    return;
+  }
+
+  // Find bucket.
+  RTC_DCHECK(buckets_.size() >= 2);
+  auto it = buckets_.upper_bound(sample);
+  --it;
+  it->second++;
+}
+
+StatsCounter::Histogram::Stats StatsCounter::Histogram::stats() {
+  Compute();
+  return stats_;
+}
+
+void StatsCounter::Histogram::Compute() {
+  if (stats_.num_samples == 0)
+    return;
+
+  stats_.average = (sum_ + (stats_.num_samples / 2)) / stats_.num_samples;
+
+  size_t sample10 = round(std::max(stats_.num_samples * 0.1f, 1.0f));
+  size_t sample50 = round(std::max(stats_.num_samples * 0.5f, 1.0f));
+  size_t sample90 = round(std::max(stats_.num_samples * 0.9f, 1.0f));
+
+  stats_.percentile10 = -1;
+  stats_.percentile50 = -1;
+  stats_.percentile90 = -1;
+
+  size_t samples = 0;
+  int last = 0;
+  for (const auto bucket : buckets_) {
+    int cur = static_cast<int>(bucket.first);
+    samples += bucket.second;
+    // 10th percentile.
+    if (!bucket_size1_ && stats_.percentile10 == last)
+      stats_.percentile10 += ((cur - last) / 2);
+    if (samples >= sample10 && stats_.percentile10 == -1)
+      stats_.percentile10 = cur;
+    // 50th percentile.
+    if (!bucket_size1_ && stats_.percentile50 == last)
+      stats_.percentile50 += ((cur - last) / 2);
+    if (samples >= sample50 && stats_.percentile50 == -1)
+      stats_.percentile50 = cur;
+    // 90th percentile.
+    if (!bucket_size1_ && stats_.percentile90 == last)
+      stats_.percentile90 += ((cur - last) / 2);
+    if (samples >= sample90 && stats_.percentile90 == -1)
+      stats_.percentile90 = cur;
+    last = cur;
+  }
+
+  // Limit percentiles by max (mid bucket value used).
+  if (stats_.max > 0) {
+    stats_.percentile10 = std::min(stats_.percentile10, stats_.max);
+    stats_.percentile50 = std::min(stats_.percentile50, stats_.max);
+    stats_.percentile90 = std::min(stats_.percentile90, stats_.max);
+  }
+}
+
+// StatsCounter class.
+StatsCounter::StatsCounter(Clock* clock,
+                           size_t bucket_count,
+                           size_t bucket_max,
+                           bool include_empty_intervals,
+                           StatsCounterObserver* observer)
+    : sum_(0),
+      num_samples_(0),
+      last_sum_(0),
+      clock_(clock),
+      include_empty_intervals_(include_empty_intervals),
+      observer_(observer),
+      last_process_time_ms_(-1),
+      histogram_(bucket_count, bucket_max) {}
+
+StatsCounter::Histogram::Stats StatsCounter::GetStats() {
+  return histogram_.stats();
+}
+
+bool StatsCounter::TimeToProcess() {
+  int64_t now = clock_->TimeInMilliseconds();
+  if (last_process_time_ms_ == -1)
+    last_process_time_ms_ = now;
+
+  int64_t diff_ms = now - last_process_time_ms_;
+  if (diff_ms < kProcessIntervalMs)
+    return false;
+
+  // Advance number of complete kProcessIntervalMs that have passed.
+  int64_t num_intervals = diff_ms / kProcessIntervalMs;
+  last_process_time_ms_ += num_intervals * kProcessIntervalMs;
+
+  // Add zero for intervals without samples.
+  if (include_empty_intervals_) {
+    for (int64_t i = 0; i < num_intervals - 1; ++i) {
+      histogram_.Add(0);
+      if (observer_)
+        observer_->OnMetricUpdated(0);
+    }
+  }
+  return true;
+}
+
+void StatsCounter::Set(int sample) {
+  Process();
+  ++num_samples_;
+  sum_ = sample;
+}
+
+void StatsCounter::Add(int sample) {
+  Process();
+  ++num_samples_;
+  sum_ += sample;
+}
+
+void StatsCounter::Process() {
+  if (!TimeToProcess())
+    return;
+
+  int metric;
+  if (GetMetric(&metric)) {
+    histogram_.Add(metric);
+    if (observer_)
+      observer_->OnMetricUpdated(metric);
+  }
+  last_sum_ = sum_;
+  sum_ = 0;
+  num_samples_ = 0;
+}
+
+// StatsCounter sub-classes.
+AvgCounter::AvgCounter(Clock* clock,
+                       size_t bucket_count,
+                       size_t bucket_max,
+                       StatsCounterObserver* observer)
+    : StatsCounter::StatsCounter(clock,
+                                 bucket_count,
+                                 bucket_max,
+                                 false,  // include_empty_intervals
+                                 observer) {}
+
+void AvgCounter::Add(int sample) {
+  StatsCounter::Add(sample);
+}
+
+bool AvgCounter::GetMetric(int* metric) const {
+  if (num_samples_ == 0)
+    return false;
+  *metric = (sum_ + (num_samples_ / 2)) / num_samples_;
+  return true;
+}
+
+PercentCounter::PercentCounter(Clock* clock, StatsCounterObserver* observer)
+    : StatsCounter::StatsCounter(clock,
+                                 101,    // bucket_count
+                                 101,    // bucket_max
+                                 false,  // include_empty_intervals
+                                 observer) {}
+
+void PercentCounter::Add(bool sample) {
+  StatsCounter::Add(sample ? 1 : 0);
+}
+
+bool PercentCounter::GetMetric(int* metric) const {
+  if (num_samples_ == 0)
+    return false;
+  *metric = (sum_ * 100 + (num_samples_ / 2)) / num_samples_;
+  return true;
+}
+
+PermilleCounter::PermilleCounter(Clock* clock,
+                                 size_t bucket_count,
+                                 StatsCounterObserver* observer)
+    : StatsCounter::StatsCounter(clock,
+                                 bucket_count,
+                                 1001,   // bucket_max
+                                 false,  // include_empty_intervals
+                                 observer) {}
+
+void PermilleCounter::Add(bool sample) {
+  StatsCounter::Add(sample ? 1 : 0);
+}
+
+bool PermilleCounter::GetMetric(int* metric) const {
+  if (num_samples_ == 0)
+    return false;
+  *metric = (sum_ * 1000 + (num_samples_ / 2)) / num_samples_;
+  return true;
+}
+
+RateCounter::RateCounter(Clock* clock,
+                         size_t bucket_count,
+                         size_t bucket_max,
+                         bool include_empty_intervals,
+                         StatsCounterObserver* observer)
+    : StatsCounter::StatsCounter(clock,
+                                 bucket_count,
+                                 bucket_max,
+                                 include_empty_intervals,
+                                 observer) {}
+
+void RateCounter::Add(int sample) {
+  StatsCounter::Add(sample);
+}
+
+bool RateCounter::GetMetric(int* metric) const {
+  if (num_samples_ == 0)
+    return false;
+  *metric = (sum_ * 1000 + (kProcessIntervalMs / 2)) / kProcessIntervalMs;
+  return true;
+}
+
+RateAccCounter::RateAccCounter(Clock* clock,
+                               size_t bucket_count,
+                               size_t bucket_max,
+                               bool include_empty_intervals,
+                               StatsCounterObserver* observer)
+    : StatsCounter::StatsCounter(clock,
+                                 bucket_count,
+                                 bucket_max,
+                                 include_empty_intervals,
+                                 observer) {}
+
+void RateAccCounter::Set(int sample) {
+  StatsCounter::Set(sample);
+}
+
+bool RateAccCounter::GetMetric(int* metric) const {
+  if (num_samples_ == 0 || last_sum_ > sum_)
+    return false;
+  *metric = ((sum_ - last_sum_) * 1000 + (kProcessIntervalMs / 2)) /
+            kProcessIntervalMs;
+  return true;
+}
+
+}  // namespace webrtc