Make order of addition the primary order of descriptor arrays.

src/objects-inl.h

Index: src/objects-inl.h
diff --git a/src/objects-inl.h b/src/objects-inl.h
index 6c4cd54f6624601f2ca21814113a3cc11824b927..b00bcbfcbd19de217a4e3e9429e39401b6a5f46e 100644
--- a/src/objects-inl.h
+++ b/src/objects-inl.h
@@ -1887,15 +1887,6 @@ bool DescriptorArray::IsEmpty() {
 }
 
 
-void DescriptorArray::NoIncrementalWriteBarrierSwap(FixedArray* array,
-                                                    int first,
-                                                    int second) {
-  Object* tmp = array->get(first);
-  NoIncrementalWriteBarrierSet(array, first, array->get(second));
-  NoIncrementalWriteBarrierSet(array, second, tmp);
-}
-
-
 // Perform a binary search in a fixed array. Low and high are entry indices. If
 // there are three entries in this array it should be called with low=0 and
 // high=2.
@@ -1908,7 +1899,7 @@ int BinarySearch(T* array, String* name, int low, int high) {
 
   while (low != high) {
     int mid = (low + high) / 2;
-    String* mid_name = array->GetKey(mid);
+    String* mid_name = array->GetSortedKey(mid);
     uint32_t mid_hash = mid_name->Hash();
 
     if (mid_hash >= hash) {
@@ -1918,24 +1909,27 @@ int BinarySearch(T* array, String* name, int low, int high) {
     }
   }
 
-  for (; low <= limit && array->GetKey(low)->Hash() == hash; ++low) {
-    if (array->GetKey(low)->Equals(name)) return low;
+  for (; low <= limit; ++low) {
+    int sort_index = array->GetSortedKeyIndex(low);
+    String* entry = array->GetKey(sort_index);
+    if (entry->Hash() != hash) break;
+    if (entry->Equals(name)) return sort_index;
   }
 
   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, String* name, int len) {
   uint32_t hash = name->Hash();
   for (int number = 0; number < len; number++) {
-    String* entry = array->GetKey(number);
+    int sorted_index = array->GetSortedKeyIndex(number);
+    String* entry = array->GetKey(sorted_index);
     uint32_t current_hash = entry->Hash();
     if (current_hash > hash) break;
-    if (current_hash == hash && name->Equals(entry)) return number;
+    if (current_hash == hash && entry->Equals(name)) return sorted_index;
   }
   return T::kNotFound;
 }
@@ -1945,13 +1939,12 @@ 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) {
+  if (nof < kMaxElementsForLinearSearch) {
     return LinearSearch(array, name, nof);
   }
 
@@ -1966,16 +1959,44 @@ int DescriptorArray::Search(String* name) {
 
 
 int DescriptorArray::SearchWithCache(String* name) {
+  if (number_of_descriptors() == 0) return kNotFound;
+
   DescriptorLookupCache* cache = GetIsolate()->descriptor_lookup_cache();
   int number = cache->Lookup(this, name);
+
   if (number == DescriptorLookupCache::kAbsent) {
-    number = internal::Search(this, name);
+    number = Search(name);
     cache->Update(this, name, number);
   }
+
   return number;
 }
 
 
+void Map::LookupDescriptor(JSObject* holder,
+                           String* name,
+                           LookupResult* result) {
+  DescriptorArray* descriptors = this->instance_descriptors();
+  int number = descriptors->SearchWithCache(name);
+  if (number == DescriptorArray::kNotFound) return result->NotFound();
+  result->DescriptorResult(holder, descriptors->GetDetails(number), number);
+}
+
+
+void Map::LookupTransition(JSObject* holder,
+                           String* name,
+                           LookupResult* result) {
+  if (HasTransitionArray()) {
+    TransitionArray* transition_array = transitions();
+    int number = transition_array->Search(name);
+    if (number != TransitionArray::kNotFound) {
+      return result->TransitionResult(holder, number);
+    }
+  }
+  result->NotFound();
+}
+
+
 Object** DescriptorArray::GetKeySlot(int descriptor_number) {
   ASSERT(descriptor_number < number_of_descriptors());
   return HeapObject::RawField(
@@ -1990,6 +2011,23 @@ String* DescriptorArray::GetKey(int descriptor_number) {
 }
 
 
+int DescriptorArray::GetSortedKeyIndex(int descriptor_number) {
+  return GetDetails(descriptor_number).pointer();
+}
+
+
+String* DescriptorArray::GetSortedKey(int descriptor_number) {
+  return GetKey(GetSortedKeyIndex(descriptor_number));
+}
+
+
+void DescriptorArray::SetSortedKey(int pointer, int descriptor_number) {
+  int details_index = ToDetailsIndex(pointer);
+  PropertyDetails details = PropertyDetails(Smi::cast(get(details_index)));
+  set_unchecked(details_index, details.set_pointer(descriptor_number).AsSmi());
+}
+
+
 Object** DescriptorArray::GetValueSlot(int descriptor_number) {
   ASSERT(descriptor_number < number_of_descriptors());
   return HeapObject::RawField(
@@ -2051,8 +2089,9 @@ void DescriptorArray::Set(int descriptor_number,
                           const WhitenessWitness&) {
   // Range check.
   ASSERT(descriptor_number < number_of_descriptors());
-  ASSERT(desc->GetDetails().index() <= number_of_descriptors());
-  ASSERT(desc->GetDetails().index() > 0);
+  ASSERT(desc->GetDetails().descriptor_index() <=
+         number_of_descriptors());
+  ASSERT(desc->GetDetails().descriptor_index() > 0);
 
   NoIncrementalWriteBarrierSet(this,
                                ToKeyIndex(descriptor_number),
@@ -2066,38 +2105,31 @@ void DescriptorArray::Set(int descriptor_number,
 }
 
 
-int DescriptorArray::Append(Descriptor* desc,
-                            const WhitenessWitness& witness,
-                            int number_of_set_descriptors) {
-  int descriptor_number = number_of_set_descriptors;
-  int enumeration_index = descriptor_number + 1;
+void DescriptorArray::Append(Descriptor* desc,
+                             const WhitenessWitness& witness,
+                             int number_of_set_descriptors) {
+  int enumeration_index = number_of_set_descriptors + 1;
   desc->SetEnumerationIndex(enumeration_index);
+  Set(number_of_set_descriptors, desc, witness);
 
   uint32_t hash = desc->GetKey()->Hash();
 
-  for (; descriptor_number > 0; --descriptor_number) {
-    String* key = GetKey(descriptor_number - 1);
+  int insertion;
+
+  for (insertion = number_of_set_descriptors; insertion > 0; --insertion) {
+    String* key = GetSortedKey(insertion - 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);
+    SetSortedKey(insertion, GetSortedKeyIndex(insertion - 1));
   }
 
-  Set(descriptor_number, desc, witness);
-  return descriptor_number;
+  SetSortedKey(insertion, number_of_set_descriptors);
 }
 
 
-void DescriptorArray::NoIncrementalWriteBarrierSwapDescriptors(
-    int first, int second) {
-  NoIncrementalWriteBarrierSwap(this, ToKeyIndex(first), ToKeyIndex(second));
-  NoIncrementalWriteBarrierSwap(this,
-                                ToValueIndex(first),
-                                ToValueIndex(second));
-  NoIncrementalWriteBarrierSwap(this,
-                                ToDetailsIndex(first),
-                                ToDetailsIndex(second));
+void DescriptorArray::SwapSortedKeys(int first, int second) {
+  int first_key = GetSortedKeyIndex(first);
+  SetSortedKey(first, GetSortedKeyIndex(second));
+  SetSortedKey(second, first_key);
 }
 
 
@@ -3455,18 +3487,18 @@ MaybeObject* Map::SetDescriptors(DescriptorArray* value,
 
 
 MaybeObject* Map::InitializeDescriptors(DescriptorArray* descriptors) {
+#ifdef DEBUG
   int len = descriptors->number_of_descriptors();
   ASSERT(len <= DescriptorArray::kMaxNumberOfDescriptors);
   SLOW_ASSERT(descriptors->IsSortedNoDuplicates());
 
-#ifdef DEBUG
   bool used_indices[DescriptorArray::kMaxNumberOfDescriptors];
   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() -
+    int enum_index = descriptors->GetDetails(i).descriptor_index() -
                      PropertyDetails::kInitialIndex;
     ASSERT(0 <= enum_index && enum_index < len);
     ASSERT(!used_indices[enum_index]);
@@ -3477,14 +3509,8 @@ MaybeObject* Map::InitializeDescriptors(DescriptorArray* descriptors) {
   MaybeObject* maybe_failure = SetDescriptors(descriptors);
   if (maybe_failure->IsFailure()) return maybe_failure;
 
-  for (int i = 0; i < len; ++i) {
-    if (descriptors->GetDetails(i).index() == len) {
-      SetLastAdded(i);
-      return this;
-    }
-  }
+  SetNumberOfOwnDescriptors(descriptors->number_of_descriptors());
 
-  ASSERT(len == 0 && LastAdded() == kNoneAdded);
   return this;
 }
 
@@ -3511,9 +3537,10 @@ void Map::ClearTransitions(Heap* heap, WriteBarrierMode mode) {
 void Map::AppendDescriptor(Descriptor* desc,
                            const DescriptorArray::WhitenessWitness& witness) {
   DescriptorArray* descriptors = instance_descriptors();
-  int set_descriptors = NumberOfSetDescriptors();
-  int new_last_added = descriptors->Append(desc, witness, set_descriptors);
-  SetLastAdded(new_last_added);
+  int number_of_own_descriptors = NumberOfOwnDescriptors();
+  ASSERT(number_of_own_descriptors < descriptors->number_of_descriptors());
+  descriptors->Append(desc, witness, number_of_own_descriptors);
+  SetNumberOfOwnDescriptors(number_of_own_descriptors + 1);
 }
 
 
@@ -5001,7 +5028,9 @@ void Dictionary<Shape, Key>::SetEntry(int entry,
                                       Object* key,
                                       Object* value,
                                       PropertyDetails details) {
-  ASSERT(!key->IsString() || details.IsDeleted() || details.index() > 0);
+  ASSERT(!key->IsString() ||
+         details.IsDeleted() ||
+         details.dictionary_index() > 0);
   int index = HashTable<Shape, Key>::EntryToIndex(entry);
   AssertNoAllocation no_gc;
   WriteBarrierMode mode = FixedArray::GetWriteBarrierMode(no_gc);