Support computing percentiles on a rolling window of samples

Support computing percentiles on a rolling window of samples

This defines RollingTimeDeltaHistory, a class that stores a
limited number of samples (of type base::TimeDelta) and allows
computing percentiles on the stored set. When the maximum size
is reached, each insertion results in the deletion of the oldest
remaining sample.

BUG=243459
Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=203847

[ajuma, 2013-05-31 17:51:30]

PTAL.

This is intended to be used the scheduler to help estimate future compositing
times based on recent compositing times.

[brianderson, 2013-05-31 18:42:05]

https://chromiumcodereview.appspot.com/15647015/diff/1/cc/scheduler/rolling_s...
File cc/scheduler/rolling_sample_window.h (right):

https://chromiumcodereview.appspot.com/15647015/diff/1/cc/scheduler/rolling_s...
cc/scheduler/rolling_sample_window.h:18: class CC_EXPORT RollingSampleWindow {
If we are going to use a generic class name like this, should we make it a
template?

Otherwise, should we rename the class to something like RollingTimeDeltaWindow
or RollingTimeDeltaHistory?

https://chromiumcodereview.appspot.com/15647015/diff/1/cc/scheduler/rolling_s...
cc/scheduler/rolling_sample_window.h:36: std::list<TimeDeltaMultiset::iterator>
chronological_sample_list_;
Would a std::deque be more efficient? Once it reaches the max size, there
wouldn't have to be any more allocations. Also, a deque would require less
storage.

https://chromiumcodereview.appspot.com/15647015/diff/1/cc/scheduler/rolling_s...
File cc/scheduler/rolling_sample_window_unittest.cc (right):

https://chromiumcodereview.appspot.com/15647015/diff/1/cc/scheduler/rolling_s...
cc/scheduler/rolling_sample_window_unittest.cc:42: EXPECT_EQ(base::TimeDelta(),
size_one_window.Percentile(0.0));
Would it make sense for the 0th percentile to return the smallest value?

[ajuma, 2013-05-31 20:41:11]

https://codereview.chromium.org/15647015/diff/1/cc/scheduler/rolling_sample_w...
File cc/scheduler/rolling_sample_window.h (right):

https://codereview.chromium.org/15647015/diff/1/cc/scheduler/rolling_sample_w...
cc/scheduler/rolling_sample_window.h:18: class CC_EXPORT RollingSampleWindow {
On 2013/05/31 18:42:05, Brian Anderson wrote:
> If we are going to use a generic class name like this, should we make it a
> template?
> 
> Otherwise, should we rename the class to something like RollingTimeDeltaWindow
> or RollingTimeDeltaHistory?

Renamed to RollingTimeDeltaHistory.

https://codereview.chromium.org/15647015/diff/1/cc/scheduler/rolling_sample_w...
cc/scheduler/rolling_sample_window.h:36: std::list<TimeDeltaMultiset::iterator>
chronological_sample_list_;
On 2013/05/31 18:42:05, Brian Anderson wrote:
> Would a std::deque be more efficient? Once it reaches the max size, there
> wouldn't have to be any more allocations. Also, a deque would require less
> storage.

Changed to a deque.

https://codereview.chromium.org/15647015/diff/1/cc/scheduler/rolling_sample_w...
File cc/scheduler/rolling_sample_window_unittest.cc (right):

https://codereview.chromium.org/15647015/diff/1/cc/scheduler/rolling_sample_w...
cc/scheduler/rolling_sample_window_unittest.cc:42: EXPECT_EQ(base::TimeDelta(),
size_one_window.Percentile(0.0));
On 2013/05/31 18:42:05, Brian Anderson wrote:
> Would it make sense for the 0th percentile to return the smallest value?

My initial thought was for Percentile(X) to return the smallest value greater
than or equal to X% of the samples. In this case, the 0th percentile would be
base::TimeDelta() (since, after all, it is indeed greater than or equal to 0% of
the samples). But I agree that the smallest sample is a much more useful thing
for Percentile(0.0) to return, so I've changed Percentile to return the smallest
*sample* greater than or equal to X% of the samples (of course, with an
exception for the case of an empty history).

[ajuma, 2013-06-03 20:42:47]

PTAL.

[brianderson, 2013-06-03 22:51:26]

lgtm

[commit-bot: I haz the power, 2013-06-03 23:01:20]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/ajuma@chromium.org/15647015/6001

[commit-bot: I haz the power, 2013-06-03 23:11:25]

Step "update" is always a major failure.
Look at the try server FAQ for more details.
http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=mac&number...

[commit-bot: I haz the power, 2013-06-03 23:47:44]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/ajuma@chromium.org/15647015/6001

[commit-bot: I haz the power, 2013-06-04 04:33:52]

Change committed as 203847