Keep new arrays allocated with 'new Array(N)' in fast mode (revisited)

src/array.js

 // 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.
 
 "use strict";
 
 // This file relies on the fact that the following declarations have been made
 // in runtime.js:
 // var $Array = global.Array;
 
@@ skipping 68 matching lines @@
       var e = array[key];
       if (!IS_STRING(e)) e = convert(e);
       elements[elements_length++] = e;
       last_key = key;
     }
   }
   return %StringBuilderConcat(elements, elements_length, '');
 }
 
 
-function UseSparseVariant(object, length, is_array) {
-   return is_array &&
-       length > 1000 &&
-       (!%_IsSmi(length) ||
-        %EstimateNumberOfElements(object) < (length >> 2));
+function UseSparseVariant(array, length, is_array, touched) {
+  // Only use the sparse variant on arrays that are likely to be sparse and the
+  // number of elements touched in the operation is relatively small compared to
+  // the overall size of the array.
+  if (!is_array || length < 1000 || %IsObserved(array)) {
+    return false;
+  }
+  if (!%_IsSmi(length)) {
+    return true;
+  }
+  var elements_threshold = length >> 2;  // No more than 75% holes
+  var estimated_elements = %EstimateNumberOfElements(array);
+  return (estimated_elements < elements_threshold) &&
+    (touched > estimated_elements * 4);
 }
 
 
 function Join(array, length, separator, convert) {
   if (length == 0) return '';
 
   var is_array = IS_ARRAY(array);
 
   if (is_array) {
     // If the array is cyclic, return the empty string for already
     // visited arrays.
     if (!%PushIfAbsent(visited_arrays, array)) return '';
   }
 
   // Attempt to convert the elements.
   try {
-    if (UseSparseVariant(array, length, is_array)) {
+    if (UseSparseVariant(array, length, is_array, length)) {
+      %NormalizeElements(array);
       if (separator.length == 0) {
         return SparseJoin(array, length, convert);
       } else {
         return SparseJoinWithSeparatorJS(array, length, convert, separator);
       }
     }
 
     // Fast case for one-element arrays.
     if (length == 1) {
       var e = array[0];
@@ skipping 390 matching lines @@
       }
     }
   }
 }
 
 
 function ArrayReverse() {
   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reverse");
 
   var array = TO_OBJECT_INLINE(this);
-  var j = TO_UINT32(array.length) - 1;
+  var len = TO_UINT32(array.length);
 
-  if (UseSparseVariant(array, j, IS_ARRAY(array))) {
-    SparseReverse(array, j+1);
+  if (UseSparseVariant(array, len, IS_ARRAY(array), len)) {
+    %NormalizeElements(array);
+    SparseReverse(array, len);
     return array;
   }
 
+  var j = len - 1;
   for (var i = 0; i < j; i++, j--) {
     var current_i = array[i];
     if (!IS_UNDEFINED(current_i) || i in array) {
       var current_j = array[j];
       if (!IS_UNDEFINED(current_j) || j in array) {
         array[i] = current_j;
         array[j] = current_i;
       } else {
         array[j] = current_i;
         delete array[i];
@@ skipping 125 matching lines @@
     end_i += len;
     if (end_i < 0) end_i = 0;
   } else {
     if (end_i > len) end_i = len;
   }
 
   var result = [];
 
   if (end_i < start_i) return result;
 
-  if (IS_ARRAY(array) &&
-      !%IsObserved(array) &&
-      (end_i > 1000) &&
-      (%EstimateNumberOfElements(array) < end_i)) {
+  if (UseSparseVariant(array, len, IS_ARRAY(array), end_i - start_i)) {
+    %NormalizeElements(array);
+    %NormalizeElements(result);
     SmartSlice(array, start_i, end_i - start_i, len, result);
   } else {
     SimpleSlice(array, start_i, end_i - start_i, len, result);
   }
 
   result.length = end_i - start_i;
 
   return result;
 }
 
@@ skipping 87 matching lines @@
   var num_elements_to_add = num_arguments > 2 ? num_arguments - 2 : 0;
 
   if (del_count != num_elements_to_add && ObjectIsSealed(array)) {
     throw MakeTypeError("array_functions_change_sealed",
                         ["Array.prototype.splice"]);
   } else if (del_count > 0 && ObjectIsFrozen(array)) {
     throw MakeTypeError("array_functions_on_frozen",
                         ["Array.prototype.splice"]);
   }
 
-  var use_simple_splice = true;
-  if (IS_ARRAY(array) &&
-      num_elements_to_add !== del_count) {
-    // If we are only deleting/moving a few things near the end of the
-    // array then the simple version is going to be faster, because it
-    // doesn't touch most of the array.
-    var estimated_non_hole_elements = %EstimateNumberOfElements(array);
-    if (len > 20 && (estimated_non_hole_elements >> 2) < (len - start_i)) {
-      use_simple_splice = false;
-    }
+  var changed_elements = del_count;
+  if (num_elements_to_add != del_count) {
+    // If the slice needs to do a actually move elements after the insertion
+    // point, then include those in the estimate of changed elements.
+    changed_elements += len - start_i - del_count;
   }
-
-  if (use_simple_splice) {
+  if (UseSparseVariant(array, len, IS_ARRAY(array), changed_elements)) {
+    %NormalizeElements(array);
+    %NormalizeElements(deleted_elements);
+    SmartSlice(array, start_i, del_count, len, deleted_elements);
+    SmartMove(array, start_i, del_count, len, num_elements_to_add);
+  } else {
     SimpleSlice(array, start_i, del_count, len, deleted_elements);
     SimpleMove(array, start_i, del_count, len, num_elements_to_add);
-  } else {
-    SmartSlice(array, start_i, del_count, len, deleted_elements);
-    SmartMove(array, start_i, del_count, len, num_elements_to_add);
   }
 
   // Insert the arguments into the resulting array in
   // place of the deleted elements.
   var i = start_i;
   var arguments_index = 2;
   var arguments_length = %_ArgumentsLength();
   while (arguments_index < arguments_length) {
     array[i++] = %_Arguments(arguments_index++);
   }
@@ skipping 464 matching lines @@
     index = TO_INTEGER(index);
     // If index is negative, index from the end of the array.
     if (index < 0) {
       index = length + index;
       // If index is still negative, search the entire array.
       if (index < 0) index = 0;
     }
   }
   var min = index;
   var max = length;
-  if (UseSparseVariant(this, length, IS_ARRAY(this))) {
+  if (UseSparseVariant(this, length, IS_ARRAY(this), max - min)) {
+    %NormalizeElements(this);
     var indices = %GetArrayKeys(this, length);
     if (IS_NUMBER(indices)) {
       // It's an interval.
       max = indices;  // Capped by length already.
       // Fall through to loop below.
     } else {
       if (indices.length == 0) return -1;
       // Get all the keys in sorted order.
       var sortedKeys = GetSortedArrayKeys(this, indices);
       var n = sortedKeys.length;
@@ skipping 34 matching lines @@
   } else {
     index = TO_INTEGER(index);
     // If index is negative, index from end of the array.
     if (index < 0) index += length;
     // If index is still negative, do not search the array.
     if (index < 0) return -1;
     else if (index >= length) index = length - 1;
   }
   var min = 0;
   var max = index;
-  if (UseSparseVariant(this, length, IS_ARRAY(this))) {
+  if (UseSparseVariant(this, length, IS_ARRAY(this), index)) {
+    %NormalizeElements(this);
     var indices = %GetArrayKeys(this, index + 1);
     if (IS_NUMBER(indices)) {
       // It's an interval.
       max = indices;  // Capped by index already.
       // Fall through to loop below.
     } else {
       if (indices.length == 0) return -1;
       // Get all the keys in sorted order.
       var sortedKeys = GetSortedArrayKeys(this, indices);
       var i = sortedKeys.length - 1;
@@ skipping 171 matching lines @@
   ));
 
   SetUpLockedPrototype(InternalPackedArray, $Array(), $Array(
     "join", getFunction("join", ArrayJoin),
     "pop", getFunction("pop", ArrayPop),
     "push", getFunction("push", ArrayPush)
   ));
 }
 
 SetUpArray();