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

Add a rate tracker that tracks rate over a given interval split up into buckets that accumulate unit counts for their portion of said interval and use this instead of the standard rate tracker so that the values of retrieved frame rate stats are completely independent of the polling rate.

BUG=
R=asapersson@webrtc.org, noahric@chromium.org, pbos@webrtc.org, pthatcher@webrtc.org

Committed: https://crrev.com/6304626268238a074051910d201e9a77aae677e0
Cr-Commit-Position: refs/heads/master@{#9933}

[noahric, 2015-08-07 23:56:37]

noahric@chromium.org changed reviewers:
+ noahric@chromium.org

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

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
File webrtc/base/bucketratetracker.cc (right):

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
webrtc/base/bucketratetracker.cc:41: uint32 interval_milliseconds =
bucket_milliseconds_ * interval_buckets_;
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_);

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
webrtc/base/bucketratetracker.cc:49: uint32 time_to_skip = current_time -
bucket_start_time_;;
extra ;

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
webrtc/base/bucketratetracker.cc:67: size_t total_units =
unit_buckets_[start_bucket] *
Yeah, consider using "sample" as a substitute for "unit" throughout this file.

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
webrtc/base/bucketratetracker.cc:71: for (uint32 i = (start_bucket + 1) %
(interval_buckets_ + 1);
size_t for indices (throughout)

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
webrtc/base/bucketratetracker.cc:71: for (uint32 i = (start_bucket + 1) %
(interval_buckets_ + 1);
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)

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
webrtc/base/bucketratetracker.cc:86: while (current_time > bucket_start_time_ +
bucket_milliseconds_) {
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.

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
File webrtc/base/bucketratetracker.h (right):

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
webrtc/base/bucketratetracker.h:24: BucketRateTracker(uint32
bucket_milliseconds, uint32 interval_buckets);
maybe size_t bucket_count? (and bucket_count_)

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
webrtc/base/bucketratetracker.h:27: size_t units_second() const;
double? Also since this is simply returning a field, you should name it
something like ComputeCurrentRate. I wouldn't overly worry about matching
ratetracker.h, since I don't think that API is super obvious.

Another thing to consider is to have interval_buckets/bucket_count be
max_bucket_count, and then have this function take a time to return the rate
over. That way send stats proxy could set something like 15-30s, and then return
the full rate tracker when asked about stats (instead of just a number), and the
caller could decide how much of the history to use at any point.

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
webrtc/base/bucketratetracker.h:28: void Update(size_t units);
I know this matches RateTracker, but I feel like AddSample or something like
that would be more clear. Also a short comment, explaining that it uses the
current time.

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/video/send_statist...
File webrtc/video/send_statistics_proxy.cc (right):

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/video/send_statist...
webrtc/video/send_statistics_proxy.cc:25: const size_t
SendStatisticsProxy::kFrameRateTrackerInterval = 15u;
I think you'll want this to be configurable, since desired stats periods may
vary.

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

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
File webrtc/base/bucketratetracker.cc (right):

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
webrtc/base/bucketratetracker.cc:41: uint32 interval_milliseconds =
bucket_milliseconds_ * interval_buckets_;
On 2015/08/07 23:56:38, noahric wrote:
> 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_);

Done.

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
webrtc/base/bucketratetracker.cc:49: uint32 time_to_skip = current_time -
bucket_start_time_;;
On 2015/08/07 23:56:38, noahric wrote:
> extra ;

Done.

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
webrtc/base/bucketratetracker.cc:67: size_t total_units =
unit_buckets_[start_bucket] *
On 2015/08/07 23:56:38, noahric wrote:
> Yeah, consider using "sample" as a substitute for "unit" throughout this file.

Done.

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
webrtc/base/bucketratetracker.cc:71: for (uint32 i = (start_bucket + 1) %
(interval_buckets_ + 1);
On 2015/08/07 23:56:38, noahric wrote:
> size_t for indices (throughout)

Done.

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
webrtc/base/bucketratetracker.cc:71: for (uint32 i = (start_bucket + 1) %
(interval_buckets_ + 1);
On 2015/08/07 23:56:38, noahric wrote:
> 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)

Done.

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
webrtc/base/bucketratetracker.cc:86: while (current_time > bucket_start_time_ +
bucket_milliseconds_) {
On 2015/08/07 23:56:38, noahric wrote:
> 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.

Done.

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
File webrtc/base/bucketratetracker.h (right):

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
webrtc/base/bucketratetracker.h:24: BucketRateTracker(uint32
bucket_milliseconds, uint32 interval_buckets);
On 2015/08/07 23:56:38, noahric wrote:
> maybe size_t bucket_count? (and bucket_count_)

Done.

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
webrtc/base/bucketratetracker.h:27: size_t units_second() const;
On 2015/08/07 23:56:38, noahric wrote:
> double? Also since this is simply returning a field, you should name it
> something like ComputeCurrentRate. I wouldn't overly worry about matching
> ratetracker.h, since I don't think that API is super obvious.
> 
> Another thing to consider is to have interval_buckets/bucket_count be
> max_bucket_count, and then have this function take a time to return the rate
> over. That way send stats proxy could set something like 15-30s, and then
return
> the full rate tracker when asked about stats (instead of just a number), and
the
> caller could decide how much of the history to use at any point.

Done.

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/base/bucketratetra...
webrtc/base/bucketratetracker.h:28: void Update(size_t units);
On 2015/08/07 23:56:38, noahric wrote:
> I know this matches RateTracker, but I feel like AddSample or something like
> that would be more clear. Also a short comment, explaining that it uses the
> current time.

Done.

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/video/send_statist...
File webrtc/video/send_statistics_proxy.cc (right):

https://codereview.webrtc.org/1279433006/diff/40001/webrtc/video/send_statist...
webrtc/video/send_statistics_proxy.cc:25: const size_t
SendStatisticsProxy::kFrameRateTrackerInterval = 15u;
On 2015/08/07 23:56:38, noahric wrote:
> I think you'll want this to be configurable, since desired stats periods may
> vary.

I switched this to be based on the kStatsTimeoutMs setting for now since that's
the expiration time used for other statistics.  I'll look into where it might
make sense to add runtime configurability for this as well.

[tpsiaki, 2015-08-12 21:07:10]

tpsiaki@google.com changed reviewers:
+ perkj@webrtc.org

[tpsiaki, 2015-08-14 18:28:05]

tpsiaki@google.com changed reviewers:
+ pbos@webrtc.org
- perkj@webrtc.org

[tpsiaki, 2015-08-17 20:15:08]

tpsiaki@google.com changed reviewers:
+ pthatcher@webrtc.org

[tpsiaki, 2015-08-17 20:42:44]

tpsiaki@google.com changed reviewers:
+ juberti@webrtc.org

[mflodman, 2015-08-24 07:22:56]

mflodman@webrtc.org changed reviewers:
+ asapersson@webrtc.org

[pbos-webrtc, 2015-08-27 15:04:10]

Can you consolidate this into rtc::RateTracker? I think the get-and-reset case
should just be checking the last second. rtc::RateTracker is not used in that
many places right now, so I'd just make this new implementation "the"
rtc::RateTracker.

[åsapersson, 2015-08-28 08:12:47]

https://codereview.webrtc.org/1279433006/diff/100001/webrtc/video/send_statis...
File webrtc/video/send_statistics_proxy.cc (right):

https://codereview.webrtc.org/1279433006/diff/100001/webrtc/video/send_statis...
webrtc/video/send_statistics_proxy.cc:47: kFrameRateTrackerInterval * 1000u));
input_fps and sent_fps below are an average over the call (updated once when a
stream is destructed). These two stats are using an average since last
read/start.

[pbos-webrtc, 2015-08-28 12:47:55]

https://codereview.webrtc.org/1279433006/diff/100001/webrtc/video/send_statis...
File webrtc/video/send_statistics_proxy.cc (right):

https://codereview.webrtc.org/1279433006/diff/100001/webrtc/video/send_statis...
webrtc/video/send_statistics_proxy.cc:47: kFrameRateTrackerInterval * 1000u));
On 2015/08/28 08:12:47, åsapersson wrote:
> input_fps and sent_fps below are an average over the call (updated once when a
> stream is destructed). These two stats are using an average since last
> read/start.

Can you add support for a ComputeTotalRate() or something equivalent which'd
replace our need for units_second() in RateTracker? (We only pick the rate once,
so that's what we're using it for.)

[tpsiaki, 2015-09-01 20:59:17]

Replaced RateTracker with the BucketRateTracker version, added TotalSampleCount
and ComputeTotalRate functions to support all of the RateTracker functionality,
and updated consumers accordingly.

https://codereview.webrtc.org/1279433006/diff/100001/webrtc/video/send_statis...
File webrtc/video/send_statistics_proxy.cc (right):

https://codereview.webrtc.org/1279433006/diff/100001/webrtc/video/send_statis...
webrtc/video/send_statistics_proxy.cc:47: kFrameRateTrackerInterval * 1000u));
On 2015/08/28 12:47:55, pbos-webrtc wrote:
> On 2015/08/28 08:12:47, åsapersson wrote:
> > input_fps and sent_fps below are an average over the call (updated once when
a
> > stream is destructed). These two stats are using an average since last
> > read/start.
> 
> Can you add support for a ComputeTotalRate() or something equivalent which'd
> replace our need for units_second() in RateTracker? (We only pick the rate
once,
> so that's what we're using it for.)

Done.

[åsapersson, 2015-09-03 14:07:35]

On 2015/09/01 20:59:17, tpsiaki wrote:
> Replaced RateTracker with the BucketRateTracker version, added
TotalSampleCount
> and ComputeTotalRate functions to support all of the RateTracker
functionality,
> and updated consumers accordingly.
> 
>
https://codereview.webrtc.org/1279433006/diff/100001/webrtc/video/send_statis...
> File webrtc/video/send_statistics_proxy.cc (right):
> 
>
https://codereview.webrtc.org/1279433006/diff/100001/webrtc/video/send_statis...
> webrtc/video/send_statistics_proxy.cc:47: kFrameRateTrackerInterval * 1000u));
> On 2015/08/28 12:47:55, pbos-webrtc wrote:
> > On 2015/08/28 08:12:47, åsapersson wrote:
> > > input_fps and sent_fps below are an average over the call (updated once
when
> a
> > > stream is destructed). These two stats are using an average since last
> > > read/start.
> > 
> > Can you add support for a ComputeTotalRate() or something equivalent which'd
> > replace our need for units_second() in RateTracker? (We only pick the rate
> once,
> > so that's what we're using it for.)
> 
> Done.

webrtc/video/*_statistics_proxy.*: lgtm

[pbos-webrtc, 2015-09-03 15:03:10]

On 2015/09/03 14:07:35, åsapersson wrote:
> On 2015/09/01 20:59:17, tpsiaki wrote:
> > Replaced RateTracker with the BucketRateTracker version, added
> TotalSampleCount
> > and ComputeTotalRate functions to support all of the RateTracker
> functionality,
> > and updated consumers accordingly.
> > 
> >
>
https://codereview.webrtc.org/1279433006/diff/100001/webrtc/video/send_statis...
> > File webrtc/video/send_statistics_proxy.cc (right):
> > 
> >
>
https://codereview.webrtc.org/1279433006/diff/100001/webrtc/video/send_statis...
> > webrtc/video/send_statistics_proxy.cc:47: kFrameRateTrackerInterval *
1000u));
> > On 2015/08/28 12:47:55, pbos-webrtc wrote:
> > > On 2015/08/28 08:12:47, åsapersson wrote:
> > > > input_fps and sent_fps below are an average over the call (updated once
> when
> > a
> > > > stream is destructed). These two stats are using an average since last
> > > > read/start.
> > > 
> > > Can you add support for a ComputeTotalRate() or something equivalent
which'd
> > > replace our need for units_second() in RateTracker? (We only pick the rate
> > once,
> > > so that's what we're using it for.)
> > 
> > Done.
> 
> webrtc/video/*_statistics_proxy.*: lgtm

lgtm for webrtc/video/ as well, noahric@ can you take care of the bucket
implementation?

[tpsiaki, 2015-09-03 17:18:57]

On 2015/09/03 15:03:10, pbos-webrtc wrote:
> On 2015/09/03 14:07:35, åsapersson wrote:
> > On 2015/09/01 20:59:17, tpsiaki wrote:
> > > Replaced RateTracker with the BucketRateTracker version, added
> > TotalSampleCount
> > > and ComputeTotalRate functions to support all of the RateTracker
> > functionality,
> > > and updated consumers accordingly.
> > > 
> > >
> >
>
https://codereview.webrtc.org/1279433006/diff/100001/webrtc/video/send_statis...
> > > File webrtc/video/send_statistics_proxy.cc (right):
> > > 
> > >
> >
>
https://codereview.webrtc.org/1279433006/diff/100001/webrtc/video/send_statis...
> > > webrtc/video/send_statistics_proxy.cc:47: kFrameRateTrackerInterval *
> 1000u));
> > > On 2015/08/28 12:47:55, pbos-webrtc wrote:
> > > > On 2015/08/28 08:12:47, åsapersson wrote:
> > > > > input_fps and sent_fps below are an average over the call (updated
once
> > when
> > > a
> > > > > stream is destructed). These two stats are using an average since last
> > > > > read/start.
> > > > 
> > > > Can you add support for a ComputeTotalRate() or something equivalent
> which'd
> > > > replace our need for units_second() in RateTracker? (We only pick the
rate
> > > once,
> > > > so that's what we're using it for.)
> > > 
> > > Done.
> > 
> > webrtc/video/*_statistics_proxy.*: lgtm
> 
> lgtm for webrtc/video/ as well, noahric@ can you take care of the bucket
> implementation?

I had to make a couple of changes in p2p as well in order to replace
RateTracker.  pthatcher@ - can you have a look at those?

[noahric, 2015-09-03 21:42:24]

Overall LGTM, a few small comment changes and a few more unit tests requested.

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker.cc
File webrtc/base/ratetracker.cc (right):

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker....
webrtc/base/ratetracker.cc:14: #include <assert.h>
Use webrtc/base/checks.h and CHECK/DCHECK

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker....
webrtc/base/ratetracker.cc:93: if (current_time <= initialization_time_) {
Wraparound? You can use TimeIsLater and TimeDiff, maybe (in timeutils.h).

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker.h
File webrtc/base/ratetracker.h (right):

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker....
webrtc/base/ratetracker.h:28: double ComputeCurrentRate() const {
Use a different name for these; C++ style guide frowns on overloads. So maybe:
ComputeRateForInterval(uint32 interval_milliseconds)
ComputeRate()

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker....
webrtc/base/ratetracker.h:33: // Computes the average rate over the lifetime of
the rate tracker.
I'd replace "lifetime" with "since the first sample was added to the rate
tracker". Also add comments for both ComputeCurrentRate, especially to
distinguish the arg-less one from this method.

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker....
webrtc/base/ratetracker.h:56: uint32 bucket_start_time_;
Prefer these have units as well (millis, ms, or milliseconds).

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker_...
File webrtc/base/ratetracker_unittest.cc (right):

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker_...
webrtc/base/ratetracker_unittest.cc:36: EXPECT_EQ(30u,
tracker.ComputeCurrentRate(50000u));
Is there a version of this for doubles/floats that does equality comparison with
an epsilon?

I'm actually surprised this doesn't fail on windows trybots, which has
occasionally more strict signed/unsigned checking.

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker_...
webrtc/base/ratetracker_unittest.cc:114: EXPECT_EQ(0u,
tracker.ComputeCurrentRate(500u));
Can you also test (1) elapsed time > number of buckets and (2) more 
explicit roll-off testing, e.g. fill with 10fps, check 10fps; half-fill with
20fps (so half the 10 rolled off), check 15fps; half-fill rest of 20fps, check
20fps

Or, for (2) put another way, tests in which ComputeCurrentRate(arg) !=
ComputeCurrentRate().

[tpsiaki, 2015-09-03 23:28:59]

Thanks!

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker.cc
File webrtc/base/ratetracker.cc (right):

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker....
webrtc/base/ratetracker.cc:14: #include <assert.h>
On 2015/09/03 21:42:24, noahric wrote:
> Use webrtc/base/checks.h and CHECK/DCHECK

Done.

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker....
webrtc/base/ratetracker.cc:93: if (current_time <= initialization_time_) {
On 2015/09/03 21:42:24, noahric wrote:
> Wraparound? You can use TimeIsLater and TimeDiff, maybe (in timeutils.h).

Done.

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker.h
File webrtc/base/ratetracker.h (right):

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker....
webrtc/base/ratetracker.h:28: double ComputeCurrentRate() const {
On 2015/09/03 21:42:24, noahric wrote:
> Use a different name for these; C++ style guide frowns on overloads. So maybe:
> ComputeRateForInterval(uint32 interval_milliseconds)
> ComputeRate()

Done.

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker....
webrtc/base/ratetracker.h:33: // Computes the average rate over the lifetime of
the rate tracker.
On 2015/09/03 21:42:24, noahric wrote:
> I'd replace "lifetime" with "since the first sample was added to the rate
> tracker". Also add comments for both ComputeCurrentRate, especially to
> distinguish the arg-less one from this method.

Done.

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker....
webrtc/base/ratetracker.h:56: uint32 bucket_start_time_;
On 2015/09/03 21:42:24, noahric wrote:
> Prefer these have units as well (millis, ms, or milliseconds).

Done.

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker_...
File webrtc/base/ratetracker_unittest.cc (right):

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker_...
webrtc/base/ratetracker_unittest.cc:36: EXPECT_EQ(30u,
tracker.ComputeCurrentRate(50000u));
On 2015/09/03 21:42:24, noahric wrote:
> Is there a version of this for doubles/floats that does equality comparison
with
> an epsilon?
> 
> I'm actually surprised this doesn't fail on windows trybots, which has
> occasionally more strict signed/unsigned checking.

Done.

https://codereview.webrtc.org/1279433006/diff/180001/webrtc/base/ratetracker_...
webrtc/base/ratetracker_unittest.cc:114: EXPECT_EQ(0u,
tracker.ComputeCurrentRate(500u));
On 2015/09/03 21:42:24, noahric wrote:
> Can you also test (1) elapsed time > number of buckets and (2) more 
> explicit roll-off testing, e.g. fill with 10fps, check 10fps; half-fill with
> 20fps (so half the 10 rolled off), check 15fps; half-fill rest of 20fps, check
> 20fps
> 
> Or, for (2) put another way, tests in which ComputeCurrentRate(arg) !=
> ComputeCurrentRate().

Done.

[pthatcher1, 2015-09-14 17:16:41]

lgtm for p2p parts

[tpsiaki, 2015-09-14 17:38:26]

Committed patchset #11 (id:190001) manually as
6304626268238a074051910d201e9a77aae677e0 (presubmit successful).

[commit-bot: I haz the power, 2015-09-14 17:38:32]

Patchset 11 (id:??) landed as
https://crrev.com/6304626268238a074051910d201e9a77aae677e0
Cr-Commit-Position: refs/heads/master@{#9933}