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

src/array.js

Index: src/array.js
diff --git a/src/array.js b/src/array.js
index 15cbbf21a6003a3336be6dd6e5f755154c510a28..d7589d61452c2d1afe54bb68179e47b78cca71d4 100644
--- a/src/array.js
+++ b/src/array.js
@@ -86,11 +86,20 @@ function SparseJoin(array, len, convert) {
 }
 
 
-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);
 }
 
 
@@ -107,7 +116,8 @@ function Join(array, length, separator, convert) {
 
   // 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 {
@@ -518,13 +528,15 @@ 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) {
@@ -670,10 +682,9 @@ function ArraySlice(start, end) {
 
   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);
@@ -781,24 +792,19 @@ function ArraySplice(start, delete_count) {
                         ["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) {
-    SimpleSlice(array, start_i, del_count, len, deleted_elements);
-    SimpleMove(array, start_i, del_count, len, num_elements_to_add);
-  } else {
+  if (UseSparseVariant(array, len, IS_ARRAY(array), changed_elements)) {
+    %NormalizeElements(array);

[Toon Verwaest, 2014/07/25 13:33:46]

Normalize 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);
   }
 
   // Insert the arguments into the resulting array in
@@ -1283,7 +1289,8 @@ function ArrayIndexOf(element, index) {
   }
   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.
@@ -1338,7 +1345,8 @@ function ArrayLastIndexOf(element, index) {
   }
   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.