Add a rate tracker that tracks rate over a given interval split up into buckets that accumulate uni…

webrtc/base/bucketratetracker.cc

Index: webrtc/base/bucketratetracker.cc
diff --git a/webrtc/base/bucketratetracker.cc b/webrtc/base/bucketratetracker.cc
new file mode 100644
index 0000000000000000000000000000000000000000..ed4d6a28459a06498b084da56be1071c1c7d5f0d
--- /dev/null
+++ b/webrtc/base/bucketratetracker.cc
@@ -0,0 +1,110 @@
+/*
+ *  Copyright 2015 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/base/bucketratetracker.h"
+
+#include <assert.h>
+
+#include "webrtc/base/timeutils.h"
+
+namespace rtc {
+
+BucketRateTracker::BucketRateTracker(
+    uint32 bucket_milliseconds, uint32 interval_buckets)
+    : bucket_milliseconds_(bucket_milliseconds),
+    interval_buckets_(interval_buckets),
+    unit_buckets_(new size_t[interval_buckets + 1]),
+    bucket_start_time_(~0u) {
+  assert(bucket_milliseconds > 0u);
+  assert(interval_buckets > 0u);
+  assert(bucket_milliseconds * interval_buckets >= 1000u);
+}
+
+BucketRateTracker::~BucketRateTracker() {
+  delete[] unit_buckets_;
+}
+
+size_t BucketRateTracker::units_second() const {
+  if (bucket_start_time_ == ~0u) {
+    return 0u;
+  }
+  uint32 current_time = Time();
+  // Calculate which buckets to sum up given the current time.  If the time
+  // has passed to a new bucket then we have to skip some of the oldest buckets.
+  uint32 interval_milliseconds = bucket_milliseconds_ * interval_buckets_;

[noahric, 2015/08/07 23:56:38]

Yeah, this would be handy to pass in, and then it'd be easy to have multiple
listeners over the same tracker get stats over different periods. And then you'd
have something like:
GetRateForInterval(uint32 interval_milliseconds) {
interval_milliseconds = min(interval_milliseconds, bucket_milliseconds_ *
bucket_count_);

[tpsiaki, 2015/08/11 18:33:26]

Done.

+  // number of old buckets (i.e. after the current bucket in the ring buffer)
+  // that are expired given our current time interval.
+  uint32 buckets_to_skip;
+  // Number of milliseconds of the first bucket that are not a portion of the
+  // current interval.
+  uint32 milliseconds_to_skip;
+  if (current_time > initialization_time_ + interval_milliseconds) {
+    uint32 time_to_skip = current_time - bucket_start_time_;;

[noahric, 2015/08/07 23:56:38]

extra ;

[tpsiaki, 2015/08/11 18:33:27]

Done.

+    buckets_to_skip = time_to_skip / bucket_milliseconds_;
+    milliseconds_to_skip = time_to_skip % bucket_milliseconds_;
+  } else {
+    buckets_to_skip = interval_buckets_ - current_bucket_;
+    milliseconds_to_skip = 0u;
+    interval_milliseconds = current_time - initialization_time_;
+  }
+  // If we're skipping all buckets that means that there have been no units
+  // within the sampling interval so report 0.  For parity with RateTracker we
+  // also do not report for intervals under 1 second.
+  if (buckets_to_skip > interval_buckets_ || interval_milliseconds < 1000u) {
+    return 0u;
+  }
+  uint32 start_bucket = (current_bucket_ + 1 + buckets_to_skip) %
+      (interval_buckets_ + 1);
+  // Only count a portion of the first bucket according to how much of the
+  // first bucket is within the current interval.
+  size_t total_units = unit_buckets_[start_bucket] *

[noahric, 2015/08/07 23:56:38]

Yeah, consider using "sample" as a substitute for "unit" throughout this file.

[tpsiaki, 2015/08/11 18:33:27]

Done.

+      (bucket_milliseconds_ - milliseconds_to_skip) /
+      bucket_milliseconds_;
+  // All other buckets in the interval are counted in their entirety.
+  for (uint32 i = (start_bucket + 1) % (interval_buckets_ + 1);

[noahric, 2015/08/07 23:56:38]

size_t for indices (throughout)

[noahric, 2015/08/07 23:56:38]

Consider a helper method like NextBucketIndex(size_t bucket_index). It would
also clear up things like start_bucket, which is:
NextBucketIndex(current_bucket_ + buckets_to_skip)

[tpsiaki, 2015/08/11 18:33:27]

Done.

[tpsiaki, 2015/08/11 18:33:27]

Done.

+      i != (current_bucket_ + 1) % (interval_buckets_ + 1);
+      i = (i + 1) % (interval_buckets_ + 1)) {
+    total_units += unit_buckets_[i];
+  }
+  // Convert to units per second.
+  return (total_units * 1000 + (interval_milliseconds >> 1)) /
+      interval_milliseconds;
+}
+
+void BucketRateTracker::Update(size_t units) {
+  EnsureInitialized();
+  uint32 current_time = Time();
+  // Advance the current bucket as needed for the current time, and reset
+  // bucket counts as we advance.
+  while (current_time > bucket_start_time_ + bucket_milliseconds_) {

[noahric, 2015/08/07 23:56:38]

I'd replace this with a for loop, so you don't accidentally fall into some case
where bucket_start_time_ super far away from current_time_ and you end up
re-looping over the buckets a ton.

[tpsiaki, 2015/08/11 18:33:27]

Done.

+    bucket_start_time_ += bucket_milliseconds_;
+    current_bucket_ = (current_bucket_ + 1u) % (interval_buckets_ + 1u);
+    unit_buckets_[current_bucket_] = 0u;
+  }
+  // Add all units in the bucket that includes the current time.
+  unit_buckets_[current_bucket_] += units;
+}
+
+uint32 BucketRateTracker::Time() const {
+  return rtc::Time();
+}
+
+void BucketRateTracker::EnsureInitialized() {
+  if (bucket_start_time_ == ~0u) {
+    initialization_time_ = Time();
+    bucket_start_time_ = initialization_time_;
+    current_bucket_ = 0u;
+    // We only need to initialize the first bucket because we reset buckets when
+    // current_bucket_ increments.
+    unit_buckets_[current_bucket_] = 0u;
+  }
+}
+
+}  // namespace rtc