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 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);
 }
 
 
 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
+  // 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)
 
 
 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_