Initial idle GC logic.

runtime/vm/scavenger.cc

 // Copyright (c) 2011, 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/scavenger.h"
 
 #include "vm/dart.h"
 #include "vm/dart_api_state.h"
 #include "vm/isolate.h"
 #include "vm/lockers.h"
@@ skipping 305 matching lines @@
 Scavenger::Scavenger(Heap* heap,
                      intptr_t max_semi_capacity_in_words,
                      uword object_alignment)
     : heap_(heap),
       max_semi_capacity_in_words_(max_semi_capacity_in_words),
       object_alignment_(object_alignment),
       scavenging_(false),
       delayed_weak_properties_(NULL),
       gc_time_micros_(0),
       collections_(0),
+      scavenge_words_per_micro_(400),
+      idle_scavenge_threshold_in_words_(0),
       external_size_(0),
       failed_to_promote_(false) {
   // Verify assumptions about the first word in objects which the scavenger is
   // going to use for forwarding pointers.
   ASSERT(Object::tags_offset() == 0);
 
   // Set initial size resulting in a total of three different levels.
   const intptr_t initial_semi_capacity_in_words =
       max_semi_capacity_in_words /
       (FLAG_new_gen_growth_factor * FLAG_new_gen_growth_factor);
 
   const intptr_t kVmNameSize = 128;
   char vm_name[kVmNameSize];
   Heap::RegionName(heap_, Heap::kNew, vm_name, kVmNameSize);
   to_ = SemiSpace::New(initial_semi_capacity_in_words, vm_name);
   if (to_ == NULL) {
     OUT_OF_MEMORY();
   }
   // Setup local fields.
   top_ = FirstObjectStart();
   resolved_top_ = top_;
   end_ = to_->end();
 
   survivor_end_ = FirstObjectStart();
+  idle_scavenge_threshold_in_words_ = initial_semi_capacity_in_words;
 
   UpdateMaxHeapCapacity();
   UpdateMaxHeapUsage();
 }
 
 Scavenger::~Scavenger() {
   ASSERT(!scavenging_);
   to_->Delete();
 }
 
@@ skipping 60 matching lines @@
     avg_frac /= 1.0 + 0.5;  // Normalize.
   }
   if (avg_frac < (FLAG_early_tenuring_threshold / 100.0)) {
     // Remember the limit to which objects have been copied.
     survivor_end_ = top_;
   } else {
     // Move survivor end to the end of the to_ space, making all surviving
     // objects candidates for promotion next time.
     survivor_end_ = end_;
   }
+
+  // Update estimate of scavenger speed. This statistic assumes survivorship
+  // rates don't change much.
+  intptr_t history_used = 0;
+  intptr_t history_micros = 0;
+  ASSERT(stats_history_.Size() > 0);
+  for (intptr_t i = 0; i < stats_history_.Size(); i++) {
+    history_used += stats_history_.Get(i).UsedBeforeInWords();
+    history_micros += stats_history_.Get(i).DurationMicros();
+  }
+  if (history_micros == 0) {
+    history_micros = 1;
+  }
+  scavenge_words_per_micro_ = history_used / history_micros;
+  if (scavenge_words_per_micro_ == 0) {
+    scavenge_words_per_micro_ = 1;
+  }
+
+  // Update amount of new-space we must allocate before performing an idle
+  // scavenge. This is based on the amount of work we expect to be able to
+  // complete in a typical idle period.
+  intptr_t average_idle_task_micros = 4000;
+  idle_scavenge_threshold_in_words_ =
+      scavenge_words_per_micro_ * average_idle_task_micros;
+  // Even if the scavenge speed is slow, make sure we don't scavenge too
+  // frequently, which just wastes power and falsely increases the promotion
+  // rate.
+  intptr_t lower_bound = 512 * KBInWords;
+  if (idle_scavenge_threshold_in_words_ < lower_bound) {
+    idle_scavenge_threshold_in_words_ = lower_bound;
+  }
+  // Even if the scavenge speed is very high, make sure we start considering
+  // idle scavenges before new space is full to avoid requiring a scavenge in
+  // the middle of a frame.
+  intptr_t upper_bound = 8 * CapacityInWords() / 10;
+  if (idle_scavenge_threshold_in_words_ > upper_bound) {
+    idle_scavenge_threshold_in_words_ = upper_bound;
+  }
+
 #if defined(DEBUG)
   // We can only safely verify the store buffers from old space if there is no
   // concurrent old space task. At the same time we prevent new tasks from
   // being spawned.
   {
     PageSpace* page_space = heap_->old_space();
     MonitorLocker ml(page_space->tasks_lock());
     if (page_space->tasks() == 0) {
       VerifyStoreBufferPointerVisitor verify_store_buffer_visitor(isolate, to_);
       heap_->old_space()->VisitObjectPointers(&verify_store_buffer_visitor);
     }
   }
 #endif  // defined(DEBUG)
   from->Delete();
   UpdateMaxHeapUsage();
   if (heap_ != NULL) {
     heap_->UpdateGlobalMaxUsed();
   }
 }
 
+bool Scavenger::ShouldPerformIdleScavenge(int64_t deadline) {
+  // TODO(rmacnak): Investigate collecting a history of idle period durations.
+  intptr_t used_in_words = UsedInWords();
+  if (used_in_words < idle_scavenge_threshold_in_words_) {
+    return false;
+  }
+  int64_t estimated_scavenge_completion =
+      OS::GetCurrentMonotonicMicros() +
+      used_in_words / scavenge_words_per_micro_;
+  return estimated_scavenge_completion <= deadline;
+}
+
 void Scavenger::IterateStoreBuffers(Isolate* isolate,
                                     ScavengerVisitor* visitor) {
   // Iterating through the store buffers.
   // Grab the deduplication sets out of the isolate's consolidated store buffer.
   StoreBufferBlock* pending = isolate->store_buffer()->Blocks();
   intptr_t total_count = 0;
   while (pending != NULL) {
     StoreBufferBlock* next = pending->next();
     // Generated code appends to store buffers; tell MemorySanitizer.
     MSAN_UNPOISON(pending, sizeof(*pending));
@@ skipping 308 matching lines @@
 }
 
 void Scavenger::Scavenge() {
   Isolate* isolate = heap_->isolate();
   // Ensure that all threads for this isolate are at a safepoint (either stopped
   // or in native code). If two threads are racing at this point, the loser
   // will continue with its scavenge after waiting for the winner to complete.
   // TODO(koda): Consider moving SafepointThreads into allocation failure/retry
   // logic to avoid needless collections.
 
-  int64_t pre_safe_point = OS::GetCurrentMonotonicMicros();
+  int64_t start = OS::GetCurrentMonotonicMicros();
 
   Thread* thread = Thread::Current();
   SafepointOperationScope safepoint_scope(thread);
 
   // Scavenging is not reentrant. Make sure that is the case.
   ASSERT(!scavenging_);
   scavenging_ = true;
 
   failed_to_promote_ = false;
 
   PageSpace* page_space = heap_->old_space();
   NoSafepointScope no_safepoints;
 
-  int64_t post_safe_point = OS::GetCurrentMonotonicMicros();
-  heap_->RecordTime(kSafePoint, post_safe_point - pre_safe_point);
+  int64_t safe_point = OS::GetCurrentMonotonicMicros();
+  heap_->RecordTime(kSafePoint, safe_point - start);
 
   // TODO(koda): Make verification more compatible with concurrent sweep.
   if (FLAG_verify_before_gc && !FLAG_concurrent_sweep) {
     OS::PrintErr("Verifying before Scavenge...");
     heap_->Verify(kForbidMarked);
     OS::PrintErr(" done.\n");
   }
 
   // Prepare for a scavenge.
   SpaceUsage usage_before = GetCurrentUsage();
   intptr_t promo_candidate_words =
       (survivor_end_ - FirstObjectStart()) / kWordSize;
   SemiSpace* from = Prologue(isolate);
   // The API prologue/epilogue may create/destroy zones, so we must not
   // depend on zone allocations surviving beyond the epilogue callback.
   {
     StackZone zone(thread);
     // Setup the visitor and run the scavenge.
     ScavengerVisitor visitor(isolate, this, from);
     page_space->AcquireDataLock();
     IterateRoots(isolate, &visitor);
-    int64_t start = OS::GetCurrentMonotonicMicros();
+    int64_t iterate_roots = OS::GetCurrentMonotonicMicros();
     ProcessToSpace(&visitor);
-    int64_t middle = OS::GetCurrentMonotonicMicros();
+    int64_t process_to_space = OS::GetCurrentMonotonicMicros();
     {
       TIMELINE_FUNCTION_GC_DURATION(thread, "WeakHandleProcessing");
       ScavengerWeakVisitor weak_visitor(thread, this);
       IterateWeakRoots(isolate, &weak_visitor);
     }
     ProcessWeakReferences();
     page_space->ReleaseDataLock();
 
     // Scavenge finished. Run accounting.
     int64_t end = OS::GetCurrentMonotonicMicros();
-    heap_->RecordTime(kProcessToSpace, middle - start);
-    heap_->RecordTime(kIterateWeaks, end - middle);
+    heap_->RecordTime(kProcessToSpace, process_to_space - iterate_roots);
+    heap_->RecordTime(kIterateWeaks, end - process_to_space);
     stats_history_.Add(ScavengeStats(
         start, end, usage_before, GetCurrentUsage(), promo_candidate_words,
         visitor.bytes_promoted() >> kWordSizeLog2));
   }
   Epilogue(isolate, from);
 
   // TODO(koda): Make verification more compatible with concurrent sweep.
   if (FLAG_verify_after_gc && !FLAG_concurrent_sweep) {
     OS::PrintErr("Verifying after Scavenge...");
     heap_->Verify(kForbidMarked);
@@ skipping 69 matching lines @@
   }
 
   Scavenge();
 
   // It is possible for objects to stay in the new space
   // if the VM cannot create more pages for these objects.
   ASSERT((UsedInWords() == 0) || failed_to_promote_);
 }
 
 }  // namespace dart