• ulan's avatar
    New algorithm for selecting evacuation candidates · 5e87a099
    ulan authored
    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}
    5e87a099
spaces.cc 100 KB