New algorithm for selecting evacuation candidates
authorulan <ulan@chromium.org>
Wed, 27 May 2015 13:07:47 +0000 (06:07 -0700)
committerCommit bot <commit-bot@chromium.org>
Wed, 27 May 2015 13:07:52 +0000 (13:07 +0000)
commit5e87a0997bad554799cdf1a07e46ecfd0af8e1fa
treedd50d61f347d94c3251e240c749fa3f14b0a79f4
parent1fb83a2f02f8eec5d9f6b041ecf2edfdf143cdce
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.

Review URL: https://codereview.chromium.org/1038313003

Cr-Commit-Position: refs/heads/master@{#28651}
src/heap/mark-compact.cc
src/heap/spaces.cc
src/heap/spaces.h