New algorithm for selecting evacuation candidates

New algorithm for selecting evacuation candidates

This lifts the sqrt(n) limit on number of evacuation candidates,
replaces O(n * sqrt(n)) algorithm with O(n*log(n)) algorithm, and
removes hard-coded constants.

Evacuation candidates are selected as follows:

1) Sort pages from the most free to the least free.

2) Select the first m pages as evacuation candidates such that m is as
large as possible under the two conditions:

- The total size of live objects in the first m pages does not exceed
the given limit. This is based on the assumption that the evacuation cost is
proportional to the total size of moved objects.

- The fragmentation of the (m+1)-th page does not exceed the given
limit.

Committed: https://crrev.com/5e87a0997bad554799cdf1a07e46ecfd0af8e1fa
Cr-Commit-Position: refs/heads/master@{#28651}

[ulan, 2015-04-24 11:05:48]

Patchset #5 (id:80001) has been deleted

[ulan, 2015-04-24 15:28:42]

ulan@chromium.org changed reviewers:
+ erikcorry@chromium.org, hpayer@chromium.org

[ulan, 2015-04-24 15:28:43]

PTAL

[ulan, 2015-05-22 13:30:23]

The last PS is performance neutral. PTAL

[Hannes Payer (out of office), 2015-05-27 08:49:30]

Cool!

https://codereview.chromium.org/1038313003/diff/180001/src/flag-definitions.h
File src/flag-definitions.h (right):

https://codereview.chromium.org/1038313003/diff/180001/src/flag-definitions.h...
src/flag-definitions.h:614: "the goal maximum percentage of free space in
committed memory")
goal -> target

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

https://codereview.chromium.org/1038313003/diff/180001/src/heap/mark-compact....
src/heap/mark-compact.cc:682:
->CurrentNewSpaceAllocationThroughputInBytesPerMillisecond());
That should be now overall allocation throughput.

https://codereview.chromium.org/1038313003/diff/180001/src/heap/mark-compact....
src/heap/mark-compact.cc:696: const int kTargetFragmentationPercent = 50;
Don't you wanna use the FLAG_target_fragmentation here?

https://codereview.chromium.org/1038313003/diff/180001/src/heap/mark-compact....
src/heap/mark-compact.cc:740: }
This piece needs a comment.

https://codereview.chromium.org/1038313003/diff/180001/src/heap/mark-compact....
src/heap/mark-compact.cc:742: int estimated_released_pages = candidate_count -
estimated_new_pages;
estimated_released_pages can be negative. That is a bit strange.

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

https://codereview.chromium.org/1038313003/diff/180001/src/heap/spaces.h#newc...
src/heap/spaces.h:681: int available_in_small_free_list_;
Why int? What about size_t?

[ulan, 2015-05-27 11:33:20]

Thanks. I uploaded new patch.

https://codereview.chromium.org/1038313003/diff/180001/src/flag-definitions.h
File src/flag-definitions.h (right):

https://codereview.chromium.org/1038313003/diff/180001/src/flag-definitions.h...
src/flag-definitions.h:614: "the goal maximum percentage of free space in
committed memory")
On 2015/05/27 08:49:30, Hannes Payer wrote:
> goal -> target

Removed the flags.

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

https://codereview.chromium.org/1038313003/diff/180001/src/heap/mark-compact....
src/heap/mark-compact.cc:682:
->CurrentNewSpaceAllocationThroughputInBytesPerMillisecond());
On 2015/05/27 08:49:30, Hannes Payer wrote:
> That should be now overall allocation throughput.

Done.

https://codereview.chromium.org/1038313003/diff/180001/src/heap/mark-compact....
src/heap/mark-compact.cc:696: const int kTargetFragmentationPercent = 50;
On 2015/05/27 08:49:30, Hannes Payer wrote:
> Don't you wanna use the FLAG_target_fragmentation here?

I removed the flags to be consistent with "*ForReduceMemory" constants.

https://codereview.chromium.org/1038313003/diff/180001/src/heap/mark-compact....
src/heap/mark-compact.cc:740: }
On 2015/05/27 08:49:30, Hannes Payer wrote:
> This piece needs a comment.

Done.

https://codereview.chromium.org/1038313003/diff/180001/src/heap/mark-compact....
src/heap/mark-compact.cc:742: int estimated_released_pages = candidate_count -
estimated_new_pages;
On 2015/05/27 08:49:30, Hannes Payer wrote:
> estimated_released_pages can be negative. That is a bit strange.

I think estimated_new_page <= candidate_count always holds. Added DCHECK

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

https://codereview.chromium.org/1038313003/diff/180001/src/heap/spaces.h#newc...
src/heap/spaces.h:681: int available_in_small_free_list_;
On 2015/05/27 08:49:30, Hannes Payer wrote:
> Why int? What about size_t?

All free list counters in other places are signed. I changed it from intptr_t to
int because we don't need 64-bits to count free bytes in a page.

[Hannes Payer (out of office), 2015-05-27 12:41:34]

LGTM

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

https://codereview.chromium.org/1038313003/diff/180001/src/heap/spaces.h#newc...
src/heap/spaces.h:681: int available_in_small_free_list_;
On 2015/05/27 11:33:20, ulan wrote:
> On 2015/05/27 08:49:30, Hannes Payer wrote:
> > Why int? What about size_t?
> 
> All free list counters in other places are signed. I changed it from intptr_t
to
> int because we don't need 64-bits to count free bytes in a page.

yeah...

[ulan, 2015-05-27 12:42:45]

The CQ bit was checked by ulan@chromium.org

[commit-bot: I haz the power, 2015-05-27 12:42:54]

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

[commit-bot: I haz the power, 2015-05-27 13:07:52]

Committed patchset #11 (id:220001)

[commit-bot: I haz the power, 2015-05-27 13:08:00]

Patchset 11 (id:??) landed as
https://crrev.com/5e87a0997bad554799cdf1a07e46ecfd0af8e1fa
Cr-Commit-Position: refs/heads/master@{#28651}