Adding ElementsAccessor::Unshift

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 544 matching lines @@
                                 uint32_t entry) {
     uint32_t index = GetIndexForEntryImpl(*backing_store, entry);
     return BackingStore::get(Handle<BackingStore>::cast(backing_store), index);
   }
 
   virtual void Set(FixedArrayBase* backing_store, uint32_t entry,
                    Object* value) final {
     ElementsAccessorSubclass::SetImpl(backing_store, entry, value);
   }
 
-  static void SetImpl(FixedArrayBase* backing_store, uint32_t entry,
-                      Object* value) {
+  static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry,
+                             Object* value) {
     BackingStore::cast(backing_store)->SetValue(entry, value);
   }
 
+  static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry,
+                             Object* value, WriteBarrierMode mode) {
+    BackingStore::cast(backing_store)->SetValue(entry, value);
+  }
+
   virtual void Reconfigure(Handle<JSObject> object,
                            Handle<FixedArrayBase> store, uint32_t entry,
                            Handle<Object> value,
                            PropertyAttributes attributes) final {
     ElementsAccessorSubclass::ReconfigureImpl(object, store, entry, value,
                                               attributes);
   }
 
   static void ReconfigureImpl(Handle<JSObject> object,
                               Handle<FixedArrayBase> store, uint32_t entry,
@@ skipping 22 matching lines @@
                                               push_size, direction);
   }
 
   static uint32_t PushImpl(Handle<JSArray> receiver,
                            Handle<FixedArrayBase> elms_obj, Object** objects,
                            uint32_t push_size, int direction) {
     UNREACHABLE();
     return 0;
   }
 
+  virtual uint32_t Unshift(Handle<JSArray> receiver,
+                           Handle<FixedArrayBase> backing_store,
+                           Arguments* args, uint32_t unshift_size) final {
+    return ElementsAccessorSubclass::UnshiftImpl(receiver, backing_store, args,
+                                                 unshift_size);
+  }
+
+  static uint32_t UnshiftImpl(Handle<JSArray> receiver,
+                              Handle<FixedArrayBase> elms_obj, Arguments* args,
+                              uint32_t unshift_size) {
+    UNREACHABLE();
+    return 0;
+  }
+
   virtual Handle<JSArray> Slice(Handle<JSObject> receiver,
                                 Handle<FixedArrayBase> backing_store,
                                 uint32_t start, uint32_t end) final {
     return ElementsAccessorSubclass::SliceImpl(receiver, backing_store, start,
                                                end);
   }
 
   static Handle<JSArray> SliceImpl(Handle<JSObject> receiver,
                                    Handle<FixedArrayBase> backing_store,
                                    uint32_t start, uint32_t end) {
@@ skipping 33 matching lines @@
                                             handle(array->elements()));
   }
 
   static void SetLengthImpl(Handle<JSArray> array, uint32_t length,
                             Handle<FixedArrayBase> backing_store);
 
   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,
+        object, old_elements, from_kind, capacity, 0, 0,
         ElementsAccessor::kCopyToEndAndInitializeToHole);
   }
 
   static Handle<FixedArrayBase> ConvertElementsWithCapacity(
       Handle<JSObject> object, Handle<FixedArrayBase> old_elements,
       ElementsKind from_kind, uint32_t capacity, int copy_size) {
+    return ConvertElementsWithCapacity(object, old_elements, from_kind,
+                                       capacity, 0, 0, copy_size);
+  }
+
+  static Handle<FixedArrayBase> ConvertElementsWithCapacity(
+      Handle<JSObject> object, Handle<FixedArrayBase> old_elements,
+      ElementsKind from_kind, uint32_t capacity, uint32_t src_index,
+      uint32_t dst_index, int copy_size) {

[Camillo Bruni, 2015/09/01 08:45:12]

Added this ConvertElementsWithCapacity to avoid code duplication and copying
elements twice (src_index and dst_index are new arguments)

     Isolate* isolate = object->GetIsolate();
     Handle<FixedArrayBase> new_elements;
     if (IsFastDoubleElementsKind(kind())) {
       new_elements = isolate->factory()->NewFixedDoubleArray(capacity);
     } else {
       new_elements = isolate->factory()->NewUninitializedFixedArray(capacity);
     }
 
     int packed_size = kPackedSizeNotKnown;
     if (IsFastPackedElementsKind(from_kind) && object->IsJSArray()) {
       packed_size = Smi::cast(JSArray::cast(*object)->length())->value();
     }
 
     ElementsAccessorSubclass::CopyElementsImpl(
-        *old_elements, 0, *new_elements, from_kind, 0, packed_size, copy_size);
+        *old_elements, src_index, *new_elements, from_kind, dst_index,
+        packed_size, copy_size);
 
     return new_elements;
   }
 
   static void GrowCapacityAndConvertImpl(Handle<JSObject> object,
                                          uint32_t capacity) {
     ElementsKind from_kind = object->GetElementsKind();
     if (IsFastSmiOrObjectElementsKind(from_kind)) {
       // Array optimizations rely on the prototype lookups of Array objects
       // always returning undefined. If there is a store to the initial
@@ skipping 297 matching lines @@
   static Object* GetRaw(FixedArrayBase* store, uint32_t entry) {
     SeededNumberDictionary* backing_store = SeededNumberDictionary::cast(store);
     return backing_store->ValueAt(entry);
   }
 
   static Handle<Object> GetImpl(Handle<FixedArrayBase> store, uint32_t entry) {
     Isolate* isolate = store->GetIsolate();
     return handle(GetRaw(*store, entry), isolate);
   }
 
-  static void SetImpl(FixedArrayBase* store, uint32_t entry, Object* value) {
+  static inline void SetImpl(FixedArrayBase* store, uint32_t entry,
+                             Object* value) {
     SeededNumberDictionary* dictionary = SeededNumberDictionary::cast(store);
     dictionary->ValueAtPut(entry, value);
   }
 
   static void ReconfigureImpl(Handle<JSObject> object,
                               Handle<FixedArrayBase> store, uint32_t entry,
                               Handle<Object> value,
                               PropertyAttributes attributes) {
     SeededNumberDictionary* dictionary = SeededNumberDictionary::cast(*store);
     if (attributes != NONE) object->RequireSlowElements(dictionary);
@@ skipping 268 matching lines @@
     }
     if (!new_elms.is_identical_to(backing_store)) {
       receiver->set_elements(*new_elms);
     }
     DCHECK(*new_elms == receiver->elements());
     // Set the length.
     receiver->set_length(Smi::FromInt(new_length));
     return new_length;
   }
 
+  static uint32_t UnshiftImpl(Handle<JSArray> receiver,
+                              Handle<FixedArrayBase> backing_store,
+                              Arguments* args, uint32_t unshift_size) {
+    uint32_t len = Smi::cast(receiver->length())->value();
+    if (unshift_size == 0) {
+      return len;
+    }
+    uint32_t elms_len = backing_store->length();
+    // Currently fixed arrays cannot grow too big, so
+    // we should never hit this case.
+    DCHECK(unshift_size <= static_cast<uint32_t>(Smi::kMaxValue - len));
+    uint32_t new_length = len + unshift_size;
+
+    if (new_length > elms_len) {
+      // New backing storage is needed.
+      uint32_t capacity = new_length + (new_length >> 1) + 16;
+      backing_store = FastElementsAccessorSubclass::ConvertElementsWithCapacity(
+          receiver, backing_store, KindTraits::Kind, capacity, 0, unshift_size,
+          ElementsAccessor::kCopyToEndAndInitializeToHole);
+      DisallowHeapAllocation no_gc;
+      receiver->set_elements(*backing_store);
+    } else {
+      // unshift_size is > 0 and new_length <= elms_len, so backing_store cannot
+      // be the empty_fixed_array.
+      DisallowHeapAllocation no_gc;
+      Isolate* isolate = receiver->GetIsolate();
+      FastElementsAccessorSubclass::MoveElements(isolate->heap(), backing_store,
+                                                 unshift_size, 0, len, 0, 0);
+    }
+
+    // Add the provided values.
+    DisallowHeapAllocation no_gc;
+    FixedArrayBase* raw_backing_store = *backing_store;
+    WriteBarrierMode mode = raw_backing_store->GetWriteBarrierMode(no_gc);

[Camillo Bruni, 2015/09/01 08:45:12]

Introduced the second SetImpl so we can pass along a single WriteBarrierrMode ->
less overhead.

+    for (uint32_t index = 0; index < unshift_size; index++) {
+      FastElementsAccessorSubclass::SetImpl(raw_backing_store, index,
+                                            (*args)[index + 1], mode);
+    }
+    // Set the length.
+    receiver->set_length(Smi::FromInt(new_length));
+    return new_length;
+  }
+
   static void MoveElements(Heap* heap, Handle<FixedArrayBase> backing_store,
                            int dst_index, int src_index, int len,
                            int hole_start, int hole_end) {
     UNREACHABLE();
   }
 
   static Handle<JSArray> SliceImpl(Handle<JSObject> receiver,
                                    Handle<FixedArrayBase> backing_store,
                                    uint32_t start, uint32_t end) {
     Isolate* isolate = receiver->GetIsolate();
@@ skipping 125 matching lines @@
 
 template<typename FastElementsAccessorSubclass,
          typename KindTraits>
 class FastSmiOrObjectElementsAccessor
     : public FastElementsAccessor<FastElementsAccessorSubclass, KindTraits> {
  public:
   explicit FastSmiOrObjectElementsAccessor(const char* name)
       : FastElementsAccessor<FastElementsAccessorSubclass,
                              KindTraits>(name) {}
 
+  static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry,
+                             Object* value) {
+    FixedArray::cast(backing_store)->set(entry, value);

[Camillo Bruni, 2015/09/01 08:45:13]

If I don't use the more uniform SetValue method (which has the same sign. on
FixedArray, FixedDoubleArray and FixedTypeArray) I get a 65% speedup on an
argument heavy [].unshift(1,...1000); Probably an inlining issue?

+  }
+
+  static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry,
+                             Object* value, WriteBarrierMode mode) {
+    FixedArray::cast(backing_store)->set(entry, value, mode);
+  }
+
   static Object* GetRaw(FixedArray* backing_store, uint32_t entry) {
     uint32_t index = FastElementsAccessorSubclass::GetIndexForEntryImpl(
         backing_store, entry);
     return backing_store->get(index);
   }
 
   static void MoveElements(Heap* heap, Handle<FixedArrayBase> backing_store,
                            int dst_index, int src_index, int len,
                            int hole_start, int hole_end) {
     Handle<FixedArray> dst_elms = Handle<FixedArray>::cast(backing_store);
@@ skipping 99 matching lines @@
 
 template<typename FastElementsAccessorSubclass,
          typename KindTraits>
 class FastDoubleElementsAccessor
     : public FastElementsAccessor<FastElementsAccessorSubclass, KindTraits> {
  public:
   explicit FastDoubleElementsAccessor(const char* name)
       : FastElementsAccessor<FastElementsAccessorSubclass,
                              KindTraits>(name) {}
 
+  static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry,
+                             Object* value) {

[Camillo Bruni, 2015/09/01 08:45:12]

If I leave out this version (for FixedDoubleArray) I get a 20% speedup on
[].unshift(1,......1000).

+    FixedDoubleArray::cast(backing_store)->set(entry, value->Number());
+  }
+
+  static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry,
+                             Object* value, WriteBarrierMode mode) {
+    FixedDoubleArray::cast(backing_store)->set(entry, value->Number());
+  }
+
   static void MoveElements(Heap* heap, Handle<FixedArrayBase> backing_store,
                            int dst_index, int src_index, int len,
                            int hole_start, int hole_end) {
     Handle<FixedDoubleArray> dst_elms =
         Handle<FixedDoubleArray>::cast(backing_store);
     if (len != 0) {
       MemMove(dst_elms->data_start() + dst_index,
               dst_elms->data_start() + src_index, len * kDoubleSize);
     }
     if (hole_start != hole_end) {
@@ skipping 170 matching lines @@
       }
       return result;
     }
   }
 
   static void GrowCapacityAndConvertImpl(Handle<JSObject> object,
                                          uint32_t capacity) {
     UNREACHABLE();
   }
 
-  static void SetImpl(FixedArrayBase* store, uint32_t entry, Object* value) {
+  static inline void SetImpl(FixedArrayBase* store, uint32_t entry,
+                             Object* value) {
     FixedArray* parameter_map = FixedArray::cast(store);
     uint32_t length = parameter_map->length() - 2;
     if (entry < length) {
       Object* probe = parameter_map->get(entry + 2);
       Context* context = Context::cast(parameter_map->get(0));
       int context_entry = Smi::cast(probe)->value();
       DCHECK(!context->get(context_entry)->IsTheHole());
       context->set(context_entry, value);
     } else {
       FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
@@ skipping 459 matching lines @@
 
 
 void ElementsAccessor::TearDown() {
   if (elements_accessors_ == NULL) return;
 #define ACCESSOR_DELETE(Class, Kind, Store) delete elements_accessors_[Kind];
   ELEMENTS_LIST(ACCESSOR_DELETE)
 #undef ACCESSOR_DELETE
   elements_accessors_ = NULL;
 }
 
-
 ElementsAccessor** ElementsAccessor::elements_accessors_ = NULL;
 }  // namespace internal
 }  // namespace v8