Promoting elements transitions to their own field.

src/objects.cc

Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index a8b13405725c82b0424af4c88047604df45f2437..ea7435dd100f1cef11eceebd805af4d08efd3d57 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -628,7 +628,6 @@ MaybeObject* Object::GetProperty(Object* receiver,
           recvr, name, attributes);
     }
     case MAP_TRANSITION:
-    case ELEMENTS_TRANSITION:
     case CONSTANT_TRANSITION:
     case NULL_DESCRIPTOR:
       break;
@@ -1551,10 +1550,7 @@ MaybeObject* JSObject::AddFastProperty(String* name,
 
   // Element transitions are stored in the descriptor for property "", which is
   // not a identifier and should have forced a switch to slow properties above.
-  ASSERT(descriptor_index == DescriptorArray::kNotFound ||
-      old_descriptors->GetType(descriptor_index) != ELEMENTS_TRANSITION);
-  bool can_insert_transition = descriptor_index == DescriptorArray::kNotFound ||
-      old_descriptors->GetType(descriptor_index) == ELEMENTS_TRANSITION;
+  bool can_insert_transition = descriptor_index == DescriptorArray::kNotFound;
   bool allow_map_transition =
       can_insert_transition &&
       (isolate->context()->global_context()->object_function()->map() != map());
@@ -1572,7 +1568,8 @@ MaybeObject* JSObject::AddFastProperty(String* name,
     // Allocate new instance descriptors for the old map with map transition.
     MapTransitionDescriptor d(name, Map::cast(new_map), attributes);
     Object* r;
-    { MaybeObject* maybe_r = old_descriptors->CopyInsert(&d, KEEP_TRANSITIONS);
+    {

[danno, 2012/06/01 13:49:55]

nit: No need for this whitespace change.

[Toon Verwaest, 2012/06/04 09:17:48]

Done.

+      MaybeObject* maybe_r = old_descriptors->CopyInsert(&d, KEEP_TRANSITIONS);
       if (!maybe_r->ToObject(&r)) return maybe_r;
     }
     old_descriptors = DescriptorArray::cast(r);
@@ -1600,7 +1597,9 @@ MaybeObject* JSObject::AddFastProperty(String* name,
   }
   // We have now allocated all the necessary objects.
   // All the changes can be applied at once, so they are atomic.
-  map()->set_instance_descriptors(old_descriptors);
+  if (allow_map_transition) {
+    map()->set_instance_descriptors(old_descriptors);
+  }
   new_map->SetBackPointer(map());
   new_map->set_instance_descriptors(DescriptorArray::cast(new_descriptors));
   set_map(new_map);
@@ -2206,9 +2205,8 @@ Handle<Map> Map::FindTransitionedMap(MapHandleList* candidates) {
   if (IsTransitionableFastElementsKind(kind)) {
     while (CanTransitionToMoreGeneralFastElementsKind(kind, false)) {
       kind = GetNextMoreGeneralFastElementsKind(kind, false);
-      bool dummy = true;
       Handle<Map> maybe_transitioned_map =
-          MaybeNull(current_map->LookupElementsTransitionMap(kind, &dummy));
+          MaybeNull(current_map->LookupElementsTransitionMap(kind));
       if (maybe_transitioned_map.is_null()) break;
       if (ContainsMap(candidates, maybe_transitioned_map) &&
           (packed || !IsFastPackedElementsKind(kind))) {
@@ -2222,207 +2220,67 @@ Handle<Map> Map::FindTransitionedMap(MapHandleList* candidates) {
 }
 
 
-static Map* GetElementsTransitionMapFromDescriptor(Object* descriptor_contents,
-                                                   ElementsKind elements_kind) {
-  if (descriptor_contents->IsMap()) {
-    Map* map = Map::cast(descriptor_contents);
-    if (map->elements_kind() == elements_kind) {
-      return map;
-    }
-    return NULL;
-  }
-
-  FixedArray* map_array = FixedArray::cast(descriptor_contents);
-  for (int i = 0; i < map_array->length(); ++i) {
-    Object* current = map_array->get(i);
-    // Skip undefined slots, they are sentinels for reclaimed maps.
-    if (!current->IsUndefined()) {
-      Map* current_map = Map::cast(map_array->get(i));
-      if (current_map->elements_kind() == elements_kind) {
-        return current_map;
-      }
+static Map* FindClosestElementsTransition(Map* map, ElementsKind to_kind) {
+  Map* current_map = map;
+  int index = GetSequenceIndexFromFastElementsKind(map->elements_kind());
+  int to_index = GetSequenceIndexFromFastElementsKind(to_kind);
+  for (; index < to_index; ++index) {
+    Map* next_map = current_map->elements_transition();
+    if (next_map == NULL) {
+      return current_map;
     }
+    current_map = next_map;
   }
-
-  return NULL;
+  ASSERT(current_map->elements_kind() == to_kind);
+  return current_map;
 }
 
 
-static MaybeObject* AddElementsTransitionMapToDescriptor(
-    Object* descriptor_contents,
-    Map* new_map) {
-  // Nothing was in the descriptor for an ELEMENTS_TRANSITION,
-  // simply add the map.
-  if (descriptor_contents == NULL) {
-    return new_map;
-  }
-
-  // There was already a map in the descriptor, create a 2-element FixedArray
-  // to contain the existing map plus the new one.
-  FixedArray* new_array;
-  Heap* heap = new_map->GetHeap();
-  if (descriptor_contents->IsMap()) {
-    // Must tenure, DescriptorArray expects no new-space objects.
-    MaybeObject* maybe_new_array = heap->AllocateFixedArray(2, TENURED);
-    if (!maybe_new_array->To<FixedArray>(&new_array)) {
-      return maybe_new_array;
-    }
-    new_array->set(0, descriptor_contents);
-    new_array->set(1, new_map);
-    return new_array;
-  }
-
-  // The descriptor already contained a list of maps for different ElementKinds
-  // of ELEMENTS_TRANSITION, first check the existing array for an undefined
-  // slot, and if that's not available, create a FixedArray to hold the existing
-  // maps plus the new one and fill it in.
-  FixedArray* array = FixedArray::cast(descriptor_contents);
-  for (int i = 0; i < array->length(); ++i) {
-    if (array->get(i)->IsUndefined()) {
-      array->set(i, new_map);
-      return array;
+Map* Map::LookupElementsTransitionMap(ElementsKind to_kind) {
+  if (this->instance_descriptors()->MayContainTransitions() &&
+      IsMoreGeneralElementsKindTransition(this->elements_kind(), to_kind)) {
+    Map* to_map = FindClosestElementsTransition(this, to_kind);
+    if (to_map->elements_kind() == to_kind) {
+      return to_map;
     }
   }
-
-  // Must tenure, DescriptorArray expects no new-space objects.
-  MaybeObject* maybe_new_array =
-      heap->AllocateFixedArray(array->length() + 1, TENURED);
-  if (!maybe_new_array->To<FixedArray>(&new_array)) {
-    return maybe_new_array;
-  }
-  int i = 0;
-  while (i < array->length()) {
-    new_array->set(i, array->get(i));
-    ++i;
-  }
-  new_array->set(i, new_map);
-  return new_array;
+  return NULL;
 }
 
 
-String* Map::elements_transition_sentinel_name() {
-  return GetHeap()->empty_symbol();
-}
+MaybeObject* Map::CreateNextElementsTransition(ElementsKind next_kind) {
+    ASSERT(elements_transition() == NULL);
+    ASSERT(GetSequenceIndexFromFastElementsKind(elements_kind()) ==
+           (GetSequenceIndexFromFastElementsKind(next_kind) - 1));
 
+    Map* next_map;
+    MaybeObject* maybe_next_map = this->CopyDropTransitions(true);
+    if (!maybe_next_map->To(&next_map)) return maybe_next_map;
 
-Object* Map::GetDescriptorContents(String* sentinel_name,
-                                   bool* safe_to_add_transition) {
-  // Get the cached index for the descriptors lookup, or find and cache it.
-  DescriptorArray* descriptors = instance_descriptors();
-  DescriptorLookupCache* cache = GetIsolate()->descriptor_lookup_cache();
-  int index = cache->Lookup(descriptors, sentinel_name);
-  if (index == DescriptorLookupCache::kAbsent) {
-    index = descriptors->Search(sentinel_name);
-    cache->Update(descriptors, sentinel_name, index);
-  }
-  // If the transition already exists, return its descriptor.
-  if (index != DescriptorArray::kNotFound) {
-    PropertyDetails details = descriptors->GetDetails(index);
-    if (details.type() == ELEMENTS_TRANSITION) {
-      return descriptors->GetValue(index);
-    } else {
-      if (safe_to_add_transition != NULL) {
-        *safe_to_add_transition = false;
-      }
-    }
-  }
-  return NULL;
+    next_map->set_elements_kind(next_kind);
+    next_map->SetBackPointer(this);
+    this->set_elements_transition(next_map);
+    return next_map;
 }
 
 
-Map* Map::LookupElementsTransitionMap(ElementsKind to_kind,
-                                      bool* safe_to_add_transition) {
-  ElementsKind from_kind = elements_kind();
-  if (IsFastElementsKind(from_kind) && IsFastElementsKind(to_kind)) {
-    if (!IsMoreGeneralElementsKindTransition(from_kind, to_kind)) {
-      if (safe_to_add_transition) *safe_to_add_transition = false;
-      return NULL;
-    }
-    ElementsKind transitioned_from_kind =
-        GetNextMoreGeneralFastElementsKind(from_kind, false);
+static MaybeObject* AddMissingElementsTransitions(Map* map,
+                                                  ElementsKind to_kind) {
+  int index = GetSequenceIndexFromFastElementsKind(map->elements_kind()) + 1;
+  int to_index = GetSequenceIndexFromFastElementsKind(to_kind);
+  ASSERT(index <= to_index);
 
+  Map* current_map = map;
 
-    // If the transition is a single step in the transition sequence, fall
-    // through to looking it up and returning it. If it requires several steps,
-    // divide and conquer.
-    if (transitioned_from_kind != to_kind) {
-      // If the transition is several steps in the lattice, divide and conquer.
-      Map* from_map = LookupElementsTransitionMap(transitioned_from_kind,
-                                                  safe_to_add_transition);
-      if (from_map == NULL) return NULL;
-      return from_map->LookupElementsTransitionMap(to_kind,
-                                                   safe_to_add_transition);
-    }
-  }
-  Object* descriptor_contents = GetDescriptorContents(
-      elements_transition_sentinel_name(), safe_to_add_transition);
-  if (descriptor_contents != NULL) {
-    Map* maybe_transition_map =
-        GetElementsTransitionMapFromDescriptor(descriptor_contents,
-                                               to_kind);
-    ASSERT(maybe_transition_map == NULL || maybe_transition_map->IsMap());
-    return maybe_transition_map;
+  for (; index <= to_index; ++index) {
+      ElementsKind next_kind = GetFastElementsKindFromSequenceIndex(index);
+      MaybeObject* maybe_next_map =
+          current_map->CreateNextElementsTransition(next_kind);
+      if (!maybe_next_map->To(&current_map)) return maybe_next_map;
   }
-  return NULL;
-}
 
-
-MaybeObject* Map::AddElementsTransition(ElementsKind to_kind,
-                                        Map* transitioned_map) {
-  ElementsKind from_kind = elements_kind();
-  if (IsFastElementsKind(from_kind) && IsFastElementsKind(to_kind)) {
-    ASSERT(IsMoreGeneralElementsKindTransition(from_kind, to_kind));
-    ElementsKind transitioned_from_kind =
-        GetNextMoreGeneralFastElementsKind(from_kind, false);
-    // The map transitions graph should be a tree, therefore transitions to
-    // ElementsKind that are not adjacent in the ElementsKind sequence are not
-    // done directly, but instead by going through intermediate ElementsKinds
-    // first.
-    if (to_kind != transitioned_from_kind) {
-      bool safe_to_add = true;
-      Map* intermediate_map = LookupElementsTransitionMap(
-          transitioned_from_kind, &safe_to_add);
-      // This method is only called when safe_to_add has been found to be true
-      // earlier.
-      ASSERT(safe_to_add);
-
-      if (intermediate_map == NULL) {
-        MaybeObject* maybe_map = CopyDropTransitions();
-        if (!maybe_map->To(&intermediate_map)) return maybe_map;
-        intermediate_map->set_elements_kind(transitioned_from_kind);
-        MaybeObject* maybe_transition = AddElementsTransition(
-            transitioned_from_kind, intermediate_map);
-        if (maybe_transition->IsFailure()) return maybe_transition;
-      }
-      return intermediate_map->AddElementsTransition(to_kind, transitioned_map);
-    }
-  }
-
-  bool safe_to_add_transition = true;
-  Object* descriptor_contents = GetDescriptorContents(
-      elements_transition_sentinel_name(), &safe_to_add_transition);
-  // This method is only called when safe_to_add_transition has been found
-  // to be true earlier.
-  ASSERT(safe_to_add_transition);
-  MaybeObject* maybe_new_contents =
-      AddElementsTransitionMapToDescriptor(descriptor_contents,
-                                           transitioned_map);
-  Object* new_contents;
-  if (!maybe_new_contents->ToObject(&new_contents)) {
-    return maybe_new_contents;
-  }
-
-  ElementsTransitionDescriptor desc(elements_transition_sentinel_name(),
-                                    new_contents);
-  Object* new_descriptors;
-  MaybeObject* maybe_new_descriptors =
-      instance_descriptors()->CopyInsert(&desc, KEEP_TRANSITIONS);
-  if (!maybe_new_descriptors->ToObject(&new_descriptors)) {
-    return maybe_new_descriptors;
-  }
-  set_instance_descriptors(DescriptorArray::cast(new_descriptors));
-  transitioned_map->SetBackPointer(this);
-  return this;
+  ASSERT(current_map->elements_kind() == to_kind);
+  return current_map;
 }
 
 
@@ -2435,58 +2293,58 @@ Handle<Map> JSObject::GetElementsTransitionMap(Handle<JSObject> object,
 }
 
 
-MaybeObject* JSObject::GetElementsTransitionMapSlow(ElementsKind to_kind) {
-  Map* current_map = map();
-  ElementsKind from_kind = current_map->elements_kind();
+// If the map is using the empty descriptor array, install a new empty
+// descriptor array that will contain an element transition.
+// TODO(verwaest) Goes away once the descriptor array is immutable.
+static MaybeObject* EnsureMayContainTransitions(Map* map) {
+  if (map->instance_descriptors()->MayContainTransitions()) return map;
+  DescriptorArray* descriptor_array;
+  MaybeObject* maybe_descriptor_array = DescriptorArray::Allocate(0, true);
+  if (!maybe_descriptor_array->To(&descriptor_array)) {
+    return maybe_descriptor_array;
+  }
+  map->set_instance_descriptors(descriptor_array);
+  return map;
+}
 
-  if (from_kind == to_kind) return current_map;
 
-  // Only objects with FastProperties can have DescriptorArrays and can track
-  // element-related maps. Also don't add descriptors to maps that are shared.
-  bool safe_to_add_transition = HasFastProperties() &&
-      !current_map->IsUndefined() &&
-      !current_map->is_shared();
+MaybeObject* JSObject::GetElementsTransitionMapSlow(ElementsKind to_kind) {
+  Map* start_map = map();
+  ElementsKind from_kind = start_map->elements_kind();
 
-  // Prevent long chains of DICTIONARY -> FAST_*_ELEMENTS maps caused by objects
-  // with elements that switch back and forth between dictionary and fast
-  // element modes.
-  if (from_kind == DICTIONARY_ELEMENTS &&
-      IsFastElementsKind(to_kind)) {
-    safe_to_add_transition = false;
+  if (from_kind == to_kind) {
+    return start_map;
   }
 
-  if (safe_to_add_transition) {
-    // It's only safe to manipulate the descriptor array if it would be
-    // safe to add a transition.
-    Map* maybe_transition_map = current_map->LookupElementsTransitionMap(
-        to_kind, &safe_to_add_transition);
-    if (maybe_transition_map != NULL) {
-      return maybe_transition_map;
-    }
+  Context* global_context = GetIsolate()->context()->global_context();
+  bool allow_store_transition =
+       // Only remember the map transition if the object's map is NOT equal to

[danno, 2012/06/01 13:49:55]

nit: indentation

[Toon Verwaest, 2012/06/04 09:17:48]

Done.

+       // the global object_function's map and there is not an already existing
+       // non-matching element transition.
+       (global_context->object_function()->map() != map()) &&
+       !start_map->IsUndefined() && !start_map->is_shared() &&
+       // Only store fast element maps in ascending generality.
+       IsTransitionableFastElementsKind(from_kind) &&
+       IsFastElementsKind(to_kind) &&
+       IsMoreGeneralElementsKindTransition(from_kind, to_kind);
+
+  if (!allow_store_transition) {
+    // Create a new free-floating map only if we are not allowed to store it.
+    Map* new_map = NULL;
+    MaybeObject* maybe_new_map = start_map->CopyDropTransitions(false);
+    if (!maybe_new_map->To(&new_map)) return maybe_new_map;
+    new_map->set_elements_kind(to_kind);
+    return new_map;
   }
 
-  Map* new_map = NULL;
+  EnsureMayContainTransitions(start_map);
+  Map* closest_map = FindClosestElementsTransition(start_map, to_kind);
 
-  // No transition to an existing map for the given ElementsKind. Make a new
-  // one.
-  { MaybeObject* maybe_map = current_map->CopyDropTransitions();
-    if (!maybe_map->To(&new_map)) return maybe_map;
+  if (closest_map->elements_kind() == to_kind) {
+    return closest_map;
   }
 
-  new_map->set_elements_kind(to_kind);
-
-  // Only remember the map transition if the object's map is NOT equal to the
-  // global object_function's map and there is not an already existing
-  // non-matching element transition.
-  Context* global_context = GetIsolate()->context()->global_context();
-  bool allow_map_transition = safe_to_add_transition &&
-      (global_context->object_function()->map() != map());
-  if (allow_map_transition) {
-    MaybeObject* maybe_transition =
-        current_map->AddElementsTransition(to_kind, new_map);
-    if (maybe_transition->IsFailure()) return maybe_transition;
-  }
-  return new_map;
+  return AddMissingElementsTransitions(closest_map, to_kind);
 }
 
 
@@ -3005,7 +2863,6 @@ MaybeObject* JSObject::SetPropertyForResult(LookupResult* result,
       return ConvertDescriptorToFieldAndMapTransition(name, value, attributes);
     }
     case NULL_DESCRIPTOR:
-    case ELEMENTS_TRANSITION:
       return ConvertDescriptorToFieldAndMapTransition(name, value, attributes);
     case HANDLER:
       UNREACHABLE();
@@ -3103,9 +2960,7 @@ MaybeObject* JSObject::SetLocalPropertyIgnoreAttributes(
     case CONSTANT_TRANSITION:
       // Replace with a MAP_TRANSITION to a new map with a FIELD, even
       // if the value is a function.
-      return ConvertDescriptorToFieldAndMapTransition(name, value, attributes);
     case NULL_DESCRIPTOR:
-    case ELEMENTS_TRANSITION:
       return ConvertDescriptorToFieldAndMapTransition(name, value, attributes);
     case HANDLER:
       UNREACHABLE();
@@ -3396,7 +3251,6 @@ MaybeObject* JSObject::NormalizeProperties(PropertyNormalizationMode mode,
       case CONSTANT_TRANSITION:
       case NULL_DESCRIPTOR:
       case INTERCEPTOR:
-      case ELEMENTS_TRANSITION:
         break;
       case HANDLER:
       case NORMAL:
@@ -4182,7 +4036,7 @@ MaybeObject* JSObject::PreventExtensions() {
   // Do a map transition, other objects with this map may still
   // be extensible.
   Map* new_map;
-  { MaybeObject* maybe = map()->CopyDropTransitions();
+  { MaybeObject* maybe = map()->CopyDropTransitions(false);

[danno, 2012/06/01 13:49:55]

This should be an enum rather than a bool, it's really difficult to see what the
parameter means at the usage site.

[Toon Verwaest, 2012/06/04 09:17:48]

Done.

     if (!maybe->To<Map>(&new_map)) return maybe;
   }
   new_map->set_is_extensible(false);
@@ -4962,7 +4816,7 @@ MaybeObject* Map::CopyDropDescriptors() {
     JSFunction* ctor = JSFunction::cast(constructor());
     Object* descriptors;
     { MaybeObject* maybe_descriptors =
-          ctor->initial_map()->instance_descriptors()->RemoveTransitions();
+          ctor->initial_map()->instance_descriptors()->RemoveTransitions(false);
       if (!maybe_descriptors->ToObject(&descriptors)) return maybe_descriptors;
     }
     Map::cast(result)->set_instance_descriptors(
@@ -5015,14 +4869,14 @@ MaybeObject* Map::CopyNormalized(PropertyNormalizationMode mode,
 }
 
 
-MaybeObject* Map::CopyDropTransitions() {
+MaybeObject* Map::CopyDropTransitions(bool mutable_transitions) {
   Object* new_map;
   { MaybeObject* maybe_new_map = CopyDropDescriptors();
     if (!maybe_new_map->ToObject(&new_map)) return maybe_new_map;
   }
   Object* descriptors;
   { MaybeObject* maybe_descriptors =
-        instance_descriptors()->RemoveTransitions();
+        instance_descriptors()->RemoveTransitions(mutable_transitions);
     if (!maybe_descriptors->ToObject(&descriptors)) return maybe_descriptors;
   }
   cast(new_map)->set_instance_descriptors(DescriptorArray::cast(descriptors));
@@ -5088,11 +4942,13 @@ class IntrusiveMapTransitionIterator {
 
   void Start() {
     ASSERT(!IsIterating());
-    if (HasDescriptors()) *DescriptorArrayHeader() = Smi::FromInt(0);
+    if (descriptor_array_->MayContainTransitions())

[danno, 2012/06/01 13:49:55]

This is confusing. What does descriptor iteration have to do with transition?
Perhaps another predicate name, even if it does the same thing? 

[Toon Verwaest, 2012/06/04 09:17:48]

As discussed offline, won't change since it is actually only related to
transitions, not so much to descriptors.

On 2012/06/01 13:49:55, danno wrote:

+      *DescriptorArrayHeader() = Smi::FromInt(0);
   }
 
   bool IsIterating() {
-    return HasDescriptors() && (*DescriptorArrayHeader())->IsSmi();
+    return descriptor_array_->MayContainTransitions() &&
+           (*DescriptorArrayHeader())->IsSmi();
   }
 
   Map* Next() {
@@ -5110,7 +4966,6 @@ class IntrusiveMapTransitionIterator {
       switch (details.type()) {
         case MAP_TRANSITION:
         case CONSTANT_TRANSITION:
-        case ELEMENTS_TRANSITION:
           // We definitely have a map transition.
           *DescriptorArrayHeader() = Smi::FromInt(raw_index + 2);
           return static_cast<Map*>(descriptor_array_->GetValue(index));
@@ -5144,15 +4999,18 @@ class IntrusiveMapTransitionIterator {
           break;
       }
     }
+    if (index == descriptor_array_->number_of_descriptors()) {
+      Map* elements_transition = descriptor_array_->elements_transition();
+      if (elements_transition != NULL) {
+        *DescriptorArrayHeader() = Smi::FromInt(index + 1);
+        return elements_transition;
+      }
+    }
     *DescriptorArrayHeader() = descriptor_array_->GetHeap()->fixed_array_map();
     return NULL;
   }
 
  private:
-  bool HasDescriptors() {
-    return descriptor_array_->length() > DescriptorArray::kFirstIndex;
-  }
-
   Object** DescriptorArrayHeader() {
     return HeapObject::RawField(descriptor_array_, DescriptorArray::kMapOffset);
   }
@@ -5841,9 +5699,10 @@ bool FixedArray::IsEqualTo(FixedArray* other) {
 #endif
 
 
-MaybeObject* DescriptorArray::Allocate(int number_of_descriptors) {
+MaybeObject* DescriptorArray::Allocate(int number_of_descriptors,
+                                       bool mutable_transition) {
   Heap* heap = Isolate::Current()->heap();
-  if (number_of_descriptors == 0) {
+  if (number_of_descriptors == 0 && !mutable_transition) {
     return heap->empty_descriptor_array();
   }
   // Allocate the array of keys.
@@ -5856,6 +5715,7 @@ MaybeObject* DescriptorArray::Allocate(int number_of_descriptors) {
   FixedArray* result = FixedArray::cast(array);
 
   result->set(kBitField3StorageIndex, Smi::FromInt(0));
+  result->set(kTransitionsIndex, Smi::FromInt(0));
   result->set(kEnumerationIndexIndex,
               Smi::FromInt(PropertyDetails::kInitialIndex));
   return result;
@@ -5959,7 +5819,7 @@ MaybeObject* DescriptorArray::CopyInsert(Descriptor* descriptor,
   }
 
   DescriptorArray* new_descriptors;
-  { MaybeObject* maybe_result = Allocate(new_size);
+  { MaybeObject* maybe_result = Allocate(new_size, !remove_transitions);
     if (!maybe_result->To(&new_descriptors)) return maybe_result;
   }
 
@@ -5976,6 +5836,10 @@ MaybeObject* DescriptorArray::CopyInsert(Descriptor* descriptor,
       ++enumeration_index;
     }
   }
+  Map* old_elements_transition = elements_transition();
+  if ((!remove_transitions) && (old_elements_transition != NULL)) {
+    new_descriptors->set_elements_transition(old_elements_transition);
+  }
   new_descriptors->SetNextEnumerationIndex(enumeration_index);
 
   // Copy the descriptors, filtering out transitions and null descriptors,
@@ -5999,6 +5863,8 @@ MaybeObject* DescriptorArray::CopyInsert(Descriptor* descriptor,
     }
   }
   if (insertion_index < 0) insertion_index = to_index++;
+
+  ASSERT(insertion_index < new_descriptors->number_of_descriptors());
   new_descriptors->Set(insertion_index, descriptor, witness);
 
   ASSERT(to_index == new_descriptors->number_of_descriptors());
@@ -6008,14 +5874,15 @@ MaybeObject* DescriptorArray::CopyInsert(Descriptor* descriptor,
 }
 
 
-MaybeObject* DescriptorArray::RemoveTransitions() {
+MaybeObject* DescriptorArray::RemoveTransitions(bool mutable_transitions) {
   // Allocate the new descriptor array.
   int new_number_of_descriptors = 0;
   for (int i = 0; i < number_of_descriptors(); i++) {
     if (IsProperty(i)) new_number_of_descriptors++;
   }
   DescriptorArray* new_descriptors;
-  { MaybeObject* maybe_result = Allocate(new_number_of_descriptors);
+  { MaybeObject* maybe_result = Allocate(new_number_of_descriptors,
+                                         mutable_transitions);
     if (!maybe_result->To(&new_descriptors)) return maybe_result;
   }
 
@@ -6034,6 +5901,7 @@ MaybeObject* DescriptorArray::RemoveTransitions() {
   return new_descriptors;
 }
 
+
 // The whiteness witness is needed since sort will reshuffle the entries in the
 // descriptor array. If the descriptor array were to be were to be black, the
 // shuffling would move a slot that was already recorded as pointing into an
@@ -6099,31 +5967,27 @@ void DescriptorArray::Sort(const WhitenessWitness& witness) {
 
 int DescriptorArray::BinarySearch(String* name, int low, int high) {
   uint32_t hash = name->Hash();
+  int limit = high;
+
+  ASSERT(low <= high);
 
-  while (low <= high) {
+  while (low != high) {
     int mid = (low + high) / 2;
     String* mid_name = GetKey(mid);
     uint32_t mid_hash = mid_name->Hash();
 
-    if (mid_hash > hash) {
-      high = mid - 1;
-      continue;
-    }
-    if (mid_hash < hash) {
+    if (mid_hash >= hash) {
+      high = mid;
+    } else {
       low = mid + 1;
-      continue;
-    }
-    // Found an element with the same hash-code.
-    ASSERT(hash == mid_hash);
-    // There might be more, so we find the first one and
-    // check them all to see if we have a match.
-    if (name == mid_name  && !IsNullDescriptor(mid)) return mid;
-    while ((mid > low) && (GetKey(mid - 1)->Hash() == hash)) mid--;
-    for (; (mid <= high) && (GetKey(mid)->Hash() == hash); mid++) {
-      if (GetKey(mid)->Equals(name) && !IsNullDescriptor(mid)) return mid;
     }
-    break;
   }
+
+  for (; low <= limit && GetKey(low)->Hash() == hash; ++low) {
+    if (GetKey(low)->Equals(name) && !IsNullDescriptor(low))
+      return low;
+  }
+
   return kNotFound;
 }
 
@@ -6132,9 +5996,8 @@ int DescriptorArray::LinearSearch(String* name, int len) {
   uint32_t hash = name->Hash();
   for (int number = 0; number < len; number++) {
     String* entry = GetKey(number);
-    if ((entry->Hash() == hash) &&
-        name->Equals(entry) &&
-        !IsNullDescriptor(number)) {
+    if (entry->Hash() > hash) break;
+    if (name->Equals(entry) && !IsNullDescriptor(number)) {
       return number;
     }
   }
@@ -7418,20 +7281,6 @@ void Map::ClearNonLiveTransitions(Heap* heap) {
       case CONSTANT_TRANSITION:
         ClearBackPointer(heap, d->GetValue(i), &keep_entry);
         break;
-      case ELEMENTS_TRANSITION: {
-        Object* object = d->GetValue(i);
-        if (object->IsMap()) {
-          ClearBackPointer(heap, object, &keep_entry);
-        } else {
-          FixedArray* array = FixedArray::cast(object);
-          for (int j = 0; j < array->length(); ++j) {
-            if (ClearBackPointer(heap, array->get(j), &keep_entry)) {
-              array->set_undefined(j);
-            }
-          }
-        }
-        break;
-      }
       case CALLBACKS: {
         Object* object = d->GetValue(i);
         if (object->IsAccessorPair()) {
@@ -7591,7 +7440,7 @@ MaybeObject* JSFunction::SetInstancePrototype(Object* value) {
     // If the function has allocated the initial map
     // replace it with a copy containing the new prototype.
     Map* new_map;
-    MaybeObject* maybe_new_map = initial_map()->CopyDropTransitions();
+    MaybeObject* maybe_new_map = initial_map()->CopyDropTransitions(false);
     if (!maybe_new_map->To(&new_map)) return maybe_new_map;
     new_map->set_prototype(value);
     MaybeObject* maybe_object =
@@ -7621,7 +7470,7 @@ MaybeObject* JSFunction::SetPrototype(Object* value) {
     // Remove map transitions because they point to maps with a
     // different prototype.
     Map* new_map;
-    { MaybeObject* maybe_new_map = map()->CopyDropTransitions();
+    { MaybeObject* maybe_new_map = map()->CopyDropTransitions(false);
       if (!maybe_new_map->To(&new_map)) return maybe_new_map;
     }
     Heap* heap = new_map->GetHeap();
@@ -8488,7 +8337,6 @@ const char* Code::PropertyType2String(PropertyType type) {
     case HANDLER: return "HANDLER";
     case INTERCEPTOR: return "INTERCEPTOR";
     case MAP_TRANSITION: return "MAP_TRANSITION";
-    case ELEMENTS_TRANSITION: return "ELEMENTS_TRANSITION";
     case CONSTANT_TRANSITION: return "CONSTANT_TRANSITION";
     case NULL_DESCRIPTOR: return "NULL_DESCRIPTOR";
   }
@@ -8879,7 +8727,7 @@ MaybeObject* JSReceiver::SetPrototype(Object* value,
 
   Object* new_map = map->GetPrototypeTransition(value);
   if (new_map == NULL) {
-    { MaybeObject* maybe_new_map = map->CopyDropTransitions();
+    { MaybeObject* maybe_new_map = map->CopyDropTransitions(false);
       if (!maybe_new_map->ToObject(&new_map)) return maybe_new_map;
     }
 
@@ -11160,7 +11008,6 @@ bool StringDictionary::ContainsTransition(int entry) {
   switch (DetailsAt(entry).type()) {
     case MAP_TRANSITION:
     case CONSTANT_TRANSITION:
-    case ELEMENTS_TRANSITION:
       return true;
     case CALLBACKS: {
       Object* value = ValueAt(entry);
@@ -12610,7 +12457,7 @@ MaybeObject* StringDictionary::TransformPropertiesToFastFor(
   // Allocate the instance descriptor.
   DescriptorArray* descriptors;
   { MaybeObject* maybe_descriptors =
-        DescriptorArray::Allocate(instance_descriptor_length);
+        DescriptorArray::Allocate(instance_descriptor_length, false);
     if (!maybe_descriptors->To<DescriptorArray>(&descriptors)) {
       return maybe_descriptors;
     }