Bug 897305 - Improve String.prototype.repeat() performance; r=tschneidereit
authorJoseph Myers <e_mayilme@hotmail.com>
Sat, 03 Aug 2013 09:57:53 +0530
changeset 148907 7c3cb4883157edf13a0ef2fc20d8d9b5c3e47a58
parent 148906 620bbab02c0bef95e53dbebe560714412d46dffe
child 148908 752a6805b83bc446dbbe72bff7872dbd341b9783
push idunknown
push userunknown
push dateunknown
reviewerstschneidereit
bugs897305
milestone25.0a1
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, "")