Estimate draw duration in SchedulerClient

Estimate draw duration in SchedulerClient

This adds a DrawDurationEstimate method to SchedulerClient. The
implementation of this method (in ThreadProxy) produces an
estimate based on recent draw times.

This also adds UMA stats measuring the duration of each draw and
the amount by which this duration is underestimated or
overestimated.

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

[ajuma, 2013-06-06 18:00:34]

PTAL.

The constants defined here will need tweaking (once we figure out what works
best).

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

https://chromiumcodereview.appspot.com/16574002/diff/1/cc/scheduler/scheduler...
cc/scheduler/scheduler.h:47: virtual base::TimeDelta DrawDurationEstimate() = 0;
I'm adding this to SchedulerClient rather than to Scheduler since we eventually
want to include GPU process execution time in the estimate, and plumbing this to
the SchedulerClient (that is, to ThreadProxy) makes more sense than plumbing it
directly to Scheduler.

https://chromiumcodereview.appspot.com/16574002/diff/1/cc/trees/thread_proxy.cc
File cc/trees/thread_proxy.cc (right):

https://chromiumcodereview.appspot.com/16574002/diff/1/cc/trees/thread_proxy....
cc/trees/thread_proxy.cc:31: const size_t kDrawDurationHistorySize = 60;
We might actually want something smaller than this since we sometimes have brief
bursts of really expensive draws (e.g. 15ms rather than 1 or 2 ms), and we
wouldn't want the effects of these expensive draws to linger in our estimates
for too long.

https://chromiumcodereview.appspot.com/16574002/diff/1/cc/trees/thread_proxy....
cc/trees/thread_proxy.cc:33: const int
kDrawDurationEstimatePaddingInMicroseconds = 0;
The padding serves 2 purposes: First, by using appropriate padding, we might be
able to use percentile smaller than 100 (without causing us to underestimate too
often), which would avoid having a single expensive outlier frame bias our
estimates. Second, we can incorporate an estimate for GPU execution time into
the padding (if we'll be using a hard-coded value of GPU latency for the first
version of this).

[Tom Hudson, 2013-06-06 18:27:46]

I thought we'd dropped the idea of estimating draw costs.
Do we have a use for it?

It'd be cheaper (no need for history buffer) to use something like an
exponentially weighted moving average, which is pretty common in this kind of
application in my experience. Is there a reason you're using the explicitly
bounded window?

[Tom Hudson, 2013-06-06 18:31:36]

On 2013/06/06 18:27:46, Tom Hudson wrote:
> I thought we'd dropped the idea of estimating draw costs.
> Do we have a use for it?
> 
> It'd be cheaper (no need for history buffer) to use something like an
> exponentially weighted moving average, which is pretty common in this kind of
> application in my experience. Is there a reason you're using the explicitly
> bounded window?

Following the bug gave me context, so if the deadline-based scheduler works then
this has a use, and my question reduces to just why not use a simpler
implementation.

[ajuma, 2013-06-06 18:39:02]

On 2013/06/06 18:31:36, Tom Hudson wrote:
> On 2013/06/06 18:27:46, Tom Hudson wrote:
> > I thought we'd dropped the idea of estimating draw costs.
> > Do we have a use for it?
> > 
> > It'd be cheaper (no need for history buffer) to use something like an
> > exponentially weighted moving average, which is pretty common in this kind
of
> > application in my experience. Is there a reason you're using the explicitly
> > bounded window?
> 
> Following the bug gave me context, so if the deadline-based scheduler works
then
> this has a use, and my question reduces to just why not use a simpler
> implementation.

There is a huge penalty for underestimating the cost (we miss the deadline and
drop a frame). So, for example, using a median would be terrible, since we would
underestimate half the time. A moving average would suffer from the same sort of
problem. We really want something more like "what is the most expensive frame
we've had recently".

[Tom Hudson, 2013-06-07 10:08:43]

On 2013/06/06 18:39:02, ajuma wrote:
> There is a huge penalty for underestimating the cost (we miss the deadline and
> drop a frame). So, for example, using a median would be terrible, since we
would
> underestimate half the time. A moving average would suffer from the same sort
of
> problem. We really want something more like "what is the most expensive frame
> we've had recently".

I guess this gets back to my distrust of the deadline-based scheduler, then.
If the penalty for underestimating is huge, is there any reason to think that
this can be remotely accurate? Costs that I've seen look highly noisy, and there
are times when they also look highly uncorrelated. Working sets are >> 60 tiles
on highdpi devices during page load, zoom, or fling. Do we have any statistics
that suggest my intuition is wrong?

We gave up on predicting the cost of the draw by examining its components
(because of cost and inaccuracy), and I don't see how this can be more accurate
if we're really requiring a very high standard of accuracy.

[ajuma, 2013-06-11 17:10:57]

PTAL.

I've added UMA histograms measuring the duration of each draw and measuring the
amount by which we're underestimating or overestimating. These will help us
evaluate and tune the estimation algorithm.

[brianderson, 2013-06-12 00:59:44]

lgtm if you make replace the UMA over/underestimate with a single difference
value.

https://codereview.chromium.org/16574002/diff/9001/cc/trees/thread_proxy.cc
File cc/trees/thread_proxy.cc (right):

https://codereview.chromium.org/16574002/diff/9001/cc/trees/thread_proxy.cc#n...
cc/trees/thread_proxy.cc:985: base::TimeDelta draw_duration_underestimate;
Instead of having over/underestimate, can we just take the difference and report
that as a single number? TimeDelta is allowed to be negative.

[ajuma, 2013-06-12 01:18:11]

https://codereview.chromium.org/16574002/diff/9001/cc/trees/thread_proxy.cc
File cc/trees/thread_proxy.cc (right):

https://codereview.chromium.org/16574002/diff/9001/cc/trees/thread_proxy.cc#n...
cc/trees/thread_proxy.cc:985: base::TimeDelta draw_duration_underestimate;
On 2013/06/12 00:59:44, Brian Anderson wrote:
> Instead of having over/underestimate, can we just take the difference and
report
> that as a single number? TimeDelta is allowed to be negative.

We need two different numbers here since UMA histograms don't support
negative-valued buckets.

[brianderson, 2013-06-12 18:01:28]

On 2013/06/12 01:18:11, ajuma wrote:
> https://codereview.chromium.org/16574002/diff/9001/cc/trees/thread_proxy.cc
> File cc/trees/thread_proxy.cc (right):
> 
>
https://codereview.chromium.org/16574002/diff/9001/cc/trees/thread_proxy.cc#n...
> cc/trees/thread_proxy.cc:985: base::TimeDelta draw_duration_underestimate;
> On 2013/06/12 00:59:44, Brian Anderson wrote:
> > Instead of having over/underestimate, can we just take the difference and
> report
> > that as a single number? TimeDelta is allowed to be negative.
> 
> We need two different numbers here since UMA histograms don't support
> negative-valued buckets.

lgtm then.

[ajuma, 2013-06-12 18:05:52]

+jar for tools/metrics/ OWNERS.

[jar (doing other things), 2013-06-12 19:09:37]

https://chromiumcodereview.appspot.com/16574002/diff/9001/tools/metrics/histo...
File tools/metrics/histograms/histograms.xml (right):

https://chromiumcodereview.appspot.com/16574002/diff/9001/tools/metrics/histo...
tools/metrics/histograms/histograms.xml:8618: The amout by which the
compositor's draw duration was overestimated in a
amout-->amount

https://chromiumcodereview.appspot.com/16574002/diff/9001/tools/metrics/histo...
tools/metrics/histograms/histograms.xml:8625: The amount by which the
compositor's draw duration was underestimated in a
Can you also explain when a sample is added?  For instance, do you always add a
sample to at least 2 out of 3 of these... and when the prediction is perfect...
do you add a sample to all 3??

[ajuma, 2013-06-12 19:28:52]

https://chromiumcodereview.appspot.com/16574002/diff/9001/tools/metrics/histo...
File tools/metrics/histograms/histograms.xml (right):

https://chromiumcodereview.appspot.com/16574002/diff/9001/tools/metrics/histo...
tools/metrics/histograms/histograms.xml:8618: The amout by which the
compositor's draw duration was overestimated in a
On 2013/06/12 19:09:38, jar wrote:
> amout-->amount

Fixed.

https://chromiumcodereview.appspot.com/16574002/diff/9001/tools/metrics/histo...
tools/metrics/histograms/histograms.xml:8625: The amount by which the
compositor's draw duration was underestimated in a
On 2013/06/12 19:09:38, jar wrote:
> Can you also explain when a sample is added?  For instance, do you always add
a
> sample to at least 2 out of 3 of these... and when the prediction is
perfect...
> do you add a sample to all 3??

We always add a sample to all 3 (e.g. adding a sample of 0 to
DrawDurationUnderestimate when the prediction is perfect or actually an
overestimate). I've updated the descriptions.

[ajuma, 2013-06-14 20:28:47]

On 2013/06/12 19:28:52, ajuma wrote:
>
https://chromiumcodereview.appspot.com/16574002/diff/9001/tools/metrics/histo...
> File tools/metrics/histograms/histograms.xml (right):
> 
>
https://chromiumcodereview.appspot.com/16574002/diff/9001/tools/metrics/histo...
> tools/metrics/histograms/histograms.xml:8618: The amout by which the
> compositor's draw duration was overestimated in a
> On 2013/06/12 19:09:38, jar wrote:
> > amout-->amount
> 
> Fixed.
> 
>
https://chromiumcodereview.appspot.com/16574002/diff/9001/tools/metrics/histo...
> tools/metrics/histograms/histograms.xml:8625: The amount by which the
> compositor's draw duration was underestimated in a
> On 2013/06/12 19:09:38, jar wrote:
> > Can you also explain when a sample is added?  For instance, do you always
add
> a
> > sample to at least 2 out of 3 of these... and when the prediction is
> perfect...
> > do you add a sample to all 3??
> 
> We always add a sample to all 3 (e.g. adding a sample of 0 to
> DrawDurationUnderestimate when the prediction is perfect or actually an
> overestimate). I've updated the descriptions.

jar@, PTAL.

[jar (doing other things), 2013-06-15 17:56:04]

histograms.xml LGTM

[commit-bot: I haz the power, 2013-06-15 20:39:01]

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

[commit-bot: I haz the power, 2013-06-16 03:07:01]

Change committed as 206624