Optimization of some packed array cases.

src/elements.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 47 matching lines @@
 //     - ExternalDoubleElementsAccessor
 //     - PixelElementsAccessor
 //   - DictionaryElementsAccessor
 //   - NonStrictArgumentsElementsAccessor
 
 
 namespace v8 {
 namespace internal {
 
 
+static const int kPackedSizeNotKnown = -1;
+
+
 // First argument in list is the accessor class, the second argument is the
 // accessor ElementsKind, and the third is the backing store class.  Use the
 // fast element handler for smi-only arrays.  The implementation is currently
 // identical.  Note that the order must match that of the ElementsKind enum for
 // the |accessor_array[]| below to work.
 #define ELEMENTS_LIST(V)                                                \
   V(FastPackedSmiElementsAccessor, FAST_SMI_ELEMENTS, FixedArray)       \
   V(FastHoleySmiElementsAccessor, FAST_HOLEY_SMI_ELEMENTS,              \
     FixedArray)                                                         \
   V(FastPackedObjectElementsAccessor, FAST_ELEMENTS, FixedArray)        \
@@ skipping 241 matching lines @@
   Address from_address = from->address() + FixedDoubleArray::kHeaderSize;
   to_address += kDoubleSize * to_start;
   from_address += kDoubleSize * from_start;
   int words_per_double = (kDoubleSize / kPointerSize);
   CopyWords(reinterpret_cast<Object**>(to_address),
             reinterpret_cast<Object**>(from_address),
             words_per_double * copy_size);
 }
 
 
+static void CopySmiToDoubleElements(FixedArray* from,
+                                    uint32_t from_start,
+                                    FixedDoubleArray* to,
+                                    uint32_t to_start,
+                                    int raw_copy_size) {
+  int copy_size = raw_copy_size;
+  if (raw_copy_size < 0) {
+    ASSERT(raw_copy_size == ElementsAccessor::kCopyToEnd ||
+           raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
+    copy_size = from->length() - from_start;
+    if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
+      for (int i = to_start + copy_size; i < to->length(); ++i) {
+        to->set_the_hole(i);
+      }
+    }
+  }
+  ASSERT((copy_size + static_cast<int>(to_start)) <= to->length() &&
+         (copy_size + static_cast<int>(from_start)) <= from->length());
+  if (copy_size == 0) return;
+  Object* the_hole = from->GetHeap()->the_hole_value();
+  for (uint32_t from_end = from_start + copy_size;
+       from_start < from_end; from_start++, to_start++) {
+    Object* hole_or_smi = from->get(from_start);
+    if (hole_or_smi == the_hole) {
+      to->set_the_hole(to_start);
+    } else {
+      to->set(to_start, Smi::cast(hole_or_smi)->value());
+    }
+  }
+}
+
+
+static void CopyPackedSmiToDoubleElements(FixedArray* from,
+                                          uint32_t from_start,
+                                          FixedDoubleArray* to,
+                                          uint32_t to_start,
+                                          int packed_size,
+                                          int raw_copy_size) {
+  int copy_size = raw_copy_size;
+  uint32_t to_end;
+  if (raw_copy_size < 0) {
+    ASSERT(raw_copy_size == ElementsAccessor::kCopyToEnd ||
+           raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
+    copy_size = from->length() - from_start;
+    if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
+      to_end = to->length();
+    } else {
+      to_end = to_start + copy_size;

[Jakob Kummerow, 2012/06/12 12:50:44]

I have a suspicion that the Windows compiler might wish for a
static_cast<uint32_t>(copy_size) here (and again below).

[danno, 2012/06/12 15:38:14]

Done.

+    }
+  } else {
+    to_end = to_start + copy_size;
+  }
+  ASSERT(static_cast<int>(to_end) <= to->length());
+  ASSERT(packed_size >= 0 && packed_size <= copy_size);
+  ASSERT((copy_size + static_cast<int>(to_start)) <= to->length() &&
+         (copy_size + static_cast<int>(from_start)) <= from->length());
+  if (copy_size == 0) return;
+  for (uint32_t from_end = from_start + packed_size;
+       from_start < from_end; from_start++, to_start++) {
+    Object* smi = from->get(from_start);
+    ASSERT(!smi->IsTheHole());
+    to->set(to_start, Smi::cast(smi)->value());
+  }
+
+  while (to_start < to_end) {
+    to->set_the_hole(to_start++);
+  }
+}
+
+
 static void CopyObjectToDoubleElements(FixedArray* from,
                                        uint32_t from_start,
                                        FixedDoubleArray* to,
                                        uint32_t to_start,
                                        int raw_copy_size) {
   int copy_size = raw_copy_size;
   if (raw_copy_size < 0) {
     ASSERT(raw_copy_size == ElementsAccessor::kCopyToEnd ||
            raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
     copy_size = from->length() - from_start;
     if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
       for (int i = to_start + copy_size; i < to->length(); ++i) {
         to->set_the_hole(i);
       }
     }
   }
   ASSERT((copy_size + static_cast<int>(to_start)) <= to->length() &&
          (copy_size + static_cast<int>(from_start)) <= from->length());
   if (copy_size == 0) return;
-  for (int i = 0; i < copy_size; i++) {
-    Object* hole_or_object = from->get(i + from_start);
-    if (hole_or_object->IsTheHole()) {
-      to->set_the_hole(i + to_start);
+  Object* the_hole = from->GetHeap()->the_hole_value();
+  for (uint32_t from_end = from_start + copy_size;
+       from_start < from_end; from_start++, to_start++) {
+    Object* hole_or_object = from->get(from_start);
+    if (hole_or_object == the_hole) {

[Jakob Kummerow, 2012/06/12 12:50:44]

Why this change? Is it faster?

[danno, 2012/06/12 15:38:14]

Yes :-) 
On 2012/06/12 12:50:44, Jakob wrote:

+      to->set_the_hole(to_start);
     } else {
-      to->set(i + to_start, hole_or_object->Number());
+      to->set(to_start, hole_or_object->Number());
     }
   }
 }
 
 
 static void CopyDictionaryToDoubleElements(SeededNumberDictionary* from,
                                            uint32_t from_start,
                                            FixedDoubleArray* to,
                                            uint32_t to_start,
                                            int raw_copy_size) {
@@ skipping 156 matching lines @@
 
   MUST_USE_RESULT virtual MaybeObject* Delete(JSObject* obj,
                                               uint32_t key,
                                               JSReceiver::DeleteMode mode) = 0;
 
   MUST_USE_RESULT static MaybeObject* CopyElementsImpl(FixedArrayBase* from,
                                                        uint32_t from_start,
                                                        FixedArrayBase* to,
                                                        ElementsKind to_kind,
                                                        uint32_t to_start,
+                                                       int packed_size,
                                                        int copy_size) {
     UNREACHABLE();
     return NULL;
   }
 
   MUST_USE_RESULT virtual MaybeObject* CopyElements(JSObject* from_holder,
                                                     uint32_t from_start,
                                                     FixedArrayBase* to,
                                                     ElementsKind to_kind,
                                                     uint32_t to_start,
                                                     int copy_size,
                                                     FixedArrayBase* from) {
+    int packed_size = kPackedSizeNotKnown;
     if (from == NULL) {
       from = from_holder->elements();
     }
+
+    if (from_holder) {
+      ElementsKind elements_kind = from_holder->GetElementsKind();
+      bool is_packed = FLAG_packed_arrays &&

[Jakob Kummerow, 2012/06/12 12:50:44]

Another unnecessary FLAG check.

[danno, 2012/06/12 15:38:14]

Done.

+          IsFastPackedElementsKind(elements_kind) && from_holder->IsJSArray();
+      if (is_packed) {
+        packed_size = Smi::cast(JSArray::cast(from_holder)->length())->value();
+        if (copy_size >= 0 && packed_size > copy_size) {
+          packed_size = copy_size;
+        }
+      }
+    }
     if (from->length() == 0) {
       return from;
     }
     return ElementsAccessorSubclass::CopyElementsImpl(
-        from, from_start, to, to_kind, to_start, copy_size);
+        from, from_start, to, to_kind, to_start, packed_size, copy_size);
   }
 
   MUST_USE_RESULT virtual MaybeObject* AddElementsToFixedArray(
       Object* receiver,
       JSObject* holder,
       FixedArray* to,
       FixedArrayBase* from) {
     int len0 = to->length();
 #ifdef DEBUG
     if (FLAG_enable_slow_asserts) {
@@ skipping 282 matching lines @@
   explicit FastSmiOrObjectElementsAccessor(const char* name)
       : FastElementsAccessor<FastElementsAccessorSubclass,
                              KindTraits,
                              kPointerSize>(name) {}
 
   static MaybeObject* CopyElementsImpl(FixedArrayBase* from,
                                        uint32_t from_start,
                                        FixedArrayBase* to,
                                        ElementsKind to_kind,
                                        uint32_t to_start,
+                                       int packed_size,
                                        int copy_size) {
     if (IsFastSmiOrObjectElementsKind(to_kind)) {
       CopyObjectToObjectElements(
           FixedArray::cast(from), KindTraits::Kind, from_start,
           FixedArray::cast(to), to_kind, to_start, copy_size);
     } else if (IsFastDoubleElementsKind(to_kind)) {
-      CopyObjectToDoubleElements(
-          FixedArray::cast(from), from_start,
-          FixedDoubleArray::cast(to), to_start, copy_size);
+      if (IsFastSmiElementsKind(KindTraits::Kind)) {
+        if (IsFastPackedElementsKind(KindTraits::Kind) &&
+            packed_size != kPackedSizeNotKnown) {
+          CopyPackedSmiToDoubleElements(
+              FixedArray::cast(from), from_start,
+              FixedDoubleArray::cast(to), to_start,
+              packed_size, copy_size);
+        } else {
+          CopySmiToDoubleElements(
+              FixedArray::cast(from), from_start,
+              FixedDoubleArray::cast(to), to_start, copy_size);
+        }
+      } else {
+        CopyObjectToDoubleElements(
+            FixedArray::cast(from), from_start,
+            FixedDoubleArray::cast(to), to_start, copy_size);
+      }
     } else {
       UNREACHABLE();
     }
     return to->GetHeap()->undefined_value();
   }
 
 
   static MaybeObject* SetFastElementsCapacityAndLength(JSObject* obj,
                                                        uint32_t capacity,
                                                        uint32_t length) {
@@ skipping 74 matching lines @@
     return obj->SetFastDoubleElementsCapacityAndLength(capacity,
                                                        length);
   }
 
  protected:
   static MaybeObject* CopyElementsImpl(FixedArrayBase* from,
                                        uint32_t from_start,
                                        FixedArrayBase* to,
                                        ElementsKind to_kind,
                                        uint32_t to_start,
+                                       int packed_size,
                                        int copy_size) {
     switch (to_kind) {
       case FAST_SMI_ELEMENTS:
       case FAST_ELEMENTS:
       case FAST_HOLEY_SMI_ELEMENTS:
       case FAST_HOLEY_ELEMENTS:
         return CopyDoubleToObjectElements(
             FixedDoubleArray::cast(from), from_start, FixedArray::cast(to),
             to_kind, to_start, copy_size);
       case FAST_DOUBLE_ELEMENTS:
@@ skipping 293 matching lines @@
       }
     }
     return heap->true_value();
   }
 
   MUST_USE_RESULT static MaybeObject* CopyElementsImpl(FixedArrayBase* from,
                                                        uint32_t from_start,
                                                        FixedArrayBase* to,
                                                        ElementsKind to_kind,
                                                        uint32_t to_start,
+                                                       int packed_size,
                                                        int copy_size) {
     switch (to_kind) {
       case FAST_SMI_ELEMENTS:
       case FAST_ELEMENTS:
       case FAST_HOLEY_SMI_ELEMENTS:
       case FAST_HOLEY_ELEMENTS:
         CopyDictionaryToObjectElements(
             SeededNumberDictionary::cast(from), from_start,
             FixedArray::cast(to), to_kind, to_start, copy_size);
         return from;
@@ skipping 132 matching lines @@
       }
     }
     return obj->GetHeap()->true_value();
   }
 
   MUST_USE_RESULT static MaybeObject* CopyElementsImpl(FixedArrayBase* from,
                                                        uint32_t from_start,
                                                        FixedArrayBase* to,
                                                        ElementsKind to_kind,
                                                        uint32_t to_start,
+                                                       int packed_size,
                                                        int copy_size) {
     FixedArray* parameter_map = FixedArray::cast(from);
     FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
     ElementsAccessor* accessor = ElementsAccessor::ForArray(arguments);
     return accessor->CopyElements(NULL, from_start, to, to_kind,
                                   to_start, copy_size, arguments);
   }
 
   static uint32_t GetCapacityImpl(FixedArray* parameter_map) {
     FixedArrayBase* arguments = FixedArrayBase::cast(parameter_map->get(1));
@@ skipping 144 matching lines @@
   if (!maybe_obj->To(&new_backing_store)) return maybe_obj;
   new_backing_store->set(0, length);
   { MaybeObject* result = array->SetContent(new_backing_store);
     if (result->IsFailure()) return result;
   }
   return array;
 }
 
 
 } }  // namespace v8::internal