[key-accumulator] Starting to reimplement the key-accumulator

src/elements.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/elements.h"
 
 #include "src/arguments.h"
 #include "src/conversions.h"
 #include "src/factory.h"
 #include "src/messages.h"
@@ skipping 410 matching lines @@
   for (int i = 0; i < copy_size; i++) {
     int entry = from->FindEntry(i + from_start);
     if (entry != SeededNumberDictionary::kNotFound) {
       to->set(i + to_start, from->ValueAt(entry)->Number());
     } else {
       to->set_the_hole(i + to_start);
     }
   }
 }
 
+Handle<FixedArray> EnsureSize(Isolate* isolate, Handle<FixedArray> array,
+                              int size) {
+  int length = array->length();
+  if (size < length) return array;
+  int new_capacity = length + length / 2;
+  int grow_by = new_capacity - length;
+  return isolate->factory()->CopyFixedArrayAndGrow(array, grow_by);
+}
 
 static void TraceTopFrame(Isolate* isolate) {
   StackFrameIterator it(isolate);
   if (it.done()) {
     PrintF("unknown location (no JavaScript frames present)");
     return;
   }
   StackFrame* raw_frame = it.frame();
   if (raw_frame->is_internal()) {
     Code* apply_builtin =
@@ skipping 279 matching lines @@
     } else {
       // Check whether the backing store should be expanded.
       capacity = Max(length, JSObject::NewElementsCapacity(capacity));
       ElementsAccessorSubclass::GrowCapacityAndConvertImpl(array, capacity);
     }
 
     array->set_length(Smi::FromInt(length));
     JSObject::ValidateElements(array);
   }
 
+  static uint32_t GetIterationLength(JSObject* receiver,
+                                     FixedArrayBase* elements) {
+    if (receiver->IsJSArray()) {
+      return static_cast<uint32_t>(
+          Smi::cast(JSArray::cast(receiver)->length())->value());
+    } else {
+      return ElementsAccessorSubclass::GetCapacityImpl(receiver, elements);
+    }
+  }
+
   static Handle<FixedArrayBase> ConvertElementsWithCapacity(
       Handle<JSObject> object, Handle<FixedArrayBase> old_elements,
       ElementsKind from_kind, uint32_t capacity) {
     return ConvertElementsWithCapacity(
         object, old_elements, from_kind, capacity, 0, 0,
         ElementsAccessor::kCopyToEndAndInitializeToHole);
   }
 
   static Handle<FixedArrayBase> ConvertElementsWithCapacity(
       Handle<JSObject> object, Handle<FixedArrayBase> old_elements,
@@ skipping 96 matching lines @@
     // intentionally to avoid ArrayConcat() builtin performance degradation.
     //
     // Details: The idea is that allocations actually happen only in case of
     // copying from object with fast double elements to object with object
     // elements. In all the other cases there are no allocations performed and
     // handle creation causes noticeable performance degradation of the builtin.
     ElementsAccessorSubclass::CopyElementsImpl(
         from, from_start, *to, from_kind, to_start, packed_size, copy_size);
   }
 
+  void CollectElementIndices(Handle<JSObject> object,
+                             Handle<FixedArrayBase> backing_store,
+                             KeyAccumulator* keys, uint32_t range,
+                             PropertyFilter filter, uint32_t offset) final {
+    ElementsAccessorSubclass::CollectElementIndicesImpl(
+        object, backing_store, keys, range, filter, offset);
+  }
+
   static void CollectElementIndicesImpl(Handle<JSObject> object,
                                         Handle<FixedArrayBase> backing_store,
                                         KeyAccumulator* keys, uint32_t range,
                                         PropertyFilter filter,
                                         uint32_t offset) {
     DCHECK_NE(DICTIONARY_ELEMENTS, kind());
     if (filter & ONLY_ALL_CAN_READ) {
       // Non-dictionary elements can't have all-can-read accessors.
       return;
     }
-    uint32_t length = 0;
-    if (object->IsJSArray()) {
-      length = Smi::cast(JSArray::cast(*object)->length())->value();
-    } else {
-      length =
-          ElementsAccessorSubclass::GetCapacityImpl(*object, *backing_store);
-    }
+    uint32_t length = GetIterationLength(*object, *backing_store);
     if (range < length) length = range;
     for (uint32_t i = offset; i < length; i++) {
-      if (!ElementsAccessorSubclass::HasElementImpl(object, i, backing_store,
-                                                    filter)) {
-        continue;
+      if (ElementsAccessorSubclass::HasElementImpl(object, i, backing_store,
+                                                   filter)) {
+        keys->AddKey(i);
       }
-      keys->AddKey(i);
     }
   }
 
-  void CollectElementIndices(Handle<JSObject> object,
-                             Handle<FixedArrayBase> backing_store,
-                             KeyAccumulator* keys, uint32_t range,
-                             PropertyFilter filter, uint32_t offset) final {
-    ElementsAccessorSubclass::CollectElementIndicesImpl(
-        object, backing_store, keys, range, filter, offset);
-  };
+  static Handle<FixedArray> FastCollectElementIndicesImpl(
+      Isolate* isolate, Handle<JSObject> object,
+      Handle<FixedArrayBase> backing_store, GetKeysConversion convert,
+      PropertyFilter filter, Handle<FixedArray> list, int* nof_indices) {
+    uint32_t length =
+        ElementsAccessorSubclass::GetIterationLength(*object, *backing_store);
+    int insertion_index = 0;
+    for (uint32_t i = 0; i < length; i++) {
+      if (IsFastPackedElementsKind(kind())) {

[Toon Verwaest, 2016/02/24 15:07:06]

HasElementImpl should just return true for packed kind(). Similarly, EnsureSize
should be a noop for packed kind(). In that case you don't need to duplicate the
branches.

+        if (convert == CONVERT_TO_STRING) {
+          list->set(insertion_index++, *isolate->factory()->Uint32ToString(i));
+        } else {
+          list->set(insertion_index++, Smi::FromInt(i), SKIP_WRITE_BARRIER);
+        }
+      } else {
+        if (ElementsAccessorSubclass::HasElementImpl(object, i, backing_store,
+                                                     filter)) {
+          list = EnsureSize(isolate, list, insertion_index);
+          if (convert == CONVERT_TO_STRING) {
+            list->set(insertion_index++,
+                      *isolate->factory()->Uint32ToString(i));
+          } else {
+            list->set(insertion_index++, Smi::FromInt(i), SKIP_WRITE_BARRIER);
+          }
+        }
+      }
+    }
+    *nof_indices = insertion_index;
+    return list;
+  }
+
+  Handle<FixedArray> PrependElementIndices(Handle<JSObject> object,
+                                           Handle<FixedArrayBase> backing_store,
+                                           Handle<FixedArray> keys,
+                                           GetKeysConversion convert,
+                                           PropertyFilter filter) final {
+    return ElementsAccessorSubclass::PrependElementIndicesImpl(
+        object, backing_store, keys, convert, filter);
+  }
+
+  Handle<FixedArray> PrependElementIndicesImpl(
+      Handle<JSObject> object, Handle<FixedArrayBase> backing_store,
+      Handle<FixedArray> keys, GetKeysConversion convert,
+      PropertyFilter filter) {
+    if (!IsDictionaryElementsKind(kind()) && filter & ONLY_ALL_CAN_READ) {

[Toon Verwaest, 2016/02/24 15:07:06]

There are no ALL_CAN_READ indexed properties that aren't handled by an
all-can-read indexed interceptor. We should probably add a (D)CHECK to the API
that this never happens, rather than implement support here. Those properties
are only relevant for browsers and browser-like settings; and in chrome we don't
use it.

+      // Non-dictionary elements can't have all-can-read accessors.
+      return keys;
+    }
+
+    Isolate* isolate = object->GetIsolate();
+    int nof_property_keys = keys->length();
+
+    // Calculate the initial list size depending on the object at hand.
+    int initial_list_length = 10;

[Toon Verwaest, 2016/02/24 15:07:06]

Why not immediately use Capacity + nof_property_keys, and then always trim
later? I doubt you'll be able to avoid much memory allocation in practice; you
probably just make it worse by using a list + expanding.

+    if (IsFastPackedElementsKind(kind())) {
+      initial_list_length =
+          ElementsAccessorSubclass::GetCapacityImpl(*object, *backing_store);
+      initial_list_length += nof_property_keys;
+    }
+
+    // Collect the element indices into a new list.
+    int nof_indices = 0;
+    Handle<FixedArray> combined_keys =
+        isolate->factory()->NewFixedArray(initial_list_length);
+    combined_keys = ElementsAccessorSubclass::FastCollectElementIndicesImpl(
+        isolate, object, backing_store, convert, filter, combined_keys,
+        &nof_indices);
+
+    // Sort the indices list if necessary.
+    if (kind() == DICTIONARY_ELEMENTS) {
+      struct {
+        bool operator()(Object* a, Object* b) {

[Toon Verwaest, 2016/02/24 15:07:06]

return a->Number()  < b->Number()? Seems like double-encoded indices aren't
going to be sorted otherwise ...

+          if (a->IsSmi()) {
+            if (!b->IsSmi()) return true;
+            return Smi::cast(a)->value() < Smi::cast(b)->value();
+          }
+          return !b->IsSmi();
+        }
+      } cmp;
+      Object** start =
+          reinterpret_cast<Object**>(combined_keys->GetFirstElementAddress());
+      std::sort(start, start + nof_indices, cmp);
+    }
+
+    // Shrink/Grow the combined_keys to the final size.
+    int final_size = nof_indices + nof_property_keys;
+    if (combined_keys->length() < final_size) {
+      combined_keys = isolate->factory()->CopyFixedArrayAndGrow(
+          combined_keys, final_size - combined_keys->length());
+    } else {
+      combined_keys->Shrink(final_size);
+    }
+
+    // Copy over the property keys.
+    ElementsKind kind = FAST_HOLEY_ELEMENTS;

[Toon Verwaest, 2016/02/24 15:07:06]

I guess it doesn't change anything, but this should be FAST_ELEMENTS right?

+    CopyObjectToObjectElements(*keys, kind, 0, *combined_keys, kind,
+                               nof_indices, nof_property_keys);
+    return combined_keys;
+  }
 
   void AddElementsToKeyAccumulator(Handle<JSObject> receiver,
                                    KeyAccumulator* accumulator,
                                    AddKeyConversion convert) final {
     ElementsAccessorSubclass::AddElementsToKeyAccumulatorImpl(
         receiver, accumulator, convert);
   }
 
   static uint32_t GetCapacityImpl(JSObject* holder,
                                   FixedArrayBase* backing_store) {
@@ skipping 12 matching lines @@
   static uint32_t GetEntryForIndexImpl(JSObject* holder,
                                        FixedArrayBase* backing_store,
                                        uint32_t index, PropertyFilter filter) {
     if (IsHoleyElementsKind(kind())) {
       return index < ElementsAccessorSubclass::GetCapacityImpl(holder,
                                                                backing_store) &&
                      !BackingStore::cast(backing_store)->is_the_hole(index)
                  ? index
                  : kMaxUInt32;
     } else {
-      uint32_t length =
-          holder->IsJSArray()
-              ? static_cast<uint32_t>(
-                    Smi::cast(JSArray::cast(holder)->length())->value())
-              : ElementsAccessorSubclass::GetCapacityImpl(holder,
-                                                          backing_store);
+      uint32_t length = GetIterationLength(holder, backing_store);
       return index < length ? index : kMaxUInt32;
     }
   }
 
   uint32_t GetEntryForIndex(JSObject* holder, FixedArrayBase* backing_store,
                             uint32_t index) final {
     return ElementsAccessorSubclass::GetEntryForIndexImpl(
         holder, backing_store, index, ALL_PROPERTIES);
   }
 
@@ skipping 181 matching lines @@
 
   static PropertyDetails GetDetailsImpl(JSObject* holder, uint32_t entry) {
     return GetDetailsImpl(holder->elements(), entry);
   }
 
   static PropertyDetails GetDetailsImpl(FixedArrayBase* backing_store,
                                         uint32_t entry) {
     return SeededNumberDictionary::cast(backing_store)->DetailsAt(entry);
   }
 
+  static uint32_t GetKeyForEntryImpl(Handle<SeededNumberDictionary> dictionary,
+                                     int entry, PropertyFilter filter) {
+    Object* raw_key = dictionary->KeyAt(entry);
+    if (!dictionary->IsKey(raw_key)) return kMaxUInt32;
+    if (raw_key->FilterKey(filter)) return kMaxUInt32;
+    if (dictionary->IsDeleted(entry)) return kMaxUInt32;
+    DCHECK(raw_key->IsNumber());
+    DCHECK_LE(raw_key->Number(), kMaxUInt32);
+    uint32_t key = static_cast<uint32_t>(raw_key->Number());
+    PropertyDetails details = dictionary->DetailsAt(entry);
+    if (filter & ONLY_ALL_CAN_READ) {
+      if (details.kind() != kAccessor) return kMaxUInt32;
+      Object* accessors = dictionary->ValueAt(entry);
+      if (!accessors->IsAccessorInfo()) return kMaxUInt32;
+      if (!AccessorInfo::cast(accessors)->all_can_read()) return kMaxUInt32;
+    }
+    PropertyAttributes attr = details.attributes();
+    if ((attr & filter) != 0) return kMaxUInt32;
+    return key;
+  }
+
   static void CollectElementIndicesImpl(Handle<JSObject> object,
                                         Handle<FixedArrayBase> backing_store,
                                         KeyAccumulator* keys, uint32_t range,
                                         PropertyFilter filter,
                                         uint32_t offset) {
     Handle<SeededNumberDictionary> dictionary =
         Handle<SeededNumberDictionary>::cast(backing_store);
     int capacity = dictionary->Capacity();
     for (int i = 0; i < capacity; i++) {
-      Object* k = dictionary->KeyAt(i);
-      if (!dictionary->IsKey(k)) continue;
-      if (k->FilterKey(filter)) continue;
-      if (dictionary->IsDeleted(i)) continue;
-      DCHECK(k->IsNumber());
-      DCHECK_LE(k->Number(), kMaxUInt32);
-      uint32_t index = static_cast<uint32_t>(k->Number());
-      if (index < offset) continue;
-      PropertyDetails details = dictionary->DetailsAt(i);
-      if (filter & ONLY_ALL_CAN_READ) {
-        if (details.kind() != kAccessor) continue;
-        Object* accessors = dictionary->ValueAt(i);
-        if (!accessors->IsAccessorInfo()) continue;
-        if (!AccessorInfo::cast(accessors)->all_can_read()) continue;
-      }
-      PropertyAttributes attr = details.attributes();
-      if ((attr & filter) != 0) continue;
-      keys->AddKey(index);
+      uint32_t key = GetKeyForEntryImpl(dictionary, i, filter);
+      if (key == kMaxUInt32) continue;
+      keys->AddKey(key);
     }
 
     keys->SortCurrentElementsList();
   }
 
+  static Handle<FixedArray> FastCollectElementIndicesImpl(
+      Isolate* isolate, Handle<JSObject> object,
+      Handle<FixedArrayBase> backing_store, GetKeysConversion convert,
+      PropertyFilter filter, Handle<FixedArray> list, int* nof_indices) {
+    Handle<SeededNumberDictionary> dictionary =
+        Handle<SeededNumberDictionary>::cast(backing_store);
+
+    int capacity = dictionary->Capacity();
+    int insertion_index = 0;
+    for (uint32_t i = 0; i < capacity; i++) {
+      uint32_t key = GetKeyForEntryImpl(dictionary, i, filter);
+      if (key == kMaxUInt32) continue;
+      list = EnsureSize(isolate, list, insertion_index);
+      if (convert == CONVERT_TO_STRING) {
+        list->set(insertion_index++, *isolate->factory()->Uint32ToString(key));
+      } else {
+        list->set(insertion_index++, Smi::FromInt(key), SKIP_WRITE_BARRIER);
+      }
+    }
+    *nof_indices = insertion_index;
+    return list;
+  }
+
   static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver,
                                               KeyAccumulator* accumulator,
                                               AddKeyConversion convert) {
     SeededNumberDictionary* dictionary =
         SeededNumberDictionary::cast(receiver->elements());
     int capacity = dictionary->Capacity();
     for (int i = 0; i < capacity; i++) {
       Object* k = dictionary->KeyAt(i);
       if (!dictionary->IsKey(k)) continue;
       if (dictionary->IsDeleted(i)) continue;
@@ skipping 144 matching lines @@
     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 void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver,
                                               KeyAccumulator* accumulator,
                                               AddKeyConversion convert) {
-    uint32_t length = 0;
     Handle<FixedArrayBase> elements(receiver->elements(),
                                     receiver->GetIsolate());
-    if (receiver->IsJSArray()) {
-      length = Smi::cast(JSArray::cast(*receiver)->length())->value();
-    } else {
-      length =
-          FastElementsAccessorSubclass::GetCapacityImpl(*receiver, *elements);
-    }
+    uint32_t length =
+        FastElementsAccessorSubclass::GetIterationLength(*receiver, *elements);
     for (uint32_t i = 0; i < length; i++) {
       if (IsFastPackedElementsKind(KindTraits::Kind) ||
           HasEntryImpl(*elements, i)) {
         accumulator->AddKey(FastElementsAccessorSubclass::GetImpl(*elements, i),
                             convert);
       }
     }
   }
 
   static void ValidateContents(Handle<JSObject> holder, int length) {
@@ skipping 1343 matching lines @@
     }
   }
 
   DCHECK(j == result_len);
   return result_array;
 }
 
 ElementsAccessor** ElementsAccessor::elements_accessors_ = NULL;
 }  // namespace internal
 }  // namespace v8