[Not for commit] Make Array.splice change receiver's FixedArray when significant part is cut.

src/builtins.cc

 // Copyright 2006-2008 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 318 matching lines @@
 }
 
 
 static FixedArray* LeftTrimFixedArray(FixedArray* elms, int to_trim) {
   // For now this trick is only applied to fixed arrays in new space.
   // In large object space the object's start must coincide with chunk
   // and thus the trick is just not applicable.
   // In old space we do not use this trick to avoid dealing with
   // remembered sets.
   ASSERT(Heap::new_space()->Contains(elms));
+  ASSERT(to_trim > 0);
 
   STATIC_ASSERT(FixedArray::kMapOffset == 0);
   STATIC_ASSERT(FixedArray::kLengthOffset == kPointerSize);
   STATIC_ASSERT(FixedArray::kHeaderSize == 2 * kPointerSize);
 
   Object** former_start = HeapObject::RawField(elms, 0);
 
   const int len = elms->length();
 
   // Technically in new space this write might be omitted (except for
@@ skipping 362 matching lines @@
   if (n_arguments > 1) {
     Object* arg2 = args[2];
     if (arg2->IsSmi()) {
       delete_count = Smi::cast(arg2)->value();
     } else {
       return CallJsBuiltin("ArraySplice", args);
     }
   }
   int actual_delete_count = Min(Max(delete_count, 0), len - actual_start);
 
-  JSArray* result_array = NULL;
-  if (actual_delete_count == 0) {
-    Object* result = AllocateEmptyJSArray();
-    if (result->IsFailure()) return result;
-    result_array = JSArray::cast(result);
-  } else {
-    // Allocate result array.
-    Object* result = AllocateJSArray();
-    if (result->IsFailure()) return result;
-    result_array = JSArray::cast(result);
-
-    result = Heap::AllocateUninitializedFixedArray(actual_delete_count);
-    if (result->IsFailure()) return result;
-    FixedArray* result_elms = FixedArray::cast(result);
-
-    AssertNoAllocation no_gc;
-    // Fill newly created array.
-    CopyElements(&no_gc,
-                 result_elms, 0,
-                 elms, actual_start,
-                 actual_delete_count);
-
-    // Set elements.
-    result_array->set_elements(result_elms);
-
-    // Set the length.
-    result_array->set_length(Smi::FromInt(actual_delete_count));
-  }
-
   int item_count = (n_arguments > 1) ? (n_arguments - 2) : 0;
 
   int new_length = len - actual_delete_count + item_count;
 
-  if (item_count < actual_delete_count) {
-    // Shrink the array.
-    const bool trim_array = Heap::new_space()->Contains(elms) &&
-      ((actual_start + item_count) <
-          (len - actual_delete_count - actual_start));
-    if (trim_array) {
-      const int delta = actual_delete_count - item_count;
+  JSArray* result_array = NULL;
+  if (Heap::new_space()->Contains(elms) &&
+      (2 * actual_delete_count >= len + item_count)) {

[antonm, 2010/04/05 12:21:13]

looks like you're trying to keep the number of writes minimal.  In this case for
inplace result number of writes is actual_start + tail_length (+ tail_length to
fill with the holes) while out of place result requires item_count + tail_length
moves.

Thus condition might be actual_start + tail_length >= item_count. 

[iegorov, 2010/04/05 13:01:49]

My counts differ:
- when making inplace (terminology: that's what I do, right?): we need
actual_start + items_count + tail_length to create result, and tail_length
writes to make holes in receiver;
- unfortunately when doing out of place, the result differs on items_count
compared to actual_delete_count. When equal: it is only items_count, when
items_count is less than actual_delete_count it is items_count + tail_length
moves, otherwise it results in creation of a new array, which is items_count +
tail_length + actual_start.

The question is what is the boundary? Should I count it precisely? 
On 2010/04/05 12:21:13, antonm wrote:

[antonm, 2010/04/05 14:34:30]

Sorry, I should have been explicit but I didn't account for item_writes as there
is no way to escape them (unless we'd like to allocate result's elements in the
stack, kidding :).

So estimate for new approach for result allocation appears to be the same for
you and me: actual_start + 2*tail_length + item_count.

Now to estimates for the present approach.  My mistake was I only thought about
one case when length of fixed element array is enough.  Now to your more
detailed analysis.

item_count == actual_delete_count:

It's not just item_count---it's 2*item_count if you account for new elements
writes---item_count to copy old items + item_count to write new ones.  So we do
less writes with new approach given actual_start + 2*tail_length < item_count.

item_count < actual_delete_count:

I think we need item_count (new elements writes) + tail_length (to move former
elements) + (actual_delete_count - item_count) (to fill with the holes) (if we
cannot apply new space trick which could save additional moves)

item_count > actual_delete_count:

even more complicated as we need to fill with the holes the rest of newly
allocated array.

Overall numbers seems quite different and I suspect (but I didn't think
properly) when simple heuristics could lead to worse behaviour.

So could you experiment (if you please, of course) if it's possible to refactor
the code in the following fashion:

for all three cases (item_count <>= actual_delete_count) we decide how exactly
we should go?

On 2010/04/05 13:01:49, iegorov wrote:

+    // Allocate array for receiver's array.
+    Object* result = AllocateJSArray();
+    if (result->IsFailure()) return result;
+    result_array = JSArray::cast(result);
 
-      if (actual_start > 0) {
-        Object** start = elms->data_start();
-        memmove(start + delta, start, actual_start * kPointerSize);
-      }
+    result = Heap::AllocateUninitializedFixedArray(new_length);
+    if (result->IsFailure()) return result;
+    FixedArray* receiver_elms = FixedArray::cast(result);
 
-      elms = LeftTrimFixedArray(elms, delta);
-      array->set_elements(elms, SKIP_WRITE_BARRIER);
+    int tail_length = len - actual_start - actual_delete_count;
+    ASSERT(tail_length >= 0);
+
+    AssertNoAllocation no_gc;
+    // Fill with receiver elements.
+    if (actual_start > 0) {
+      CopyElements(&no_gc,
+                   receiver_elms, 0,
+                   elms, 0,
+                   actual_start);
+    }
+    if (tail_length > 0) {
+      CopyElements(&no_gc,
+                   receiver_elms, actual_start + item_count,
+                   elms, actual_start + actual_delete_count,
+                   tail_length);
+    }
+    array->set_elements(receiver_elms);
+    array->set_length(Smi::FromInt(new_length));
+
+    if (actual_start > 0) {
+      elms = LeftTrimFixedArray(elms, actual_start);

[antonm, 2010/04/05 12:21:13]

good you noticed that---was going to bring your attention to it :)

[iegorov, 2010/04/05 13:01:49]

Yeah, testing rocks :)
On 2010/04/05 12:21:13, antonm wrote:

+    }
+    result_array->set_elements(elms, SKIP_WRITE_BARRIER);
+    result_array->set_length(Smi::FromInt(actual_delete_count));
+    FillWithHoles(elms, actual_delete_count, len - actual_start);
+
+    elms = receiver_elms;
+  } else {
+    if (actual_delete_count == 0) {
+      Object* result = AllocateEmptyJSArray();
+      if (result->IsFailure()) return result;
+      result_array = JSArray::cast(result);
     } else {
-      AssertNoAllocation no_gc;
-      MoveElements(&no_gc,
-                   elms, actual_start + item_count,
-                   elms, actual_start + actual_delete_count,
-                   (len - actual_delete_count - actual_start));
-      FillWithHoles(elms, new_length, len);
-    }
-  } else if (item_count > actual_delete_count) {
-    // Currently fixed arrays cannot grow too big, so
-    // we should never hit this case.
-    ASSERT((item_count - actual_delete_count) <= (Smi::kMaxValue - len));
+      // Allocate result array.
+      Object* result = AllocateJSArray();
+      if (result->IsFailure()) return result;
+      result_array = JSArray::cast(result);
 
-    // Check if array need to grow.
-    if (new_length > elms->length()) {
-      // New backing storage is needed.
-      int capacity = new_length + (new_length >> 1) + 16;
-      Object* obj = Heap::AllocateUninitializedFixedArray(capacity);
-      if (obj->IsFailure()) return obj;
-      FixedArray* new_elms = FixedArray::cast(obj);
+      result = Heap::AllocateUninitializedFixedArray(actual_delete_count);
+      if (result->IsFailure()) return result;
+      FixedArray* result_elms = FixedArray::cast(result);
 
       AssertNoAllocation no_gc;
-      // Copy the part before actual_start as is.
-      if (actual_start > 0) {
-        CopyElements(&no_gc, new_elms, 0, elms, 0, actual_start);
+      // Fill newly created array.
+      CopyElements(&no_gc,
+                   result_elms, 0,
+                   elms, actual_start,
+                   actual_delete_count);
+
+      // Set elements.
+      result_array->set_elements(result_elms);
+
+      // Set the length.
+      result_array->set_length(Smi::FromInt(actual_delete_count));
+    }
+
+    if (item_count < actual_delete_count) {
+      // Shrink the array.
+      const bool trim_array = Heap::new_space()->Contains(elms) &&
+        ((actual_start + item_count) <
+            (len - actual_delete_count - actual_start));
+      if (trim_array) {
+        const int delta = actual_delete_count - item_count;
+
+        if (actual_start > 0) {
+          Object** start = elms->data_start();
+          memmove(start + delta, start, actual_start * kPointerSize);
+        }
+
+        elms = LeftTrimFixedArray(elms, delta);
+        array->set_elements(elms, SKIP_WRITE_BARRIER);
+      } else {
+        AssertNoAllocation no_gc;
+        MoveElements(&no_gc,
+                     elms, actual_start + item_count,
+                     elms, actual_start + actual_delete_count,
+                     (len - actual_delete_count - actual_start));
+        FillWithHoles(elms, new_length, len);
       }
-      const int to_copy = len - actual_delete_count - actual_start;
-      if (to_copy > 0) {
-        CopyElements(&no_gc,
-                     new_elms, actual_start + item_count,
+    } else if (item_count > actual_delete_count) {
+      // Currently fixed arrays cannot grow too big, so
+      // we should never hit this case.
+      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;
+        Object* obj = Heap::AllocateUninitializedFixedArray(capacity);
+        if (obj->IsFailure()) return obj;
+        FixedArray* new_elms = FixedArray::cast(obj);
+
+        AssertNoAllocation no_gc;
+        // Copy the part before actual_start as is.
+        if (actual_start > 0) {
+          CopyElements(&no_gc, new_elms, 0, elms, 0, actual_start);
+        }
+        const int to_copy = len - actual_delete_count - actual_start;
+        if (to_copy > 0) {
+          CopyElements(&no_gc,
+                       new_elms, actual_start + item_count,
+                       elms, actual_start + actual_delete_count,
+                       to_copy);
+        }
+        FillWithHoles(new_elms, new_length, capacity);
+
+        elms = new_elms;
+        array->set_elements(elms);
+      } else {
+        AssertNoAllocation no_gc;
+        MoveElements(&no_gc,
+                     elms, actual_start + item_count,
                      elms, actual_start + actual_delete_count,
-                     to_copy);
+                     (len - actual_delete_count - actual_start));
       }
-      FillWithHoles(new_elms, new_length, capacity);
-
-      elms = new_elms;
-      array->set_elements(elms);
-    } else {
-      AssertNoAllocation no_gc;
-      MoveElements(&no_gc,
-                   elms, actual_start + item_count,
-                   elms, actual_start + actual_delete_count,
-                   (len - actual_delete_count - actual_start));
     }
   }
 
   AssertNoAllocation no_gc;
   WriteBarrierMode mode = elms->GetWriteBarrierMode(no_gc);
   for (int k = actual_start; k < actual_start + item_count; k++) {
     elms->set(k, args[3 + k - actual_start], mode);
   }
 
   // Set the length.
@@ skipping 710 matching lines @@
       if (entry->contains(pc)) {
         return names_[i];
       }
     }
   }
   return NULL;
 }
 
 
 } }  // namespace v8::internal