Start incremental marking on idle notification.

Start incremental marking on idle notification.


BUG=v8:1458
TEST=cctest/test-api/IdleNotification*

Committed: http://code.google.com/p/v8/source/detail?r=10093

[ulan, 2011-11-10 12:38:26]

This CL uses idle notifications to make kMaxIdleCount incremental GC cycles and
then to wait until the mutator creates more garbage. 

A GC cycle consists of:
1. many incremental marking steps,
2. one old space mark-sweep-compact,
3. many lazy sweep steps.

It works well with low-frequency idle notifications (>100ms) and is needed for
this CL http://codereview.chromium.org/8519001/ which sends idle notifications
when the user is idle. 

High-frequency idle notifications can be enabled by tweaking the constants and
heuristics, but first we need to land these two CLs without performance
regression.

[Erik Corry, 2011-11-10 15:06:55]

http://codereview.chromium.org/8519002/diff/1/src/heap.cc
File src/heap.cc (right):

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode518
src/heap.cc:518: !idle_notification_will_schedule_next_gc()) {
I think if the heuristics say we need to start a GC then we should start a GC. 
Expecting the idle notification to schedule a GC is not reliable, because the
idle notifications may not arrive.

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4465
src/heap.cc:4465: bool Heap::IdleNotification() {
A comment here to say what the return value means would be helpful.

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4475
src/heap.cc:4475: // wait until the mutator creates more garbage.
"Creates more garbage" is rather vague.  If this means that a certain number of
scavenges have taken place then we should write that.

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4480
src/heap.cc:4480: // The counters from IdleGlobalGC are reused, but have
different meaning:
This seems unnecessarily complicated.  Counters are not expensive, lets give
them just one meaning.

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4481
src/heap.cc:4481: // - number_idle_notifications_ counts the GC cycles.
I do not like the phrase "GC cycles".  If we use the following phrases it is
clearer:

Scavenge
Full GC
Incremental GC (always full)
Nonincremental GC (always full)

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4497
src/heap.cc:4497: // Speed up if idle notifications are rare.
Time-based things make debugging difficult, and in this case I cannot see that
it makes sense.  We should not try to autodetect the version of Chrome based on
the interval between the idle notifications, which is what this looks like.

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4503
src/heap.cc:4503: !old_pointer_space()->IsSweepingComplete()) {
It is a little dangerous to name individual spaces here.  If we later have
another space that is swept lazily then we will have to remember to update this
place.

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4520
src/heap.cc:4520: incremental_marking()->Step(step_size);
It seems that we do a step without checking that we are currently in the middle
of incremental marking?

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4526
src/heap.cc:4526: isolate_->compilation_cache()->Clear();
We seem to be duplicating a lot of the logic of incremental GC here.  Clearing
specific caches, but leaving others alone, and calling CollectAllGarbage in
order to finish the incremental GC.  Can we factor that out into a common
routine with the other place(s) where we discover that incremental GC is nearly
done?

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4540
src/heap.cc:4540: return !WorthStartingGCWhenIdle() &&
If it is worth starting, should we not just start it, then the next line would
take care of this situation?

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4542
src/heap.cc:4542: old_data_space()->IsSweepingComplete() &&
Listing the lazily swept pages is fragile.

http://codereview.chromium.org/8519002/diff/1/src/heap.h
File src/heap.h (right):

http://codereview.chromium.org/8519002/diff/1/src/heap.h#newcode1804
src/heap.h:1804: static const int kMaxIdleCount = kIdlesBeforeMarkCompact + 1;
The name kMaxIdleCount no longer makes much sense.  Can't we get any more idle
notifications than this, and why not?

http://codereview.chromium.org/8519002/diff/1/src/heap.h#newcode1805
src/heap.h:1805: static const unsigned int kGCsBetweenCleanup = 4;
I suggest kScavengesBeforeFullGC for this one.

http://codereview.chromium.org/8519002/diff/1/src/incremental-marking.h
File src/incremental-marking.h (right):

http://codereview.chromium.org/8519002/diff/1/src/incremental-marking.h#newco...
src/incremental-marking.h:103: static const intptr_t kStepFakeAllocatedBytes =
kAllocatedThreshold * 3;
This is rather ugly.  Instead of lying to the Step function about how much
memory has been allocated, we should create a step function that takes a number
of bytes to scan, and then we should call that from the old Step function.

[ulan, 2011-11-11 13:27:26]

Please take another look.

Addressed comments, added a new "hint" argument, gave descriptive names to the
counters and predicates, simplified logic.

http://codereview.chromium.org/8519002/diff/1/src/heap.cc
File src/heap.cc (right):

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode518
src/heap.cc:518: !idle_notification_will_schedule_next_gc()) {
On 2011/11/10 15:06:55, Erik Corry wrote:
> I think if the heuristics say we need to start a GC then we should start a GC.

> Expecting the idle notification to schedule a GC is not reliable, because the
> idle notifications may not arrive.
Removed the flag.

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4465
src/heap.cc:4465: bool Heap::IdleNotification() {
On 2011/11/10 15:06:55, Erik Corry wrote:
> A comment here to say what the return value means would be helpful.
This function is documented in V8 API. Added a comment saying that in header
file.

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4475
src/heap.cc:4475: // wait until the mutator creates more garbage.
On 2011/11/10 15:06:55, Erik Corry wrote:
> "Creates more garbage" is rather vague.  If this means that a certain number
of
> scavenges have taken place then we should write that.
Rephrased it to "enough garbage to justify a new round". Extracted this
condition into a separate predicate function.

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4480
src/heap.cc:4480: // The counters from IdleGlobalGC are reused, but have
different meaning:
On 2011/11/10 15:06:55, Erik Corry wrote:
> This seems unnecessarily complicated.  Counters are not expensive, lets give
> them just one meaning.

Done.

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4481
src/heap.cc:4481: // - number_idle_notifications_ counts the GC cycles.
On 2011/11/10 15:06:55, Erik Corry wrote:
> I do not like the phrase "GC cycles".  If we use the following phrases it is
> clearer:
> 
> Scavenge
> Full GC
> Incremental GC (always full)
> Nonincremental GC (always full)

Done.

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4497
src/heap.cc:4497: // Speed up if idle notifications are rare.
On 2011/11/10 15:06:55, Erik Corry wrote:
> Time-based things make debugging difficult, and in this case I cannot see that
> it makes sense.  We should not try to autodetect the version of Chrome based
on
> the interval between the idle notifications, which is what this looks like.
As discussed offline, added a "hint" argument to IdleNotification and now using
it to compute the right size.

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4503
src/heap.cc:4503: !old_pointer_space()->IsSweepingComplete()) {
On 2011/11/10 15:06:55, Erik Corry wrote:
> It is a little dangerous to name individual spaces here.  If we later have
> another space that is swept lazily then we will have to remember to update
this
> place.

Done.

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4520
src/heap.cc:4520: incremental_marking()->Step(step_size);
On 2011/11/10 15:06:55, Erik Corry wrote:
> It seems that we do a step without checking that we are currently in the
middle
> of incremental marking?
Line 4513 starts marking if it is not started already.

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4526
src/heap.cc:4526: isolate_->compilation_cache()->Clear();
On 2011/11/10 15:06:55, Erik Corry wrote:
> We seem to be duplicating a lot of the logic of incremental GC here.  Clearing
> specific caches, but leaving others alone, and calling CollectAllGarbage in
> order to finish the incremental GC.  Can we factor that out into a common
> routine with the other place(s) where we discover that incremental GC is
nearly
> done?
We do it in LowMemoryNotification and in old version of IdleNotification, but
they are not related to incremental marking.

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4540
src/heap.cc:4540: return !WorthStartingGCWhenIdle() &&
On 2011/11/10 15:06:55, Erik Corry wrote:
> If it is worth starting, should we not just start it, then the next line would
> take care of this situation?
Now I am simply returning false, so the next notification will check the
conditions properly and start marking if needed.

http://codereview.chromium.org/8519002/diff/1/src/heap.cc#newcode4542
src/heap.cc:4542: old_data_space()->IsSweepingComplete() &&
On 2011/11/10 15:06:55, Erik Corry wrote:
> Listing the lazily swept pages is fragile.

Done.

http://codereview.chromium.org/8519002/diff/1/src/heap.h
File src/heap.h (right):

http://codereview.chromium.org/8519002/diff/1/src/heap.h#newcode1804
src/heap.h:1804: static const int kMaxIdleCount = kIdlesBeforeMarkCompact + 1;
On 2011/11/10 15:06:55, Erik Corry wrote:
> The name kMaxIdleCount no longer makes much sense.  Can't we get any more idle
> notifications than this, and why not?
Now I don't use this constant in the new IdleNotification.

http://codereview.chromium.org/8519002/diff/1/src/heap.h#newcode1805
src/heap.h:1805: static const unsigned int kGCsBetweenCleanup = 4;
On 2011/11/10 15:06:55, Erik Corry wrote:
> I suggest kScavengesBeforeFullGC for this one.
Ditto.

http://codereview.chromium.org/8519002/diff/1/src/incremental-marking.h
File src/incremental-marking.h (right):

http://codereview.chromium.org/8519002/diff/1/src/incremental-marking.h#newco...
src/incremental-marking.h:103: static const intptr_t kStepFakeAllocatedBytes =
kAllocatedThreshold * 3;
On 2011/11/10 15:06:55, Erik Corry wrote:
> This is rather ugly.  Instead of lying to the Step function about how much
> memory has been allocated, we should create a step function that takes a
number
> of bytes to scan, and then we should call that from the old Step function.
Removed this completely, because the size is now computed using the hint
argument of the IdleNotification.

http://codereview.chromium.org/8519002/diff/5001/src/heap.h
File src/heap.h (right):

http://codereview.chromium.org/8519002/diff/5001/src/heap.h#newcode1781
src/heap.h:1781: return (gc_count_ - gc_count_when_last_idle_round_finished_ >
4);
We agreed to count only scavenges here, but for that I need to add another
counter and code to maintain the counter. Since full GC are rare anyway, I think
gc_count_ is good enough until we add much better counters like "promoted bytes
since last full GC".

[Erik Corry, 2011-11-14 23:05:17]

http://codereview.chromium.org/8519002/diff/5001/src/heap.h
File src/heap.h (right):

http://codereview.chromium.org/8519002/diff/5001/src/heap.h#newcode1781
src/heap.h:1781: return (gc_count_ - gc_count_when_last_idle_round_finished_ >
4);
On 2011/11/11 13:27:26, ulan wrote:
> We agreed to count only scavenges here, but for that I need to add another
> counter and code to maintain the counter. Since full GC are rare anyway, I
think
> gc_count_ is good enough until we add much better counters like "promoted
bytes
> since last full GC".

I really think we should just add the extra counter here.  It's only about 3
lines.  You are counting scavenges to decide to do a full GC.  If you count full
GCs too then you risk a situation where a full GC contributes to the decision to
do another full GC.  That sounds like the sort of positive feedback that should
be avoided on principle.

[ulan, 2011-11-15 09:08:43]

Please take another look, added scavenges_since_last_full_gc_ counter.

http://codereview.chromium.org/8519002/diff/5001/src/heap.h
File src/heap.h (right):

http://codereview.chromium.org/8519002/diff/5001/src/heap.h#newcode1781
src/heap.h:1781: return (gc_count_ - gc_count_when_last_idle_round_finished_ >
4);
On 2011/11/14 23:05:17, Erik Corry wrote:
> On 2011/11/11 13:27:26, ulan wrote:
> > We agreed to count only scavenges here, but for that I need to add another
> > counter and code to maintain the counter. Since full GC are rare anyway, I
> think
> > gc_count_ is good enough until we add much better counters like "promoted
> bytes
> > since last full GC".
> 
> I really think we should just add the extra counter here.  It's only about 3
> lines.  You are counting scavenges to decide to do a full GC.  If you count
full
> GCs too then you risk a situation where a full GC contributes to the decision
to
> do another full GC.  That sounds like the sort of positive feedback that
should
> be avoided on principle.

Done.

[Erik Corry, 2011-11-22 12:29:26]

LGTM

http://codereview.chromium.org/8519002/diff/9002/src/heap.cc
File src/heap.cc (right):

http://codereview.chromium.org/8519002/diff/9002/src/heap.cc#newcode4497
src/heap.cc:4497: if (mark_sweeps_since_idle_round_started_ >=
kMaxMarkSweepsInIdleRound) {
This test is also included in WorthStartingGCWhenIdle.  Do we need it both
places?

http://codereview.chromium.org/8519002/diff/9002/src/heap.cc#newcode4499
src/heap.cc:4499: return true;
If sweeping is not complete we should not return here.

http://codereview.chromium.org/8519002/diff/9002/src/heap.cc#newcode4524
src/heap.cc:4524: if (gc_count_at_last_idle_gc_ == gc_count_) {
It would be nice with a comment that explained the thinking behind this
condition.

http://codereview.chromium.org/8519002/diff/9002/test/cctest/test-heap.cc
File test/cctest/test-heap.cc (right):

http://codereview.chromium.org/8519002/diff/9002/test/cctest/test-heap.cc#new...
test/cctest/test-heap.cc:1320: CHECK(new_size < old_size);
I think we need more testing.  There should be a test that makes sure we use the
hint argument, eg. a loop that keeps calling with a hint of 10 and checks that
we eventually finish GCing.

[ulan, 2011-11-23 16:18:06]

Addressed comments and tuned heuristics for starting and finishing the idle
round.

Could you please take another look?

http://codereview.chromium.org/8519002/diff/9002/src/heap.cc
File src/heap.cc (right):

http://codereview.chromium.org/8519002/diff/9002/src/heap.cc#newcode4497
src/heap.cc:4497: if (mark_sweeps_since_idle_round_started_ >=
kMaxMarkSweepsInIdleRound) {
On 2011/11/22 12:29:26, Erik Corry wrote:
> This test is also included in WorthStartingGCWhenIdle.  Do we need it both
> places?
Removed the test from WorthStartingGCWhenIdle.

http://codereview.chromium.org/8519002/diff/9002/src/heap.cc#newcode4499
src/heap.cc:4499: return true;
On 2011/11/22 12:29:26, Erik Corry wrote:
> If sweeping is not complete we should not return here.
Moved the sweeping steps up.

http://codereview.chromium.org/8519002/diff/9002/src/heap.cc#newcode4524
src/heap.cc:4524: if (gc_count_at_last_idle_gc_ == gc_count_) {
On 2011/11/22 12:29:26, Erik Corry wrote:
> It would be nice with a comment that explained the thinking behind this
> condition.

Done.

http://codereview.chromium.org/8519002/diff/16001/src/heap.cc
File src/heap.cc (right):

http://codereview.chromium.org/8519002/diff/16001/src/heap.cc#newcode150
src/heap.cc:150: scavenges_since_last_idle_round_(kIdleScavengeThreshold),
The initial value allows to start the idle round on the first idle notification.

http://codereview.chromium.org/8519002/diff/16001/src/heap.cc#newcode4511
src/heap.cc:4511: if (hint < 1000 && !WorthStartingGCWhenIdle()) {
If hint >= 1000 then the embedder is asking us to do a lot of GC work. This
helps to reduce the memory usage in Chrome memory tests.

http://codereview.chromium.org/8519002/diff/16001/src/heap.h
File src/heap.h (right):

http://codereview.chromium.org/8519002/diff/16001/src/heap.h#newcode1781
src/heap.h:1781: return (scavenges_since_last_idle_round_ >=
kIdleScavengeThreshold);
The previous version would fail to start the idle round if there were many
scavenges followed by a full GC, which did not collect all garbage because of
weak external references. In this case another full GC could collect more
garbage.

[Erik Corry, 2011-11-25 09:21:30]

Still LGTM

http://codereview.chromium.org/8519002/diff/16001/test/cctest/test-api.cc
File test/cctest/test-api.cc (right):

http://codereview.chromium.org/8519002/diff/16001/test/cctest/test-api.cc#new...
test/cctest/test-api.cc:13430: }
Can we test that the heap is now much smaller?

http://codereview.chromium.org/8519002/diff/16001/test/cctest/test-heap.cc
File test/cctest/test-heap.cc (right):

http://codereview.chromium.org/8519002/diff/16001/test/cctest/test-heap.cc#ne...
test/cctest/test-heap.cc:1320: CHECK(new_size < old_size);
Can we tighten this assertion?   It should have collected a lot of memory by
this time.  Perhaps we can insist that it has collected half?