Optimize ClearNonLiveReferences: do not compact prototype transitions in GC.

src/transitions.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/transitions.h"
 
 #include "src/objects-inl.h"
 #include "src/transitions-inl.h"
 #include "src/utils.h"
 
@@ skipping 216 matching lines @@
   Object* raw_transitions = map->raw_transitions();
   if (IsFullTransitionArray(raw_transitions)) {
     TransitionArray* transitions = TransitionArray::cast(raw_transitions);
     return transitions->number_of_transitions() < kMaxNumberOfTransitions;
   }
   return true;
 }
 
 
 // static
+bool TransitionArray::CompactPrototypeTransitionArray(FixedArray* array) {
+  const int header = kProtoTransitionHeaderSize;
+  int number_of_transitions = NumberOfPrototypeTransitions(array);
+  if (number_of_transitions == 0) {
+    // Empty array cannot be compacted.
+    return false;
+  }
+  int new_number_of_transitions = 0;
+  for (int i = 0; i < number_of_transitions; i++) {
+    Object* cell = array->get(header + i);
+    if (!WeakCell::cast(cell)->cleared()) {
+      if (new_number_of_transitions != i) {
+        array->set(header + new_number_of_transitions, cell);
+      }
+      new_number_of_transitions++;
+    }
+  }
+  // Fill slots that became free with undefined value.
+  for (int i = new_number_of_transitions; i < number_of_transitions; i++) {
+    array->set_undefined(header + i);
+  }
+  if (number_of_transitions != new_number_of_transitions) {
+    SetNumberOfPrototypeTransitions(array, new_number_of_transitions);
+  }
+  return new_number_of_transitions < number_of_transitions;
+}
+
+
+// static
+Handle<FixedArray> TransitionArray::GrowPrototypeTransitionArray(
+    Handle<FixedArray> array, int new_capacity, Isolate* isolate) {
+  // Grow array by factor 2 up to MaxCachedPrototypeTransitions.
+  int capacity = array->length() - kProtoTransitionHeaderSize;
+  new_capacity = Min(kMaxCachedPrototypeTransitions, new_capacity);
+  DCHECK_GT(new_capacity, capacity);
+  int grow_by = new_capacity - capacity;
+  array = isolate->factory()->CopyFixedArrayAndGrow(array, grow_by);
+  if (capacity < 0) {
+    // There was no prototype transitions array before, so the size
+    // couldn't be copied. Initialize it explicitly.
+    SetNumberOfPrototypeTransitions(*array, 0);
+  }
+  return array;
+}
+
+
+// static
+int TransitionArray::NumberOfPrototypeTransitionsForTest(Map* map) {
+  FixedArray* transitions = GetPrototypeTransitions(map);
+  CompactPrototypeTransitionArray(transitions);
+  return TransitionArray::NumberOfPrototypeTransitions(transitions);
+}
+
+
+// static
 void TransitionArray::PutPrototypeTransition(Handle<Map> map,
                                              Handle<Object> prototype,
                                              Handle<Map> target_map) {
   DCHECK(HeapObject::cast(*prototype)->map()->IsMap());
   // Don't cache prototype transition if this map is either shared, or a map of
   // a prototype.
   if (map->is_prototype_map()) return;
   if (map->is_dictionary_map() || !FLAG_cache_prototype_transitions) return;
 
   const int header = kProtoTransitionHeaderSize;
 
   Handle<WeakCell> target_cell = Map::WeakCellForMap(target_map);
 
   Handle<FixedArray> cache(GetPrototypeTransitions(*map));
   int capacity = cache->length() - header;
   int transitions = NumberOfPrototypeTransitions(*cache) + 1;
 
   if (transitions > capacity) {
-    // Grow array by factor 2 up to MaxCachedPrototypeTransitions.
-    int new_capacity = Min(kMaxCachedPrototypeTransitions, transitions * 2);
-    if (new_capacity == capacity) return;
-    int grow_by = new_capacity - capacity;
-
-    Isolate* isolate = map->GetIsolate();
-    cache = isolate->factory()->CopyFixedArrayAndGrow(cache, grow_by);
-    if (capacity < 0) {
-      // There was no prototype transitions array before, so the size
-      // couldn't be copied. Initialize it explicitly.
-      SetNumberOfPrototypeTransitions(*cache, 0);
+    // Grow the array if compacting it doesn't free space.
+    if (!CompactPrototypeTransitionArray(*cache)) {
+      if (capacity == kMaxCachedPrototypeTransitions) return;
+      cache = GrowPrototypeTransitionArray(cache, 2 * transitions,
+                                           map->GetIsolate());
+      SetPrototypeTransitions(map, cache);
     }
-
-    SetPrototypeTransitions(map, cache);
   }
 
-  // Reload number of transitions as GC might shrink them.
+  // Reload number of transitions as they might have been compacted.
   int last = NumberOfPrototypeTransitions(*cache);
   int entry = header + last;
 
   cache->set(entry, *target_cell);
   SetNumberOfPrototypeTransitions(*cache, last + 1);
 }
 
 
 // static
 Handle<Map> TransitionArray::GetPrototypeTransition(Handle<Map> map,
@@ skipping 98 matching lines @@
     // Transition arrays are not shared. When one is replaced, it should not
     // keep referenced objects alive, so we zap it.
     // When there is another reference to the array somewhere (e.g. a handle),
     // not zapping turns from a waste of memory into a source of crashes.
     ZapTransitionArray(old_transitions);
   }
   map->set_raw_transitions(new_transitions);
 }
 
 
-static void ZapPrototypeTransitions(Object* raw_transitions) {
-  DCHECK(TransitionArray::IsFullTransitionArray(raw_transitions));
-  TransitionArray* transitions = TransitionArray::cast(raw_transitions);
-  if (!transitions->HasPrototypeTransitions()) return;
-  FixedArray* proto_transitions = transitions->GetPrototypeTransitions();
-  MemsetPointer(proto_transitions->data_start(),
-                proto_transitions->GetHeap()->the_hole_value(),
-                proto_transitions->length());
-}
-
-
 void TransitionArray::SetPrototypeTransitions(
     Handle<Map> map, Handle<FixedArray> proto_transitions) {
   EnsureHasFullTransitionArray(map);
-  if (Heap::ShouldZapGarbage()) {
-    Object* raw_transitions = map->raw_transitions();
-    DCHECK(raw_transitions != *proto_transitions);
-    ZapPrototypeTransitions(raw_transitions);
-  }
   TransitionArray* transitions = TransitionArray::cast(map->raw_transitions());
   transitions->SetPrototypeTransitions(*proto_transitions);
 }
 
 
 void TransitionArray::EnsureHasFullTransitionArray(Handle<Map> map) {
   Object* raw_transitions = map->raw_transitions();
   if (IsFullTransitionArray(raw_transitions)) return;
   int nof = IsSimpleTransition(raw_transitions) ? 1 : 0;
   Handle<TransitionArray> result = Allocate(map->GetIsolate(), nof);
@@ skipping 18 matching lines @@
                                                      TraverseCallback callback,
                                                      void* data) {
   Object* raw_transitions = map->raw_transitions();
   if (IsFullTransitionArray(raw_transitions)) {
     TransitionArray* transitions = TransitionArray::cast(raw_transitions);
     if (transitions->HasPrototypeTransitions()) {
       FixedArray* proto_trans = transitions->GetPrototypeTransitions();
       for (int i = 0; i < NumberOfPrototypeTransitions(proto_trans); ++i) {
         int index = TransitionArray::kProtoTransitionHeaderSize + i;
         WeakCell* cell = WeakCell::cast(proto_trans->get(index));
-        TraverseTransitionTreeInternal(Map::cast(cell->value()), callback,
-                                       data);
+        if (!cell->cleared()) {
+          TraverseTransitionTreeInternal(Map::cast(cell->value()), callback,
+                                         data);
+        }
       }
     }
     for (int i = 0; i < transitions->number_of_transitions(); ++i) {
       TraverseTransitionTreeInternal(transitions->GetTarget(i), callback, data);
     }
   } else if (IsSimpleTransition(raw_transitions)) {
     TraverseTransitionTreeInternal(GetSimpleTransition(raw_transitions),
                                    callback, data);
   }
   callback(map, data);
@@ skipping 57 matching lines @@
                             PropertyAttributes attributes,
                             int* out_insertion_index) {
   int transition = SearchName(name, out_insertion_index);
   if (transition == kNotFound) {
     return kNotFound;
   }
   return SearchDetails(transition, kind, attributes, out_insertion_index);
 }
 }  // namespace internal
 }  // namespace v8