Implement progress bar for large objects.

src/incremental-marking.cc

Index: src/incremental-marking.cc
diff --git a/src/incremental-marking.cc b/src/incremental-marking.cc
index b34d6d902c8a59761d4578a1722df83410dc4993..2ee3ebf601906eea4e8e737f69bee078b1ae60c0 100644
--- a/src/incremental-marking.cc
+++ b/src/incremental-marking.cc
@@ -188,16 +188,71 @@ static void MarkObjectGreyDoNotEnqueue(Object* obj) {
 }
 
 
+static inline void MarkBlackOrKeepGrey(HeapObject* heap_object,
+                                       MarkBit mark_bit,
+                                       int size) {
+  ASSERT(!Marking::IsImpossible(mark_bit));
+  if (mark_bit.Get()) return;
+  mark_bit.Set();
+  MemoryChunk::IncrementLiveBytesFromGC(heap_object->address(), size);
+  ASSERT(Marking::IsBlack(mark_bit));
+}
+
+
+static inline void MarkBlackOrKeepBlack(HeapObject* heap_object,
+                                        MarkBit mark_bit,
+                                        int size) {
+  ASSERT(!Marking::IsImpossible(mark_bit));
+  if (Marking::IsBlack(mark_bit)) return;
+  Marking::MarkBlack(mark_bit);
+  MemoryChunk::IncrementLiveBytesFromGC(heap_object->address(), size);
+  ASSERT(Marking::IsBlack(mark_bit));
+}
+
+
 class IncrementalMarkingMarkingVisitor
     : public StaticMarkingVisitor<IncrementalMarkingMarkingVisitor> {
  public:
   static void Initialize() {
     StaticMarkingVisitor<IncrementalMarkingMarkingVisitor>::Initialize();
-
+    table_.Register(kVisitFixedArray, &VisitFixedArrayIncremental);
     table_.Register(kVisitNativeContext, &VisitNativeContextIncremental);
     table_.Register(kVisitJSRegExp, &VisitJSRegExp);
   }
 
+  static const int kProgressBarScanningChunk = 32 * 1024;
+
+  static void VisitFixedArrayIncremental(Map* map, HeapObject* object) {
+    MemoryChunk* chunk = MemoryChunk::FromAddress(object->address());
+    if (FLAG_use_progress_bar && chunk->owner()->identity() == LO_SPACE) {
+      Heap* heap = map->GetHeap();

[Hannes Payer (out of office), 2012/11/14 12:21:04]

can you set that flag earlier e.g. at allocation time?

[Michael Starzinger, 2012/11/15 15:12:50]

Yes, that would be cleaner. I just couldn't find a clean bottle-neck in the
allocation function. I'll try to find one.

[Michael Starzinger, 2012/11/15 17:54:51]

Left a TODO in the code about that. Currently there are just too many
bottle-necks that allocate a fixed array.

+      chunk->SetFlag(MemoryChunk::HAS_PROGRESS_BAR);
+      // When using a progress bar for large fixed arrays, scan only a chunk of
+      // the array and try to push it onto the marking deque again until it is
+      // fully scanned. Fall back to scanning it through to the end in case this
+      // fails because of a full deque.
+      bool scan_until_end = false;
+      int object_size = FixedArray::BodyDescriptor::SizeOf(map, object);
+      do {
+        int start_offset = Max(FixedArray::BodyDescriptor::kStartOffset,

[ulan, 2012/11/15 09:54:23]

Not sure if worthwhile as the loop rarely executes more than once: we could move
the initialization of start_offset and end_offset out of the loop, and at the
end of loop do: start_offset = end_offset, end_offset = Min(object_size,
end_offset + kProgressBarScanningChunk);
This would allow to get rid of chunk->progress_bar() accesses in the loop and do
chunk->set_progress_bar(end_offset) once after the loop.

[Michael Starzinger, 2012/11/15 15:12:50]

Done.

+                               chunk->progress_bar());
+        int end_offset = Min(object_size,
+                             chunk->progress_bar() + kProgressBarScanningChunk);

[ulan, 2012/11/15 09:54:23]

Shouldn't this be start_offset + kProgressBarScanningChunk ?

[Michael Starzinger, 2012/11/15 15:12:50]

Done.

+        chunk->set_progress_bar(end_offset);
+        VisitPointersWithAnchor(heap,
+                                HeapObject::RawField(object, 0),
+                                HeapObject::RawField(object, start_offset),
+                                HeapObject::RawField(object, end_offset));
+        scan_until_end = heap->incremental_marking()->marking_deque()->IsFull();
+        if (end_offset < object_size) {

[Hannes Payer (out of office), 2012/11/14 12:21:04]

why is this method called UnshiftGrey and not Unshift (or enqueue)?
Wouldn't it be better to push the object on the marking deque before we pop the
referenced objects? Doing that will keep the object closer to its referenced
objects.

[ulan, 2012/11/15 09:54:23]

(end_offset < object_size && !scan_until_end) would be more clear here.

[Michael Starzinger, 2012/11/15 15:12:50]

Done.

[Michael Starzinger, 2012/11/15 15:12:50]

The method is called UnshiftGrey because at the time the object is pushed, it is
supposed to be grey, which also holds in this case. If you call UnshiftBlack it
will do a black-to-grey transition if the marking deque is full to make sure it
gets added again once the marking deque is refilled.

I think pushing will not reduce pressure on the deque, because the large array
would stay in front of all reference objects all the time and the pressure
introduced by the references objects will not reduce until the large array is
fully scanned. So I think we should try to keep the large array at the end of
the marking deque. WDYT?

[Hannes Payer (out of office), 2012/11/15 16:25:54]

There is probably no performance difference, I just found it cleaner to have a
stack access pattern.

On 2012/11/15 15:12:50, Michael Starzinger wrote:

+          heap->incremental_marking()->marking_deque()->UnshiftGrey(object);
+        }
+      } while (scan_until_end && chunk->progress_bar() < object_size);
+    } else {
+      FixedArrayVisitor::Visit(map, object);
+    }
+  }
+
   static void VisitNativeContextIncremental(Map* map, HeapObject* object) {
     Context* context = Context::cast(object);
 
@@ -234,15 +289,25 @@ class IncrementalMarkingMarkingVisitor
     }
   }
 
+  INLINE(static void VisitPointersWithAnchor(Heap* heap,
+                                             Object** anchor,
+                                             Object** start,
+                                             Object** end)) {
+    for (Object** p = start; p < end; p++) {
+      Object* obj = *p;
+      if (obj->NonFailureIsHeapObject()) {
+        heap->mark_compact_collector()->RecordSlot(anchor, p, obj);
+        MarkObject(heap, obj);
+      }
+    }
+  }
+
   // Marks the object grey and pushes it on the marking stack.

[Hannes Payer (out of office), 2012/11/14 12:21:04]

update comment

[Michael Starzinger, 2012/11/15 15:12:50]

I think the comment still applies. I didn't change semantics of this, just moved
the incrementing of live-bytes into the helper method. The object is only marked
black if it's a data objects and that is just an optimization.

   INLINE(static void MarkObject(Heap* heap, Object* obj)) {
     HeapObject* heap_object = HeapObject::cast(obj);
     MarkBit mark_bit = Marking::MarkBitFrom(heap_object);
     if (mark_bit.data_only()) {
-      if (heap->incremental_marking()->MarkBlackOrKeepGrey(mark_bit)) {
-        MemoryChunk::IncrementLiveBytesFromGC(heap_object->address(),
-                                              heap_object->Size());
-      }
+      MarkBlackOrKeepGrey(heap_object, mark_bit, heap_object->Size());
     } else if (Marking::IsWhite(mark_bit)) {
       heap->incremental_marking()->WhiteToGreyAndPush(heap_object, mark_bit);
     }
@@ -288,10 +353,7 @@ class IncrementalMarkingRootMarkingVisitor : public ObjectVisitor {
     HeapObject* heap_object = HeapObject::cast(obj);
     MarkBit mark_bit = Marking::MarkBitFrom(heap_object);
     if (mark_bit.data_only()) {
-      if (incremental_marking_->MarkBlackOrKeepGrey(mark_bit)) {
-          MemoryChunk::IncrementLiveBytesFromGC(heap_object->address(),
-                                                heap_object->Size());
-      }
+      MarkBlackOrKeepGrey(heap_object, mark_bit, heap_object->Size());
     } else {
       if (Marking::IsWhite(mark_bit)) {
         incremental_marking_->WhiteToGreyAndPush(heap_object, mark_bit);
@@ -616,8 +678,11 @@ void IncrementalMarking::UpdateMarkingDequeAfterScavenge() {
       ASSERT(new_top != marking_deque_.bottom());
 #ifdef DEBUG
         MarkBit mark_bit = Marking::MarkBitFrom(obj);
+        MemoryChunk* chunk = MemoryChunk::FromAddress(obj->address());
         ASSERT(Marking::IsGrey(mark_bit) ||
-               (obj->IsFiller() && Marking::IsWhite(mark_bit)));
+               (obj->IsFiller() && Marking::IsWhite(mark_bit)) ||
+               (chunk->IsFlagSet(MemoryChunk::HAS_PROGRESS_BAR) &&
+                Marking::IsBlack(mark_bit)));
 #endif
     }
   }
@@ -637,11 +702,15 @@ void IncrementalMarking::VisitObject(Map* map, HeapObject* obj, int size) {
 
   IncrementalMarkingMarkingVisitor::IterateBody(map, obj);
 
-  MarkBit obj_mark_bit = Marking::MarkBitFrom(obj);
-  SLOW_ASSERT(Marking::IsGrey(obj_mark_bit) ||
-             (obj->IsFiller() && Marking::IsWhite(obj_mark_bit)));
-  Marking::MarkBlack(obj_mark_bit);
-  MemoryChunk::IncrementLiveBytesFromGC(obj->address(), size);
+  MarkBit mark_bit = Marking::MarkBitFrom(obj);
+#ifdef DEBUG
+  MemoryChunk* chunk = MemoryChunk::FromAddress(obj->address());
+  SLOW_ASSERT(Marking::IsGrey(mark_bit) ||
+              (obj->IsFiller() && Marking::IsWhite(mark_bit)) ||
+              (chunk->IsFlagSet(MemoryChunk::HAS_PROGRESS_BAR) &&
+               Marking::IsBlack(mark_bit)));
+#endif
+  MarkBlackOrKeepBlack(obj, mark_bit, size);
 }