Implement progress bar for large objects.

src/incremental-marking.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 170 matching lines @@
     MarkBit mark_bit = Marking::MarkBitFrom(HeapObject::cast(obj));
     if (Marking::IsBlack(mark_bit)) {
       MemoryChunk::IncrementLiveBytesFromGC(heap_obj->address(),
                                             -heap_obj->Size());
     }
     Marking::AnyToGrey(mark_bit);
   }
 }
 
 
+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);
 
     // We will mark cache black with a separate pass
     // when we finish marking.
     MarkObjectGreyDoNotEnqueue(context->normalized_map_cache());
     VisitNativeContext(map, context);
   }
 
   static void VisitJSWeakMap(Map* map, HeapObject* object) {
@@ skipping 16 matching lines @@
   INLINE(static void VisitPointers(Heap* heap, Object** start, Object** end)) {
     for (Object** p = start; p < end; p++) {
       Object* obj = *p;
       if (obj->NonFailureIsHeapObject()) {
         heap->mark_compact_collector()->RecordSlot(start, p, obj);
         MarkObject(heap, obj);
       }
     }
   }
 
+  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);
     }
   }
 
   // Marks the object black without pushing it on the marking stack.
   // Returns true if object needed marking and false otherwise.
   INLINE(static bool MarkObjectWithoutPush(Heap* heap, Object* obj)) {
     HeapObject* heap_object = HeapObject::cast(obj);
     MarkBit mark_bit = Marking::MarkBitFrom(heap_object);
@@ skipping 25 matching lines @@
   }
 
  private:
   void MarkObjectByPointer(Object** p) {
     Object* obj = *p;
     if (!obj->IsHeapObject()) return;
 
     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);
       }
     }
   }
 
   Heap* heap_;
   IncrementalMarking* incremental_marking_;
 };
@@ skipping 304 matching lines @@
 #endif
       }
     } else if (obj->map() != filler_map) {
       // Skip one word filler objects that appear on the
       // stack when we perform in place array shift.
       array[new_top] = obj;
       new_top = ((new_top + 1) & mask);
       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
     }
   }
   marking_deque_.set_top(new_top);
 
   steps_took_since_last_gc_ = 0;
   steps_count_since_last_gc_ = 0;
   longest_step_ = 0.0;
 }
 
 
 void IncrementalMarking::VisitObject(Map* map, HeapObject* obj, int size) {
   MarkBit map_mark_bit = Marking::MarkBitFrom(map);
   if (Marking::IsWhite(map_mark_bit)) {
     WhiteToGreyAndPush(map, map_mark_bit);
   }
 
   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);
 }
 
 
 void IncrementalMarking::ProcessMarkingDeque(intptr_t bytes_to_process) {
   Map* filler_map = heap_->one_pointer_filler_map();
   while (!marking_deque_.IsEmpty() && bytes_to_process > 0) {
     HeapObject* obj = marking_deque_.Pop();
 
     // Explicitly skip one word fillers. Incremental markbit patterns are
     // correct only for objects that occupy at least two words.
@@ skipping 265 matching lines @@
   bytes_scanned_ = 0;
   write_barriers_invoked_since_last_step_ = 0;
 }
 
 
 int64_t IncrementalMarking::SpaceLeftInOldSpace() {
   return heap_->MaxOldGenerationSize() - heap_->PromotedSpaceSizeOfObjects();
 }
 
 } }  // namespace v8::internal