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

runtime/vm/pages.h

 // 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.
 
 #ifndef VM_PAGES_H_
 #define VM_PAGES_H_
 
 #include "vm/freelist.h"
 #include "vm/globals.h"
 #include "vm/virtual_memory.h"
@@ skipping 58 matching lines @@
   uword used_;
   uword top_;
 
   friend class PageSpace;
 
   DISALLOW_ALLOCATION();
   DISALLOW_IMPLICIT_CONSTRUCTORS(HeapPage);
 };
 
 
+// The history holds the timing information of the last garbage collection
+// runs.
+class PageSpaceGarbageCollectionHistory {
+ public:
+  PageSpaceGarbageCollectionHistory();
+  ~PageSpaceGarbageCollectionHistory() {}
+
+  void AddGarbageCollectionTime(uint64_t start, uint64_t end);
+
+  int GarbageCollectionTimeFraction();
+
+ private:
+  static const uint32_t kHistoryLength = 16;

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

I have the feeling (no data) that this longish history will lead to being too
slow to react to changes.

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

I have set this back to 4.  I think 4 is too short of a kernel.  I am not sure
what the right value is without more data.  However, a single spike in the data
will contribute too much to the time threshold whereas a longer history has more
smoothing.  Too much history is not good.

A compromise would be to not abort the averaging when the buffer is partially
filled.

+  uint64_t start_[kHistoryLength];
+  uint64_t end_[kHistoryLength];
+  uint32_t index_;
+
+  DISALLOW_ALLOCATION();
+  DISALLOW_COPY_AND_ASSIGN(PageSpaceGarbageCollectionHistory);
+};
+
+
+// If GC is able to reclaim more than heap_growth_ratio (in percent) memory
+// and if the relative GC time is below a given threshold,
+// then the heap is not grown when the next GC decision is made.
+// PageSpaceController controls the heap size.
+class PageSpaceController {
+ public:
+  PageSpaceController(int heap_growth_ratio,
+                      int heap_growth_rate,
+                      int garbage_collection_time_ratio);
+  ~PageSpaceController();
+
+  bool CanGrowPageSpace();

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

Maybe this should be dependent on the amount of memory requested?

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

Done.

+
+  // A garbage collection is considered as successful if more than
+  // heap_growth_ratio % of memory got deallocated by the garbage collector.
+  // In this case garbage collection will be performed next time. Otherwise
+  // the heap will grow.
+  void EvaluateGarbageCollection(size_t in_use_before, size_t in_use_after,
+                                 int64_t start, int64_t end);
+
+ private:
+  // Heap growth control variable.
+  uword grow_heap_;
+
+  // If the garbage collector was not able to free more than heap_growth_ratio_
+  // memory, then the heap is grown. Otherwise garbage collection is performed.
+  int heap_growth_ratio_;
+
+  // Number of pages we grow.
+  int heap_growth_rate_;
+
+  // If the relative GC time stays below garbage_collection_time_ratio_
+  // garbage collection can be performed.
+  int garbage_collection_time_ratio_;
+
+  PageSpaceGarbageCollectionHistory history_;
+
+  DISALLOW_IMPLICIT_CONSTRUCTORS(PageSpaceController);
+};
+
+
 class PageSpace {
  public:
   // TODO(iposva): Determine heap sizes and tune the page size accordingly.
   static const intptr_t kPageSize = 256 * KB;
   static const intptr_t kPageAlignment = kPageSize;
 
-  PageSpace(Heap* heap, intptr_t max_capacity, bool is_executable = false);
+  PageSpace(Heap* heap,

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

?

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

Noise.  Done.

+            intptr_t max_capacity,
+            bool is_executable = false);
   ~PageSpace();
 
   uword TryAllocate(intptr_t size);
 
   intptr_t in_use() const { return in_use_; }
   intptr_t capacity() const { return capacity_; }
 
   bool Contains(uword addr) const;
   bool IsValidAddress(uword addr) const {
     return Contains(addr);
   }
   static bool IsPageAllocatableSize(intptr_t size) {
     return size <= kAllocatablePageSize;
   }
 
   void VisitObjectPointers(ObjectPointerVisitor* visitor) const;
 
   RawObject* FindObject(FindObjectVisitor* visitor) const;
 
   // Collect the garbage in the page space using mark-sweep.
   void MarkSweep(bool invoke_api_callbacks);
 
   static HeapPage* PageFor(RawObject* raw_obj) {
     return reinterpret_cast<HeapPage*>(
         RawObject::ToAddr(raw_obj) & ~(kPageSize -1));
   }
 
+  void EnableGrowthControl() {
+    is_growth_controlled_ = true;
+  }
+
  private:
   static const intptr_t kAllocatablePageSize = kPageSize - sizeof(HeapPage);
 
   void AllocatePage();
   void FreePage(HeapPage* page, HeapPage* previous_page);
   HeapPage* AllocateLargePage(intptr_t size);
   void FreeLargePage(HeapPage* page, HeapPage* previous_page);
   void FreePages(HeapPage* pages);
 
   static intptr_t LargePageSizeFor(intptr_t size);
@@ skipping 26 matching lines @@
   intptr_t in_use_;
 
   // Old-gen GC cycle count.
   int count_;
 
   bool is_executable_;
 
   // Keep track whether a MarkSweep is currently running.
   bool sweeping_;
 
+  // True if the page space controller regulates heap growth.
+  bool is_growth_controlled_;

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

How about tracking this in the controller itself?

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

Sure.  Done.

+
+  PageSpaceController page_space_controller_;
+
   DISALLOW_IMPLICIT_CONSTRUCTORS(PageSpace);
 };
 
 }  // namespace dart
 
 #endif  // VM_PAGES_H_