Improve fast to slow elements conversion:

src/objects.cc

Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index 8e36ae5337a8da2f0aea27b5b9ae1d1af2698899..f0224d217b992f5bf07d2623c0a04c9098133928 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -2896,9 +2896,12 @@ MaybeObject* JSObject::NormalizeElements() {
   int length = IsJSArray()
       ? Smi::cast(JSArray::cast(this)->length())->value()
       : array->length();
+  int old_capacity = 0;
+  int used_elements = 0;
+  GetElementsCapacityAndUsage(&old_capacity, &used_elements);
   NumberDictionary* dictionary = NULL;
   { Object* object;
-    MaybeObject* maybe = NumberDictionary::Allocate(length);
+    MaybeObject* maybe = NumberDictionary::Allocate(used_elements);
     if (!maybe->ToObject(&object)) return maybe;
     dictionary = NumberDictionary::cast(object);
   }
@@ -8615,7 +8618,7 @@ MaybeObject* JSObject::SetDictionaryElement(uint32_t index,
     } else {
       new_length = dictionary->max_number_key() + 1;
     }
-    MaybeObject* result = ShouldConvertToFastDoubleElements()
+    MaybeObject* result = CanConvertToFastDoubleElements()
         ? SetFastDoubleElementsCapacityAndLength(new_length, new_length)
         : SetFastElementsCapacityAndLength(new_length, new_length);
     if (result->IsFailure()) return result;
@@ -9157,7 +9160,15 @@ MaybeObject* JSObject::GetExternalElement(uint32_t index) {
 
 bool JSObject::HasDenseElements() {
   int capacity = 0;
-  int number_of_elements = 0;
+  int used = 0;
+  GetElementsCapacityAndUsage(&capacity, &used);
+  return (capacity == 0) || (used > (capacity / 2));
+}
+
+
+void JSObject::GetElementsCapacityAndUsage(int* capacity, int* used) {
+  *capacity = 0;
+  *used = 0;
 
   FixedArrayBase* backing_store_base = FixedArrayBase::cast(elements());
   FixedArray* backing_store = NULL;
@@ -9168,34 +9179,33 @@ bool JSObject::HasDenseElements() {
       backing_store = FixedArray::cast(backing_store_base);
       if (backing_store->IsDictionary()) {
         NumberDictionary* dictionary = NumberDictionary::cast(backing_store);
-        capacity = dictionary->Capacity();
-        number_of_elements = dictionary->NumberOfElements();
+        *capacity = dictionary->Capacity();
+        *used = dictionary->NumberOfElements();
         break;
       }
       // Fall through.
     case FAST_ELEMENTS:
       backing_store = FixedArray::cast(backing_store_base);
-      capacity = backing_store->length();
-      for (int i = 0; i < capacity; ++i) {
-        if (!backing_store->get(i)->IsTheHole()) ++number_of_elements;
+      *capacity = backing_store->length();
+      for (int i = 0; i < *capacity; ++i) {
+        if (!backing_store->get(i)->IsTheHole()) ++(*used);
       }
       break;
     case DICTIONARY_ELEMENTS: {
       NumberDictionary* dictionary =
           NumberDictionary::cast(FixedArray::cast(elements()));
-      capacity = dictionary->Capacity();
-      number_of_elements = dictionary->NumberOfElements();
+      *capacity = dictionary->Capacity();
+      *used = dictionary->NumberOfElements();
       break;
     }
     case FAST_DOUBLE_ELEMENTS: {
       FixedDoubleArray* elms = FixedDoubleArray::cast(elements());
-      capacity = elms->length();
-      for (int i = 0; i < capacity; i++) {
-        if (!elms->is_the_hole(i)) number_of_elements++;
+      *capacity = elms->length();
+      for (int i = 0; i < *capacity; i++) {
+        if (!elms->is_the_hole(i)) ++(*used);
       }
       break;
     }
-    case EXTERNAL_PIXEL_ELEMENTS:
     case EXTERNAL_BYTE_ELEMENTS:
     case EXTERNAL_UNSIGNED_BYTE_ELEMENTS:
     case EXTERNAL_SHORT_ELEMENTS:
@@ -9203,31 +9213,34 @@ bool JSObject::HasDenseElements() {
     case EXTERNAL_INT_ELEMENTS:
     case EXTERNAL_UNSIGNED_INT_ELEMENTS:
     case EXTERNAL_FLOAT_ELEMENTS:
-    case EXTERNAL_DOUBLE_ELEMENTS: {
-      return true;
-    }
+    case EXTERNAL_DOUBLE_ELEMENTS:
+    case EXTERNAL_PIXEL_ELEMENTS:
+      // External arrays are considered 100% used.
+      ExternalArray* external_array = ExternalArray::cast(elements());
+      *capacity = external_array->length();
+      *used = external_array->length();
+      break;
   }
-  return (capacity == 0) || (number_of_elements > (capacity / 2));
 }
 
 
 bool JSObject::ShouldConvertToSlowElements(int new_capacity) {
-  if (new_capacity <= kMaxFastElementsLength) return false;
-  // Keep the array in fast case if the current backing storage is
-  // almost filled and if the new capacity is no more than twice the
-  // old capacity.
-  int old_capacity = 0;
-  if (elements()->map() == GetHeap()->non_strict_arguments_elements_map()) {
-    FixedArray* backing_store = FixedArray::cast(elements());
-    old_capacity = FixedArray::cast(backing_store->get(1))->length();
-  } else if (HasFastElements()) {
-    old_capacity = FixedArray::cast(elements())->length();
-  } else if (HasFastDoubleElements()) {
-    old_capacity = FixedDoubleArray::cast(elements())->length();
-  } else {
-    UNREACHABLE();
+  STATIC_ASSERT(kMaxUncheckedOldFastElementsLength <=
+                kMaxUncheckedFastElementsLength);
+  if (new_capacity <= kMaxUncheckedOldFastElementsLength ||
+      (new_capacity <= kMaxUncheckedFastElementsLength &&
+       GetHeap()->InNewSpace(this))) {
+    return false;
   }
-  return !HasDenseElements() || ((new_capacity / 2) > old_capacity);
+  // If the fast-case backing storage takes up roughly three times as
+  // much space (in machine words) as a dictionary backing storage
+  // would, the object should have slow elements.
+  int old_capacity = 0;
+  int used_elements = 0;
+  GetElementsCapacityAndUsage(&old_capacity, &used_elements);
+  int dictionary_size = NumberDictionary::ComputeCapacity(used_elements) *
+      NumberDictionary::kEntrySize;
+  return 3 * dictionary_size <= new_capacity;
 }
 
 
@@ -9250,20 +9263,21 @@ bool JSObject::ShouldConvertToFastElements() {
   // dictionary, we cannot go back to fast case.
   if (dictionary->requires_slow_elements()) return false;
   // If the dictionary backing storage takes up roughly half as much
-  // space as a fast-case backing storage would the array should have
-  // fast elements.
-  uint32_t length = 0;
+  // space (in machine words) as a fast-case backing storage would,
+  // the object should have fast elements.
+  uint32_t array_size = 0;
   if (IsJSArray()) {
-    CHECK(JSArray::cast(this)->length()->ToArrayIndex(&length));
+    CHECK(JSArray::cast(this)->length()->ToArrayIndex(&array_size));
   } else {
-    length = dictionary->max_number_key();
+    array_size = dictionary->max_number_key();
   }
-  return static_cast<uint32_t>(dictionary->Capacity()) >=
-      (length / (2 * NumberDictionary::kEntrySize));
+  uint32_t dictionary_size = static_cast<uint32_t>(dictionary->Capacity()) *
+      NumberDictionary::kEntrySize;
+  return 2 * dictionary_size >= array_size;
 }
 
 
-bool JSObject::ShouldConvertToFastDoubleElements() {
+bool JSObject::CanConvertToFastDoubleElements() {
   if (FLAG_unbox_double_arrays) {
     ASSERT(HasDictionaryElements());
     NumberDictionary* dictionary = NumberDictionary::cast(elements());
@@ -10194,11 +10208,8 @@ void HashTable<Shape, Key>::IterateElements(ObjectVisitor* v) {
 template<typename Shape, typename Key>
 MaybeObject* HashTable<Shape, Key>::Allocate(int at_least_space_for,
                                              PretenureFlag pretenure) {
-  const int kMinCapacity = 32;
-  int capacity = RoundUpToPowerOf2(at_least_space_for * 2);
-  if (capacity < kMinCapacity) {
-    capacity = kMinCapacity;  // Guarantee min capacity.
-  } else if (capacity > HashTable::kMaxCapacity) {
+  int capacity = ComputeCapacity(at_least_space_for);
+  if (capacity > HashTable::kMaxCapacity) {
     return Failure::OutOfMemoryException();
   }