Replace PushIfAbsent by a Stack object

src/js/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.
 
 (function(global, utils, extrasUtils) {
 
 "use strict";
 
 %CheckIsBootstrapping();
 
@@ skipping 55 matching lines @@
   if (FLAG_harmony_species) {
     var result = ObjectDefineProperty(array, i, {
       value: value, writable: true, configurable: true, enumerable: true
     });
     if (!result) throw MakeTypeError(kStrictCannotAssign, i);
   } else {
     AddIndexedProperty(array, i, value);
   }
 }
 
+function KeySortCompare(a, b) {
+  return a - b;
+}
 
-// Global list of arrays visited during toString, toLocaleString and
-// join invocations.
-var visited_arrays = new InternalArray();
-
-
-// Gets a sorted array of array keys.  Useful for operations on sparse
-// arrays.  Dupes have not been removed.
 function GetSortedArrayKeys(array, indices) {
-  var keys = new InternalArray();
   if (IS_NUMBER(indices)) {
+    var keys = new InternalArray();
     // It's an interval
     var limit = indices;
     for (var i = 0; i < limit; ++i) {
       var e = array[i];
       if (!IS_UNDEFINED(e) || i in array) {
         keys.push(i);
       }
     }
-  } else {
-    var length = indices.length;
-    for (var k = 0; k < length; ++k) {
-      var key = indices[k];
-      if (!IS_UNDEFINED(key)) {
-        var e = array[key];
-        if (!IS_UNDEFINED(e) || key in array) {
-          keys.push(key);
-        }
-      }
-    }
-    keys.sort(function(a, b) { return a - b; });
   }
-  return keys;
+  return InnerArraySort(indices, indices.length, KeySortCompare);
 }
 
 
-function SparseJoinWithSeparatorJS(array, len, convert, separator) {
-  var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
-  var totalLength = 0;
-  var elements = new InternalArray(keys.length * 2);
-  var previousKey = -1;
-  for (var i = 0; i < keys.length; i++) {
+function SparseJoinWithSeparatorJS(array, keys, length, convert, separator) {
+  var keys_length = keys.length;
+  var elements = new InternalArray(keys_length * 2);
+  for (var i = 0; i < keys_length; i++) {
     var key = keys[i];
-    if (key != previousKey) {  // keys may contain duplicates.
-      var e = array[key];
-      if (!IS_STRING(e)) e = convert(e);
-      elements[i * 2] = key;
-      elements[i * 2 + 1] = e;
-      previousKey = key;
-    }
+    var e = array[key];
+    elements[i * 2] = key;
+    elements[i * 2 + 1] = IS_STRING(e) ? e : convert(e);
   }
-  return %SparseJoinWithSeparator(elements, len, separator);
+  return %SparseJoinWithSeparator(elements, length, separator);
 }
 
 
 // Optimized for sparse arrays if separator is ''.
-function SparseJoin(array, len, convert) {
-  var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
-  var last_key = -1;
+function SparseJoin(array, keys, convert) {
   var keys_length = keys.length;
-
   var elements = new InternalArray(keys_length);
-  var elements_length = 0;
-
   for (var i = 0; i < keys_length; i++) {
-    var key = keys[i];
-    if (key != last_key) {
-      var e = array[key];
-      if (!IS_STRING(e)) e = convert(e);
-      elements[elements_length++] = e;
-      last_key = key;
-    }
+    var e = array[keys[i]];
+    elements[i] = IS_STRING(e) ? e : convert(e);
   }
-  return %StringBuilderConcat(elements, elements_length, '');
+  return %StringBuilderConcat(elements, keys_length, '');
 }
 
 
 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) ||
       %HasComplexElements(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 Stack() {
+  this.length = 0;
+  this.values = new InternalArray();
+}
+
+// Predeclare the instance variables on the prototype. Otherwise setting them in
+// the constructor will leak the instance through settings on Object.prototype.
+Stack.prototype.length = null;
+Stack.prototype.values = null;
+
+function StackPush(stack, value) {
+  stack.values[stack.length++] = value;
+}
+
+function StackPop(stack) {
+  stack.values[--stack.length] = null
+}
+
+function StackHas(stack, v) {
+  var length = stack.length;
+  var values = stack.values;
+  for (var i = 0; i < length; i++) {
+    if (values[i] === v) return true;
+  }
+  return false;
+}
+
+// Global list of arrays visited during toString, toLocaleString and
+// join invocations.
+var visited_arrays = new Stack();
+
+function DoJoin(array, length, is_array, separator, convert) {
+  if (UseSparseVariant(array, length, is_array, length)) {
+    %NormalizeElements(array);
+    var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, length));
+    if (separator === '') {
+      if (keys.length === 0) return '';
+      return SparseJoin(array, keys, convert);
+    } else {
+      return SparseJoinWithSeparatorJS(array, keys, length, convert, separator);
+    }
+  }
+
+  // Fast case for one-element arrays.
+  if (length === 1) {
+    var e = array[0];
+    return IS_STRING(e) ? e : convert(e);
+  }
+
+  // Construct an array for the elements.
+  var elements = new InternalArray(length);
+
+  // We pull the empty separator check outside the loop for speed!
+  if (separator === '') {
+    for (var i = 0; i < length; i++) {
+      var e = array[i];
+      elements[i] = IS_STRING(e) ? e : convert(e);
+    }
+    return %StringBuilderConcat(elements, length, '');

[Camillo Bruni, 2016/03/14 10:09:52]

As you said, you could probably still create a silly cons string for small
lengths here...

+  }
+  // Non-empty separator case.
+  // If the first element is a number then use the heuristic that the
+  // remaining elements are also likely to be numbers.
+  var e = array[0];
+  if (IS_NUMBER(e)) {
+    elements[0] = %_NumberToString(e);
+    for (var i = 1; i < length; i++) {
+      e = array[i];
+      if (IS_NUMBER(e)) {
+        elements[i] = %_NumberToString(e);
+      } else {
+        elements[i] = IS_STRING(e) ? e : convert(e);
+      }
+    }
+  } else {
+    elements[0] = IS_STRING(e) ? e : convert(e);
+    for (var i = 1; i < length; i++) {
+      e = array[i];
+      elements[i] = IS_STRING(e) ? e : convert(e);
+    }
+  }
+  return %StringBuilderJoin(elements, length, separator);
+}
 
 function Join(array, length, separator, convert) {
-  if (length == 0) return '';
+  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 '';
+    if (StackHas(visited_arrays, array)) return '';
+    StackPush(visited_arrays, array);
   }
 
   // Attempt to convert the elements.
   try {
-    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];
-      if (IS_STRING(e)) return e;
-      return convert(e);
-    }
-
-    // Construct an array for the elements.
-    var elements = new InternalArray(length);
-
-    // We pull the empty separator check outside the loop for speed!
-    if (separator.length == 0) {
-      var elements_length = 0;
-      for (var i = 0; i < length; i++) {
-        var e = array[i];
-        if (!IS_STRING(e)) e = convert(e);
-        elements[elements_length++] = e;
-      }
-      elements.length = elements_length;
-      return %StringBuilderConcat(elements, elements_length, '');
-    }
-    // Non-empty separator case.
-    // If the first element is a number then use the heuristic that the
-    // remaining elements are also likely to be numbers.
-    var e = array[0];
-    if (!IS_NUMBER(e)) {
-      if (!IS_STRING(e)) e = convert(e);
-      elements[0] = e;
-      for (var i = 1; i < length; i++) {
-        e = array[i];
-        if (!IS_STRING(e)) e = convert(e);
-        elements[i] = e;
-      }
-    } else {
-      elements[0] = %_NumberToString(e);
-      for (var i = 1; i < length; i++) {
-        e = array[i];
-        if (IS_NUMBER(e)) {
-          e = %_NumberToString(e);
-        } else if (!IS_STRING(e)) {
-          e = convert(e);
-        }
-        elements[i] = e;
-      }
-    }
-    return %StringBuilderJoin(elements, length, separator);
+    return DoJoin(array, length, is_array, separator, convert);
   } finally {
     // Make sure to remove the last element of the visited array no
     // matter what happens.
-    if (is_array) visited_arrays.length = visited_arrays.length - 1;
+    if (is_array) StackPop(visited_arrays);
   }
 }
 
 
 function ConvertToString(x) {
-  if (IS_NULL_OR_UNDEFINED(x)) {
-    return '';
-  } else {
-    return TO_STRING(x);
-  }
+  if (IS_NULL_OR_UNDEFINED(x)) return '';
+  return TO_STRING(x);
 }
 
 
 function ConvertToLocaleString(e) {
-  if (IS_NULL_OR_UNDEFINED(e)) {
-    return '';
-  } else {
-    return TO_STRING(e.toLocaleString());
-  }
+  if (IS_NULL_OR_UNDEFINED(e)) return '';
+  return TO_STRING(e.toLocaleString());
 }
 
 
 // This function implements the optimized splice implementation that can use
 // special array operations to handle sparse arrays in a sensible fashion.
 function SparseSlice(array, start_i, del_count, len, deleted_elements) {
   // Move deleted elements to a new array (the return value from splice).
   var indices = %GetArrayKeys(array, start_i + del_count);
   if (IS_NUMBER(indices)) {
     var limit = indices;
@@ skipping 1680 matching lines @@
   to.InnerArrayIncludes = InnerArrayIncludes;
   to.InnerArrayIndexOf = InnerArrayIndexOf;
   to.InnerArrayJoin = InnerArrayJoin;
   to.InnerArrayLastIndexOf = InnerArrayLastIndexOf;
   to.InnerArrayReduce = InnerArrayReduce;
   to.InnerArrayReduceRight = InnerArrayReduceRight;
   to.InnerArraySome = InnerArraySome;
   to.InnerArraySort = InnerArraySort;
   to.InnerArrayToLocaleString = InnerArrayToLocaleString;
   to.PackedArrayReverse = PackedArrayReverse;
+  to.Stack = Stack;
+  to.StackHas = StackHas;
+  to.StackPush = StackPush;
+  to.StackPop = StackPop;
 });
 
 %InstallToContext([
   "array_pop", ArrayPop,
   "array_push", ArrayPush,
   "array_shift", ArrayShift,
   "array_splice", ArraySplice,
   "array_slice", ArraySlice,
   "array_unshift", ArrayUnshift,
 ]);
 
 });