Fix array concat for holey arrays and concat of double to object arrays.

src/builtins.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 250 matching lines @@
   // Allocate an appropriately typed elements array.
   MaybeObject* maybe_elms;
   ElementsKind elements_kind = array->GetElementsKind();
   if (IsFastDoubleElementsKind(elements_kind)) {
     maybe_elms = heap->AllocateUninitializedFixedDoubleArray(
         number_of_elements);
   } else {
     maybe_elms = heap->AllocateFixedArrayWithHoles(number_of_elements);
   }
   FixedArrayBase* elms;
-  if (!maybe_elms->To<FixedArrayBase>(&elms)) return maybe_elms;
+  if (!maybe_elms->To(&elms)) return maybe_elms;
 
   // Fill in the content
   switch (array->GetElementsKind()) {
     case FAST_HOLEY_SMI_ELEMENTS:
     case FAST_SMI_ELEMENTS: {
       FixedArray* smi_elms = FixedArray::cast(elms);
       for (int index = 0; index < number_of_elements; index++) {
         smi_elms->set(index, (*args)[index+1], SKIP_WRITE_BARRIER);
       }
       break;
@@ skipping 105 matching lines @@
   ASSERT(!HEAP->lo_space()->Contains(elms));
 
   STATIC_ASSERT(FixedArrayBase::kMapOffset == 0);
   STATIC_ASSERT(FixedArrayBase::kLengthOffset == kPointerSize);
   STATIC_ASSERT(FixedArrayBase::kHeaderSize == 2 * kPointerSize);
 
   Object** former_start = HeapObject::RawField(elms, 0);
 
   const int len = elms->length();
 
-  if (to_trim > FixedArrayBase::kHeaderSize / entry_size &&
+  if (to_trim * entry_size > FixedArrayBase::kHeaderSize &&
       elms->IsFixedArray() &&
       !heap->new_space()->Contains(elms)) {
     // If we are doing a big trim in old space then we zap the space that was
     // formerly part of the array so that the GC (aided by the card-based
     // remembered set) won't find pointers to new-space there.
     Object** zap = reinterpret_cast<Object**>(elms->address());
     zap++;  // Header of filler must be at least one word so skip that.
     for (int i = 1; i < to_trim; i++) {
       *zap++ = Smi::FromInt(0);
     }
@@ skipping 162 matching lines @@
     if (new_length > elms->length()) {
       // New backing storage is needed.
       int capacity = new_length + (new_length >> 1) + 16;
       FixedArray* new_elms;
       MaybeObject* maybe_obj = heap->AllocateUninitializedFixedArray(capacity);
       if (!maybe_obj->To(&new_elms)) return maybe_obj;
 
       if (len > 0) {
         ElementsAccessor* accessor = array->GetElementsAccessor();
         MaybeObject* maybe_failure =
-            accessor->CopyElements(array, 0, new_elms, kind, 0, len, elms_obj);
+            accessor->CopyElements(NULL, 0, new_elms, kind, 0, len, elms_obj);
         ASSERT(!maybe_failure->IsFailure());
         USE(maybe_failure);
       }
       FillWithHoles(heap, new_elms, new_length, capacity);
 
       elms = new_elms;
     }
 
     // Add the provided values.
     AssertNoAllocation no_gc;
@@ skipping 28 matching lines @@
     if (new_length > elms_len) {
       // New backing storage is needed.
       int capacity = new_length + (new_length >> 1) + 16;
       MaybeObject* maybe_obj =
           heap->AllocateUninitializedFixedDoubleArray(capacity);
       if (!maybe_obj->To(&new_elms)) return maybe_obj;
 
       if (len > 0) {
         ElementsAccessor* accessor = array->GetElementsAccessor();
         MaybeObject* maybe_failure =
-            accessor->CopyElements(array, 0, new_elms, kind, 0, len, elms_obj);
+            accessor->CopyElements(NULL, 0, new_elms, kind, 0, len, elms_obj);
         ASSERT(!maybe_failure->IsFailure());
         USE(maybe_failure);
       }
 
       FillWithHoles(new_elms, len + to_add, new_elms->length());
     } else {
       // to_add is > 0 and new_length <= elms_len, so elms_obj cannot be the
       // empty_fixed_array.
       new_elms = FixedDoubleArray::cast(elms_obj);
     }
@@ skipping 144 matching lines @@
     // New backing storage is needed.
     int capacity = new_length + (new_length >> 1) + 16;
     FixedArray* new_elms;
     MaybeObject* maybe_elms = heap->AllocateUninitializedFixedArray(capacity);
     if (!maybe_elms->To(&new_elms)) return maybe_elms;
 
     if (len > 0) {
       ElementsKind kind = array->GetElementsKind();
       ElementsAccessor* accessor = array->GetElementsAccessor();
       MaybeObject* maybe_failure =
-          accessor->CopyElements(array, 0, new_elms, kind, to_add, len, elms);
+          accessor->CopyElements(NULL, 0, new_elms, kind, to_add, len, elms);
       ASSERT(!maybe_failure->IsFailure());
       USE(maybe_failure);
     }
 
     FillWithHoles(heap, new_elms, new_length, capacity);
     elms = new_elms;
     array->set_elements(elms);
   } else {
     AssertNoAllocation no_gc;
     MoveElements(heap, &no_gc, elms, to_add, elms, 0, len);
@@ skipping 124 matching lines @@
                                  : Min(relative_end, len);
 
   // Calculate the length of result array.
   int result_len = Max(final - k, 0);
 
   JSArray* result_array;
   MaybeObject* maybe_array = heap->AllocateJSArrayAndStorage(kind,
                                                              result_len,
                                                              result_len);
 
+  AssertNoAllocation no_gc;
   if (result_len == 0) return maybe_array;
   if (!maybe_array->To(&result_array)) return maybe_array;
 
   ElementsAccessor* accessor = object->GetElementsAccessor();
   MaybeObject* maybe_failure =
-      accessor->CopyElements(object, k, result_array->elements(),
+      accessor->CopyElements(NULL, k, result_array->elements(),
                              kind, 0, result_len, elms);
   ASSERT(!maybe_failure->IsFailure());
   USE(maybe_failure);
 
   return result_array;
 }
 
 
 BUILTIN(ArraySplice) {
   Heap* heap = isolate->heap();
@@ skipping 78 matching lines @@
     return maybe_array;
   }
 
   JSArray* result_array = NULL;
   MaybeObject* maybe_array =
       heap->AllocateJSArrayAndStorage(elements_kind,
                                       actual_delete_count,
                                       actual_delete_count);
   if (!maybe_array->To(&result_array)) return maybe_array;
 
-  if (actual_delete_count > 0) {
-    ElementsAccessor* accessor = array->GetElementsAccessor();
-    MaybeObject* maybe_failure =
-        accessor->CopyElements(array, actual_start, result_array->elements(),
-                               elements_kind, 0, actual_delete_count, elms_obj);
-    // Cannot fail since the origin and target array are of the same elements
-    // kind.
-    ASSERT(!maybe_failure->IsFailure());
-    USE(maybe_failure);
+  {
+    AssertNoAllocation no_gc;

[mvstanton, 2012/11/22 15:55:41]

Here you have a scoping brace, for the AssertNoAllocation? Style-wise, I
wouldn't do it because it's not done at other sites.

[Toon Verwaest, 2012/11/22 16:23:13]

Done.

+
+    if (actual_delete_count > 0) {
+      ElementsAccessor* accessor = array->GetElementsAccessor();
+      MaybeObject* maybe_failure =
+          accessor->CopyElements(NULL, actual_start, result_array->elements(),
+                                 elements_kind, 0, actual_delete_count, elms_obj);
+      // Cannot fail since the origin and target array are of the same elements
+      // kind.
+      ASSERT(!maybe_failure->IsFailure());
+      USE(maybe_failure);
+    }
   }
 
   bool elms_changed = false;
   if (item_count < actual_delete_count) {
     // Shrink the array.
     const bool trim_array = !heap->lo_space()->Contains(elms_obj) &&
       ((actual_start + item_count) <
           (len - actual_delete_count - actual_start));
     if (trim_array) {
       const int delta = actual_delete_count - item_count;
@@ skipping 34 matching lines @@
     ASSERT((item_count - actual_delete_count) <= (Smi::kMaxValue - len));
 
     // Check if array need to grow.
     if (new_length > elms->length()) {
       // New backing storage is needed.
       int capacity = new_length + (new_length >> 1) + 16;
       FixedArray* new_elms;
       MaybeObject* maybe_obj = heap->AllocateUninitializedFixedArray(capacity);
       if (!maybe_obj->To(&new_elms)) return maybe_obj;
 
+      AssertNoAllocation no_gc;
+
       ElementsKind kind = array->GetElementsKind();
       ElementsAccessor* accessor = array->GetElementsAccessor();
       if (actual_start > 0) {
         // Copy the part before actual_start as is.
         MaybeObject* maybe_failure = accessor->CopyElements(
-            array, 0, new_elms, kind, 0, actual_start, elms);
+            NULL, 0, new_elms, kind, 0, actual_start, elms);
         ASSERT(!maybe_failure->IsFailure());
         USE(maybe_failure);
       }
       const int to_copy = len - actual_delete_count - actual_start;
       if (to_copy > 0) {
         MaybeObject* maybe_failure = accessor->CopyElements(
-            array, actual_start + actual_delete_count, new_elms, kind,
+            NULL, actual_start + actual_delete_count, new_elms, kind,
             actual_start + item_count, to_copy, elms);
         ASSERT(!maybe_failure->IsFailure());
         USE(maybe_failure);
       }
 
       FillWithHoles(heap, new_elms, new_length, capacity);
 
       elms_obj = new_elms;
       elms_changed = true;
     } else {
@@ skipping 41 matching lines @@
       JSObject::cast(native_context->array_function()->prototype());
   if (!ArrayPrototypeHasNoElements(heap, native_context, array_proto)) {
     return CallJsBuiltin(isolate, "ArrayConcat", args);
   }
 
   // Iterate through all the arguments performing checks
   // and calculating total length.
   int n_arguments = args.length();
   int result_len = 0;
   ElementsKind elements_kind = GetInitialFastElementsKind();
+  bool has_double = false;
+  bool is_holey = false;
   for (int i = 0; i < n_arguments; i++) {
     Object* arg = args[i];
     if (!arg->IsJSArray() ||
         !JSArray::cast(arg)->HasFastElements() ||
         JSArray::cast(arg)->GetPrototype() != array_proto) {
       return CallJsBuiltin(isolate, "ArrayConcat", args);
     }
     int len = Smi::cast(JSArray::cast(arg)->length())->value();
 
     // We shouldn't overflow when adding another len.
     const int kHalfOfMaxInt = 1 << (kBitsPerInt - 2);
     STATIC_ASSERT(FixedArray::kMaxLength < kHalfOfMaxInt);
     USE(kHalfOfMaxInt);
     result_len += len;
     ASSERT(result_len >= 0);
 
     if (result_len > FixedDoubleArray::kMaxLength) {
       return CallJsBuiltin(isolate, "ArrayConcat", args);
     }
 
     ElementsKind arg_kind = JSArray::cast(arg)->map()->elements_kind();
+    has_double = has_double || IsFastDoubleElementsKind(arg_kind);

[mvstanton, 2012/11/22 15:55:41]

This works, but you might like something that I have in my current project:

ElementsKind GetUnifiedFastElementsKind(k1,k2);

It does the right thing for our elements transition tree.
For example DOUBLE and HOLEY_SMI unifies to HOLEY_DOUBLE.

You'd still need to keep the has_double boolean for the predicate below.

[Toon Verwaest, 2012/11/22 16:23:13]

Seems like what I have is faster. You can replace it with your
GetUnifiedFastElement once it's in and fast.

On 2012/11/22 15:55:41, mvstanton wrote:

+    is_holey = is_holey || IsFastHoleyElementsKind(arg_kind);
     if (IsMoreGeneralElementsKindTransition(elements_kind, arg_kind)) {
-      elements_kind = IsFastHoleyElementsKind(elements_kind)
-          ? GetHoleyElementsKind(arg_kind) : arg_kind;
+      elements_kind = arg_kind;
     }
   }
 
+  if (is_holey) elements_kind = GetHoleyElementsKind(elements_kind);
+
+  // If a double array is concatted into a fast elements array, the fast
+  // elements array needs to be initialized to contain proper holes, since
+  // boxing doubles may cause incremental marking.
+  ArrayStorageAllocationMode mode =
+      has_double && IsFastObjectElementsKind(elements_kind)
+      ? INITIALIZE_ARRAY_ELEMENTS_WITH_HOLE : DONT_INITIALIZE_ARRAY_ELEMENTS;
   JSArray* result_array;
   // Allocate result.
   MaybeObject* maybe_array =
       heap->AllocateJSArrayAndStorage(elements_kind,
                                       result_len,
-                                      result_len);
+                                      result_len,
+                                      mode);
   if (!maybe_array->To(&result_array)) return maybe_array;
   if (result_len == 0) return result_array;
 
   int j = 0;
   FixedArrayBase* storage = result_array->elements();
   for (int i = 0; i < n_arguments; i++) {
     JSArray* array = JSArray::cast(args[i]);
     int len = Smi::cast(array->length())->value();
     if (len > 0) {
       ElementsAccessor* accessor = array->GetElementsAccessor();
@@ skipping 707 matching lines @@
   return Handle<Code>(code_address);                        \
 }
 BUILTIN_LIST_C(DEFINE_BUILTIN_ACCESSOR_C)
 BUILTIN_LIST_A(DEFINE_BUILTIN_ACCESSOR_A)
 BUILTIN_LIST_DEBUG_A(DEFINE_BUILTIN_ACCESSOR_A)
 #undef DEFINE_BUILTIN_ACCESSOR_C
 #undef DEFINE_BUILTIN_ACCESSOR_A
 
 
 } }  // namespace v8::internal