Add prototype transitions cache to Map.

src/objects.cc

Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index c3a900d0dc8b655356a5bb5f69dded0de548d159..a069f195a59af7565e765a32482125c19ad4e95d 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -6883,6 +6883,46 @@ MaybeObject* JSObject::SetElementsLength(Object* len) {
 }
 
 
+Object* Map::GetPrototypeTransition(Object* prototype) {
+  FixedArray* cache = prototype_transitions();
+  int capacity = cache->length();
+  if (capacity == 0) return NULL;
+  int finger = Smi::cast(cache->get(0))->value();
+  for (int i = 1; i < finger; i += 2) {
+    if (cache->get(i) == prototype) return cache->get(i + 1);
+  }
+  return NULL;
+}
+
+
+MaybeObject* Map::PutPrototypeTransition(Object* prototype, Map* map) {
+  // Don't cache prototype transition if this map is shared.
+  if (is_shared() || !FLAG_cache_prototype_transitions) return this;
+
+  FixedArray* cache = prototype_transitions();
+
+  int capacity = cache->length();
+  int finger = (capacity == 0) ? 1 : Smi::cast(cache->get(0))->value();
+
+  if (finger >= capacity) {

[Mads Ager (chromium), 2011/04/26 09:14:23]

I think we want to put a limit on the number of prototype transitions that we
want to cache. In particular since we are doing linear search.

+    FixedArray* new_cache;
+    { MaybeObject* maybe_cache = heap()->AllocateFixedArray(finger * 2 + 1);
+      if (!maybe_cache->To<FixedArray>(&new_cache)) return maybe_cache;
+    }
+
+    for (int i = 1; i < capacity; i++) new_cache->set(i, cache->get(i));
+    cache = new_cache;
+    set_prototype_transitions(cache);
+  }
+
+  cache->set(finger, prototype);
+  cache->set(finger + 1, map);
+  cache->set(0, Smi::FromInt(finger + 2));
+
+  return cache;
+}
+
+
 MaybeObject* JSObject::SetPrototype(Object* value,
                                     bool skip_hidden_prototypes) {
   Heap* heap = GetHeap();
@@ -6933,11 +6973,25 @@ MaybeObject* JSObject::SetPrototype(Object* value,
   }
 
   // Set the new prototype of the object.
-  Object* new_map;
-  { MaybeObject* maybe_new_map = real_receiver->map()->CopyDropTransitions();
-    if (!maybe_new_map->ToObject(&new_map)) return maybe_new_map;
+  Map* map = real_receiver->map();
+
+  // Nothing to do if prototype is already set.
+  if (map->prototype() == value) return value;
+
+  Object* new_map = map->GetPrototypeTransition(value);
+  if (new_map == NULL) {
+    { MaybeObject* maybe_new_map = map->CopyDropTransitions();
+      if (!maybe_new_map->ToObject(&new_map)) return maybe_new_map;
+    }
+
+    { MaybeObject* maybe_new_cache =
+          map->PutPrototypeTransition(value, Map::cast(new_map));
+      if (maybe_new_cache->IsFailure()) return maybe_new_cache;
+    }
+
+    Map::cast(new_map)->set_prototype(value);
   }
-  Map::cast(new_map)->set_prototype(value);
+  ASSERT(Map::cast(new_map)->prototype() == value);
   real_receiver->set_map(Map::cast(new_map));
 
   heap->ClearInstanceofCache();