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

runtime/vm/pages.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/pages.h"
 
 #include "platform/assert.h"
 #include "vm/gc_marker.h"
 #include "vm/gc_sweeper.h"
 #include "vm/object.h"
 #include "vm/virtual_memory.h"
 
 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);
 
   HeapPage* result = reinterpret_cast<HeapPage*>(memory->address());
   result->memory_ = memory;
   result->next_ = NULL;
   result->used_ = 0;
   result->top_ = result->first_object_start();
   return result;
@@ skipping 32 matching lines @@
     if (raw_obj->FindObject(visitor)) {
       return raw_obj;  // Found object, return it.
     }
     obj_addr += raw_obj->Size();
   }
   ASSERT(obj_addr == end_addr);
   return Object::null();
 }
 
 
-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),
       pages_tail_(NULL),
       large_pages_(NULL),
       bump_page_(NULL),
       max_capacity_(max_capacity),
       capacity_(0),
       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() {
   FreePages(pages_);
   FreePages(large_pages_);
 }
 
 
 intptr_t PageSpace::LargePageSizeFor(intptr_t size) {
   intptr_t page_size = Utils::RoundUp(size + sizeof(HeapPage),
@@ skipping 90 matching lines @@
 
 
 uword PageSpace::TryAllocate(intptr_t size) {
   ASSERT(size >= kObjectAlignment);
   ASSERT(Utils::IsAligned(size, kObjectAlignment));
   uword result = 0;
   if (size < kAllocatablePageSize) {
     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);
       }
     }
   } else {
     // Large page allocation.
     intptr_t page_size = LargePageSizeFor(size);
     if (page_size < size) {
       // On overflow we fail to allocate.
@@ skipping 80 matching lines @@
   NoHandleScope no_handles(isolate);
 
   if (FLAG_verify_before_gc) {
     OS::PrintErr("Verifying before MarkSweep... ");
     heap_->Verify();
     OS::PrintErr(" done.\n");
   }
 
   Timer timer(FLAG_verbose_gc, "MarkSweep");
   timer.Start();
+  int64_t start = OS::GetCurrentTimeMillis();
 
   // Mark all reachable old-gen objects.
   GCMarker marker(heap_);
   marker.MarkObjects(isolate, this, invoke_api_callbacks);
 
   // Reset the bump allocation page to unused.
   bump_page_ = NULL;
   // Reset the freelists and setup sweeping.
   freelist_.Reset();
   GCSweeper sweeper(heap_);
@@ skipping 23 matching lines @@
       FreeLargePage(page, prev_page);
     } else {
       in_use += page_in_use;
       prev_page = page;
     }
     // Advance to the next page.
     page = next_page;
   }
 
   // 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();
   if (FLAG_verbose_gc) {
     const intptr_t KB2 = KB / 2;
     OS::PrintErr("Mark-Sweep[%d]: %lldus (%dK -> %dK, %dK)\n",
                  count_,
                  timer.TotalElapsedTime(),
                  (in_use_before + (KB2)) / KB,
                  (in_use + (KB2)) / KB,
                  (capacity_ + KB2) / KB);
   }
 
   if (FLAG_verify_after_gc) {
     OS::PrintErr("Verifying after MarkSweep... ");
     heap_->Verify();
     OS::PrintErr(" done.\n");
   }
 
   count_++;
   // Done, reset the marker.
   ASSERT(sweeping_);
   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