Let DescriptorArray::Append insert at proper position, avoiding need for resorting.

src/objects-inl.h

 // 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 1934 matching lines @@
     if (array->GetKey(low)->Equals(name)) return low;
   }
 
   return T::kNotFound;
 }
 
 
 // Perform a linear search in this fixed array. len is the number of entry
 // indices that are valid.
 template<typename T>
-int LinearSearch(T* array, SearchMode mode, String* name, int len) {
+int LinearSearch(T* array, String* name, int len) {
   uint32_t hash = name->Hash();
   for (int number = 0; number < len; number++) {
     String* entry = array->GetKey(number);
     uint32_t current_hash = entry->Hash();
-    if (mode == EXPECT_SORTED && current_hash > hash) break;
+    if (current_hash > hash) break;
     if (current_hash == hash && name->Equals(entry)) return number;
   }
   return T::kNotFound;
 }
 
 
 template<typename T>
 int Search(T* array, String* name) {
   SLOW_ASSERT(array->IsSortedNoDuplicates());
 
   // Check for empty descriptor array.
   int nof = array->number_of_entries();
   if (nof == 0) return T::kNotFound;
 
   // Fast case: do linear search for small arrays.
   const int kMaxElementsForLinearSearch = 8;
   if (StringShape(name).IsSymbol() && nof < kMaxElementsForLinearSearch) {
-    return LinearSearch(array, EXPECT_SORTED, name, nof);
+    return LinearSearch(array, name, nof);
   }
 
   // Slow case: perform binary search.
   return BinarySearch(array, name, 0, nof - 1);
 }
 
 
 int DescriptorArray::Search(String* name) {
   return internal::Search(this, name);
 }
@@ skipping 119 matching lines @@
                                ToDetailsIndex(descriptor_number),
                                desc->GetDetails().AsSmi());
 }
 
 
 void DescriptorArray::Append(Descriptor* desc,
                              const WhitenessWitness& witness) {
   int descriptor_number = NumberOfSetDescriptors();
   int enumeration_index = descriptor_number + 1;
   desc->SetEnumerationIndex(enumeration_index);
+
+  uint32_t hash = desc->GetKey()->Hash();
+
+  for (; descriptor_number > 0; --descriptor_number) {
+    String* key = GetKey(descriptor_number - 1);
+    if (key->Hash() <= hash) break;
+    Object* value = GetValue(descriptor_number - 1);
+    PropertyDetails details = GetDetails(descriptor_number - 1);
+    Descriptor moved_descriptor(key, value, details);
+    Set(descriptor_number, &moved_descriptor, witness);
+  }
+
   Set(descriptor_number, desc, witness);
   SetLastAdded(descriptor_number);
 }
 
 
 void DescriptorArray::NoIncrementalWriteBarrierSwapDescriptors(
     int first, int second) {
   NoIncrementalWriteBarrierSwap(this, ToKeyIndex(first), ToKeyIndex(second));
   NoIncrementalWriteBarrierSwap(this,
                                 ToValueIndex(first),
@@ skipping 1354 matching lines @@
     value->set_back_pointer_storage(object);
   }
 
   ASSERT(!is_shared());
   WRITE_FIELD(this, kInstanceDescriptorsOrBackPointerOffset, value);
   CONDITIONAL_WRITE_BARRIER(
       heap, this, kInstanceDescriptorsOrBackPointerOffset, value, mode);
 }
 
 
+void Map::InitializeDescriptors(DescriptorArray* descriptors) {
+  int len = descriptors->number_of_descriptors();
+  SLOW_ASSERT(descriptors->IsSortedNoDuplicates());
+
+#ifdef DEBUG
+  bool* used_indices =
+      reinterpret_cast<bool*>(alloca(sizeof(*used_indices) * len));
+  for (int i = 0; i < len; ++i) used_indices[i] = false;
+
+  // Ensure that all enumeration indexes between 1 and length occur uniquely in
+  // the descriptor array.
+  for (int i = 0; i < len; ++i) {
+    int enum_index = descriptors->GetDetails(i).index() -
+                     PropertyDetails::kInitialIndex;
+    ASSERT(!used_indices[enum_index]);
+    used_indices[enum_index] = true;
+  }
+#endif
+
+  for (int i = 0; i < len; ++i) {
+    if (descriptors->GetDetails(i).index() == len) {
+      descriptors->SetLastAdded(i);
+      break;
+    }
+  }
+
+  ASSERT(len == 0 ||
+         len == descriptors->GetDetails(descriptors->LastAdded()).index());
+
+  set_instance_descriptors(descriptors);
+}
+
+
 SMI_ACCESSORS(Map, bit_field3, kBitField3Offset)
 
 
 void Map::ClearDescriptorArray(Heap* heap, WriteBarrierMode mode) {
   Object* back_pointer = GetBackPointer();
 #ifdef DEBUG
   Object* object = READ_FIELD(this, kInstanceDescriptorsOrBackPointerOffset);
   if (object->IsDescriptorArray()) {
     ZapTransitions();
   } else {
@@ skipping 1821 matching lines @@
 #undef WRITE_UINT32_FIELD
 #undef READ_SHORT_FIELD
 #undef WRITE_SHORT_FIELD
 #undef READ_BYTE_FIELD
 #undef WRITE_BYTE_FIELD
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_OBJECTS_INL_H_