Oilpan: Implement marking time estimation

Oilpan: Implement marking time estimation

Oilpan schedules GC as idleTask in the Blink scheduler.
When idle, the Blink scheduler notifies Oilpan with a "deadline" timestamp,
and let the idleTask client (Oilpan) decide whether to proceed with
processing the task, or skip processing the task as it may take beyond
the "deadline".

Before this CL, Oilpan idleTask handler didn't implement this decision properly,
and always proceeded with a GC assuming the GC would take 0 ms.
This CL implements a heuristics so that Oilpan GC would only proceed when
it is assumed to finish within the given "deadline".

This CL implements a heuristics assuming that GC would take a linear time
O(N_live_objs). The number of live objects is estimated by taking the ratio of
heap size increase since last gc.

BUG=420515
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=192397

[kouhei (in TOK), 2015-03-02 03:05:19]

kouhei@chromium.org changed reviewers:
+ oilpan-reviews@chromium.org

[haraken, 2015-03-02 04:49:41]

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

[haraken, 2015-03-02 04:49:42]

LGTM

https://codereview.chromium.org/965283002/diff/1/Source/platform/heap/Heap.cpp
File Source/platform/heap/Heap.cpp (right):

https://codereview.chromium.org/965283002/diff/1/Source/platform/heap/Heap.cp...
Source/platform/heap/Heap.cpp:2204: s_recentMarkingTime = 0.0;

s_recentMarkingTime => s_markingTimeInLastGC

https://codereview.chromium.org/965283002/diff/1/Source/platform/heap/Heap.cp...
Source/platform/heap/Heap.cpp:2637: estimatedObjectCountIncreaseRatio =
(Heap::allocatedObjectSize() + Heap::markedObjectSize()) *
ThreadState::mainThreadState()->collectionRate() / Heap::markedObjectSize();

I'd prefer to add ASSERT(isMainThread()) at the top of the function and use
ThreadState::current() here, to indicate that we currently support only the main
thread but want to support other threads in the future.

https://codereview.chromium.org/965283002/diff/1/Source/platform/heap/Heap.cp...
Source/platform/heap/Heap.cpp:2637: estimatedObjectCountIncreaseRatio =
(Heap::allocatedObjectSize() + Heap::markedObjectSize()) *
ThreadState::mainThreadState()->collectionRate() / Heap::markedObjectSize();

Can you fprintf estimatedObjectCountIncreaseRatio and see if you're getting a
reasonable value in various benchmarks before landing this CL? I think your
heuristics make sense but want to confirm that it's actually working as
expected.

[kouhei (in TOK), 2015-03-03 04:45:08]

https://codereview.chromium.org/965283002/diff/1/Source/platform/heap/Heap.cpp
File Source/platform/heap/Heap.cpp (right):

https://codereview.chromium.org/965283002/diff/1/Source/platform/heap/Heap.cp...
Source/platform/heap/Heap.cpp:2204: s_recentMarkingTime = 0.0;
On 2015/03/02 04:49:41, haraken wrote:
> 
> s_recentMarkingTime => s_markingTimeInLastGC

Done.

https://codereview.chromium.org/965283002/diff/1/Source/platform/heap/Heap.cp...
Source/platform/heap/Heap.cpp:2637: estimatedObjectCountIncreaseRatio =
(Heap::allocatedObjectSize() + Heap::markedObjectSize()) *
ThreadState::mainThreadState()->collectionRate() / Heap::markedObjectSize();
On 2015/03/02 04:49:41, haraken wrote:
> 
> I'd prefer to add ASSERT(isMainThread()) at the top of the function and use
> ThreadState::current() here, to indicate that we currently support only the
main
> thread but want to support other threads in the future.

Done.

https://codereview.chromium.org/965283002/diff/1/Source/platform/heap/Heap.cp...
Source/platform/heap/Heap.cpp:2637: estimatedObjectCountIncreaseRatio =
(Heap::allocatedObjectSize() + Heap::markedObjectSize()) *
ThreadState::mainThreadState()->collectionRate() / Heap::markedObjectSize();
On 2015/03/02 04:49:41, haraken wrote:
> 
> Can you fprintf estimatedObjectCountIncreaseRatio and see if you're getting a
> reasonable value in various benchmarks before landing this CL? I think your
> heuristics make sense but want to confirm that it's actually working as
> expected.

Tested locally visiting some real world websites.
Estimate seems to work well while loading (max off by 25%-ish).
However, after page load (e.g. object created as response to user action), it
varies on the website and sometimes off by 200% (too conservative on the
estimate).

Imo the current one is good enough to start experiment with, and let me improve
the metric progressively.

[kouhei (in TOK), 2015-03-03 04:46:58]

+scheduler-dev fyi

[Sami, 2015-03-03 12:25:18]

skyostil@chromium.org changed reviewers:
+ rmcilroy@chromium.org, skyostil@chromium.org

[Sami, 2015-03-03 12:25:19]

+rmcilroy

https://codereview.chromium.org/965283002/diff/40001/Source/platform/heap/Hea...
File Source/platform/heap/Heap.cpp (right):

https://codereview.chromium.org/965283002/diff/40001/Source/platform/heap/Hea...
Source/platform/heap/Heap.cpp:2641: return s_markingTimeInLastGC *
estimatedObjectCountIncreaseRatio;
Do you find that this function returns stable values or is there lots of
variation in s_markingTimeInLastGC? I'm wondering if s_markingTimeInLastGC
should be updated with some kind of easing function to filter out the noise.

[rmcilroy, 2015-03-03 12:36:44]

On 2015/03/03 04:46:58, kouhei wrote:
> +scheduler-dev fyi

Looks great.  

One thing we may want to do is always do the idle GC task if we are scheduled
with the longest possible idle deadline which the scheduler would ever provide
irrespective of how long we think the GC would take.  The reasoning being that
it would be better to do the GC during this long idle period than it would at
any other time even if it ends up going over the deadline.  I've uploaded a CL
which adds this support at https://codereview.chromium.org/971283002/.

[rmcilroy, 2015-03-03 12:49:13]

https://codereview.chromium.org/965283002/diff/40001/Source/platform/heap/Hea...
File Source/platform/heap/Heap.cpp (right):

https://codereview.chromium.org/965283002/diff/40001/Source/platform/heap/Hea...
Source/platform/heap/Heap.cpp:2641: return s_markingTimeInLastGC *
estimatedObjectCountIncreaseRatio;
On 2015/03/03 12:25:19, Sami wrote:
> Do you find that this function returns stable values or is there lots of
> variation in s_markingTimeInLastGC? I'm wondering if s_markingTimeInLastGC
> should be updated with some kind of easing function to filter out the noise.

I would be interested in this too.

[kouhei (in TOK), 2015-03-23 05:18:18]

On 2015/03/03 12:49:13, rmcilroy wrote:
>
https://codereview.chromium.org/965283002/diff/40001/Source/platform/heap/Hea...
> File Source/platform/heap/Heap.cpp (right):
> 
>
https://codereview.chromium.org/965283002/diff/40001/Source/platform/heap/Hea...
> Source/platform/heap/Heap.cpp:2641: return s_markingTimeInLastGC *
> estimatedObjectCountIncreaseRatio;
> On 2015/03/03 12:25:19, Sami wrote:
> > Do you find that this function returns stable values or is there lots of
> > variation in s_markingTimeInLastGC? I'm wondering if s_markingTimeInLastGC
> > should be updated with some kind of easing function to filter out the noise.
> 
> I would be interested in this too.

Here are some plots for idletime budget and {estimated,actual} marking time:
https://docs.google.com/document/d/110kkxHW7s1rKMfYY4DJZV9vXHYmGEP1zfeSI4bTBB...

[haraken, 2015-03-23 05:32:09]

On 2015/03/23 05:18:18, kouhei wrote:
> On 2015/03/03 12:49:13, rmcilroy wrote:
> >
>
https://codereview.chromium.org/965283002/diff/40001/Source/platform/heap/Hea...
> > File Source/platform/heap/Heap.cpp (right):
> > 
> >
>
https://codereview.chromium.org/965283002/diff/40001/Source/platform/heap/Hea...
> > Source/platform/heap/Heap.cpp:2641: return s_markingTimeInLastGC *
> > estimatedObjectCountIncreaseRatio;
> > On 2015/03/03 12:25:19, Sami wrote:
> > > Do you find that this function returns stable values or is there lots of
> > > variation in s_markingTimeInLastGC? I'm wondering if s_markingTimeInLastGC
> > > should be updated with some kind of easing function to filter out the
noise.
> > 
> > I would be interested in this too.
> 
> Here are some plots for idletime budget and {estimated,actual} marking time:
>
https://docs.google.com/document/d/110kkxHW7s1rKMfYY4DJZV9vXHYmGEP1zfeSI4bTBB...

Looks like the estimation is working well. LGTM on my side.

[rmcilroy, 2015-03-23 12:33:34]

On 2015/03/23 05:32:09, haraken wrote:
> On 2015/03/23 05:18:18, kouhei wrote:
> > On 2015/03/03 12:49:13, rmcilroy wrote:
> > >
> >
>
https://codereview.chromium.org/965283002/diff/40001/Source/platform/heap/Hea...
> > > File Source/platform/heap/Heap.cpp (right):
> > > 
> > >
> >
>
https://codereview.chromium.org/965283002/diff/40001/Source/platform/heap/Hea...
> > > Source/platform/heap/Heap.cpp:2641: return s_markingTimeInLastGC *
> > > estimatedObjectCountIncreaseRatio;
> > > On 2015/03/03 12:25:19, Sami wrote:
> > > > Do you find that this function returns stable values or is there lots of
> > > > variation in s_markingTimeInLastGC? I'm wondering if
s_markingTimeInLastGC
> > > > should be updated with some kind of easing function to filter out the
> noise.
> > > 
> > > I would be interested in this too.
> > 
> > Here are some plots for idletime budget and {estimated,actual} marking time:
> >
>
https://docs.google.com/document/d/110kkxHW7s1rKMfYY4DJZV9vXHYmGEP1zfeSI4bTBB...
> 
> Looks like the estimation is working well. LGTM on my side.

Nice, lgtm. Thanks for the analysis!

[kouhei (in TOK), 2015-03-24 01:17:27]

The CQ bit was checked by kouhei@chromium.org

[commit-bot: I haz the power, 2015-03-24 01:17:39]

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

[commit-bot: I haz the power, 2015-03-24 01:21:17]

Committed patchset #4 (id:60001) as
https://src.chromium.org/viewvc/blink?view=rev&revision=192397