JavaScript String Multiplication Performance Exploration

Since JavaScript concatenates strings with the + operator, it would be nifty if it would also let you multiply strings using e.g. str * 10 (as can be done in Python, at least). Since you can't do that, and no native string multiplication method is provided, I recently explored a few ways to pull it off…

A naive approach to writing a string multiplier function goes something like this:

function mul0 (str, num) {
	if (!num) return "";
	var newStr = str;
	while (--num) newStr += str;
	return newStr;
}

As many JavaScripters are aware, that isn't the best approach since string concatenation can be quite slow in Internet Explorer. And while IE tends to get a bad rap for this (fortunately, the IE team is fixing the problem in the next version of their browser), Firefox isn't exactly blazing fast at string concatenation either. Due to the performance issues, the typical string multiplication approach is to build an array and join it. Here's a nice, short way to do that:

function mul1 (str, num) {
	return num ? Array(num + 1).join(str) : "";
}

Note that the falsy num handling is probably not warranted in this case since the function would handle value 0 correctly without it. It's done anyway to keep functionality equivalent across the variations.

Unfortunately, mul1 can still be pretty slow in Firefox 2 when multiplying large strings many times. It might be unnoticeable with small strings and repetition numbers, but the completion time goes up at a super-linear rate as the numbers increase. In search of a faster solution, I tried using a regex to keep down the size of the string being worked with:

var mul2 = function () {
	function mul (str, num) {
		return Array(num + 1).join(str);
	}
	return function (str, num) {
		return num ? str.replace(/^/, mul("$'", num - 1)) : "";
	};
}();

The above multiplies the two-character string "$'" num - 1 times, then uses that as the replacement for a regex which just matches the start of the string ($' returns the text to the right of the match). How does that perform? It delivers in Firefox 2 on my Windows Vista system, with numbers like 95ms vs. 29800ms (mul1) when using a 2700x2700 string length/multiplier. However, based on my testing, that sort of speed gain appears to be limited to Firefox, and in Safari 3 beta mul2 is considerably slower that the alternative versions.

Finally, I tried creating a version which multiplied the string at an exponential rate:

function mul3 (str, num) {
	if (!num) return "";
	var	orig = str,
		soFar = [str],
		added = 1,
		left, i;
	while (added < num) {
		left = num - added;
		str = orig;
		for (i = 2; i < left; i *= 2) {
			str += str;
		}
		soFar.push(str);
		added += (i / 2);
	}
	return soFar.join("");
}

Although that might be more code than you're willing to dedicate to a string multiplication method, it's the fastest of the above versions on average cross-browser. I've also tried a few variations using from zero to two arrays and various array methods (push, concat, etc.), but the above seems to be the fastest on average across the big four browsers.

Make sure to try the tests for yourself, and let me know your thoughts and how you would improve the code.

---

Edit: Kris Kowal contributed mul4 (shown below, and added to the test page). It uses binary interpolation, and in Kris's words "it takes advantage of a fun bitwise identity: (1 << n) == Math.pow(2, n)". On my system it's significantly faster than mul3 in Firefox, but a little slower than mul3 in IE, Safari, and Opera. Due to its high speed and lighter weight, this looks like the one to beat. Try the test page in several browsers and see what you think.

function mul4 (str, num) {
	var acc = [];
	for (var i = 0; (1 << i) <= num; i++) {
		if ((1 << i) & num)
			acc.push(str);
		str += str;
	}
	return acc.join("");
}

---

Edit 2: LiuCougar of the Dojo development team posted a follow-up which includes several additional variations, and David Andersson emailed me an additional four variations including this one:

function mul8 (str, num) {
	var	i = Math.ceil(Math.log(num) / Math.LN2),
		res = str;
	do {
		res += res;
	} while (0 < --i);
	return res.slice(0, str.length * num);
}

I should clarify however that this is mostly just academic discussion, since repeating the kinds of strings in the test page as many times as it does is a pretty crazy idea. Still, it's fun to experiment.

---

Edit 3: All the variations posted or emailed in response to this post can be seen at stevenlevithan.com/demo/mul/all.js. For the sake of consistency I've made a few minor adjustments to some of the functions such as whitespace tweaks and renaming the input arguments to str and num.