Bug 897305 - Improve String.prototype.repeat() performance; r=tschneidereit
authorJoseph Myers <e_mayilme@hotmail.com>
Sat, 03 Aug 2013 09:57:53 +0530
changeset 153613 7c3cb4883157edf13a0ef2fc20d8d9b5c3e47a58
parent 153612 620bbab02c0bef95e53dbebe560714412d46dffe
child 153614 752a6805b83bc446dbbe72bff7872dbd341b9783
push id2859
push userakeybl@mozilla.com
push dateMon, 16 Sep 2013 19:14:59 +0000
treeherdermozilla-beta@87d3c51cd2bf [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerstschneidereit
bugs897305
milestone25.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 897305 - Improve String.prototype.repeat() performance; r=tschneidereit
js/src/builtin/String.js
js/src/jit-test/tests/basic/string-repeat.js
js/src/js.msg
--- a/js/src/builtin/String.js
+++ b/js/src/builtin/String.js
@@ -12,29 +12,37 @@ function String_repeat(count) {
     // Steps 1-3.
     CheckObjectCoercible(this);
     var S = ToString(this);
 
     // Steps 4-5.
     var n = ToInteger(count);
 
     // Steps 6-7.
-    if (n < 0 || n === std_Number_POSITIVE_INFINITY)
-        ThrowError(JSMSG_REPEAT_RANGE);
+    if (n < 0)
+        ThrowError(JSMSG_NEGATIVE_REPETITION_COUNT); // a RangeError
 
-    // Step 8-9.
-    if (n === 0)
-        return "";
+    if (!(n * S.length < (1 << 28)))
+        ThrowError(JSMSG_RESULTING_STRING_TOO_LARGE); // a RangeError
+
+    // Communicate |n|'s possible range to the compiler.
+    n = n & ((1 << 28) - 1);
 
-    var result = S;
-    for (var i = 1; i <= n / 2; i *= 2)
-        result += result;
-    for (; i < n; i++)
-        result += S;
-    return result;
+    // Steps 8-9.
+    var T = '';
+    for (;;) {
+        if (n & 1)
+            T += S;
+        n >>= 1;
+        if (n)
+            S += S;
+        else
+            break;
+    }
+    return T;
 }
 
 /**
  * Compare this String against that String, using the locale and collation
  * options provided.
  *
  * Spec: ECMAScript Internationalization API Specification, 13.1.1.
  */
--- a/js/src/jit-test/tests/basic/string-repeat.js
+++ b/js/src/jit-test/tests/basic/string-repeat.js
@@ -1,22 +1,30 @@
 /* Test String.prototype.repeat */
 
 load(libdir + 'asserts.js');
 
 assertEq("abc".repeat(1), "abc");
 assertEq("abc".repeat(2), "abcabc");
 assertEq("abc".repeat(3), "abcabcabc");
 assertEq("a".repeat(10), "aaaaaaaaaa");
+assertEq("abc".repeat(0), "");
+assertEq("abc".repeat(2.9), "abcabc");
+
 var myobj = {toString : (function () "abc"), repeat : String.prototype.repeat};
 assertEq(myobj.repeat(1), "abc");
 assertEq(myobj.repeat(2), "abcabc");
-assertEq("abc".repeat(0), "");
+
 assertThrowsInstanceOf(function() {
                          "abc".repeat(-1);
                        }, RangeError,
                        "String.prototype.repeat should raise RangeError on negative arguments");
 assertThrowsInstanceOf(function() {
                          "abc".repeat(Number.POSITIVE_INFINITY);
                        }, RangeError,
-                       "String.prototype.repeat should raise RangeError on positive infinity arguments");
+                       "String.prototype.repeat should raise RangeError on excedding maximum string length");
+assertThrowsInstanceOf(function() {
+                         "abc".repeat(1 << 29);
+                       }, RangeError,
+                       "String.prototype.repeat should raise RangeError on excedding maximum string length");
+
 assertEq("".repeat(5), "");
-assertEq("abc".repeat(2.0), "abcabc");
+assertEq("".repeat(1 << 29), "");
--- a/js/src/js.msg
+++ b/js/src/js.msg
@@ -191,17 +191,17 @@ MSG_DEF(JSMSG_OUT_OF_MEMORY,          13
 MSG_DEF(JSMSG_UNTERMINATED_STRING,    138, 0, JSEXN_SYNTAXERR, "unterminated string literal")
 MSG_DEF(JSMSG_TOO_MANY_PARENS,        139, 0, JSEXN_INTERNALERR, "too many parentheses in regular expression")
 MSG_DEF(JSMSG_UNTERMINATED_COMMENT,   140, 0, JSEXN_SYNTAXERR, "unterminated comment")
 MSG_DEF(JSMSG_UNTERMINATED_REGEXP,    141, 0, JSEXN_SYNTAXERR, "unterminated regular expression literal")
 MSG_DEF(JSMSG_BAD_CLONE_FUNOBJ_SCOPE, 142, 0, JSEXN_TYPEERR, "bad cloned function scope chain")
 MSG_DEF(JSMSG_MISSING_OCTAL_DIGITS,   143, 0, JSEXN_SYNTAXERR, "missing octal digits after '0o'")
 MSG_DEF(JSMSG_ILLEGAL_CHARACTER,      144, 0, JSEXN_SYNTAXERR, "illegal character")
 MSG_DEF(JSMSG_BAD_OCTAL,              145, 1, JSEXN_SYNTAXERR, "{0} is not a legal ECMA-262 octal constant")
-MSG_DEF(JSMSG_REPEAT_RANGE,           146, 0, JSEXN_RANGEERR, "repeat count must be positive and less than inifinity")
+MSG_DEF(JSMSG_RESULTING_STRING_TOO_LARGE, 146, 0, JSEXN_RANGEERR, "repeat count must be less than infinity and not overflow maximum string size")
 MSG_DEF(JSMSG_UNCAUGHT_EXCEPTION,     147, 1, JSEXN_INTERNALERR, "uncaught exception: {0}")
 MSG_DEF(JSMSG_INVALID_BACKREF,        148, 0, JSEXN_SYNTAXERR, "non-octal digit in an escape sequence that doesn't match a back-reference")
 MSG_DEF(JSMSG_BAD_BACKREF,            149, 0, JSEXN_SYNTAXERR, "back-reference exceeds number of capturing parentheses")
 MSG_DEF(JSMSG_PRECISION_RANGE,        150, 1, JSEXN_RANGEERR, "precision {0} out of range")
 MSG_DEF(JSMSG_BAD_GETTER_OR_SETTER,   151, 1, JSEXN_TYPEERR, "invalid {0} usage")
 MSG_DEF(JSMSG_BAD_ARRAY_LENGTH,       152, 0, JSEXN_RANGEERR, "invalid array length")
 MSG_DEF(JSMSG_CANT_DESCRIBE_PROPS,    153, 1, JSEXN_TYPEERR, "can't describe non-native properties of class {0}")
 MSG_DEF(JSMSG_BAD_APPLY_ARGS,         154, 1, JSEXN_TYPEERR, "second argument to Function.prototype.{0} must be an array")
@@ -215,17 +215,17 @@ MSG_DEF(JSMSG_IDSTART_AFTER_NUMBER,   16
 MSG_DEF(JSMSG_UNDEFINED_PROP,         162, 1, JSEXN_REFERENCEERR, "reference to undefined property {0}")
 MSG_DEF(JSMSG_USELESS_EXPR,           163, 0, JSEXN_TYPEERR, "useless expression")
 MSG_DEF(JSMSG_REDECLARED_PARAM,       164, 1, JSEXN_TYPEERR, "redeclaration of formal parameter {0}")
 MSG_DEF(JSMSG_NEWREGEXP_FLAGGED,      165, 0, JSEXN_TYPEERR, "can't supply flags when constructing one RegExp from another")
 MSG_DEF(JSMSG_RESERVED_SLOT_RANGE,    166, 0, JSEXN_RANGEERR, "reserved slot index out of range")
 MSG_DEF(JSMSG_CANT_DECODE_PRINCIPALS, 167, 0, JSEXN_INTERNALERR, "can't decode JSPrincipals")
 MSG_DEF(JSMSG_CANT_SEAL_OBJECT,       168, 1, JSEXN_ERR, "can't seal {0} objects")
 MSG_DEF(JSMSG_TOO_MANY_CATCH_VARS,    169, 0, JSEXN_SYNTAXERR, "too many catch variables")
-MSG_DEF(JSMSG_UNUSED170,              170, 0, JSEXN_NONE, "")
+MSG_DEF(JSMSG_NEGATIVE_REPETITION_COUNT, 170, 0, JSEXN_RANGEERR, "repeat count must be non-negative")
 MSG_DEF(JSMSG_UNUSED171,              171, 0, JSEXN_NONE, "")
 MSG_DEF(JSMSG_UNUSED172,              172, 0, JSEXN_NONE, "")
 MSG_DEF(JSMSG_UNUSED173,              173, 0, JSEXN_NONE, "")
 MSG_DEF(JSMSG_UNUSED174,              174, 0, JSEXN_NONE, "")
 MSG_DEF(JSMSG_NESTING_GENERATOR,      175, 0, JSEXN_TYPEERR, "already executing generator")
 MSG_DEF(JSMSG_UNUSED176,              176, 0, JSEXN_NONE, "")
 MSG_DEF(JSMSG_UNUSED177,              177, 0, JSEXN_NONE, "")
 MSG_DEF(JSMSG_UNUSED178,              178, 0, JSEXN_NONE, "")