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

src/builtins.cc

Index: src/builtins.cc
diff --git a/src/builtins.cc b/src/builtins.cc
index f40b5c27741787d5869fd3e0a61e92bb917d3bf1..5fbe000f87f7d7745390880d3ae61fc1a9f338e1 100644
--- a/src/builtins.cc
+++ b/src/builtins.cc
@@ -336,6 +336,7 @@ static FixedArray* LeftTrimFixedArray(FixedArray* elms, int to_trim) {
   // 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);
@@ -718,97 +719,138 @@ BUILTIN(ArraySplice) {
   }
   int actual_delete_count = Min(Max(delete_count, 0), len - actual_start);
 
+  int item_count = (n_arguments > 1) ? (n_arguments - 2) : 0;
+
+  int new_length = len - actual_delete_count + item_count;
+
   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.
+  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);
 
-    result = Heap::AllocateUninitializedFixedArray(actual_delete_count);
+    result = Heap::AllocateUninitializedFixedArray(new_length);
     if (result->IsFailure()) return result;
-    FixedArray* result_elms = FixedArray::cast(result);
+    FixedArray* receiver_elms = FixedArray::cast(result);
 
-    AssertNoAllocation no_gc;
-    // Fill newly created array.
-    CopyElements(&no_gc,
-                 result_elms, 0,
-                 elms, actual_start,
-                 actual_delete_count);
+    int tail_length = len - actual_start - actual_delete_count;
+    ASSERT(tail_length >= 0);
 
-    // Set elements.
-    result_array->set_elements(result_elms);
+    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));
 
-    // Set the 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);
 
-  int item_count = (n_arguments > 1) ? (n_arguments - 2) : 0;
-
-  int new_length = len - actual_delete_count + item_count;
+    elms = receiver_elms;
+  } else {
+    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);
 
-  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);
-      }
+      result = Heap::AllocateUninitializedFixedArray(actual_delete_count);
+      if (result->IsFailure()) return result;
+      FixedArray* result_elms = FixedArray::cast(result);
 
-      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);
+      // 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));
     }
-  } 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,
+    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,
-                     to_copy);
+                     (len - actual_delete_count - actual_start));
+        FillWithHoles(elms, new_length, len);
       }
-      FillWithHoles(new_elms, new_length, capacity);
+    } 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);
 
-      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;
+        // 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,
+                     (len - actual_delete_count - actual_start));
+      }
     }
   }