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

src/objects.cc

 // 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 5682 matching lines @@
 void DescriptorArray::CopyFrom(int dst_index,
                                DescriptorArray* src,
                                int src_index,
                                const WhitenessWitness& witness) {
   Object* value = src->GetValue(src_index);
   PropertyDetails details = src->GetDetails(src_index);
   Descriptor desc(src->GetKey(src_index), value, details);
   Set(dst_index, &desc, witness);
 }
 
+
 MaybeObject* DescriptorArray::CopyReplace(Descriptor* descriptor,
                                           int insertion_index) {
   ASSERT(0 <= insertion_index && insertion_index < number_of_descriptors());
 
   // Ensure the key is a symbol.
-  { MaybeObject* maybe_result = descriptor->KeyToSymbol();
-    if (maybe_result->IsFailure()) return maybe_result;
-  }
+  MaybeObject* maybe_failure = descriptor->KeyToSymbol();
+  if (maybe_failure->IsFailure()) return maybe_failure;
 
   int size = number_of_descriptors();
 
   DescriptorArray* new_descriptors;
-  { MaybeObject* maybe_result = Allocate(size, MAY_BE_SHARED);
-    if (!maybe_result->To(&new_descriptors)) return maybe_result;
-  }
+  MaybeObject* maybe_descriptors = Allocate(size, MAY_BE_SHARED);
+  if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors;
 
   FixedArray::WhitenessWitness witness(new_descriptors);
 
   // Copy the descriptors, replacing a descriptor.
   for (int index = 0; index < size; ++index) {
     if (index == insertion_index) continue;
     new_descriptors->CopyFrom(index, this, index, witness);
   }
 
   descriptor->SetEnumerationIndex(GetDetails(insertion_index).index());
   new_descriptors->Set(insertion_index, descriptor, witness);
   new_descriptors->SetLastAdded(LastAdded());
 
   SLOW_ASSERT(new_descriptors->IsSortedNoDuplicates());
 
   return new_descriptors;
 }
 
 
 MaybeObject* DescriptorArray::CopyAdd(Descriptor* descriptor) {
   // Ensure the key is a symbol.
-  MaybeObject* maybe_result = descriptor->KeyToSymbol();
-  if (maybe_result->IsFailure()) return maybe_result;
+  MaybeObject* maybe_failure = descriptor->KeyToSymbol();
+  if (maybe_failure->IsFailure()) return maybe_failure;
 
   String* key = descriptor->GetKey();
   ASSERT(Search(key) == kNotFound);
 
   int new_size = number_of_descriptors() + 1;
 
   DescriptorArray* new_descriptors;
   MaybeObject* maybe_descriptors = Allocate(new_size, MAY_BE_SHARED);
   if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors;
 
@@ skipping 35 matching lines @@
     FixedArray::WhitenessWitness witness(new_descriptors);
     for (int i = 0; i < number_of_descriptors; i++) {
       new_descriptors->CopyFrom(i, this, i, witness);
     }
     new_descriptors->SetLastAdded(LastAdded());
   }
 
   return new_descriptors;
 }
 
+
 // We need the whiteness witness since sort will reshuffle the entries in the
 // descriptor array. If the descriptor array were to be black, the shuffling
 // would move a slot that was already recorded as pointing into an evacuation
 // candidate. This would result in missing updates upon evacuation.
-void DescriptorArray::SortUnchecked(const WhitenessWitness& witness) {
+void DescriptorArray::Sort(const WhitenessWitness& witness) {
   // In-place heap sort.
   int len = number_of_descriptors();
-  // Nothing to sort.
-  if (len == 0) return;
-
-  ASSERT(LastAdded() == kNoneAdded ||
-         GetDetails(LastAdded()).index() == number_of_descriptors());
-
   // Bottom-up max-heap construction.
   // Index of the last node with children
   const int max_parent_index = (len / 2) - 1;
   for (int i = max_parent_index; i >= 0; --i) {
     int parent_index = i;
     const uint32_t parent_hash = GetKey(i)->Hash();
     while (parent_index <= max_parent_index) {
       int child_index = 2 * parent_index + 1;
       uint32_t child_hash = GetKey(child_index)->Hash();
       if (child_index + 1 < len) {
@@ skipping 26 matching lines @@
         if (right_child_hash > child_hash) {
           child_index++;
           child_hash = right_child_hash;
         }
       }
       if (child_hash <= parent_hash) break;
       NoIncrementalWriteBarrierSwapDescriptors(parent_index, child_index);
       parent_index = child_index;
     }
   }
-
-#ifdef DEBUG
-  // Ensure that all enumeration indexes between 1 and length occur uniquely in
-  // the descriptor array.
-  for (int i = 1; i <= len; ++i) {
-    int j;
-    for (j = 0; j < len; ++j) {
-      if (GetDetails(j).index() == i) break;
-    }
-    ASSERT(j != len);
-    for (j++; j < len; ++j) {
-      ASSERT(GetDetails(j).index() != i);
-    }
-  }
-#endif
-
-  for (int i = 0; i < len; ++i) {
-    if (GetDetails(i).index() == len) {
-      SetLastAdded(i);
-      return;
-    }
-  }
-
-  UNREACHABLE();
 }
 
 
-void DescriptorArray::Sort(const WhitenessWitness& witness) {
-  SortUnchecked(witness);
-  SLOW_ASSERT(IsSortedNoDuplicates());
-}
-
-
 MaybeObject* AccessorPair::Copy() {
   Heap* heap = GetHeap();
   AccessorPair* copy;
   MaybeObject* maybe_copy = heap->AllocateAccessorPair();
   if (!maybe_copy->To(&copy)) return maybe_copy;
 
   copy->set_getter(getter());
   copy->set_setter(setter());
   return copy;
 }
@@ skipping 6650 matching lines @@
         UNREACHABLE();
       }
       ++next_descriptor;
     }
   }
   ASSERT(current_offset == number_of_fields);
 
   descriptors->Sort(witness);
   // Allocate new map.
   Map* new_map;
-  MaybeObject* maybe_new_map =
-      obj->map()->CopyReplaceDescriptors(descriptors, NULL, OMIT_TRANSITION);
+  MaybeObject* maybe_new_map = obj->map()->CopyDropDescriptors();
   if (!maybe_new_map->To(&new_map)) return maybe_new_map;
 
+  new_map->InitializeDescriptors(descriptors);
   new_map->set_unused_property_fields(unused_property_fields);
 
   // Transform the object.
   obj->set_map(new_map);
 
   obj->set_properties(fields);
   ASSERT(obj->IsJSObject());
 
   // Check that it really works.
   ASSERT(obj->HasFastProperties());
@@ skipping 499 matching lines @@
   set_year(Smi::FromInt(year), SKIP_WRITE_BARRIER);
   set_month(Smi::FromInt(month), SKIP_WRITE_BARRIER);
   set_day(Smi::FromInt(day), SKIP_WRITE_BARRIER);
   set_weekday(Smi::FromInt(weekday), SKIP_WRITE_BARRIER);
   set_hour(Smi::FromInt(hour), SKIP_WRITE_BARRIER);
   set_min(Smi::FromInt(min), SKIP_WRITE_BARRIER);
   set_sec(Smi::FromInt(sec), SKIP_WRITE_BARRIER);
 }
 
 } }  // namespace v8::internal