Implement growth policy for old space using time and space signals.

runtime/vm/pages.cc

Index: runtime/vm/pages.cc
diff --git a/runtime/vm/pages.cc b/runtime/vm/pages.cc
index 9194db706929bba0878cf8cb99152001e32b1dba..82ea65df96e9498c0c29cb072bd8638e478c9b1d 100644
--- a/runtime/vm/pages.cc
+++ b/runtime/vm/pages.cc
@@ -12,6 +12,13 @@
 
 namespace dart {
 
+DEFINE_FLAG(int, heap_growth_space_ratio, 10,
+            "The desired maximum percentage of free space after GC");
+DEFINE_FLAG(int, heap_growth_time_ratio, 3,
+            "The desired maximum percentage of time spent in GC");
+DEFINE_FLAG(int, heap_growth_rate, 4,
+            "The size the heap is grown, in heap pages");
+
 HeapPage* HeapPage::Initialize(VirtualMemory* memory, bool is_executable) {
   ASSERT(memory->size() > VirtualMemory::PageSize());
   memory->Commit(is_executable);
@@ -64,7 +71,9 @@ RawObject* HeapPage::FindObject(FindObjectVisitor* visitor) const {
 }
 
 
-PageSpace::PageSpace(Heap* heap, intptr_t max_capacity, bool is_executable)
+PageSpace::PageSpace(Heap* heap,
+                     intptr_t max_capacity,
+                     bool is_executable)

[Ivan Posva, 2012/05/29 23:27:37]

?

[cshapiro, 2012/05/30 17:56:24]

More noise.  Done.

     : freelist_(),
       heap_(heap),
       pages_(NULL),
@@ -76,7 +85,12 @@ PageSpace::PageSpace(Heap* heap, intptr_t max_capacity, bool is_executable)
       in_use_(0),
       count_(0),
       is_executable_(is_executable),
-      sweeping_(false) { }
+      sweeping_(false),
+      is_growth_controlled_(false),
+      page_space_controller_(FLAG_heap_growth_space_ratio,
+                             FLAG_heap_growth_rate,
+                             FLAG_heap_growth_time_ratio) {
+}
 
 
 PageSpace::~PageSpace() {
@@ -187,7 +201,10 @@ uword PageSpace::TryAllocate(intptr_t size) {
     result = TryBumpAllocate(size);
     if (result == 0) {
       result = freelist_.TryAllocate(size);
-      if ((result == 0) && CanIncreaseCapacity(kPageSize)) {
+      if ((result == 0) &&
+          (is_growth_controlled_ != true ||
+           page_space_controller_.CanGrowPageSpace()) &&
+          CanIncreaseCapacity(kPageSize)) {
         AllocatePage();
         result = TryBumpAllocate(size);
         ASSERT(result != 0);
@@ -288,6 +305,7 @@ void PageSpace::MarkSweep(bool invoke_api_callbacks) {
 
   Timer timer(FLAG_verbose_gc, "MarkSweep");
   timer.Start();
+  int64_t start = OS::GetCurrentTimeMillis();
 
   // Mark all reachable old-gen objects.
   GCMarker marker(heap_);
@@ -331,7 +349,10 @@ void PageSpace::MarkSweep(bool invoke_api_callbacks) {
   }
 
   // Record data and print if requested.
+  int64_t end = OS::GetCurrentTimeMillis();

[Ivan Posva, 2012/05/29 23:27:37]

Why not use the timer object?

[cshapiro, 2012/05/30 17:56:24]

Okay.  The timer does not directly provide this data so is somewhat more
verbose.  Let me know what you think.

   intptr_t in_use_before = in_use_;
+  page_space_controller_.EvaluateGarbageCollection(in_use_before, in_use,
+                                                   start, end);
   in_use_ = in_use;
 
   timer.Stop();
@@ -357,4 +378,89 @@ void PageSpace::MarkSweep(bool invoke_api_callbacks) {
   sweeping_ = false;
 }
 
+
+PageSpaceController::PageSpaceController(int heap_growth_ratio,
+                                         int heap_growth_rate,
+                                         int garbage_collection_time_ratio)
+    : grow_heap_(heap_growth_rate),
+      heap_growth_ratio_(heap_growth_ratio),
+      heap_growth_rate_(heap_growth_rate),
+      garbage_collection_time_ratio_(garbage_collection_time_ratio) {
+}
+
+
+PageSpaceController::~PageSpaceController() {}
+
+
+bool PageSpaceController::CanGrowPageSpace() {
+  if (heap_growth_ratio_ == 100) {

[Ivan Posva, 2012/05/29 23:27:37]

For debugging we might want to add a always_grow_to_max instead of this hack.

[cshapiro, 2012/05/30 17:56:24]

Or, I could suppress the enabling of the controller.  Do you want this in the
current CL or...?

+    return true;
+  }
+  if (grow_heap_ == 0) {

[Ivan Posva, 2012/05/29 23:27:37]

<= 0

[cshapiro, 2012/05/30 17:56:24]

Done.

+    return false;
+  }
+  grow_heap_ -= 1;
+  return true;
+}
+
+
+void PageSpaceController::EvaluateGarbageCollection(
+    size_t in_use_before, size_t in_use_after, int64_t start, int64_t end) {
+  ASSERT(in_use_before >= in_use_after);
+  ASSERT(end >= start);
+  history_.AddGarbageCollectionTime(start, end);
+  int collected_garbage_ratio =
+      static_cast<int>((static_cast<double>(in_use_before - in_use_after) /
+                        static_cast<double>(in_use_before)) * 100);
+  if ((collected_garbage_ratio > heap_growth_ratio_) &&
+      (history_.GarbageCollectionTimeFraction() <
+       garbage_collection_time_ratio_)) {
+    grow_heap_ = 0;
+  } else {
+    grow_heap_ = heap_growth_rate_;
+  }
+}
+
+
+PageSpaceGarbageCollectionHistory::PageSpaceGarbageCollectionHistory()
+    : index_(0) {
+  for (uint32_t i = 0; i < kHistoryLength; i++) {
+    start_[i] = 0;
+    end_[i] = 0;
+  }
+}
+
+
+void PageSpaceGarbageCollectionHistory::
+    AddGarbageCollectionTime(uint64_t start, uint64_t end) {
+  int index = index_ % kHistoryLength;
+  start_[index] = start;
+  end_[index] = end;
+  index_++;
+}
+
+
+int PageSpaceGarbageCollectionHistory::GarbageCollectionTimeFraction() {
+  int current;
+  int previous;
+  uint64_t gc_time = 0;
+  uint64_t total_time = 0;
+  for (uint32_t i = 1; i < kHistoryLength; i++) {
+    current = (index_ - i) % kHistoryLength;
+    previous = (index_ - 1 - i) % kHistoryLength;
+    if (end_[previous] == 0) {
+       break;
+    }
+    // iterate over the circular buffer in reverse order
+    gc_time += end_[current] - start_[current];
+    total_time += end_[current] - end_[previous];
+  }
+  if (total_time == 0) {
+    return 0;
+  } else {
+    return static_cast<int>((static_cast<double>(gc_time) /
+                             static_cast<double>(total_time))*100);
+  }
+}
+
 }  // namespace dart