Improve speed of String.replace by around 33% by not constructing...

src/string.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 180 matching lines @@
       return StringReplaceRegExp(subject, search, replace);
     }
   }
 
   // Convert the search argument to a string and search for it.
   search = ToString(search);
   var start = %StringIndexOf(subject, search, 0);
   if (start < 0) return subject;
   var end = start + search.length;
 
-  var builder = new StringBuilder();
+  var builder = new ReplaceResultBuilder(subject);
   // prefix
-  builder.add(SubString(subject, 0, start));
+  builder.addSpecialSlice(0, start);
 
   // Compute the string to replace with.
   if (IS_FUNCTION(replace)) {
     builder.add(replace.call(null, search, start, subject));
   } else {
     ExpandReplacement(ToString(replace), subject, [ start, end ], builder);
   }
 
   // suffix
-  builder.add(SubString(subject, end, subject.length));
+  builder.addSpecialSlice(end, subject.length);
 
   return builder.generate();
 }
 
 
 // Helper function for regular expressions in String.prototype.replace.
 function StringReplaceRegExp(subject, regexp, replace) {
   // Compute an array of matches; each match is really a list of
   // captures - pairs of (start, end) indexes into the subject string.
   var matches;
   if (regexp.global) {
     matches = DoRegExpExecGlobal(regexp, subject);
     if (matches.length == 0) return subject;
   } else {
     var captures = DoRegExpExec(regexp, subject, 0);
     if (IS_NULL(captures)) return subject;
     matches = [ captures ];
   }
 
   // Determine the number of matches.
   var length = matches.length;
 
   // Build the resulting string of subject slices and replacements.
-  var result = new StringBuilder();
+  var result = new ReplaceResultBuilder(subject);
   var previous = 0;
   // The caller of StringReplaceRegExp must ensure that replace is not a
   // function.
   replace = ToString(replace);
-  for (var i = 0; i < length; i++) {
-    var captures = matches[i];
-    result.add(SubString(subject, previous, captures[0]));
-    ExpandReplacement(replace, subject, captures, result);
-    previous = captures[1];  // continue after match
+  if (%StringIndexOf(replace, "$", 0) < 0) {
+    for (var i = 0; i < length; i++) {
+      var captures = matches[i];
+      result.addSpecialSlice(previous, captures[0]);
+      result.add(replace);
+      previous = captures[1];  // continue after match
+    }
+  } else {
+    for (var i = 0; i < length; i++) {
+      var captures = matches[i];
+      result.addSpecialSlice(previous, captures[0]);
+      ExpandReplacement(replace, subject, captures, result);
+      previous = captures[1];  // continue after match
+    }
   }
-  result.add(SubString(subject, previous, subject.length));
+  result.addSpecialSlice(previous, subject.length);
   return result.generate();
 };
 
 
 // Expand the $-expressions in the string and return a new string with
 // the result.
 function ExpandReplacement(string, subject, captures, builder) {
   var next = %StringIndexOf(string, '$', 0);
   if (next < 0) {
     builder.add(string);
     return;
   }
 
   // Compute the number of captures; see ECMA-262, 15.5.4.11, p. 102.
   var m = captures.length >> 1;  // includes the match
 
   if (next > 0) builder.add(SubString(string, 0, next));
   var length = string.length;
 
   while (true) {
     var expansion = '$';
     var position = next + 1;
     if (position < length) {
       var peek = %StringCharCodeAt(string, position);
       if (peek == 36) {         // $$
         ++position;
+        builder.add('$');
       } else if (peek == 38) {  // $& - match
         ++position;
-        expansion = SubString(subject, captures[0], captures[1]);
+        builder.addSpecialSlice(captures[0], captures[1]);
       } else if (peek == 96) {  // $` - prefix
         ++position;
-        expansion = SubString(subject, 0, captures[0]);
+        builder.addSpecialSlice(0, captures[0]);
       } else if (peek == 39) {  // $' - suffix
         ++position;
-        expansion = SubString(subject, captures[1], subject.length);
+        builder.addSpecialSlice(captures[1], subject.length);
       } else if (peek >= 48 && peek <= 57) {  // $n, 0 <= n <= 9
         ++position;
         var n = peek - 48;
         if (position < length) {
           peek = %StringCharCodeAt(string, position);
           // $nn, 01 <= nn <= 99
           if (n != 0 && peek == 48 || peek >= 49 && peek <= 57) {
             var nn = n * 10 + (peek - 48);
             if (nn < m) {
               // If the two digit capture reference is within range of
               // the captures, we use it instead of the single digit
               // one. Otherwise, we fall back to using the single
               // digit reference. This matches the behavior of
               // SpiderMonkey.
               ++position;
               n = nn;
             }
           }
         }
         if (0 < n && n < m) {
-          expansion = CaptureString(subject, captures, n);
-          if (IS_UNDEFINED(expansion)) expansion = "";
+          addCaptureString(builder, captures, n);
         } else {
           // Because of the captures range check in the parsing of two
           // digit capture references, we can only enter here when a
           // single digit capture reference is outside the range of
           // captures.
+          builder.add('$');
           --position;
         }
       }
+    } else {
+      builder.add('$');
     }
 
-    // Append the $ expansion and go the the next $ in the string.
-    builder.add(expansion);
+    // Go the the next $ in the string.
     next = %StringIndexOf(string, '$', position);
 
     // Return if there are no more $ characters in the string. If we
     // haven't reached the end, we need to append the suffix.
     if (next < 0) {
       if (position < length) {
         builder.add(SubString(string, position, length));
       }
       return;
     }
@@ skipping 10 matching lines @@
   var scaled = index << 1;
   // Compute start and end.
   var start = captures[scaled];
   var end = captures[scaled + 1];
   // If either start or end is missing return undefined.
   if (start < 0 || end < 0) return;
   return SubString(string, start, end);
 };
 
 
+// Add the string of a given PCRE capture to the ReplaceResultBuilder
+function addCaptureString(builder, captures, index) {
+  // Scale the index.
+  var scaled = index << 1;
+  // Compute start and end.
+  var start = captures[scaled];
+  var end = captures[scaled + 1];
+  // If either start or end is missing return.
+  if (start < 0 || end < 0) return;
+  builder.addSpecialSlice(start, end);
+};
+
+
 // Helper function for replacing regular expressions with the result of a
 // function application in String.prototype.replace.  The function application
 // must be interleaved with the regexp matching (contrary to ECMA-262
 // 15.5.4.11) to mimic SpiderMonkey and KJS behavior when the function uses
 // the static properties of the RegExp constructor.  Example:
 //     'abcd'.replace(/(.)/g, function() { return RegExp.$1; }
 // should be 'abcd' and not 'dddd' (or anything else).
 function StringReplaceRegExpWithFunction(subject, regexp, replace) {
   var result = new ReplaceResultBuilder(subject);
   // Captures is an array of pairs of (start, end) indices for the match and
@@ skipping 467 matching lines @@
     "italics", StringItalics,
     "small", StringSmall,
     "strike", StringStrike,
     "sub", StringSub,
     "sup", StringSup
   ));
 }
 
 
 SetupString();