Improve performance of Array.prototype.join and String.prototype.substring...

src/array.js

 // 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 52 matching lines @@
     }
   }
   keys.sort(function(a, b) { return a - b; });
   return keys;
 }
 
 
 // Optimized for sparse arrays if separator is ''.
 function SparseJoin(array, len, convert) {
   var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
-  var builder = new StringBuilder();
   var last_key = -1;
   var keys_length = keys.length;
+
+  var elements = new $Array(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 (typeof(e) !== 'string') e = convert(e);
-      builder.add(e);
+      if (!IS_STRING(e)) e = convert(e);
+      elements[elements_length++] = e;
       last_key = key;
     }
   }
-  return builder.generate();
+  return %StringBuilderConcat(elements, elements_length, '');
 }
 
 
 function UseSparseVariant(object, length, is_array) {
    return is_array &&
        length > 1000 &&
        (!%_IsSmi(length) ||
         %EstimateNumberOfElements(object) < (length >> 2));
 }
 
 
 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) && separator === '') {
+    if (UseSparseVariant(array, length, is_array) && (separator.length == 0)) {

[Erik Corry, 2010/01/06 14:03:57]

I don't think the extra () around separator.length == 0 really add anything
here.

       return SparseJoin(array, length, convert);
     }
 
     // Fast case for one-element arrays.
     if (length == 1) {
       var e = array[0];
       if (!IS_UNDEFINED(e) || (0 in array)) {
-        if (typeof(e) === 'string') return e;
+        if (IS_STRING(e)) return e;
         return convert(e);
       }
     }
 
-    var builder = new StringBuilder();
+    // Construct an array for the elements.
+    var elements;
+    var elements_length = 0;
 
     // We pull the empty separator check outside the loop for speed!
     if (separator.length == 0) {
+      elements = new $Array(length);
       for (var i = 0; i < length; i++) {
         var e = array[i];
         if (!IS_UNDEFINED(e) || (i in array)) {
-          if (typeof(e) !== 'string') e = convert(e);
-          if (e.length > 0) {
-            var elements = builder.elements;
-            elements[elements.length] = e;
-          }
+          if (!IS_STRING(e)) e = convert(e);
+          elements[elements_length++] = e;
         }
       }
     } else {
+      elements = new $Array(length << 1);
       for (var i = 0; i < length; i++) {
         var e = array[i];
-        if (i != 0) builder.add(separator);
+        if (i != 0) elements[elements_length++] = separator;
         if (!IS_UNDEFINED(e) || (i in array)) {
-          if (typeof(e) !== 'string') e = convert(e);
-          if (e.length > 0) {
-            var elements = builder.elements;
-            elements[elements.length] = e;
-          }
+          if (!IS_STRING(e)) e = convert(e);
+          elements[elements_length++] = e;
         }
       }
     }
-    return builder.generate();
+    return %StringBuilderConcat(elements, elements_length, '');
   } finally {
     // Make sure to pop the visited array no matter what happens.
     if (is_array) visited_arrays.pop();
   }
 }
 
 
 function ConvertToString(e) {
-  if (typeof(e) === 'string') return e;
   if (e == null) return '';
   else return ToString(e);
 }
 
 
 function ConvertToLocaleString(e) {
-  if (typeof(e) === 'string') return e;
-  if (e == null) return '';
-  else {
+  if (e == null) {
+    return '';
+  } else {
     // e_obj's toLocaleString might be overwritten, check if it is a function.
     // Call ToString if toLocaleString is not a function.
     // See issue 877615.
     var e_obj = ToObject(e);
     if (IS_FUNCTION(e_obj.toLocaleString))
       return ToString(e_obj.toLocaleString());
     else
       return ToString(e);
   }
 }
@@ skipping 173 matching lines @@
 
 function ArrayToLocaleString() {
   if (!IS_ARRAY(this)) {
     throw new $TypeError('Array.prototype.toString is not generic');
   }
   return Join(this, this.length, ',', ConvertToLocaleString);
 }
 
 
 function ArrayJoin(separator) {
-  if (IS_UNDEFINED(separator)) separator = ',';
-  else separator = ToString(separator);
-  return Join(this, ToUint32(this.length), separator, ConvertToString);
+  if (IS_UNDEFINED(separator)) {
+    separator = ',';
+  } else if (!IS_STRING(separator)) {
+    separator = ToString(separator);
+  }
+  var length = TO_UINT32(this.length);
+  return Join(this, length, separator, ConvertToString);
 }
 
 
 // Removes the last element from the array and returns it. See
 // ECMA-262, section 15.4.4.6.
 function ArrayPop() {
-  var n = ToUint32(this.length);
+  var n = TO_UINT32(this.length);
   if (n == 0) {
     this.length = n;
     return;
   }
   n--;
   var value = this[n];
   this.length = n;
   delete this[n];
   return value;
 }
 
 
 // Appends the arguments to the end of the array and returns the new
 // length of the array. See ECMA-262, section 15.4.4.7.
 function ArrayPush() {
-  var n = ToUint32(this.length);
+  var n = TO_UINT32(this.length);
   var m = %_ArgumentsLength();
   for (var i = 0; i < m; i++) {
     this[i+n] = %_Arguments(i);
   }
   this.length = n + m;
   return this.length;
 }
 
 
 function ArrayConcat(arg1) {  // length == 1
@@ skipping 47 matching lines @@
       if (!IS_UNDEFINED(current_j) || high in array) {
         array[low] = current_j;
         delete array[high];
       }
     }
   }
 }
 
 
 function ArrayReverse() {
-  var j = ToUint32(this.length) - 1;
+  var j = TO_UINT32(this.length) - 1;
 
   if (UseSparseVariant(this, j, IS_ARRAY(this))) {
     SparseReverse(this, j+1);
     return this;
   }
 
   for (var i = 0; i < j; i++, j--) {
     var current_i = this[i];
     if (!IS_UNDEFINED(current_i) || i in this) {
       var current_j = this[j];
@@ skipping 10 matching lines @@
         this[i] = current_j;
         delete this[j];
       }
     }
   }
   return this;
 }
 
 
 function ArrayShift() {
-  var len = ToUint32(this.length);
+  var len = TO_UINT32(this.length);
 
   if (len === 0) {
     this.length = 0;
     return;
   }
 
   var first = this[0];
 
   if (IS_ARRAY(this))
     SmartMove(this, 0, 1, len, 0);
   else
     SimpleMove(this, 0, 1, len, 0);
 
   this.length = len - 1;
 
   return first;
 }
 
 
 function ArrayUnshift(arg1) {  // length == 1
-  var len = ToUint32(this.length);
+  var len = TO_UINT32(this.length);
   var num_arguments = %_ArgumentsLength();
 
   if (IS_ARRAY(this))
     SmartMove(this, 0, 0, len, num_arguments);
   else
     SimpleMove(this, 0, 0, len, num_arguments);
 
   for (var i = 0; i < num_arguments; i++) {
     this[i] = %_Arguments(i);
   }
 
   this.length = len + num_arguments;
 
   return len + num_arguments;
 }
 
 
 function ArraySlice(start, end) {
-  var len = ToUint32(this.length);
+  var len = TO_UINT32(this.length);
   var start_i = TO_INTEGER(start);
   var end_i = len;
 
   if (end !== void 0) end_i = TO_INTEGER(end);
 
   if (start_i < 0) {
     start_i += len;
     if (start_i < 0) start_i = 0;
   } else {
     if (start_i > len) start_i = len;
@@ skipping 24 matching lines @@
 
 function ArraySplice(start, delete_count) {
   var num_arguments = %_ArgumentsLength();
 
   // SpiderMonkey and KJS return undefined in the case where no
   // arguments are given instead of using the implicit undefined
   // arguments.  This does not follow ECMA-262, but we do the same for
   // compatibility.
   if (num_arguments == 0) return;
 
-  var len = ToUint32(this.length);
+  var len = TO_UINT32(this.length);
   var start_i = TO_INTEGER(start);
 
   if (start_i < 0) {
     start_i += len;
     if (start_i < 0) start_i = 0;
   } else {
     if (start_i > len) start_i = len;
   }
 
   // SpiderMonkey and KJS treat the case where no delete count is
@@ skipping 261 matching lines @@
         obj[i] = void 0;
       } else {
         delete obj[i];
       }
     }
 
     // Return the number of defined elements.
     return first_undefined;
   }
 
-  length = ToUint32(this.length);
+  length = TO_UINT32(this.length);
   if (length < 2) return this;
 
   var is_array = IS_ARRAY(this);
   var max_prototype_element;
   if (!is_array) {
     // For compatibility with JSC, we also sort elements inherited from
     // the prototype chain on non-Array objects.
     // We do this by copying them to this object and sorting only
     // local elements. This is not very efficient, but sorting with
     // inherited elements happens very, very rarely, if at all.
@@ skipping 279 matching lines @@
     ArrayIndexOf: 1,
     ArrayLastIndexOf: 1,
     ArrayPush: 1,
     ArrayReduce: 1,
     ArrayReduceRight: 1
   });
 }
 
 
 SetupArray();