[heap] Sort sweep pages list by free memory.

[heap] Sort sweep pages list by free memory.

Also restrict how many pages are swept during slow path allocation.

BUG=chromium:524425
LOG=N

Committed: https://crrev.com/2e481c15b77e733c8313ddc2c1e2ef9fda773b31
Cr-Commit-Position: refs/heads/master@{#33435}

[Michael Lippautz, 2016-01-19 14:59:49]

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

[Michael Lippautz, 2016-01-19 14:59:50]

- Performance neutral on a single run on v8.infinite_scroll.
- Performance neutral on the microbenchmarks
- Sorting the pages is below 20us, even for larger chunks (~100 pages)

[Hannes Payer (out of office), 2016-01-20 09:25:03]

https://codereview.chromium.org/1596343004/diff/1/src/heap/mark-compact.cc
File src/heap/mark-compact.cc (right):

https://codereview.chromium.org/1596343004/diff/1/src/heap/mark-compact.cc#ne...
src/heap/mark-compact.cc:3762: void
MarkCompactCollector::MoveEvacuationCandidatesToEndOfPagesList() {
This logic is not needed anymore, since we have a sweeping todo list.

https://codereview.chromium.org/1596343004/diff/1/src/heap/mark-compact.cc#ne...
src/heap/mark-compact.cc:3799: for (Page* p : sweeping_list(space)) {
Since we have now a separate data structure, why don't we remove entries from
the data structure in a synchronized way?

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

https://codereview.chromium.org/1596343004/diff/1/src/heap/spaces.cc#newcode2851
src/heap/spaces.cc:2851: size_in_bytes, 1);
1 should be a constant.

https://codereview.chromium.org/1596343004/diff/1/src/heap/spaces.cc#newcode2852
src/heap/spaces.cc:2852: if (max_freed >= size_in_bytes) {
If you add this case, you want to call RefillFreeList(); after SweepInParallel.

https://codereview.chromium.org/1596343004/diff/1/src/heap/spaces.h
File src/heap/spaces.h (left):

https://codereview.chromium.org/1596343004/diff/1/src/heap/spaces.h#oldcode2208
src/heap/spaces.h:2208: // end_of_unswept_pages_ page.
Good by, end_of_unswept_pages_.

[Michael Lippautz, 2016-01-20 11:11:16]

PTAL

https://codereview.chromium.org/1596343004/diff/1/src/heap/mark-compact.cc
File src/heap/mark-compact.cc (right):

https://codereview.chromium.org/1596343004/diff/1/src/heap/mark-compact.cc#ne...
src/heap/mark-compact.cc:3762: void
MarkCompactCollector::MoveEvacuationCandidatesToEndOfPagesList() {
On 2016/01/20 09:25:03, Hannes Payer wrote:
> This logic is not needed anymore, since we have a sweeping todo list.

Done.

https://codereview.chromium.org/1596343004/diff/1/src/heap/mark-compact.cc#ne...
src/heap/mark-compact.cc:3799: for (Page* p : sweeping_list(space)) {
On 2016/01/20 09:25:03, Hannes Payer wrote:
> Since we have now a separate data structure, why don't we remove entries from
> the data structure in a synchronized way?

Because removing items from a std::vector can be quite expensive. Since those
calls are interleaving (and unbalanced) we might end up removing an item in the
middle, resulting in expensive move operations in the vector.

(And iterating should be fast in this case.)

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

https://codereview.chromium.org/1596343004/diff/1/src/heap/spaces.cc#newcode2851
src/heap/spaces.cc:2851: size_in_bytes, 1);
On 2016/01/20 09:25:03, Hannes Payer wrote:
> 1 should be a constant.

Done: kMaxPagesSweptDuringSlowAllocation

https://codereview.chromium.org/1596343004/diff/1/src/heap/spaces.cc#newcode2852
src/heap/spaces.cc:2852: if (max_freed >= size_in_bytes) {
On 2016/01/20 09:25:03, Hannes Payer wrote:
> If you add this case, you want to call RefillFreeList(); after
SweepInParallel.

Done. (ftr: this is to move over already freed memory, in case we need them in
following allocations)

https://codereview.chromium.org/1596343004/diff/1/src/heap/spaces.h
File src/heap/spaces.h (left):

https://codereview.chromium.org/1596343004/diff/1/src/heap/spaces.h#oldcode2208
src/heap/spaces.h:2208: // end_of_unswept_pages_ page.
On 2016/01/20 09:25:03, Hannes Payer wrote:
> Good by, end_of_unswept_pages_.

Done.

[Michael Lippautz, 2016-01-20 11:46:36]

Description was changed from

==========
[heap] Sorted sweep pages list by free memory.

Also restrict how much pages are swept during slow path allocation.

BUG=chromium:524425
LOG=N
==========

to

==========
[heap] Sort sweep pages list by free memory.

Also restrict how much pages are swept during slow path allocation.

BUG=chromium:524425
LOG=N
==========

[Michael Lippautz, 2016-01-20 11:46:47]

Description was changed from

==========
[heap] Sort sweep pages list by free memory.

Also restrict how much pages are swept during slow path allocation.

BUG=chromium:524425
LOG=N
==========

to

==========
[heap] Sort sweep pages list by free memory.

Also restrict how mny pages are swept during slow path allocation.

BUG=chromium:524425
LOG=N
==========

[Michael Lippautz, 2016-01-20 11:46:53]

Description was changed from

==========
[heap] Sort sweep pages list by free memory.

Also restrict how mny pages are swept during slow path allocation.

BUG=chromium:524425
LOG=N
==========

to

==========
[heap] Sort sweep pages list by free memory.

Also restrict how many pages are swept during slow path allocation.

BUG=chromium:524425
LOG=N
==========

[Michael Lippautz, 2016-01-20 11:47:22]

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

[commit-bot: I haz the power, 2016-01-20 11:47:30]

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

[commit-bot: I haz the power, 2016-01-20 11:51:40]

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

[commit-bot: I haz the power, 2016-01-20 11:51:41]

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

[Michael Lippautz, 2016-01-20 11:56:53]

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

[commit-bot: I haz the power, 2016-01-20 11:57:03]

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

[Hannes Payer (out of office), 2016-01-20 12:08:19]

https://codereview.chromium.org/1596343004/diff/1/src/heap/mark-compact.cc
File src/heap/mark-compact.cc (right):

https://codereview.chromium.org/1596343004/diff/1/src/heap/mark-compact.cc#ne...
src/heap/mark-compact.cc:3799: for (Page* p : sweeping_list(space)) {
On 2016/01/20 11:11:16, Michael Lippautz wrote:
> On 2016/01/20 09:25:03, Hannes Payer wrote:
> > Since we have now a separate data structure, why don't we remove entries
from
> > the data structure in a synchronized way?
> 
> Because removing items from a std::vector can be quite expensive. Since those
> calls are interleaving (and unbalanced) we might end up removing an item in
the
> middle, resulting in expensive move operations in the vector.
> 
> (And iterating should be fast in this case.)

Why don't we use a priority_queue?

[commit-bot: I haz the power, 2016-01-20 12:32:36]

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

[commit-bot: I haz the power, 2016-01-20 12:32:37]

Dry run: This issue passed the CQ dry run.

[Michael Lippautz, 2016-01-21 08:22:56]

On 2016/01/20 12:08:19, Hannes Payer wrote:
> https://codereview.chromium.org/1596343004/diff/1/src/heap/mark-compact.cc
> File src/heap/mark-compact.cc (right):
> 
>
https://codereview.chromium.org/1596343004/diff/1/src/heap/mark-compact.cc#ne...
> src/heap/mark-compact.cc:3799: for (Page* p : sweeping_list(space)) {
> On 2016/01/20 11:11:16, Michael Lippautz wrote:
> > On 2016/01/20 09:25:03, Hannes Payer wrote:
> > > Since we have now a separate data structure, why don't we remove entries
> from
> > > the data structure in a synchronized way?
> > 
> > Because removing items from a std::vector can be quite expensive. Since
those
> > calls are interleaving (and unbalanced) we might end up removing an item in
> the
> > middle, resulting in expensive move operations in the vector.
> > 
> > (And iterating should be fast in this case.)
> 
> Why don't we use a priority_queue?

As discussed offline, let's keep the vector for now. The reasons are:
- Priority queue does not provide random access, but rather push/pop
- We would need to sync the priority queue, but cannot get rid of
synchronization on page level as we have another entry point to sweeping
- We need to finalize on page level for WAS_SWEPT (which we cannot get rid of
unless we make live_bytes atomic). So we need to  keep a list of pages that have
been swept.

[Hannes Payer (out of office), 2016-01-21 10:35:22]

lgtm

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

https://codereview.chromium.org/1596343004/diff/40001/src/heap/spaces.h#newco...
src/heap/spaces.h:2146: static const int kMaxPagesSweptDuringSlowAllocation = 1;
This one can be local in the function.

[Michael Lippautz, 2016-01-21 12:03:14]

The CQ bit was checked by mlippautz@chromium.org

[Michael Lippautz, 2016-01-21 12:03:14]

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/1596343004/#ps60001
(title: "Adressed final comment")

[commit-bot: I haz the power, 2016-01-21 12:03:24]

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

[commit-bot: I haz the power, 2016-01-21 12:50:10]

Description was changed from

==========
[heap] Sort sweep pages list by free memory.

Also restrict how many pages are swept during slow path allocation.

BUG=chromium:524425
LOG=N
==========

to

==========
[heap] Sort sweep pages list by free memory.

Also restrict how many pages are swept during slow path allocation.

BUG=chromium:524425
LOG=N
==========

[commit-bot: I haz the power, 2016-01-21 12:50:11]

Committed patchset #4 (id:60001)

[commit-bot: I haz the power, 2016-01-21 12:50:50]

Description was changed from

==========
[heap] Sort sweep pages list by free memory.

Also restrict how many pages are swept during slow path allocation.

BUG=chromium:524425
LOG=N
==========

to

==========
[heap] Sort sweep pages list by free memory.

Also restrict how many pages are swept during slow path allocation.

BUG=chromium:524425
LOG=N

Committed: https://crrev.com/2e481c15b77e733c8313ddc2c1e2ef9fda773b31
Cr-Commit-Position: refs/heads/master@{#33435}
==========

[commit-bot: I haz the power, 2016-01-21 12:50:51]

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