Reland of "[heap] Add more tasks for parallel compaction"

Reland of "[heap] Add more tasks for parallel compaction"

- We now compute the number of parallel compaction tasks, depending on the
  evacuation candidate list, the number of cores, and some hard limit.
- Free memory is moved over to compaction tasks (up to some limit)
- Moving over memory is done by dividing the free list of a given space up among
  other free lists. Since this is potentially slow we limit the maximum amount
  of moved memory.

This reverts commit bfccd5187ceb21c99feea4538e08ca7aef48b65b.

BUG=chromium:524425
LOG=N

Committed: https://crrev.com/7e283d746a194ceaaca114e2ba17504653d6a109
Cr-Commit-Position: refs/heads/master@{#30945}

[Michael Lippautz, 2015-09-24 14:36:58]

Patchset #2 (id:20001) has been deleted

[Michael Lippautz, 2015-09-24 14:39:37]

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

[commit-bot: I haz the power, 2015-09-24 14:39:45]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1365743003/40001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1365743003/40001

[commit-bot: I haz the power, 2015-09-24 14:53:44]

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

[commit-bot: I haz the power, 2015-09-24 14:53:44]

Dry run: Try jobs failed on following builders:
  v8_linux_nodcheck_rel on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_nodcheck_rel/build...)

[Michael Lippautz, 2015-09-25 09:43:57]

Patchset #2 (id:40001) has been deleted

[Michael Lippautz, 2015-09-25 09:45:06]

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

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

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1365743003/60001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1365743003/60001

[commit-bot: I haz the power, 2015-09-25 10:09:39]

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

[commit-bot: I haz the power, 2015-09-25 10:09:40]

Dry run: This issue passed the CQ dry run.

[Michael Lippautz, 2015-09-25 10:36:47]

mlippautz@chromium.org changed reviewers:
+ hpayer@chromium.org

[Michael Lippautz, 2015-09-25 10:36:47]

PTAL; This implements dividing up memory properly now, keeping the counters
sane. I am still open for other ideas on how to simplify this. 

The interface is much stricter now (requiring CompactionSpaceCollection's
instead of passing raw memory).

The diff to PS-1 contains some artifacts from yesterday's ToT. Please ignore
them.

Refilling free lists from our Sweeper is still a TODO.

[Hannes Payer (out of office), 2015-09-25 13:04:51]

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.cc
File src/heap/spaces.cc (right):

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.cc#newc...
src/heap/spaces.cc:1504: void NewSpace::InlineAllocationStep(Address top,
Address new_top) {
Uh, looks like you added another CL to your CL.

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

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.h#newco...
src/heap/spaces.h:1532: DCHECK_GE(capacity_, 0);
DCHECK_GE(capacity_, 0); is not needed.

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.h#newco...
src/heap/spaces.h:1547: intptr_t capacity_;
Can you add comments that explain these variables?

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.h#newco...
src/heap/spaces.h:2796: // allocated since the last step.) new_top is the
address of the bump pointer
This is not from your cl.

[Hannes Payer (out of office), 2015-09-25 13:07:38]

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.cc
File src/heap/spaces.cc (right):

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.cc#newc...
src/heap/spaces.cc:1504: void NewSpace::InlineAllocationStep(Address top,
Address new_top) {
On 2015/09/25 13:04:51, Hannes Payer wrote:
> Uh, looks like you added another CL to your CL.

Ah, wrong diff view. Thanks for pointing this out.

[Hannes Payer (out of office), 2015-09-25 13:16:00]

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

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.h#newco...
src/heap/spaces.h:1513: void Merge(const AllocationStats& other) {
Why don't you reset the borrowed counter?

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.h#newco...
src/heap/spaces.h:1521: capacity_ -= other.borrowed_;
Why do you subtract it from both? Can you explain that in a comment?

[Michael Lippautz, 2015-09-25 13:28:50]

PTAL; Sorry for the diff, but the baseline was uploaded before ToT landed fixes.

I am still open to suggestions on the counter business ;)

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.cc
File src/heap/spaces.cc (right):

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.cc#newc...
src/heap/spaces.cc:1504: void NewSpace::InlineAllocationStep(Address top,
Address new_top) {
On 2015/09/25 13:07:38, Hannes Payer wrote:
> On 2015/09/25 13:04:51, Hannes Payer wrote:
> > Uh, looks like you added another CL to your CL.
> 
> Ah, wrong diff view. Thanks for pointing this out.

Acknowledged.

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.cc#newc...
src/heap/spaces.cc:1504: void NewSpace::InlineAllocationStep(Address top,
Address new_top) {
On 2015/09/25 13:04:51, Hannes Payer wrote:
> Uh, looks like you added another CL to your CL.

Acknowledged.

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

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.h#newco...
src/heap/spaces.h:1513: void Merge(const AllocationStats& other) {
On 2015/09/25 13:15:59, Hannes Payer wrote:
> Why don't you reset the borrowed counter?

The caller needs to make sure that the counters are properly "reset". You are
right though, because we only call Reset() and not Clear() in
MergeCompactionSpace().

The whole data structure is set up in a way that callers ensure consistency
(which is the hard part).

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.h#newco...
src/heap/spaces.h:1521: capacity_ -= other.borrowed_;
On 2015/09/25 13:15:59, Hannes Payer wrote:
> Why do you subtract it from both? Can you explain that in a comment?

The reason is:
 - The borrowed amount is accounted as allocated (size_) in the original space.
We do not decrease capacity_ (and thus prohibit accounting for it in size_) of
the original space to keep the invariante of SizeOfObjects() > 0 at all times.
 - The borrowed amount is accounted as "borrowed_" in the destination space.
This recording is needed to properly undo the operation while merging.
 - The borrowed amount also increases the capacity of the destination space,
i.e., the borrowed amount can be used for further allocation (thus increasing
also size_ of the destination spacE).

Upon merging we need to make sure that we account for the "double-accounting" of
allocated space by decreasing it from size_, but also capacity_.

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.h#newco...
src/heap/spaces.h:1532: DCHECK_GE(capacity_, 0);
On 2015/09/25 13:04:51, Hannes Payer wrote:
> DCHECK_GE(capacity_, 0); is not needed.

Done.

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.h#newco...
src/heap/spaces.h:1547: intptr_t capacity_;
On 2015/09/25 13:04:51, Hannes Payer wrote:
> Can you add comments that explain these variables?

The variables are explained on top of the class. Should I move their description
in here?

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.h#newco...
src/heap/spaces.h:2796: // allocated since the last step.) new_top is the
address of the bump pointer
On 2015/09/25 13:04:51, Hannes Payer wrote:
> This is not from your cl.

Ack. The baseline did not contain the fixes. Sorry for the troubles.

[Hannes Payer (out of office), 2015-09-25 14:11:07]

lgtm, with nits

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

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.h#newco...
src/heap/spaces.h:1521: capacity_ -= other.borrowed_;
On 2015/09/25 13:28:50, Michael Lippautz wrote:
> On 2015/09/25 13:15:59, Hannes Payer wrote:
> > Why do you subtract it from both? Can you explain that in a comment?
> 
> The reason is:
>  - The borrowed amount is accounted as allocated (size_) in the original
space.
> We do not decrease capacity_ (and thus prohibit accounting for it in size_) of
> the original space to keep the invariante of SizeOfObjects() > 0 at all times.
>  - The borrowed amount is accounted as "borrowed_" in the destination space.
> This recording is needed to properly undo the operation while merging.
>  - The borrowed amount also increases the capacity of the destination space,
> i.e., the borrowed amount can be used for further allocation (thus increasing
> also size_ of the destination spacE).
> 
> Upon merging we need to make sure that we account for the "double-accounting"
of
> allocated space by decreasing it from size_, but also capacity_.

This is really complicated. Can you make your comment more precise?

Overall, the counters are really tricky to get right. We should clean that up at
some point.

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.h#newco...
src/heap/spaces.h:1547: intptr_t capacity_;
On 2015/09/25 13:28:50, Michael Lippautz wrote:
> On 2015/09/25 13:04:51, Hannes Payer wrote:
> > Can you add comments that explain these variables?
> 
> The variables are explained on top of the class. Should I move their
description
> in here?

No, that is fine. An explanation of borrowed_ is missing than.

[Michael Lippautz, 2015-09-25 14:31:39]

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

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.h#newco...
src/heap/spaces.h:1521: capacity_ -= other.borrowed_;
On 2015/09/25 14:11:07, Hannes Payer wrote:
> On 2015/09/25 13:28:50, Michael Lippautz wrote:
> > On 2015/09/25 13:15:59, Hannes Payer wrote:
> > > Why do you subtract it from both? Can you explain that in a comment?
> > 
> > The reason is:
> >  - The borrowed amount is accounted as allocated (size_) in the original
> space.
> > We do not decrease capacity_ (and thus prohibit accounting for it in size_)
of
> > the original space to keep the invariante of SizeOfObjects() > 0 at all
times.
> >  - The borrowed amount is accounted as "borrowed_" in the destination space.
> > This recording is needed to properly undo the operation while merging.
> >  - The borrowed amount also increases the capacity of the destination space,
> > i.e., the borrowed amount can be used for further allocation (thus
increasing
> > also size_ of the destination spacE).
> > 
> > Upon merging we need to make sure that we account for the
"double-accounting"
> of
> > allocated space by decreasing it from size_, but also capacity_.
> 
> This is really complicated. Can you make your comment more precise?
> 
> Overall, the counters are really tricky to get right. We should clean that up
at
> some point.

I added some more explanation to the actual member description.

https://codereview.chromium.org/1365743003/diff/60001/src/heap/spaces.h#newco...
src/heap/spaces.h:1547: intptr_t capacity_;
On 2015/09/25 14:11:07, Hannes Payer wrote:
> On 2015/09/25 13:28:50, Michael Lippautz wrote:
> > On 2015/09/25 13:04:51, Hannes Payer wrote:
> > > Can you add comments that explain these variables?
> > 
> > The variables are explained on top of the class. Should I move their
> description
> > in here?
> 
> No, that is fine. An explanation of borrowed_ is missing than.

Changed my mind on this. I moved the descriptions of the fields down, added the
one for borrowed_, and kept the general description of the class at the top.

[Michael Lippautz, 2015-09-25 14:32:28]

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

[commit-bot: I haz the power, 2015-09-25 14:32:36]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1365743003/100001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1365743003/100001

[commit-bot: I haz the power, 2015-09-25 14:58:37]

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

[commit-bot: I haz the power, 2015-09-25 14:58:38]

Dry run: This issue passed the CQ dry run.

[Michael Lippautz, 2015-09-25 15:03:04]

The CQ bit was checked by mlippautz@chromium.org

[Michael Lippautz, 2015-09-25 15:03:04]

The patchset sent to the CQ was uploaded after l-g-t-m from hpayer@chromium.org
Link to the patchset: https://codereview.chromium.org/1365743003/#ps100001
(title: "Added further comments to code.")

[commit-bot: I haz the power, 2015-09-25 15:03:12]

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

[commit-bot: I haz the power, 2015-09-25 15:05:14]

Committed patchset #4 (id:100001)

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

Patchset 4 (id:??) landed as
https://crrev.com/7e283d746a194ceaaca114e2ba17504653d6a109
Cr-Commit-Position: refs/heads/master@{#30945}

[Michael Lippautz, 2015-09-25 15:40:10]

A revert of this CL (patchset #4 id:100001) has been created in
https://codereview.chromium.org/1371653002/ by mlippautz@chromium.org.

The reason for reverting is: failing again:
https://chromegw.corp.google.com/i/client.v8/builders/V8%20Mac/builds/4505/st....