Change halfway-to-the-max GC trigger to measure committed pages, not allocated objects

Change halfway-to-the-max GC trigger to measure committed pages, not allocated objects

This also adds a little more logging around how we decide to trigger GCs, and
it renames a predicate function that looked like a command.  This will trigger
more GCs when we are close to the limit, but if the incremental GCs are not
compacting then that may not help much.  However, that's a change that's being
dealt with in a different CL

R=hpayer@chromium.org,ulan@chromium.org
BUG=

[Hannes Payer (out of office), 2015-03-25 14:30:06]

a few nits

https://codereview.chromium.org/1038653003/diff/1/src/heap/heap.cc
File src/heap/heap.cc (right):

https://codereview.chromium.org/1038653003/diff/1/src/heap/heap.cc#newcode57
src/heap/heap.cc:57: static const intptr_t kDefaultMaxOldGenSize = 700ul *
(kPointerSize / 4) * MB;
Please define the constant next to the other heap size constants in heap.h

https://codereview.chromium.org/1038653003/diff/1/src/heap/heap.cc#newcode107
src/heap/heap.cc:107:
old_generation_committed_memory_limit_(kDefaultMaxOldGenSize >> 1),
why not set it to initial_old_generation_size_?

https://codereview.chromium.org/1038653003/diff/1/src/heap/heap.cc#newcode5270
src/heap/heap.cc:5270: if (FLAG_trace_gc) {
We may want to print that behind a different flag (also for the other flag uses
in this cl). The trace_gc output should be minimal.

https://codereview.chromium.org/1038653003/diff/1/src/heap/heap.h
File src/heap/heap.h (right):

https://codereview.chromium.org/1038653003/diff/1/src/heap/heap.h#newcode1249
src/heap/heap.h:1249: PrintF("Next GC will be full: We are at %" V8_PTR_PREFIX
... likely to be full

https://codereview.chromium.org/1038653003/diff/1/src/heap/heap.h#newcode1260
src/heap/heap.h:1260: PrintF("Next GC will be full: We are at %" V8_PTR_PREFIX
... likely to be full

[Erik Corry Chromium.org, 2015-03-25 15:16:07]

https://codereview.chromium.org/1038653003/diff/1/src/heap/heap.cc
File src/heap/heap.cc (right):

https://codereview.chromium.org/1038653003/diff/1/src/heap/heap.cc#newcode57
src/heap/heap.cc:57: static const intptr_t kDefaultMaxOldGenSize = 700ul *
(kPointerSize / 4) * MB;
On 2015/03/25 14:30:06, Hannes Payer wrote:
> Please define the constant next to the other heap size constants in heap.h

Done.

https://codereview.chromium.org/1038653003/diff/1/src/heap/heap.cc#newcode107
src/heap/heap.cc:107:
old_generation_committed_memory_limit_(kDefaultMaxOldGenSize >> 1),
On 2015/03/25 14:30:06, Hannes Payer wrote:
> why not set it to initial_old_generation_size_?

This is "halfway from here to the limit", which is what we use after a GC, too. 
I'm mainly interested in affecting the behaviour close to the max heap size
here, so I'm happy to have a high limit for the committed memory on startup.  If
I change the limits at startup I may perturb the benchmarks, which may lead to a
revert.

https://codereview.chromium.org/1038653003/diff/1/src/heap/heap.cc#newcode5270
src/heap/heap.cc:5270: if (FLAG_trace_gc) {
On 2015/03/25 14:30:05, Hannes Payer wrote:
> We may want to print that behind a different flag (also for the other flag
uses
> in this cl). The trace_gc output should be minimal.

I'd like to keep this one, but I put the other ones behind --trace-gc-verbose.

It looks like this:

...
[32021]      306 ms: Scavenge 107.8 (131.1) -> 97.1 (133.1) MB, 12.7 ms (+ 12.1
ms in 201 steps since last GC) [allocation failure].
[32021]      353 ms: Scavenge 120.8 (144.1) -> 110.2 (147.1) MB, 12.6 ms (+ 12.3
ms in 201 steps since last GC) [allocation failure].
[32021] Speed up marking because marker was not keeping up
[32021] Marking speed increased to 3
[32021]      456 ms: Next GC at 119.7 (121.3) -> 478.8 (760.7)
[32021]      456 ms: Mark-sweep 131.7 (157.1) -> 122.0 (159.1) MB, 52.8 ms (+
60.7 ms in 695 steps since start of marking, biggest step 0.3 ms) [GC interrupt]
[GC in old space requested].
[32021]      487 ms: Scavenge 146.2 (170.1) -> 135.3 (173.1) MB, 11.7 ms
[allocation failure].
[32021]      517 ms: Scavenge 158.9 (184.1) -> 148.3 (186.1) MB, 11.7 ms
[allocation failure].
...

https://codereview.chromium.org/1038653003/diff/1/src/heap/heap.h
File src/heap/heap.h (right):

https://codereview.chromium.org/1038653003/diff/1/src/heap/heap.h#newcode1249
src/heap/heap.h:1249: PrintF("Next GC will be full: We are at %" V8_PTR_PREFIX
On 2015/03/25 14:30:06, Hannes Payer wrote:
> ... likely to be full

Done.

https://codereview.chromium.org/1038653003/diff/1/src/heap/heap.h#newcode1260
src/heap/heap.h:1260: PrintF("Next GC will be full: We are at %" V8_PTR_PREFIX
On 2015/03/25 14:30:06, Hannes Payer wrote:
> ... likely to be full

Done.

[ulan, 2015-03-26 08:28:55]

https://codereview.chromium.org/1038653003/diff/60001/src/heap/heap.h
File src/heap/heap.h (right):

https://codereview.chromium.org/1038653003/diff/60001/src/heap/heap.h#newcode...
src/heap/heap.h:1348: inline bool OldGenerationAllocationLimitReached();
To be consistent, we need similar predicate for committed_memory_limit and check
it at every place we expand old space.

[Erik Corry Chromium.org, 2015-04-06 14:00:53]

I added checks for committed-memory-limit in
OldGenerationAllocationLimitReached.  This is called to decide between old and
new space GCs and before tenured old space allocations but it's not consulted
during evacuations, when we are in an always-allocate scope.

I'm not going to check this when expanding the heap, which typically happens
during GC (evacuation of new space or fragmented pages).

This is the right thing because the new limit is intentionally set below the max
heap size (halfway to the max).  It's a soft limit that is intended to trigger a
GC before we expand the heap to that level.  If I make this new low limit a hard
limit, we will need a new soft limit that is lower to trigger GC before we hit
this new low hard limit.

Added test which causes a lot of fragmentation.  It has 20Mbytes of live data
(on 32 bit) but still used to fail with a 70Mbyte committed old space memory
limit. Now it can cope with 40Mbytes, again, on 32bit.

[Erik Corry Chromium.org, 2015-04-06 14:20:38]

The CQ bit was checked by erikcorry@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2015-04-06 14:20:51]

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

[commit-bot: I haz the power, 2015-04-06 14:24:42]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-04-06 14:24:43]

Try jobs failed on following builders:
  v8_presubmit on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_presubmit/builds/1728)

[Erik Corry Chromium.org, 2015-04-06 15:07:00]

The CQ bit was checked by erikcorry@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2015-04-06 15:07:13]

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

[commit-bot: I haz the power, 2015-04-06 15:10:44]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-04-06 15:10:45]

Try jobs failed on following builders:
  v8_presubmit on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_presubmit/builds/1732)

[ulan, 2015-04-07 13:27:19]

https://codereview.chromium.org/1038653003/diff/120001/src/heap/heap.cc
File src/heap/heap.cc (right):

https://codereview.chromium.org/1038653003/diff/120001/src/heap/heap.cc#newco...
src/heap/heap.cc:5274: old_generation_allocation_limit_ = limit +
new_space_.Capacity();
Should we enforce that old_generation_allocation_limit_ <
old_generation_committed_memory_limit_ ?

https://codereview.chromium.org/1038653003/diff/120001/src/heap/heap.cc#newco...
src/heap/heap.cc:5282: intptr_t commit_limit_basis = old_gen_size;
This can lead to never-ending GCs even if fragmentation is moderate.
Example:
max_old_generation_size = 1400
old_gen_size = 800
committed = 1101

This will immediately start another GC and there is no guarantee "committed"
will decrease.

I think commit_limit_basis should always be CommittedOldGenerationMemory().

[Erik Corry Chromium.org, 2015-04-08 11:57:31]

The CQ bit was checked by erikcorry@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2015-04-08 11:57:46]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1038653003/140001

[Erik Corry Chromium.org, 2015-04-08 12:07:48]

The CQ bit was checked by erikcorry@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2015-04-08 12:08:03]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1038653003/160001

[commit-bot: I haz the power, 2015-04-08 12:17:05]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-04-08 12:17:06]

Try jobs failed on following builders:
  v8_presubmit on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_presubmit/builds/1788)

[Erik Corry Chromium.org, 2015-04-09 12:26:16]

The try job failed because of the issue fixed in
https://codereview.chromium.org/1078533003/ PTAL

https://codereview.chromium.org/1038653003/diff/120001/src/heap/heap.cc
File src/heap/heap.cc (right):

https://codereview.chromium.org/1038653003/diff/120001/src/heap/heap.cc#newco...
src/heap/heap.cc:5274: old_generation_allocation_limit_ = limit +
new_space_.Capacity();
On 2015/04/07 13:27:19, ulan wrote:
> Should we enforce that old_generation_allocation_limit_ <
> old_generation_committed_memory_limit_ ?

I think since we consult both, it is clearer to let them be independent.

https://codereview.chromium.org/1038653003/diff/120001/src/heap/heap.cc#newco...
src/heap/heap.cc:5282: intptr_t commit_limit_basis = old_gen_size;
On 2015/04/07 13:27:19, ulan wrote:
> This can lead to never-ending GCs even if fragmentation is moderate.
> Example:
> max_old_generation_size = 1400
> old_gen_size = 800
> committed = 1101
> 
> This will immediately start another GC and there is no guarantee "committed"
> will decrease.
> 
> I think commit_limit_basis should always be CommittedOldGenerationMemory().

Done.

[Erik Corry Chromium.org, 2015-04-09 13:15:17]

The CQ bit was checked by erikcorry@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2015-04-09 13:15:25]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1038653003/160001

[commit-bot: I haz the power, 2015-04-09 13:33:24]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-04-09 13:33:24]

Try jobs failed on following builders:
  v8_presubmit on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_presubmit/builds/1842)

[Erik Corry Chromium.org, 2015-04-13 13:12:56]

Ping!

[ulan, 2015-04-13 13:58:04]

Sorry for the delay. I've been thinking if we can get rid of the
"halfway-to-the-max" heuristic completely.

Right now it seems like a band-aid that is hiding real issues. If we would
properly set the allocation limit and compact the heap, then this heuristic
would not be necessary, right?

[Erik Corry Chromium.org, 2015-04-13 15:12:16]

I think we need both limits.

It's really hard to know how well allocation is going to work depending on how
fragmented the heap is.  If all our allocations fit in the gaps then we do a lot
of allocation without expanding the committed memory.  This is great, but we
still want to schedule a new GC when we hit our heap expansion factor of 1.1 to
4.

But if the allocations don't fit in the gaps we can expand our committed memory
with doing much allocation, and we will get too close to the limit (which is in
terms of the committed memory) quite quickly.

Without a crystal ball it's not possible to tell how big the allocated objects
will be at the moment when we should do a new GC. This lets us set both limits
and schedule when we hit the first one.

[ulan, 2015-04-14 08:54:57]

There are two different questions to discuss:
1. Do we need two limits?
2. Do we need the "half-way-to-max" heuristic at all? (either for the allocation
limit or for the committed memory limit).

I would be for removing the "half-way-to-max" heuristic completely and replacing
it with
- smarter selection of the allocation limit factor based on mutator utilization
- and possibly emergency GC before OOM. 
It is difficult to do without regressing benchmarks though.

About question 1:

> But if the allocations don't fit in the gaps we can expand our committed
memory
> with doing much allocation, and we will get too close to the limit (which is
in
> terms of the committed memory) quite quickly.

As we expand the committed memory we get fresh pages without any fragmentation.
We do bump pointer allocation in the fresh pages, which does not introduce
fragmentation (except the part at the end of the page). So my intuition would be
that almost every newly committed byte contributes towards the allocation limit.

More formally: if X is the size of live objects in old generation after GC, we
set allocation limit at X + Y, and the current committed memory is C, then the
next GC will happen in the worst case at committed memory (C + 2*Y). This case
is when the current committed memory is completely unusable for allocation due
to fragmentation and all newly allocated objects have size (N/2+1) where N is
the page area size (this leaves half of the page empty). So allocation limit
implicitly sets the committed memory limit.

Unfortunately the JSON parser breaks this theory because it allocates a big
string, truncates it (by writing the free map), and adjusts the live object size
counter. I think adjusting the counter is the bug here because the freed space
is not available for allocation until the next GC so it should be counted towers
the allocation limit.

[Hannes Payer (out of office), 2015-04-14 09:29:27]

The live counter correctly tells us how much memory is live, but decrementing
does not give us more allocatable space back. This seems to be an issue.

Overall, I would like to have a simpler growing strategy. Adding another
heuristic does not really make the current situation better. We should perform
more compaction when we are in a very fragmented state.

[Erik Corry Chromium.org, 2015-04-14 09:33:07]

The C+2Y is another way of saying "halfway to the max" for committed memory, but
you also want to impose the Y limit for allocated memory.  This can hurt us if
we are good at using the free list.

A concrete example: If we have X=200, C=500, limit = 700, then in your proposal
we have to set Y=100 so that C+2Y does not exceed 700.  This means we get a new
GC at 300 after only a factor 1.5 expansion of live objects, which is very early
and will hurt performance.

In contrast, with my proposal the X limit would be set at 400 with a C limit of
600.  That way we get the factor 2 on X for performance, but if fragmentation
becomes an issue we will hit the C limit of 600 first.

[ulan, 2015-04-15 09:55:01]

> A concrete example: If we have X=200, C=500, limit = 700, then in your
proposal
> we have to set Y=100 so that C+2Y does not exceed 700.  This means we get a
new
> GC at 300 after only a factor 1.5 expansion of live objects, which is very
early
> and will hurt performance.

We discussed this offline with Erik. To clarify for others:

in this example we would set the Y to 400 independent from the C and the limit.
If the committed memory hits the limit we would get an emergency GC.

[Erik Corry Chromium.org, 2015-04-15 14:46:47]

After some offline discussion here's how I understand the new plan:

* This trigger will be for starting incremental GC only, not for stop-the-world.
* We try to mark at the same speed as new-space allocation, which (rule of
thumb) is about a third the speed of old-space allocation.
* We estimate the amount of memory that needs marking to be the live objects
from the last GC plus any objects allocated after that.
* Therefore we aim to start incremental marking when the allocated objects are
3x as big as the remaining distance to the allocation limit.
* We will also start incremental marking when the allocated objects are 3x as
big as the difference between the max heap size and the committed memory.
* These two rules together mean we expect to finish incremental marking before
we hit either the allocated object limit or the committed memory limit.

A consequence of this is that sometimes we will start incremental marking
immediately after a GC. For example if we have X=450 C=550 then we aim to mark
450Mbytes while we allocate 150Mbytes (one third), so we will start immediately,
since we are only 150M from the 700M and we want to finish before C hits that
limit.

All this only makes sense if an incremental GC actually compacts at the end. 
But I think this is the case now, even if we the incremental GC ends during an
idle notification?

[rmcilroy, 2015-04-15 15:02:10]

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