downloads: Improve download rate estimation.

content/browser/download/rate_estimator.cc

+// Copyright (c) 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "content/browser/download/rate_estimator.h"
+
+#include "base/logging.h"
+
+using base::TimeDelta;
+using base::TimeTicks;
+
+namespace content {
+
+namespace {
+
+static const int kDefaultBucketTimeSeconds = 1;
+static const size_t kDefaultNumBuckets = 10;
+
+} // namespace
+
+RateEstimator::RateEstimator()
+    : history_(kDefaultNumBuckets),
+      bucket_time_(TimeDelta::FromSeconds(kDefaultBucketTimeSeconds)),
+      oldest_index_(0),
+      bucket_count_(1) {
+  ResetBuckets(TimeTicks::Now());
+}
+
+RateEstimator::RateEstimator(TimeDelta bucket_time,
+                             size_t num_buckets,
+                             TimeTicks now)
+    : history_(num_buckets),
+      bucket_time_(bucket_time),
+      oldest_index_(0),
+      bucket_count_(1) {
+  DCHECK(bucket_time_.InSeconds() > 0);
+  ResetBuckets(now);
+}
+
+RateEstimator::~RateEstimator() {
+}
+
+void RateEstimator::Increment(uint32 count) {
+  Increment(count, TimeTicks::Now());
+}
+
+void RateEstimator::Increment(uint32 count, TimeTicks now) {
+  ClearOldBuckets(now);
+  int64 seconds_since_oldest = (now - oldest_time_).InSeconds();
+  DCHECK(seconds_since_oldest >= 0);
+  int64 delta_buckets = seconds_since_oldest / bucket_time_.InSeconds();
+  DCHECK(delta_buckets >= 0);
+  size_t index_offset = static_cast<size_t>(delta_buckets);
+  DCHECK(index_offset <= history_.size());
+  int current_index = (oldest_index_ + delta_buckets) % history_.size();
+  history_[current_index] += count;
+}
+
+uint64 RateEstimator::GetCountPerSecond() const {
+  return GetCountPerSecond(TimeTicks::Now());
+}
+
+uint64 RateEstimator::GetCountPerSecond(TimeTicks now) const {
+  const_cast<RateEstimator*>(this)->ClearOldBuckets(now);
+  // TODO(cbentzel): Support fractional seconds for active bucket?
+  // We explicitly don't check for overflow here. If it happens, unsigned
+  // arithmetic at least guarantees behavior by wrapping around. The estimate
+  // will be off, but the code will still be valid.
+  uint64 total_count = 0;
+  for (size_t i = 0; i < bucket_count_; ++i) {
+    size_t index = (oldest_index_ + i) % history_.size();
+    total_count += history_[index];
+  }
+  return total_count / (bucket_count_ * bucket_time_.InSeconds());
+}
+
+void RateEstimator::ClearOldBuckets(TimeTicks now) {
+  int64 seconds_since_oldest = (now - oldest_time_).InSeconds();
+
+  int64 delta_buckets = seconds_since_oldest / bucket_time_.InSeconds();
+
+  // It's possible (although unlikely) for there to be rollover with TimeTicks.
+  // If that's the case, just reset the history.
+  if (delta_buckets < 0) {
+    ResetBuckets(now);
+    return;
+  }
+  size_t delta_index = static_cast<size_t>(delta_buckets);
+
+  // If we are within the current window, keep the existing data.
+  if (delta_index < history_.size()) {
+    bucket_count_ = delta_index + 1;
+    return;
+  }
+
+  // If it's been long enough that all history data is too stale, just
+  // clearn all the buckets.

[asanka, 2013/05/16 22:23:10]

Nit: clear

+  size_t extra_buckets = delta_index - history_.size() + 1;
+  if (extra_buckets > history_.size()) {
+    ResetBuckets(now);
+    return;
+  }
+
+  // Clear out stale buckets in the history.
+  bucket_count_ = history_.size();
+  for (size_t i = 0; i < extra_buckets; ++i) {
+    history_[oldest_index_] = 0;
+    oldest_index_ = (oldest_index_ + 1) % history_.size();
+    oldest_time_ = oldest_time_ + bucket_time_;
+  }
+}
+
+void RateEstimator::ResetBuckets(TimeTicks now) {
+  for (size_t i = 0; i < history_.size(); ++i) {
+    history_[i] = 0;
+  }
+  oldest_index_ = 0;
+  bucket_count_ = 1;
+  oldest_time_ = now;
+}
+
+}  // namespace content