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

src/objects-inl.h

Index: src/objects-inl.h
diff --git a/src/objects-inl.h b/src/objects-inl.h
index 6e67a77c94d2203d68f742df4db5132c4eb01c30..9ddbcdf755c3b84212646de25fcd408aacc5162e 100644
--- a/src/objects-inl.h
+++ b/src/objects-inl.h
@@ -1952,12 +1952,12 @@ int BinarySearch(T* array, String* name, int low, int high) {
 // 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;
@@ -1975,7 +1975,7 @@ int Search(T* array, String* name) {
   // 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.
@@ -2115,6 +2115,18 @@ void DescriptorArray::Append(Descriptor* desc,
   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 desc(key, value, details);

[Jakob Kummerow, 2012/07/18 15:17:55]

nit: I don't like shadowing variables. Can you pick another name for this (e.g.
"descriptor" or "moved_descriptor")?

+    Set(descriptor_number, &desc, witness);
+  }
+
   Set(descriptor_number, desc, witness);
   SetLastAdded(descriptor_number);
 }
@@ -3489,6 +3501,39 @@ void Map::set_instance_descriptors(DescriptorArray* value,
 }
 
 
+void Map::InitializeDescriptors(DescriptorArray* descriptors) {
+  int len = descriptors->number_of_descriptors();
+  SLOW_ASSERT(descriptors->IsSortedNoDuplicates());
+
+#ifdef DEBUG
+  // Ensure that all enumeration indexes between 1 and length occur uniquely in
+  // the descriptor array.
+  for (int i = 1; i <= len; ++i) {

[Jakob Kummerow, 2012/07/18 15:17:55]

Not sure if it's worth the effort, but we *could* make this check faster by
using an array :-)
Or you could hide it behind FLAG_enable_slow_asserts and/or add a TODO comment.

+    int j;
+    for (j = 0; j < len; ++j) {
+      if (descriptors->GetDetails(j).index() == i) break;
+    }
+    ASSERT(j != len);
+    for (j++; j < len; ++j) {
+      ASSERT(descriptors->GetDetails(j).index() != i);
+    }
+  }
+#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)