Flagrant Badassery

A JavaScript and regular expression centric blog

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. smile


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.

There Are 14 Responses So Far. »

  1. […] saw a post from Steve on his blog about ” Fast String Multiplication with Regular Expressions, Exponential Concatenation, and Binary Interpola…“. Basically, it deals with how to fast multiplicate a string n times in […]

  2. Nothing like a good challenge 😉

    I came up with this:

    function (str, num) {
    var pre = [str],
    b = num.toString(2).split(“”).reverse(),
    l = b.length,
    i = 1;
    while (i<l) {
    var s = pre[i-1];
    pre.push(s + s);
    i++;
    }
    var i = 0;
    while (i<l) {
    if (b[i]==”0″) pre[i] = “”;
    i++;
    }
    return pre.join(“”);
    }

    it isn’t the fastest of the lot (well it is in Safari 3) – but it’s close! – and it does have a pretty stable perfomance across browsers.

  3. @rasmus, I’ve created a list of all the versions submitted in response to this post so far and added yours to it:

    http://stevenlevithan.com/demo/mul/all.js

    It’s great to see all these different approaches (14 so far)! Note that I’ve made several adjustments to the posted versions, including whitespace tweaks and changing the input argument names to “str” and “num”.

  4. Are there any practical applications of this sort of stuff? In any case, the general principles would be useful to others. I haven’t seen any other blogs with this much detail about regular expressions, so yours is very interesting.

  5. @Sam, yeah, this was mostly just for the fun of it. As for regular expressions, as you can see I’m a big fan. It keeps my blog geared towards a niche audience, but so be it.

  6. Ordinary square-and-multiply without use of arrays etc
    works better-than-or-equal-to the ones above for ie7 and ff2 (as far as i tested:) )

    Thank you all for this great thread

    function mulDaghan(str,count){
        if(count==0) return '';
        var binaryCount = count.toString(2);
        var numDegree = binaryCount.length;
        var resultStr='';
        for(var i=0; i<numDegree; i++){
            resultStr+=resultStr; // for both 0 and 1
            if(binaryCount.charAt(i) == '1'){
                resultStr+=str;
            }
        }
        return resultStr;
    }

  7. i want natural language search that code is very usefull for me.

  8. here is a little something that I usually use.
    since i am a fan of Perl which uses x for multiplying strings
    i named the function x and added it to the string object.

    //– adds a multiplier function to any string object
    //– use: String.x(number)
    //– example:
    //– var str=’hi’;
    //– str.x(3);
    //– returns: hihihi

    String.prototype.x=function(x){
    if(arguments.length==0)return this;
    if(x<=0)return this;
    var out=”;
    for(i=0;i<x;i++){
    out+=this
    }
    return out;
    }

    this is useful since you can add it to any other built in string modifier
    eg.
    string.replace(/hi/,’bye’).x(10)

  9. Another “square-and-multiply” algorithm:

    String.prototype.times = function(count) {
    count = (count >> 0);
    var t = (count > 1? this.times(count / 2): ”);
    return t + (count % 2? t + this: t);
    };
    //use ‘x’.times(1000000)

  10. Harnessing the magical powers of exponentiation *and* recursion I present you the most powerful string multiplication method ever devised! (To see it’s true power compare to it other functions by multiplying strings by 100 million, etc.)

    function stringMultiply3(string, n) {
    var x = Math.floor(Math.log(n)/Math.LN2), temp = string;
    for(var i=0; i < x; i++)
    string += string;
    return (n) ? string + stringMultiply3(temp, n – Math.pow(2, x)) : ”;
    }

    Huzzah! (Visit my website http://ian0.com/ for more cool JS magic.)

  11. Further optimization:

    function stringMultiply(s, n, i) {
    for (i = 0, x = Math.log(n) / Math.LN2 | 0, t = s; i++ < x; s += s);
    return n ? s + stringMultiply(t, n – (2 << x – 1 || 1)) : '';
    }

  12. Now on jsperf: http://jsperf.com/string-multiplication-levithan

  13. Greetings! Very helpful advice within this post!
    It’s the little changes that will make the greatest changes.
    Thanks a lot for sharing!

  14. Valuable info. Fortunate me I found your web site unintentionally, and I am stunned
    why this accident did not came about earlier! I bookmarked it.

Post a Response

If you are about to post code, please escape your HTML entities (&amp;, &gt;, &lt;).