[elements] Precisely estimate elements size for large-object limits

src/elements.cc

Index: src/elements.cc
diff --git a/src/elements.cc b/src/elements.cc
index 02f79c60a1d07861c5b3d964d6f390a626893bc4..e8f2c79f851dbafe471fa345b6a2dc083f2e44fd 100644
--- a/src/elements.cc
+++ b/src/elements.cc
@@ -523,8 +523,10 @@ class ElementsAccessorBase : public ElementsAccessor {
                            Handle<FixedArrayBase> backing_store, uint32_t start,
                            uint32_t end) {
     if (IsFastPackedElementsKind(kind())) return true;
+    Isolate* isolate = backing_store->GetIsolate();
     for (uint32_t i = start; i < end; i++) {
-      if (!Subclass::HasElementImpl(holder, i, backing_store, ALL_PROPERTIES)) {
+      if (!Subclass::HasElementImpl(isolate, holder, i, backing_store,
+                                    ALL_PROPERTIES)) {
         return false;
       }
     }
@@ -551,14 +553,16 @@ class ElementsAccessorBase : public ElementsAccessor {
   bool HasElement(Handle<JSObject> holder, uint32_t index,
                   Handle<FixedArrayBase> backing_store,
                   PropertyFilter filter) final {
-    return Subclass::HasElementImpl(holder, index, backing_store, filter);
+    return Subclass::HasElementImpl(holder->GetIsolate(), holder, index,
+                                    backing_store, filter);
   }
 
-  static bool HasElementImpl(Handle<JSObject> holder, uint32_t index,
+  static bool HasElementImpl(Isolate* isolate, Handle<JSObject> holder,
+                             uint32_t index,
                              Handle<FixedArrayBase> backing_store,
                              PropertyFilter filter) {
-    return Subclass::GetEntryForIndexImpl(*holder, *backing_store, index,
-                                          filter) != kMaxUInt32;
+    return Subclass::GetEntryForIndexImpl(isolate, *holder, *backing_store,
+                                          index, filter) != kMaxUInt32;
   }
 
   bool HasAccessors(JSObject* holder) final {
@@ -729,6 +733,15 @@ class ElementsAccessorBase : public ElementsAccessor {
     JSObject::ValidateElements(array);
   }
 
+  uint32_t NumberOfElements(JSObject* receiver) final {
+    return Subclass::NumberOfElementsImpl(receiver, receiver->elements());
+  }
+
+  static uint32_t NumberOfElementsImpl(JSObject* receiver,
+                                       FixedArrayBase* backing_store) {
+    UNREACHABLE();
+  }
+
   static uint32_t GetMaxIndex(JSObject* receiver, FixedArrayBase* elements) {
     if (receiver->IsJSArray()) {
       DCHECK(JSArray::cast(receiver)->length()->IsSmi());
@@ -899,7 +912,7 @@ class ElementsAccessorBase : public ElementsAccessor {
       if (!key->ToUint32(&index)) continue;
 
       uint32_t entry = Subclass::GetEntryForIndexImpl(
-          *object, object->elements(), index, filter);
+          isolate, *object, object->elements(), index, filter);
       if (entry == kMaxUInt32) continue;
 
       PropertyDetails details = Subclass::GetDetailsImpl(*object, entry);
@@ -935,9 +948,10 @@ class ElementsAccessorBase : public ElementsAccessor {
     // Non-dictionary elements can't have all-can-read accessors.
     uint32_t length = Subclass::GetMaxIndex(*object, *backing_store);
     PropertyFilter filter = keys->filter();
-    Factory* factory = keys->isolate()->factory();
+    Isolate* isolate = keys->isolate();
+    Factory* factory = isolate->factory();
     for (uint32_t i = 0; i < length; i++) {
-      if (Subclass::HasElementImpl(object, i, backing_store, filter)) {
+      if (Subclass::HasElementImpl(isolate, object, i, backing_store, filter)) {
         keys->AddKey(factory->NewNumberFromUint(i));
       }
     }
@@ -950,7 +964,7 @@ class ElementsAccessorBase : public ElementsAccessor {
       uint32_t insertion_index = 0) {
     uint32_t length = Subclass::GetMaxIndex(*object, *backing_store);
     for (uint32_t i = 0; i < length; i++) {
-      if (Subclass::HasElementImpl(object, i, backing_store, filter)) {
+      if (Subclass::HasElementImpl(isolate, object, i, backing_store, filter)) {
         if (convert == GetKeysConversion::kConvertToString) {
           Handle<String> index_string = isolate->factory()->Uint32ToString(i);
           list->set(insertion_index, *index_string);
@@ -973,6 +987,20 @@ class ElementsAccessorBase : public ElementsAccessor {
                                                convert, filter);
   }
 
+  static uint32_t EstimatePrependElementSize(JSObject* object,
+                                             FixedArrayBase* backing_store,
+                                             uint32_t length) {
+    if (kind() == FAST_HOLEY_ELEMENTS) {

[Igor Sheludko, 2016/06/07 14:50:01]

FAST_HOLEY_DOUBLE_ELEMENTS ?

+      if (FixedDoubleArray::SizeFor(length) <=
+          Page::kMaxRegularHeapObjectSize) {
+        return length;
+      }
+    } else if (FixedArray::SizeFor(length) <= Page::kMaxRegularHeapObjectSize) {
+      return length;
+    }
+    return Subclass::NumberOfElementsImpl(object, backing_store);
+  }
+
   static Handle<FixedArray> PrependElementIndicesImpl(
       Handle<JSObject> object, Handle<FixedArrayBase> backing_store,
       Handle<FixedArray> keys, GetKeysConversion convert,
@@ -980,9 +1008,17 @@ class ElementsAccessorBase : public ElementsAccessor {
     Isolate* isolate = object->GetIsolate();
     uint32_t nof_property_keys = keys->length();
     uint32_t initial_list_length =
-        Subclass::GetCapacityImpl(*object, *backing_store);
+        Subclass::GetMaxNumberOfEntries(*object, *backing_store);

[Igor Sheludko, 2016/06/07 14:50:01]

It does not have to be called for holey kinds. Maybe you can even move this code
to Estimate... function.

     initial_list_length += nof_property_keys;
 
+    if (IsHoleyElementsKind(kind())) {
+      // If we overestimate the result list size we might end up in old space

[Michael Lippautz, 2016/06/07 17:28:27]

s/old space/large object space/

+      // which doesn't free memory on shrinking the list. Hence we try to
+      // estimate the final size for holey backing stores more precisely here.
+      initial_list_length = EstimatePrependElementSize(*object, *backing_store,
+                                                       initial_list_length);
+    }
+
     // Collect the element indices into a new list.
     uint32_t nof_indices = 0;
     Handle<FixedArray> combined_keys =
@@ -1049,12 +1085,13 @@ class ElementsAccessorBase : public ElementsAccessor {
     return entry;
   }
 
-  static uint32_t GetEntryForIndexImpl(JSObject* holder,
+  static uint32_t GetEntryForIndexImpl(Isolate* isolate, JSObject* holder,
                                        FixedArrayBase* backing_store,
                                        uint32_t index, PropertyFilter filter) {
     if (IsHoleyElementsKind(kind())) {
       return index < Subclass::GetCapacityImpl(holder, backing_store) &&
-                     !BackingStore::cast(backing_store)->is_the_hole(index)
+                     !BackingStore::cast(backing_store)
+                          ->is_the_hole(isolate, index)
                  ? index
                  : kMaxUInt32;
     } else {
@@ -1063,9 +1100,10 @@ class ElementsAccessorBase : public ElementsAccessor {
     }
   }
 
-  uint32_t GetEntryForIndex(JSObject* holder, FixedArrayBase* backing_store,
+  uint32_t GetEntryForIndex(Isolate* isolate, JSObject* holder,
+                            FixedArrayBase* backing_store,
                             uint32_t index) final {
-    return Subclass::GetEntryForIndexImpl(holder, backing_store, index,
+    return Subclass::GetEntryForIndexImpl(isolate, holder, backing_store, index,
                                           ALL_PROPERTIES);
   }
 
@@ -1106,6 +1144,11 @@ class DictionaryElementsAccessor
     return dict->NumberOfElements();
   }
 
+  static uint32_t NumberOfElementsImpl(JSObject* receiver,
+                                       FixedArrayBase* backing_store) {
+    return GetMaxNumberOfEntries(receiver, backing_store);
+  }
+
   static void SetLengthImpl(Isolate* isolate, Handle<JSArray> array,
                             uint32_t length,
                             Handle<FixedArrayBase> backing_store) {
@@ -1252,11 +1295,12 @@ class DictionaryElementsAccessor
     object->set_elements(*new_dictionary);
   }
 
-  static bool HasEntryImpl(FixedArrayBase* store, uint32_t entry) {
+  static bool HasEntryImpl(Isolate* isolate, FixedArrayBase* store,
+                           uint32_t entry) {
     DisallowHeapAllocation no_gc;
     SeededNumberDictionary* dict = SeededNumberDictionary::cast(store);
     Object* index = dict->KeyAt(entry);
-    return !index->IsTheHole(dict->GetIsolate());
+    return !index->IsTheHole(isolate);
   }
 
   static uint32_t GetIndexForEntryImpl(FixedArrayBase* store, uint32_t entry) {
@@ -1267,11 +1311,12 @@ class DictionaryElementsAccessor
     return result;
   }
 
-  static uint32_t GetEntryForIndexImpl(JSObject* holder, FixedArrayBase* store,
-                                       uint32_t index, PropertyFilter filter) {
+  static uint32_t GetEntryForIndexImpl(Isolate* isolate, JSObject* holder,
+                                       FixedArrayBase* store, uint32_t index,
+                                       PropertyFilter filter) {
     DisallowHeapAllocation no_gc;
     SeededNumberDictionary* dictionary = SeededNumberDictionary::cast(store);
-    int entry = dictionary->FindEntry(index);
+    int entry = dictionary->FindEntry(isolate, index);
     if (entry == SeededNumberDictionary::kNotFound) return kMaxUInt32;
     if (filter != ALL_PROPERTIES) {
       PropertyDetails details = dictionary->DetailsAt(entry);
@@ -1380,8 +1425,8 @@ class DictionaryElementsAccessor
     Isolate* isolate = accumulator->isolate();
     Handle<Object> undefined = isolate->factory()->undefined_value();
     Handle<Object> the_hole = isolate->factory()->the_hole_value();
-    SeededNumberDictionary* dictionary =
-        SeededNumberDictionary::cast(receiver->elements());
+    Handle<SeededNumberDictionary> dictionary(
+        SeededNumberDictionary::cast(receiver->elements()), isolate);
     int capacity = dictionary->Capacity();
     for (int i = 0; i < capacity; i++) {
       Object* k = dictionary->KeyAt(i);
@@ -1427,7 +1472,7 @@ class FastElementsAccessor : public ElementsAccessorBase<Subclass, KindTraits> {
     int j = 0;
     for (int i = 0; j < capacity; i++) {
       if (IsHoleyElementsKind(kind)) {
-        if (BackingStore::cast(*store)->is_the_hole(i)) continue;
+        if (BackingStore::cast(*store)->is_the_hole(isolate, i)) continue;
       }
       Handle<Object> value = Subclass::GetImpl(*store, i);
       dictionary = SeededNumberDictionary::AddNumberEntry(
@@ -1440,12 +1485,12 @@ class FastElementsAccessor : public ElementsAccessorBase<Subclass, KindTraits> {
   static void DeleteAtEnd(Handle<JSObject> obj,
                           Handle<BackingStore> backing_store, uint32_t entry) {
     uint32_t length = static_cast<uint32_t>(backing_store->length());
-    Heap* heap = obj->GetHeap();
+    Isolate* isolate = obj->GetIsolate();
     for (; entry > 0; entry--) {
-      if (!backing_store->is_the_hole(entry - 1)) break;
+      if (!backing_store->is_the_hole(isolate, entry - 1)) break;
     }
     if (entry == 0) {
-      FixedArray* empty = heap->empty_fixed_array();
+      FixedArray* empty = isolate->heap()->empty_fixed_array();
       // Dynamically ask for the elements kind here since we manually redirect
       // the operations for argument backing stores.
       if (obj->GetElementsKind() == FAST_SLOPPY_ARGUMENTS_ELEMENTS) {
@@ -1456,8 +1501,8 @@ class FastElementsAccessor : public ElementsAccessorBase<Subclass, KindTraits> {
       return;
     }
 
-    heap->RightTrimFixedArray<Heap::CONCURRENT_TO_SWEEPER>(*backing_store,
-                                                           length - entry);
+    isolate->heap()->RightTrimFixedArray<Heap::CONCURRENT_TO_SWEEPER>(
+        *backing_store, length - entry);
   }
 
   static void DeleteCommon(Handle<JSObject> obj, uint32_t entry,
@@ -1472,6 +1517,7 @@ class FastElementsAccessor : public ElementsAccessorBase<Subclass, KindTraits> {
       return;
     }
 
+    Isolate* isolate = obj->GetIsolate();
     backing_store->set_the_hole(entry);
 
     // TODO(verwaest): Move this out of elements.cc.
@@ -1488,12 +1534,13 @@ class FastElementsAccessor : public ElementsAccessorBase<Subclass, KindTraits> {
     } else {
       length = static_cast<uint32_t>(store->length());
     }
-    if ((entry > 0 && backing_store->is_the_hole(entry - 1)) ||
-        (entry + 1 < length && backing_store->is_the_hole(entry + 1))) {
+    if ((entry > 0 && backing_store->is_the_hole(isolate, entry - 1)) ||
+        (entry + 1 < length &&
+         backing_store->is_the_hole(isolate, entry + 1))) {
       if (!obj->IsJSArray()) {
         uint32_t i;
         for (i = entry + 1; i < length; i++) {
-          if (!backing_store->is_the_hole(i)) break;
+          if (!backing_store->is_the_hole(isolate, i)) break;
         }
         if (i == length) {
           DeleteAtEnd(obj, backing_store, entry);
@@ -1502,7 +1549,7 @@ class FastElementsAccessor : public ElementsAccessorBase<Subclass, KindTraits> {
       }
       int num_used = 0;
       for (int i = 0; i < backing_store->length(); ++i) {
-        if (!backing_store->is_the_hole(i)) {
+        if (!backing_store->is_the_hole(isolate, i)) {
           ++num_used;
           // Bail out if a number dictionary wouldn't be able to save at least
           // 75% space.
@@ -1563,19 +1610,32 @@ class FastElementsAccessor : public ElementsAccessorBase<Subclass, KindTraits> {
     DeleteCommon(obj, entry, handle(obj->elements()));
   }
 
-  static bool HasEntryImpl(FixedArrayBase* backing_store, uint32_t entry) {
-    return !BackingStore::cast(backing_store)->is_the_hole(entry);
+  static bool HasEntryImpl(Isolate* isolate, FixedArrayBase* backing_store,
+                           uint32_t entry) {
+    return !BackingStore::cast(backing_store)->is_the_hole(isolate, entry);
+  }
+
+  static uint32_t NumberOfElementsImpl(JSObject* receiver,
+                                       FixedArrayBase* backing_store) {
+    uint32_t max_index = Subclass::GetMaxIndex(receiver, backing_store);
+    if (IsFastPackedElementsKind(Subclass::kind())) return max_index;
+    Isolate* isolate = receiver->GetIsolate();
+    uint32_t count = 0;
+    for (uint32_t i = 0; i < max_index; i++) {
+      if (Subclass::HasEntryImpl(isolate, backing_store, i)) count++;
+    }
+    return count;
   }
 
   static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver,
                                               KeyAccumulator* accumulator,
                                               AddKeyConversion convert) {
-    Handle<FixedArrayBase> elements(receiver->elements(),
-                                    accumulator->isolate());
+    Isolate* isolate = accumulator->isolate();
+    Handle<FixedArrayBase> elements(receiver->elements(), isolate);
     uint32_t length = Subclass::GetMaxNumberOfEntries(*receiver, *elements);
     for (uint32_t i = 0; i < length; i++) {
       if (IsFastPackedElementsKind(KindTraits::Kind) ||
-          HasEntryImpl(*elements, i)) {
+          HasEntryImpl(isolate, *elements, i)) {
         accumulator->AddKey(Subclass::GetImpl(*elements, i), convert);
       }
     }
@@ -1604,12 +1664,12 @@ class FastElementsAccessor : public ElementsAccessorBase<Subclass, KindTraits> {
       for (int i = 0; i < length; i++) {
         DCHECK(BackingStore::get(*backing_store, i, isolate)->IsSmi() ||
                (IsFastHoleyElementsKind(KindTraits::Kind) &&
-                backing_store->is_the_hole(i)));
+                backing_store->is_the_hole(isolate, i)));
       }
     } else if (KindTraits::Kind == FAST_ELEMENTS ||
                KindTraits::Kind == FAST_DOUBLE_ELEMENTS) {
       for (int i = 0; i < length; i++) {
-        DCHECK(!backing_store->is_the_hole(i));
+        DCHECK(!backing_store->is_the_hole(isolate, i));
       }
     } else {
       DCHECK(IsFastHoleyElementsKind(KindTraits::Kind));
@@ -1711,11 +1771,13 @@ class FastElementsAccessor : public ElementsAccessorBase<Subclass, KindTraits> {
       Isolate* isolate, Handle<JSObject> object,
       Handle<FixedArray> values_or_entries, bool get_entries, int* nof_items,
       PropertyFilter filter) {
+    Handle<BackingStore> elements(BackingStore::cast(object->elements()),
+                                  isolate);
     int count = 0;
-    uint32_t length = object->elements()->length();
+    uint32_t length = elements->length();
     for (uint32_t index = 0; index < length; ++index) {
-      if (!HasEntryImpl(object->elements(), index)) continue;
-      Handle<Object> value = Subclass::GetImpl(object->elements(), index);
+      if (!HasEntryImpl(isolate, *elements, index)) continue;
+      Handle<Object> value = Subclass::GetImpl(*elements, index);
       if (get_entries) {
         value = MakeEntryPair(isolate, index, value);
       }
@@ -1905,7 +1967,6 @@ class FastSmiOrObjectElementsAccessor
     return backing_store->get(index);
   }
 
-
   // NOTE: this method violates the handlified function signature convention:
   // raw pointer parameters in the function that allocates.
   // See ElementsAccessor::CopyElements() for details.
@@ -2144,7 +2205,8 @@ class TypedElementsAccessor
     return PropertyDetails(DONT_DELETE, DATA, 0, PropertyCellType::kNoCell);
   }
 
-  static bool HasElementImpl(Handle<JSObject> holder, uint32_t index,
+  static bool HasElementImpl(Isolate* isolate, Handle<JSObject> holder,
+                             uint32_t index,
                              Handle<FixedArrayBase> backing_store,
                              PropertyFilter filter) {
     return index < AccessorClass::GetCapacityImpl(*holder, *backing_store);
@@ -2171,7 +2233,7 @@ class TypedElementsAccessor
     return entry;
   }
 
-  static uint32_t GetEntryForIndexImpl(JSObject* holder,
+  static uint32_t GetEntryForIndexImpl(Isolate* isolate, JSObject* holder,
                                        FixedArrayBase* backing_store,
                                        uint32_t index, PropertyFilter filter) {
     return index < AccessorClass::GetCapacityImpl(holder, backing_store)
@@ -2186,6 +2248,11 @@ class TypedElementsAccessor
     return backing_store->length();
   }
 
+  static uint32_t NumberOfElementsImpl(JSObject* receiver,
+                                       FixedArrayBase* backing_store) {
+    return AccessorClass::GetCapacityImpl(receiver, backing_store);
+  }
+
   static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver,
                                               KeyAccumulator* accumulator,
                                               AddKeyConversion convert) {
@@ -2321,25 +2388,26 @@ class SloppyArgumentsElementsAccessor
   static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver,
                                               KeyAccumulator* accumulator,
                                               AddKeyConversion convert) {
-    FixedArrayBase* elements = receiver->elements();
-    uint32_t length = GetCapacityImpl(*receiver, elements);
+    Isolate* isolate = accumulator->isolate();
+    Handle<FixedArrayBase> elements(receiver->elements(), isolate);
+    uint32_t length = GetCapacityImpl(*receiver, *elements);
     for (uint32_t entry = 0; entry < length; entry++) {
-      if (!HasEntryImpl(elements, entry)) continue;
-      Handle<Object> value = GetImpl(elements, entry);
+      if (!HasEntryImpl(isolate, *elements, entry)) continue;
+      Handle<Object> value = GetImpl(*elements, entry);
       accumulator->AddKey(value, convert);
     }
   }
 
-  static bool HasEntryImpl(FixedArrayBase* parameters, uint32_t entry) {
+  static bool HasEntryImpl(Isolate* isolate, FixedArrayBase* parameters,
+                           uint32_t entry) {
     FixedArray* parameter_map = FixedArray::cast(parameters);
     uint32_t length = parameter_map->length() - 2;
     if (entry < length) {
-      return !GetParameterMapArg(parameter_map, entry)
-                  ->IsTheHole(parameter_map->GetIsolate());
+      return !GetParameterMapArg(parameter_map, entry)->IsTheHole(isolate);
     }
 
     FixedArrayBase* arguments = FixedArrayBase::cast(parameter_map->get(1));
-    return ArgumentsAccessor::HasEntryImpl(arguments, entry - length);
+    return ArgumentsAccessor::HasEntryImpl(isolate, arguments, entry - length);
   }
 
   static bool HasAccessorsImpl(JSObject* holder,
@@ -2359,16 +2427,16 @@ class SloppyArgumentsElementsAccessor
     return ArgumentsAccessor::GetIndexForEntryImpl(arguments, entry - length);
   }
 
-  static uint32_t GetEntryForIndexImpl(JSObject* holder,
+  static uint32_t GetEntryForIndexImpl(Isolate* isolate, JSObject* holder,
                                        FixedArrayBase* parameters,
                                        uint32_t index, PropertyFilter filter) {
     FixedArray* parameter_map = FixedArray::cast(parameters);
     Object* probe = GetParameterMapArg(parameter_map, index);
-    if (!probe->IsTheHole(holder->GetIsolate())) return index;
+    if (!probe->IsTheHole(isolate)) return index;
 
     FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
-    uint32_t entry = ArgumentsAccessor::GetEntryForIndexImpl(holder, arguments,
-                                                             index, filter);
+    uint32_t entry = ArgumentsAccessor::GetEntryForIndexImpl(
+        isolate, holder, arguments, index, filter);
     if (entry == kMaxUInt32) return kMaxUInt32;
     return (parameter_map->length() - 2) + entry;
   }
@@ -2561,9 +2629,9 @@ class FastSloppyArgumentsElementsAccessor
     FixedArray* parameters = FixedArray::cast(receiver->elements());
     uint32_t insertion_index = 0;
     for (uint32_t i = start; i < end; i++) {
-      uint32_t entry =
-          GetEntryForIndexImpl(*receiver, parameters, i, ALL_PROPERTIES);
-      if (entry != kMaxUInt32 && HasEntryImpl(parameters, entry)) {
+      uint32_t entry = GetEntryForIndexImpl(isolate, *receiver, parameters, i,
+                                            ALL_PROPERTIES);
+      if (entry != kMaxUInt32 && HasEntryImpl(isolate, parameters, entry)) {
         elements->set(insertion_index, *GetImpl(parameters, entry));
       } else {
         elements->set_the_hole(insertion_index);
@@ -2686,13 +2754,13 @@ class StringWrapperElementsAccessor
     return BackingStoreAccessor::GetDetailsImpl(holder, entry - length);
   }
 
-  static uint32_t GetEntryForIndexImpl(JSObject* holder,
+  static uint32_t GetEntryForIndexImpl(Isolate* isolate, JSObject* holder,
                                        FixedArrayBase* backing_store,
                                        uint32_t index, PropertyFilter filter) {
     uint32_t length = static_cast<uint32_t>(GetString(holder)->length());
     if (index < length) return index;
     uint32_t backing_store_entry = BackingStoreAccessor::GetEntryForIndexImpl(
-        holder, backing_store, index, filter);
+        isolate, holder, backing_store, index, filter);
     if (backing_store_entry == kMaxUInt32) return kMaxUInt32;
     DCHECK(backing_store_entry < kMaxUInt32 - length);
     return backing_store_entry + length;