[heap] Tweak evacuation candidate selection.

src/heap/mark-compact.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/heap/mark-compact.h"
 
 #include "src/base/atomicops.h"
 #include "src/base/bits.h"
 #include "src/base/sys-info.h"
 #include "src/code-stubs.h"
@@ skipping 630 matching lines @@
     CHECK(p->slots_buffer() == NULL);
     DCHECK(p->area_size() == area_size);
     int live_bytes =
         p->WasSwept() ? p->LiveBytesFromFreeList() : p->LiveBytes();
     pages.push_back(std::make_pair(live_bytes, p));
   }
 
   int candidate_count = 0;
   int total_live_bytes = 0;
 
-  bool reduce_memory = heap()->ShouldReduceMemory();
+  const bool reduce_memory = heap()->ShouldReduceMemory();
   if (FLAG_manual_evacuation_candidates_selection) {
     for (size_t i = 0; i < pages.size(); i++) {
       Page* p = pages[i].second;
       if (p->IsFlagSet(MemoryChunk::FORCE_EVACUATION_CANDIDATE_FOR_TESTING)) {
         candidate_count++;
         total_live_bytes += pages[i].first;
         p->ClearFlag(MemoryChunk::FORCE_EVACUATION_CANDIDATE_FOR_TESTING);
         AddEvacuationCandidate(p);
       }
     }
   } else if (FLAG_stress_compaction) {
     for (size_t i = 0; i < pages.size(); i++) {
       Page* p = pages[i].second;
       if (i % 2 == 0) {
         candidate_count++;
         total_live_bytes += pages[i].first;
         AddEvacuationCandidate(p);
       }
     }
   } else {
-    const int kTargetFragmentationPercent = 50;
-    const int kMaxEvacuatedBytes = 4 * Page::kPageSize;
+    // The following approach determines the pages that should be evacuated.
+    //
+    // We use two conditions to decide whether a page qualifies as an evacuation
+    // candidate, or not:
+    // * Target fragmentation: How fragmented is a page, i.e., how is the ratio
+    //   between live bytes and capacity of this page (= area).
+    // * Evacuation quota: A global quota determining how much bytes should be
+    //   compacted.
+    //
+    // The algorithm sorts all pages by live bytes and then iterates through
+    // them starting at page with the most free memory, adding them to the set
+    // of evacuation candidates as long as both conditions (fragmentation and
+    // quota) hold.
 
+    // For memory reducing mode we directly define both constants.
     const int kTargetFragmentationPercentForReduceMemory = 20;
     const int kMaxEvacuatedBytesForReduceMemory = 12 * Page::kPageSize;
 
+    // For regular mode (which is latency critical) we define less aggressive
+    // defaults to start and switch to a trace-based (using compaction speed)
+    // approach as soon as we have enough samples.
+    const int kTargetFragmentationPercent = 70;

[Michael Lippautz, 2015/11/26 13:19:08]

Increased the default from 50 to 70, making it less aggressive. 

+    const int kMaxEvacuatedBytes = 4 * Page::kPageSize;
+    // Time to take for a single area (=payload of page). Used as soon as there
+    // exist enough compaction speed samples.
+    const int kTargetMsPerArea = 1;
+
     int max_evacuated_bytes;
     int target_fragmentation_percent;
 
     if (reduce_memory) {
       target_fragmentation_percent = kTargetFragmentationPercentForReduceMemory;
       max_evacuated_bytes = kMaxEvacuatedBytesForReduceMemory;
     } else {
-      target_fragmentation_percent = kTargetFragmentationPercent;
+      const intptr_t estimated_compaction_speed =
+          heap()->tracer()->CompactionSpeedInBytesPerMillisecond();
+      if (estimated_compaction_speed != 0) {
+        // Estimate the target fragmentation based on traced compaction speed
+        // and a goal for a single page.
+        const intptr_t estimated_ms_per_area =
+            1 + static_cast<intptr_t>(area_size) / estimated_compaction_speed;
+        target_fragmentation_percent =
+            100 - 100 * kTargetMsPerArea / estimated_ms_per_area;
+        if (target_fragmentation_percent < 0) {

[ulan, 2015/11/26 14:15:59]

Let's cap it from below by kTargetFragmentationPercentForReduceMemory or
kTargetFragmentationPercent

[Michael Lippautz, 2015/11/26 14:36:31]

Done. Lower cap is using kTargetFragmentationPercentForReduceMemory

+          target_fragmentation_percent = 0;
+        }
+      } else {
+        target_fragmentation_percent = kTargetFragmentationPercent;
+      }
       max_evacuated_bytes = kMaxEvacuatedBytes;
     }
-    intptr_t free_bytes_threshold =
+    const intptr_t free_bytes_threshold =
         target_fragmentation_percent * (area_size / 100);
 
     // Sort pages from the most free to the least free, then select
     // the first n pages for evacuation such that:
     // - the total size of evacuated objects does not exceed the specified
     // limit.
     // - fragmentation of (n+1)-th page does not exceed the specified limit.
     std::sort(pages.begin(), pages.end(),
               [](const LiveBytesPagePair& a, const LiveBytesPagePair& b) {
                 return a.first < b.first;
               });
     for (size_t i = 0; i < pages.size(); i++) {
       int live_bytes = pages[i].first;
       int free_bytes = area_size - live_bytes;
       if (FLAG_always_compact ||
-          (free_bytes >= free_bytes_threshold &&
-           total_live_bytes + live_bytes <= max_evacuated_bytes)) {
+          ((free_bytes >= free_bytes_threshold) &&
+           ((total_live_bytes + live_bytes) <= max_evacuated_bytes))) {
         candidate_count++;
         total_live_bytes += live_bytes;
       }
       if (FLAG_trace_fragmentation_verbose) {
-        PrintF(
-            "Page in %s: %d KB free [fragmented if this >= %d KB], "
-            "sum of live bytes in fragmented pages %d KB [max is %d KB]\n",
-            AllocationSpaceName(space->identity()),
-            static_cast<int>(free_bytes / KB),
-            static_cast<int>(free_bytes_threshold / KB),
-            static_cast<int>(total_live_bytes / KB),
-            static_cast<int>(max_evacuated_bytes / KB));
+        PrintIsolate(isolate(),
+                     "compaction-selection-page: space=%s free_bytes_page=%d "
+                     "fragmentation_limit_kb=%d fragmentation_limit_percent=%d "
+                     "sum_compaction_kb=%d "
+                     "compaction_limit_kb=%d\n",
+                     AllocationSpaceName(space->identity()), free_bytes / KB,
+                     free_bytes_threshold / KB, target_fragmentation_percent,
+                     total_live_bytes / KB, max_evacuated_bytes / KB);
       }
     }
     // How many pages we will allocated for the evacuated objects
     // in the worst case: ceil(total_live_bytes / area_size)
     int estimated_new_pages = (total_live_bytes + area_size - 1) / area_size;
     DCHECK_LE(estimated_new_pages, candidate_count);
     int estimated_released_pages = candidate_count - estimated_new_pages;
     // Avoid (compact -> expand) cycles.
-    if (estimated_released_pages == 0 && !FLAG_always_compact)
+    if ((estimated_released_pages == 0) && !FLAG_always_compact) {
       candidate_count = 0;
+    }
     for (int i = 0; i < candidate_count; i++) {
       AddEvacuationCandidate(pages[i].second);
     }
   }
 
   if (FLAG_trace_fragmentation) {
-    PrintF(
-        "Collected %d evacuation candidates [%d KB live] for space %s "
-        "[mode %s]\n",
-        candidate_count, static_cast<int>(total_live_bytes / KB),
-        AllocationSpaceName(space->identity()),
-        (reduce_memory ? "reduce memory footprint" : "normal"));
+    PrintIsolate(isolate(),
+                 "compaction-selection: space=%s reduce_memory=%d pages=%d "
+                 "total_live_bytes=%d\n",
+                 AllocationSpaceName(space->identity()), reduce_memory,
+                 candidate_count, total_live_bytes / KB);
   }
 }
 
 
 void MarkCompactCollector::AbortCompaction() {
   if (compacting_) {
     int npages = evacuation_candidates_.length();
     for (int i = 0; i < npages; i++) {
       Page* p = evacuation_candidates_[i];
       slots_buffer_allocator_->DeallocateChain(p->slots_buffer_address());
@@ skipping 3356 matching lines @@
     MarkBit mark_bit = Marking::MarkBitFrom(host);
     if (Marking::IsBlack(mark_bit)) {
       RelocInfo rinfo(pc, RelocInfo::CODE_TARGET, 0, host);
       RecordRelocSlot(&rinfo, target);
     }
   }
 }
 
 }  // namespace internal
 }  // namespace v8