FeedbackSignalAccumulator utility class for averaging feedback signals

FeedbackSignalAccumulator utility class for averaging feedback signals

This provides the implementation and tests to maintain an
exponentially-decaying average of feedback signal values.  This will
be used in soon-upcoming changes that will allow screen capture to
auto-adapt the frame resolution and frame rate to the user's
environment.

BUG=156767
Committed: https://crrev.com/4b12889a5d7000febb4b2efc2ad21fc99d6604ca
Cr-Commit-Position: refs/heads/master@{#329537}

[miu, 2015-04-25 03:28:53]

miu@chromium.org changed reviewers:
+ hubbe@chromium.org

[miu, 2015-04-25 03:28:54]

hubbe: PTAL.

[hubbe, 2015-04-27 20:50:42]

Will look at implementation next go around.

https://codereview.chromium.org/1097633005/diff/1/content/browser/media/captu...
File content/browser/media/capture/time_weighted_average.h (right):

https://codereview.chromium.org/1097633005/diff/1/content/browser/media/captu...
content/browser/media/capture/time_weighted_average.h:13: // Utility class for
maintaining an time-weighted moving average value of a
I think time-weighted might be an accurate but confusing way to explain what
this class does. It might be better to just say that it handles irregular
updates correctly.

https://codereview.chromium.org/1097633005/diff/1/content/browser/media/captu...
content/browser/media/capture/time_weighted_average.h:14: // metric value.
It doesn't work with imperial values? :)

https://codereview.chromium.org/1097633005/diff/1/content/browser/media/captu...
content/browser/media/capture/time_weighted_average.h:24: explicit
TimeWeightedAverage(base::TimeDelta time_constant);
maybe call time_constant half_life instead?
Although, I'm confused, does this implement a moving average (windowed) or an
exponential decay function?

If this is a windowed average, then perhaps call it "window_time"?

https://codereview.chromium.org/1097633005/diff/1/content/browser/media/captu...
content/browser/media/capture/time_weighted_average.h:32: // |timestamp|.  If
the timestamp was no more than one step out-of-order, the
Wait, what's a step?

https://codereview.chromium.org/1097633005/diff/1/content/browser/media/captu...
content/browser/media/capture/time_weighted_average.h:46: bool
was_recently_updated(base::TimeTicks now) const {
This seems like an odd function
I think "recent" needs to be decoupled from the decay rate.

https://codereview.chromium.org/1097633005/diff/1/content/browser/media/captu...
content/browser/media/capture/time_weighted_average.h:49: base::TimeDelta
elapsed_since_reset() const {
This also seems like an odd function.
From the name, I would have thought it would return TimeTicks::Now() -
last_reset_time().  If no updates have been given in a while, then this function
starts to lie...

[miu, 2015-05-05 04:56:59]

Responded to your first round comments.  Made a number of naming and comment
changes to clarify things.  PTAL.

https://codereview.chromium.org/1097633005/diff/1/content/browser/media/captu...
File content/browser/media/capture/time_weighted_average.h (right):

https://codereview.chromium.org/1097633005/diff/1/content/browser/media/captu...
content/browser/media/capture/time_weighted_average.h:13: // Utility class for
maintaining an time-weighted moving average value of a
On 2015/04/27 20:50:42, hubbe wrote:
> I think time-weighted might be an accurate but confusing way to explain what
> this class does. It might be better to just say that it handles irregular
> updates correctly.

Done.

https://codereview.chromium.org/1097633005/diff/1/content/browser/media/captu...
content/browser/media/capture/time_weighted_average.h:14: // metric value.
On 2015/04/27 20:50:42, hubbe wrote:
> It doesn't work with imperial values? :)

Done.

https://codereview.chromium.org/1097633005/diff/1/content/browser/media/captu...
content/browser/media/capture/time_weighted_average.h:24: explicit
TimeWeightedAverage(base::TimeDelta time_constant);
On 2015/04/27 20:50:42, hubbe wrote:
> maybe call time_constant half_life instead?
> Although, I'm confused, does this implement a moving average (windowed) or an
> exponential decay function?
> 
> If this is a windowed average, then perhaps call it "window_time"?

Done.  Yeah, half_life is a great name for this!  :)

Adjusted comments to eliminate "window" wordings.

https://codereview.chromium.org/1097633005/diff/1/content/browser/media/captu...
content/browser/media/capture/time_weighted_average.h:32: // |timestamp|.  If
the timestamp was no more than one step out-of-order, the
On 2015/04/27 20:50:42, hubbe wrote:
> Wait, what's a step?

Done.  Explained this further in class-level comment, and changed wording here
to be "one step out of chronological order" for clarity.

https://codereview.chromium.org/1097633005/diff/1/content/browser/media/captu...
content/browser/media/capture/time_weighted_average.h:46: bool
was_recently_updated(base::TimeTicks now) const {
On 2015/04/27 20:50:42, hubbe wrote:
> This seems like an odd function
> I think "recent" needs to be decoupled from the decay rate.

I got rid of this one.  I may or may not introduce along with code that uses it
in a later CL, with a more-proper name.

https://codereview.chromium.org/1097633005/diff/1/content/browser/media/captu...
content/browser/media/capture/time_weighted_average.h:49: base::TimeDelta
elapsed_since_reset() const {
On 2015/04/27 20:50:42, hubbe wrote:
> This also seems like an odd function.
> From the name, I would have thought it would return TimeTicks::Now() -
> last_reset_time().  If no updates have been given in a while, then this
function
> starts to lie...

Removed this one too.  I may or may not introduce along with code that uses it
in a later CL, with a more-proper name.

[hubbe, 2015-05-06 17:54:49]

https://codereview.chromium.org/1097633005/diff/20001/content/browser/media/c...
File content/browser/media/capture/time_weighted_average.cc (right):

https://codereview.chromium.org/1097633005/diff/20001/content/browser/media/c...
content/browser/media/capture/time_weighted_average.cc:43:
Undo(most_recent_value_,
May I suggest that it might be easier to keep the internal state in a struct and
then have a "previous_state_" that you can revert to.

Even easier: Ignore out-of-order timestamps completely.

I think the behavior of this class is a little weird, because the amount of
allowed out-of-order-ness depends on the data I've given it recently. It seems
like the behavior would be more well defined if the amount of allowed
out-of-order-ness was purely time based, or if it wasn't allowed at all.

If I'm reading this code right, it also means that

   Update(5, t=1.0);
   Update(10, t=1.0+eps);

behave very differently from

   Update(10, t=1.0);
   Update(5, t=1.0+eps);

which seems odd.

https://codereview.chromium.org/1097633005/diff/20001/content/browser/media/c...
File content/browser/media/capture/time_weighted_average.h (right):

https://codereview.chromium.org/1097633005/diff/20001/content/browser/media/c...
content/browser/media/capture/time_weighted_average.h:15: // chronological
order.  If updates occur more than one stop out-of-sequence,
"one stop"
How much is that?
Is the "step size" related to half_life, or is it 1.0?

It seems odd for this class to care about chronological order.
Without knowing what the use case looks like, I would think that a DCHECK()
would be a better way to handle out-of-order values.

https://codereview.chromium.org/1097633005/diff/20001/content/browser/media/c...
content/browser/media/capture/time_weighted_average.h:28: explicit
TimeWeightedAverage(base::TimeDelta half_life);
Actually, half_life might not be the right name, because it implies decay.
(Which I thought this class was doing last time I read this file.)

I'm not sure if there is a better name though. Maybe crossover time or something
could work...

https://codereview.chromium.org/1097633005/diff/20001/content/browser/media/c...
content/browser/media/capture/time_weighted_average.h:40: // Two or more updates
at the same |timestamp| will have their values
This kind of seems like an odd thing to do. Does this mean that

   Update(5, t=1.0);
   Update(10, t=1.0);

will affect the output differently from:

  Update(5, t=1.0);
  Update(10, t=1.0+epsilon);

?

Or will they do the same thing?
(If they do the same thing, this comment is redundant.)

https://codereview.chromium.org/1097633005/diff/20001/content/browser/media/c...
content/browser/media/capture/time_weighted_average.h:58: const base::TimeDelta
half_life_;
These variables needs comments too.
In particular, I have no idea what most_recent_count_ does.

[miu, 2015-05-09 22:08:21]

Okay, reworked it all as we discussed.  PTAL.

https://codereview.chromium.org/1097633005/diff/20001/content/browser/media/c...
File content/browser/media/capture/time_weighted_average.cc (right):

https://codereview.chromium.org/1097633005/diff/20001/content/browser/media/c...
content/browser/media/capture/time_weighted_average.cc:43:
Undo(most_recent_value_,
On 2015/05/06 17:54:49, hubbe wrote:
> Even easier: Ignore out-of-order timestamps completely.

As discussed face-to-face, I removed all the out-of-order foo.

https://codereview.chromium.org/1097633005/diff/20001/content/browser/media/c...
File content/browser/media/capture/time_weighted_average.h (right):

https://codereview.chromium.org/1097633005/diff/20001/content/browser/media/c...
content/browser/media/capture/time_weighted_average.h:15: // chronological
order.  If updates occur more than one stop out-of-sequence,
On 2015/05/06 17:54:49, hubbe wrote:
> "one stop"
> How much is that?
> Is the "step size" related to half_life, or is it 1.0?
> 
> It seems odd for this class to care about chronological order.
> Without knowing what the use case looks like, I would think that a DCHECK()
> would be a better way to handle out-of-order values.

As discussed face-to-face, I removed all the out-of-order foo.

https://codereview.chromium.org/1097633005/diff/20001/content/browser/media/c...
content/browser/media/capture/time_weighted_average.h:28: explicit
TimeWeightedAverage(base::TimeDelta half_life);
On 2015/05/06 17:54:49, hubbe wrote:
> Actually, half_life might not be the right name, because it implies decay.
> (Which I thought this class was doing last time I read this file.)
> 
> I'm not sure if there is a better name though. Maybe crossover time or
something
> could work...

IMO, it works really well.  It's describing the half-life of its "memory" of
prior updates.

https://codereview.chromium.org/1097633005/diff/20001/content/browser/media/c...
content/browser/media/capture/time_weighted_average.h:40: // Two or more updates
at the same |timestamp| will have their values
On 2015/05/06 17:54:49, hubbe wrote:
> This kind of seems like an odd thing to do. Does this mean that

As discussed face-to-face, I really don't want to take the arithmetic average of
all values at the same timestamp.  Instead, I want the max.  This made the code
much simpler, and was the right thing to do.

https://codereview.chromium.org/1097633005/diff/20001/content/browser/media/c...
content/browser/media/capture/time_weighted_average.h:58: const base::TimeDelta
half_life_;
On 2015/05/06 17:54:49, hubbe wrote:
> These variables needs comments too.
> In particular, I have no idea what most_recent_count_ does.

Done.

[hubbe, 2015-05-12 19:10:07]

https://codereview.chromium.org/1097633005/diff/40001/content/browser/media/c...
File content/browser/media/capture/feedback_signal_accumulator.cc (right):

https://codereview.chromium.org/1097633005/diff/40001/content/browser/media/c...
content/browser/media/capture/feedback_signal_accumulator.cc:41: prior_average_
= average_;
Make prior_average_ and prior_update_time_ local variables?

https://codereview.chromium.org/1097633005/diff/40001/content/browser/media/c...
File content/browser/media/capture/feedback_signal_accumulator.h (right):

https://codereview.chromium.org/1097633005/diff/40001/content/browser/media/c...
content/browser/media/capture/feedback_signal_accumulator.h:36: // |timestamp|,
only the one with the greatest value will be accounted for.
Document why "greatest value" makes sense.

[miu, 2015-05-12 20:58:37]

https://codereview.chromium.org/1097633005/diff/40001/content/browser/media/c...
File content/browser/media/capture/feedback_signal_accumulator.cc (right):

https://codereview.chromium.org/1097633005/diff/40001/content/browser/media/c...
content/browser/media/capture/feedback_signal_accumulator.cc:41: prior_average_
= average_;
On 2015/05/12 19:10:07, hubbe wrote:
> Make prior_average_ and prior_update_time_ local variables?

I can't.  They're needed for the timestamp == update_time_ case where the
average_ needs to be recomputed with the new, larger value for the same
timestamp.

https://codereview.chromium.org/1097633005/diff/40001/content/browser/media/c...
File content/browser/media/capture/feedback_signal_accumulator.h (right):

https://codereview.chromium.org/1097633005/diff/40001/content/browser/media/c...
content/browser/media/capture/feedback_signal_accumulator.h:36: // |timestamp|,
only the one with the greatest value will be accounted for.
On 2015/05/12 19:10:07, hubbe wrote:
> Document why "greatest value" makes sense.

Done.  (Documented at class-level comments.)

[hubbe, 2015-05-13 00:04:17]

lgtm

[miu, 2015-05-13 00:05:23]

The CQ bit was checked by miu@chromium.org

[commit-bot: I haz the power, 2015-05-13 00:05:49]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1097633005/60001

[commit-bot: I haz the power, 2015-05-13 00:12:22]

Committed patchset #4 (id:60001)

[commit-bot: I haz the power, 2015-05-13 00:14:10]

Patchset 4 (id:??) landed as
https://crrev.com/4b12889a5d7000febb4b2efc2ad21fc99d6604ca
Cr-Commit-Position: refs/heads/master@{#329537}