OLD | NEW |
1 /* | 1 /* |
2 * Copyright (c) 2013 The WebRTC project authors. All Rights Reserved. | 2 * Copyright (c) 2013 The WebRTC project authors. All Rights Reserved. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license | 4 * Use of this source code is governed by a BSD-style license |
5 * that can be found in the LICENSE file in the root of the source | 5 * that can be found in the LICENSE file in the root of the source |
6 * tree. An additional intellectual property rights grant can be found | 6 * tree. An additional intellectual property rights grant can be found |
7 * in the file PATENTS. All contributing project authors may | 7 * in the file PATENTS. All contributing project authors may |
8 * be found in the AUTHORS file in the root of the source tree. | 8 * be found in the AUTHORS file in the root of the source tree. |
9 */ | 9 */ |
10 | 10 |
11 #include "webrtc/base/rate_statistics.h" | 11 #include "webrtc/base/rate_statistics.h" |
12 | 12 |
13 #include <algorithm> | 13 #include <algorithm> |
14 | 14 |
15 #include "webrtc/base/checks.h" | 15 #include "webrtc/base/checks.h" |
16 | 16 |
17 namespace webrtc { | 17 namespace webrtc { |
18 | 18 |
19 RateStatistics::RateStatistics(uint32_t window_size_ms, float scale) | 19 RateStatistics::RateStatistics(int64_t window_size_ms, float scale) |
20 : num_buckets_(window_size_ms + 1), // N ms in (N+1) buckets. | 20 : buckets_(new Bucket[window_size_ms]()), |
21 buckets_(new size_t[num_buckets_]()), | |
22 accumulated_count_(0), | 21 accumulated_count_(0), |
23 oldest_time_(0), | 22 num_samples_(0), |
| 23 oldest_time_(-window_size_ms), |
24 oldest_index_(0), | 24 oldest_index_(0), |
25 scale_(scale) {} | 25 scale_(scale), |
| 26 max_window_size_ms_(window_size_ms), |
| 27 current_window_size_ms_(max_window_size_ms_) {} |
26 | 28 |
27 RateStatistics::~RateStatistics() {} | 29 RateStatistics::~RateStatistics() {} |
28 | 30 |
29 void RateStatistics::Reset() { | 31 void RateStatistics::Reset() { |
30 accumulated_count_ = 0; | 32 accumulated_count_ = 0; |
31 oldest_time_ = 0; | 33 num_samples_ = 0; |
| 34 oldest_time_ = -max_window_size_ms_; |
32 oldest_index_ = 0; | 35 oldest_index_ = 0; |
33 for (int i = 0; i < num_buckets_; i++) { | 36 current_window_size_ms_ = max_window_size_ms_; |
34 buckets_[i] = 0; | 37 for (int64_t i = 0; i < max_window_size_ms_; i++) |
35 } | 38 buckets_[i] = Bucket(); |
36 } | 39 } |
37 | 40 |
38 void RateStatistics::Update(size_t count, int64_t now_ms) { | 41 void RateStatistics::Update(size_t count, int64_t now_ms) { |
39 if (now_ms < oldest_time_) { | 42 if (now_ms < oldest_time_) { |
40 // Too old data is ignored. | 43 // Too old data is ignored. |
41 return; | 44 return; |
42 } | 45 } |
43 | 46 |
44 EraseOld(now_ms); | 47 EraseOld(now_ms); |
45 | 48 |
46 int now_offset = static_cast<int>(now_ms - oldest_time_); | 49 // First ever sample, reset window to start now. |
47 RTC_DCHECK_LT(now_offset, num_buckets_); | 50 if (!IsInitialized()) |
48 int index = oldest_index_ + now_offset; | 51 oldest_time_ = now_ms; |
49 if (index >= num_buckets_) { | 52 |
50 index -= num_buckets_; | 53 uint32_t now_offset = static_cast<uint32_t>(now_ms - oldest_time_); |
51 } | 54 RTC_DCHECK_LT(now_offset, max_window_size_ms_); |
52 buckets_[index] += count; | 55 uint32_t index = oldest_index_ + now_offset; |
| 56 if (index >= max_window_size_ms_) |
| 57 index -= max_window_size_ms_; |
| 58 buckets_[index].sum += count; |
| 59 ++buckets_[index].samples; |
53 accumulated_count_ += count; | 60 accumulated_count_ += count; |
| 61 ++num_samples_; |
54 } | 62 } |
55 | 63 |
56 uint32_t RateStatistics::Rate(int64_t now_ms) { | 64 rtc::Optional<uint32_t> RateStatistics::Rate(int64_t now_ms) { |
57 EraseOld(now_ms); | 65 EraseOld(now_ms); |
58 float scale = scale_ / (now_ms - oldest_time_ + 1); | 66 |
59 return static_cast<uint32_t>(accumulated_count_ * scale + 0.5f); | 67 // If window is a single bucket or there is only one sample in a data set that |
| 68 // has not grown to the full window size, treat this as rate unavailable. |
| 69 int64_t active_window_size = now_ms - oldest_time_ + 1; |
| 70 if (num_samples_ == 0 || active_window_size <= 1 || |
| 71 (num_samples_ <= 1 && active_window_size < current_window_size_ms_)) { |
| 72 return rtc::Optional<uint32_t>(); |
| 73 } |
| 74 |
| 75 float scale = scale_ / active_window_size; |
| 76 return rtc::Optional<uint32_t>( |
| 77 static_cast<uint32_t>(accumulated_count_ * scale + 0.5f)); |
60 } | 78 } |
61 | 79 |
62 void RateStatistics::EraseOld(int64_t now_ms) { | 80 void RateStatistics::EraseOld(int64_t now_ms) { |
63 int64_t new_oldest_time = now_ms - num_buckets_ + 1; | 81 if (!IsInitialized()) |
64 if (new_oldest_time <= oldest_time_) { | |
65 if (accumulated_count_ == 0) | |
66 oldest_time_ = now_ms; | |
67 return; | 82 return; |
68 } | 83 |
69 while (oldest_time_ < new_oldest_time) { | 84 // New oldest time that is included in data set. |
70 size_t count_in_oldest_bucket = buckets_[oldest_index_]; | 85 int64_t new_oldest_time = now_ms - current_window_size_ms_ + 1; |
71 RTC_DCHECK_GE(accumulated_count_, count_in_oldest_bucket); | 86 |
72 accumulated_count_ -= count_in_oldest_bucket; | 87 // New oldest time is older than the current one, no need to cull data. |
73 buckets_[oldest_index_] = 0; | 88 if (new_oldest_time <= oldest_time_) |
74 if (++oldest_index_ >= num_buckets_) { | 89 return; |
| 90 |
| 91 // Loop over buckets and remove too old data points. |
| 92 while (num_samples_ > 0 && oldest_time_ < new_oldest_time) { |
| 93 const Bucket& oldest_bucket = buckets_[oldest_index_]; |
| 94 RTC_DCHECK_GE(accumulated_count_, oldest_bucket.sum); |
| 95 RTC_DCHECK_GE(num_samples_, oldest_bucket.samples); |
| 96 accumulated_count_ -= oldest_bucket.sum; |
| 97 num_samples_ -= oldest_bucket.samples; |
| 98 buckets_[oldest_index_] = Bucket(); |
| 99 if (++oldest_index_ >= max_window_size_ms_) |
75 oldest_index_ = 0; | 100 oldest_index_ = 0; |
76 } | |
77 ++oldest_time_; | 101 ++oldest_time_; |
78 if (accumulated_count_ == 0) { | |
79 // This guarantees we go through all the buckets at most once, even if | |
80 // |new_oldest_time| is far greater than |oldest_time_|. | |
81 new_oldest_time = now_ms; | |
82 break; | |
83 } | |
84 } | 102 } |
85 oldest_time_ = new_oldest_time; | 103 oldest_time_ = new_oldest_time; |
86 } | 104 } |
87 | 105 |
| 106 bool RateStatistics::SetWindowSize(int64_t window_size_ms, int64_t now_ms) { |
| 107 if (window_size_ms <= 0 || window_size_ms > max_window_size_ms_) |
| 108 return false; |
| 109 |
| 110 current_window_size_ms_ = window_size_ms; |
| 111 EraseOld(now_ms); |
| 112 return true; |
| 113 } |
| 114 |
| 115 bool RateStatistics::IsInitialized() { |
| 116 return oldest_time_ != -max_window_size_ms_; |
| 117 } |
| 118 |
88 } // namespace webrtc | 119 } // namespace webrtc |
OLD | NEW |