Add prototype transitions cache to Map.

src/objects.cc

 // Copyright 2011 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 6865 matching lines @@
   { MaybeObject* maybe_obj = GetHeap()->AllocateFixedArray(1);
     if (!maybe_obj->ToObject(&obj)) return maybe_obj;
   }
   FixedArray::cast(obj)->set(0, len);
   if (IsJSArray()) JSArray::cast(this)->set_length(Smi::FromInt(1));
   set_elements(FixedArray::cast(obj));
   return this;
 }
 
 
+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();
   // Silently ignore the change if value is not a JSObject or null.
   // SpiderMonkey behaves this way.
   if (!value->IsJSObject() && !value->IsNull()) return value;
 
   // From 8.6.2 Object Internal Methods
   // ...
   // In addition, if [[Extensible]] is false the value of the [[Class]] and
@@ skipping 30 matching lines @@
     // hidden and set the new prototype on that object.
     Object* current_proto = real_receiver->GetPrototype();
     while (current_proto->IsJSObject() &&
           JSObject::cast(current_proto)->map()->is_hidden_prototype()) {
       real_receiver = JSObject::cast(current_proto);
       current_proto = current_proto->GetPrototype();
     }
   }
 
   // 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();
 
   return value;
 }
 
 
 bool JSObject::HasElementPostInterceptor(JSObject* receiver, uint32_t index) {
   switch (GetElementsKind()) {
@@ skipping 3415 matching lines @@
   if (break_point_objects()->IsUndefined()) return 0;
   // Single beak point.
   if (!break_point_objects()->IsFixedArray()) return 1;
   // Multiple break points.
   return FixedArray::cast(break_point_objects())->length();
 }
 #endif
 
 
 } }  // namespace v8::internal