String Performance: an Analysis

By on May 9, 2008 12:02 am

Recently I was writing a “tips and tricks” blog post that was going to focus on the idea that it is better to use an object as a “string buffer”; the idea was that by passing this object around to various functions and pushing string fragments into it, you can get better performance from a JavaScript engine. My friend and colleague Alex Russell challenged me to show him hard data supporting this hypothesis—and the results were quite eye-opening!

String performance by browser

For this analysis, I used two sources for tests: the dojox.string.Builder Builder performance test, and a custom test implementing three versions of a common JavaScript task: a JSON Serializer. The initial concept was to show that pushing strings into an object buffer would be faster than using the simple JavaScript operations available to any developer.

Background: String Theory.

From my friend and colleague Eugene Lazutkin comes this excellent explanation about strings in programming:

Many modern languages (especially functional languages) employ “the immutable object” paradigm, which solves a lot of problems including the memory conservation, the cache localization, addressing concurrency concerns, and so on. The idea is simple: if object is immutable, it can be represented by a reference (a pointer, a handle), and passing a reference is the same as passing an object by value — if object is immutable, its value cannot be changed => a pointer pointing to this object can be dereferenced producing the same original value. It means we can replicate pointers without replicating objects. And all of them would point to the same object. What do we do when we need to change the object? One popular solution is to use Copy-on-write (COW). Under COW principle we have a pointer to the object (a reference, a handle), we clone the object it points to, we change the value of the pointer so now it points to the cloned object, and proceed with our mutating algorithm. All other references are still the same.

JavaScript performs all of “the immutable object” things for strings, but it doesn’t do COW on strings because it uses even simpler trick: there is no way to modify a string. All strings are immutable by virtue of the language specification and the standard library it comes with. For example: str.replace(“a”, “b”) doesn’t modify str at all, it returns a new string with the replacement executed. Or not. If the pattern was not found I suspect it’ll return a pointer to the original string. Every “mutating” operation for strings actually returns a new object leaving the original string unchanged: replace, concat, slice, substr, split, and even exotic anchor, big, bold, and so on.

The issue is usually string operations come with a “hidden cost”; because strings are (in theory) immutable, we would expect that any kind of string mutation will come with the costs of copy and replace, taking up valuable CPU cycles, consuming memory space, and putting strains on a garbage collector (among other things). A typical technique used in many languages is to use something you can pass by reference (like an object or array) to your methods, and push string fragments into that—delaying the cost of string mutation until it is absolutely needed. In fact, this was the exact reason I wrote the original dojox.string.Builder; I borrowed the idea from C# as a way of increasing efficiency for large string operations, such as building a document fragment on the fly or serializing a JavaScript Object Literal.

(A side note: the original has gone through quite a few iterations, the latest one by Ben Lowery, who was initially using Builder extensively with Bloglines.)

After doing some fairly extensive testing, I learned that with the modern browsers, this is not the case at all; in fact, not only were typical string operations optimized cross-browser but the performance of dojox.string.Builder was dismal, particularly when compared against native operations.

Round 1: Measuring Native Operations.

The chart at the top of this article is the summary of native operation performance. All tests were done on a MacBook Pro 2.4Ghz Core 2 Duo, with 4GB of installed RAM; tests were run on both OS X and on Windows 2003 Server running under Parallels Desktop (with enough RAM allocated to ensure consistent results).

The first set of tests run was based on the tests made by Ben Lowery (the BuilderPerf test, see link above), using a Lorem Ipsum dictionary with the default numbers (1000 iterations using 100 words). The basic concept is to test performance based on both one-time and iterative operations. As an example, here are the tests for concat() once and concat() for:

{
    name: "concatOnce",
    test: function() {
        var s = "";
        s = String.prototype.concat.apply(s, words);
        return s;
    }
},
{
    name: "concatFor",
    test: function(){
        var s = "";
        for(var i=0; i<words.length; i++){
            s = s.concat(words[i]);
        }
        return s;
    }
}

…where the variable words is the dictionary initially generated used for all the tests.

The results were about what we would expect: one time operations in general executed much faster than iterative ones. Here’s the chart again:

String performance by browser

One interesting result: the += operator on strings is actually faster, across the board, than [string].concat().

Taking a closer look, we can also accurately gauge performance by browser. For example, comparing the major browsers with the once operations:

One time operations by browser

…we can see that the two most common browsers, Internet Explorer and Firefox (under Windows) have some issues; join performance with Firefox is not great but concat performance with Internet Explorer is absolutely dismal.

However, one time operations such as these—while attractive and certainly the best performing—are not nearly as common as operations made during some sort of iteration. Here’s the comparison of major browsers using the three most common operations during iteration (join, concat and the “+=” operator):

String operations through iteration

We can draw a few conclusions from this particular chart:

  1. The += operator is faster—even more than pushing string fragments into an array and joining them at the last minute
  2. An array as a string buffer is more efficient on all browsers, with the exception of Firefox 2.0.0.14/Windows, than using String.prototype.concat.apply.

The performance of dojox.string.Builder was also measured with this battery of tests; we’ll present that data later in the article.

Round 2: Comparing types of buffering techniques.

The second round of tests was performed using three slightly different versions of a typical JSON serializer, based on the one used in the Dojo Toolkit. The serializer has three versions:

  1. Recursive serialization using += (passing strings as the result of a function)
  2. Recursive serialization using local arrays as buffers (created internally to a function)
  3. Serialization using a single array passed to methods as an argument with no return (i.e. void)

The test takes a large pre-loaded Javascript Object Literal structure (the serialized version weighs in at 19,200 characters), and serializes it using all three serializers 10 times, taking the average result. Each test is run 5 times in succession. Finally, 20 samples were taken for each browser.

The expectation was that a single object as a string buffer would yield better performance results, consistently across browsers.

Results

Summary of performance through JSON serialization

In all cases (with the exception of Opera 9.27/Win), using a single object as a string buffer performed the worst, with the best general performance coming from using recursive serialization with the “+=” operator.

Comparing Browsers

To shed a little further light—and to accurately gauge the performance of each browser—we can compare each serialization technique:

Serialization using +=
Serialization using local arrays
Serialization using an object as buffer

As detailed elsewhere, Safari (on both OS X and Windows) is by far the fastest executing browser; unexpectedly, Opera 9.27—which historically has an excellent track record in terms of performance—was the least performant in these tests. Also of interest is the fact that the cross-platform browsers (Safari, Firefox and Opera) remain fairly consistent in terms of actual performance.

Round 3: Applying Results to dojox.string.Builder.

With the results of both rounds available, an analysis of the performance of dojox.string.Builder was undertaken. Performance numbers (pre-optimization) were captured during the first battery of tests, revealing a number of issues with the Builder.append method (by far the most commonly used method). However, some investigation and testing resulted in up to a 10x increase in performance—in some cases, being either comparable to or even beating certain browser operations!

Before and after optimization of dojox.string.Builder

Because of the very good performance in Safari and Opera, the goal of the optimization process was to address shortcomings in both Internet Explorer and Firefox.

Finding the culprits

Carefully analyzing the original code with dojox.string.Builder.append:

append: function(s){
    return this.appendArray(dojo._toArray(arguments));
}

…we determined that a number of things were causing performance issues:

  • The call to dojo._toArray, with the arguments object
  • Passing the results to dojox.string.Builder.appendArray, without testing first for a shorter branch
  • Dynamic arguments object access

Optimization 1: Addressing the Simplest Case.

The first change made introduced a branch, for all browsers, that checks to see if more than one argument was passed.

append: function(s){
    if(arguments.length>1){
        return this.appendArray(dojo._toArray(arguments));
    } else {
        this.b += s;
        return this;
    }
}

By performing this simple check, we eliminate the need for calling both dojo._toArray as well as the passthrough to the method appendArray. This change increased the performance of the append method with dramatic results—referring to the chart above, this was by far the greatest performance enhancer.

However, when passing multiple arguments to the append method, both Internet Explorer and Firefox slowed down dramatically.

Optimization 2: Fixing Internet Explorer

The internal string buffer used for Internet Explorer is different than any other browser; based on the test results from our first round, we know that pushing string fragments into an array and then join-ing them only when a complete string is needed is the best method for string handling.

Knowing that the culprit for real performance issues is the call to dojo._toArray with the arguments object, the goal was to eliminate the need for using it. One simple way to deal would be to simply iterate through the arguments and append each one, one by one:

append: function(s){
    if(arguments.length>1){
        for(var i=0, l=arguments.length; i < l; i++){
            this.b.push(arguments[i]);
        }
    } else {
        this.b.push(s);
    }
    return this;
}

This helped a bit, but there was not a dramatic increase in performance. To eek a bit more out of the method, we tested the difference between using [].push and manually specifying the next available index in the array; we found that specifying the next available index was a bit faster. Finally, we resorted to an implementation of Duff's Device, a technique for loop unrolling. Here's the final code:

append: function(s){
	if(arguments.length>1){
		//	Some Duff's device love here.
		var n = Math.floor(arguments.length/8), r = arguments.length%8, i=0;
		do {
			switch(r){
				case 0: this.b[this.b.length]=arguments[i++];
				case 7: this.b[this.b.length]=arguments[i++];
				case 6: this.b[this.b.length]=arguments[i++];
				case 5: this.b[this.b.length]=arguments[i++];
				case 4: this.b[this.b.length]=arguments[i++];
				case 3: this.b[this.b.length]=arguments[i++];
				case 2: this.b[this.b.length]=arguments[i++];
				case 1: this.b[this.b.length]=arguments[i++];
			}
			r = 0;
		} while(--n>0);
	} else {
		this.b[this.b.length]=s;
	}
	return this;
}

This loop unroll brought the performance of append with multiple arguments down to the same, or faster, than using append with a single argument multiple times.

Optimization 3: Fixing Firefox.

The last set of optimizations involved fixing the dismal performance in Firefox. Like with Internet Explorer, Firefox had major problems when using dojo._toArray, so the first order of business was to move iterating over the arguments object within the append method itself:

append: function(s){ 
	if(arguments.length>1){
		var i=0;
		while(i < arguments.length){
			this.b += arguments[i++];
		}
	} else {
		this.b += s;
	}
	return this;
}

What this revealed was that accessing members of the arguments object seemed to be very slow—to the point where just iterating over each argument caused enough of a performance hit to actually decrease the performance over using dojo._toArray!

With that in mind, and the help of my colleague Kris Zyp, what we determined was that the issue in Firefox isn't so much that accessing members of the arguments object is the issue; it's that dynamic access of the arguments object is the problem. With that in mind, a different kind of loop unroll was called for:

append: function(s){ 
	if(arguments.length>1){
		var tmp="", l=arguments.length;
		switch(l){
			case 9: tmp=arguments[8]+tmp;
			case 8: tmp=arguments[7]+tmp;
			case 7: tmp=arguments[6]+tmp;
			case 6: tmp=arguments[5]+tmp;
			case 5: tmp=arguments[4]+tmp;
			case 4: tmp=arguments[3]+tmp;
			case 3: tmp=arguments[2]+tmp;
			case 2: {
				this.b+=arguments[0]+arguments[1]+tmp;
				break;
			}
			default: {
				var i=0;
				while(i < arguments.length){
					this.b += arguments[i++];
				}
			}
		}
	} else {
		this.b += s;
	}
	return this;
}

With this unrolling technique, we accomplish the following:

  1. We create a temporary string buffer (tmp)
  2. We take advantage of Javascript's fall-through switch...case structure to deal with up to 9 arguments
  3. We specify in each case branch the actual argument number
  4. We prepend the argument to the temporary buffer
  5. ...finally appending the result to the internal buffer (this.b).

This unroll did not noticeably affect the performance of either Safari or Opera, but made a huge difference with Firefox; from the chart above, you can see close to a 10x increase in performance with both the Windows and OS X versions of Firefox. Note that passing more than 9 arguments will cause Firefox to fall back to the dynamic arguments access version; in theory we can simply add more case statements to deal with this, but from a practical standpoint 9 arguments should be a good limit.

Comparing dojox.string.Builder Performance with Native Operations

Finally, we should compare how the new optimized version of dojox.string.Builder compares to the native operations we analyzed in Rounds 1 and 2. Again, the tests (including a new one that tested the performance of Builder.append with mulitple arguments) were run, as they were with Round 1—this time with the optimized Builder.

Native string ops vs. dojox.string.Builder

With Safari and Opera, dojox.string.Builder is still slightly slower when used in iterative situations; however, the difference is close enough so that one should not find a noticeable decrease in performance when using it. With Internet Explorer, we find that the performance of the Builder is still pretty bad when compared to native operations.

However, with Firefox, the only operation faster than using Builder.append is the "+=" operator; both join and concat are close enough to Builder.append that it makes no difference which version you use.

Conclusions

Though this analysis, a number of things about string performance have been observed:

  • Native string operations in all browsers have been optimized to the point where borrowing techniques from other languages (such as passing around a single buffer for use by many methods) is for the most part unneeded.
  • Array.join still seems to be the fastest method with Internet Explorer; either += or String.prototype.concat.apply("", arguments) work best for all other browsers.
  • Firefox has definite issues with accessing argument members via dynamic/variables
  • And of course, the reminder to not ignore the data

For those numerically inclined, you can download the PDF version of all the data collected.

Comments

  • bob

    so, use “+=” is the best choice ? and dojox.string.Builder is not the best one, right?

  • ttrenka

    The short answer is that it depends on your situation.

    The longer answer is that by abstracting a good deal of these issues into an object such as dojox.string.Builder, you don’t have to worry about whether or not += is better for you than a join operation. A large part of the goodness of Builder is that those decisions are handled for you–especially if something changes internally with a browser engine. This article is actually a good example of that…2 years ago the internals of Builder were designed around string performance in older browsers (like IE6 and FF 1.5); things have obviously changed since then (for the better).

    I would say that if you aren’t building up very large strings, then using += is more than fine. When you start creating very large strings and manipulating them, it can be a different story.

  • Great post!

    The main reason for using push() is IE6 and it’s really bad GC. See Dan’s post from last year, http://pupius.co.uk/log/2007-03-07/

    It would also be interesting to see JScript 8 (or is it called 5.8?) which is included in IE8. They have done a great job improving the performance of JScript.

    How about using the Array.prototype.join.apply for IE?

    append: function(s){
    this.b.push.apply(this.b, arguments);
    return this;
    }

  • ttrenka

    Hi Erik,

    Thanks, it was a bit of work ;)

    I didn’t try either Firefox 3b or IE8 because of the beta status of both (and I need to have the current versions “unencumbered” for other dev); one thing I’m planning on is revisiting this when both are out in full. We did do some of the tests on FF3 but I didn’t record those numbers, mostly because they were performed on a badder machine (Core 2 Quad/Linux).

    I’ll try out the join.apply and see if that does anything for performance as well, I’ll let you know how it goes.

  • ttrenka

    OK, just tried it out (don’t know why I didn’t think of it), here’s the basic results.

    Before using push.apply (the Duff’s Device):
    builderMultiFor:
    1071, 1042, 1062
    builderFor:
    1312, 1252, 1272

    After implementing push.apply, with the branch for one argument:
    builderMultiFor:
    911, 942, 921

    …and with a little bit of spin-up (running the tests 4 times, reloading the test page 3 times):
    builderMultiFor:
    842, 841, 882
    builderFor:
    1121, 1022, 1011

    …so using push.apply has shaved a little bit of extra time. Thanks for the tip!

  • Carl

    Really nice-looking graphs. What did you generate them with?

  • The graphs were generated with Numbers, part of Apple’s iWork suite.

  • The test code is slow because of the recursive approach used to serialize the object (testcode: recursor = arguments.callee). It adds noise to the test. It seems that the results are closer together than if the test performed only concatenation.

    Have you tried isolating the serialization aspect in one function that does only the concatenation — no recursion, no serialization, just concatenation?

  • Ben

    Great work Tom! It’s always good to see numbers. I recall trying to use Duff’s back when I wrote those tests, but I don’t recall it helping.

    For Bloglines, we try to only use the “once” operations, and we have a little function internally that handles the browser differences. Based on this article I think I’ll revisit it and see if I can shave any more time off.

    In the bit about “dynamic access to the arguments object” being really slow in Firefox, do you mean that going after an item using a variable is slow (vs. a constant)? Like var i = 1, a = arguments[i]; is slower than var a = arguments[1]; ? If so, that’s an amazingly weird find. :)

    A couple really minor nits: the color used to represent each browser changes throughout the article. Any chance you could make it consistent? Also, the scales for some comparative graphs are different; it would help if they were consistent.

  • ttrenka

    @Garrett: yes, this was the point of using the BuilderPerf tests first; the JSON serialization battery of tests were intended to take a very common JS task and test different approaches, while looking for hints as to what approaches might be beneficial in other tasks. The recursive nature of that test was the point–especially since the BuilderPerf tests are deliberately *not* recursive in nature.

    @Ben: wrt to arguments object access, yes that’s exactly what we found. The loop unroll I pulled for the FF branch in Builder is what brought the performance of it back down to being comparable or faster than some of the other native operations.

    As far as the colors and ranges in the graphs are concerned…I *might* be able to fix colors but the ranges are a different story. I used Apple’s Numbers (iWork ’08) to create the graphs and while they are very pretty, there’s not a lot of control you have over how the graphs get rendered :(

  • Performance with arguments deserves a better explanation:
    FF performs optimizations where it will not actually build an “arguments” array object unless there is actually a need for to use the “arguments” object with dynamic indexes. When you use arguments[1], FF can optimize that to directly pull the value from the call parameters, rather than creating an arguments object and doing a GetValue on it. Once FF creates the arguments object, it is just as fast as a normal array. When you use dynamic indexes with the arguments object, it is not that FF has a particular performance problem with that, it is simply that turns off an optimization (not creating an unnecessary arguments object), and so you see a performance hit in comparison to the optimized code that doesn’t use the arguments with dynamic index access.

  • @Carl: pretty looking, yes, but distorting the facts as well. The 3d appearance of the top of the bars make it hard to determine whether we should read the front or the back of the bar in relation to the lines.

    Interesting article Tom, but the charts could use less eye-candy and more fact representation. Right now it would be classified as chartjunk.

  • ddunlop

    The while loop in your Duff’s device looks slightly wrong.

    n = Math.floor(9/8); // = 1

    do {} while(–n>0); // this would only do one iteration but needs to do two

    fixes:
    change floor to ceil
    change while test to n–>0 or –n>=0

    Over all nice work, thanks for sharing.

  • Pingback: Mellow Morning » Javascript optimization - high performance JS apps()

  • ttrenka

    @Jeroen: I would think (despite my general agreement with your sentiment) that it is obvious you should be using the back of the bars (i.e. the portion from the perspective closest to the measuring axis) than the front; in fact, some would argue that the perspective can actually help interpretation–since you are given a subtle indication (or pointer) at where the data actually lies WRT to an axis measurement.

    However…there is, at the end of the article, a link to download all of the raw numbers so that you might revisualize it for yourself; this is because I’m more than aware that many people have different ways of visualizing information, and there are those who are much happier with a more Tufte-based (if I might call it that) simplification of visual data.

    On the other hand, the attractiveness of these particular charts make for compelling arguments, especially when you take into account that very few people are interested in absolute data, and more are interested in relative. In that respect, these particular charts show–at a glance–exactly the information I am trying to convey, which is the relationship between various methods in terms of performance.

    While I agree with you in principle about chartjunk, I was *very* careful to attempt to ensure these particular charts ably conveyed the information I was presenting in an attractive way. We cannot simply dismiss the idea that so-called “bland” charts (read: charts that show exact data in a boring/non-visually-appealing way) are superior to careful chart rendering with more inviting visual appeal. I would wager than many people reading this article understood the points I was making because of the particular charts that I used, and that if I’d substituted more exact but less appealing charts a number of people would not have gotten far enough through the article to understand the conclusions.

    To summarize: summary points tend to be relative to the topic at hand, in which case these charts more than convey the relationships I am attempting to present. Exact datapoints are made available to anyone who wishes to review–for those of us like you.

    @ddunlop: thank you for the pointer; I’ve actually removed the Duff’s device in favor of Erik’s suggestions. You might want to post information about that somewhere where Google can index it, I’m sure many people would be grateful.

    @Mellow Morning (the trackback): you mention using Array.join over +=, which I directly contradicted in this article.

  • Hi Tom, nice article.

    My question deals with IE7 and the results from your += vs array.push tests. What test function did you use to conclude that IE7 is faster using +=?

    I ask because I have not been able to duplicate those results myself in my own tests. Such as,

    (function () {
    
        var times = [0, 0];
        
        var start = new Date();
        var s = "";
        for (var i=0; i<100000; i++) {
            s += "a";
        }
        times[0] = ((new Date()) - start);
        
        start = new Date();
        var s = [""];
        for (var i=0; ix.length; i--) { }
        times[0] = ((new Date()) - start);
        
        start = new Date();
        for (var i=1000000, j=x.length; i>j; i--) { }
        times[1] = ((new Date()) - start);
        
        alert("Times: " + times.join(" "));
    
    })();
    

    Matt

  • ( for moderator ) It seems my above post had a lot of the guts ripped out…

  • ttrenka

    Hi Matt–

    I didn’t. There’s some very close results in some of the Builder tests Ben Lowery wrote but for the most part += and Array.join are comparable with IE7. What I was saying was that overall, += is faster–but I think at this point, given the slight differences, you can get away with += over .join with IE7. The tests I based it on is the BuilderPerf tests (which I did not write); you can see the differences with the chart called “via Iteration”, section 1.

    Your tests, while definitely valid, are not necessarily realistic; adding a single character is not really a “real-world” situation. You might be better off trying that with a full word that changes per iteration, and then see what the results are (and I’d be interested as well!)

  • splintor

    Following Kris Zyp’s explanation of the dynamic arguments issue, would it be faster to use:
    var i=0;
    while(i<arguments.length){
    this.b += eval(‘arguments[‘ + (i++) + ‘]’);
    }

    or would the eval call outweigh the arguments array optimization?

    Another issue that comes to mind is using:
    append: function(s, s2, s3, s4, s5, s6, s7, s8, s9){
    and then use named arguments instead of arguments[2], arguments[3], etc. Would this change anything?

  • Pingback: SitePen Blog » String Performance: Getting Good Performance from Internet Explorer()

  • Prestaul

    @splintor: Why would you use eval? Your code should look like:

    var i = 0, len = arguments.length;
    while(i < len){
    this.b += arguments[i++];
    }

  • Pingback: Ajax Performance » Catching up on performance with the SitePen crew()

  • @Prestaul: As I said, my suggestion follows Kris Zyp’s explanation of the dynamic arguments, where he explain that using arguments[1], arguments[2], etc. can be optimized by Firefox to access the passed arguments directly, without creating an arguments array, whereas using arguments[i] forces Firefox to create the arguments array. I was thinking that if we use eval, Firefox sees “arguments[1]”, and this is better than arguments[i], but as I said, the trouble with eval might outweigh the arguments issue.

  • Pingback: Performance web » Concaténation javascript()

  • Pingback: New browsers : SunSpider JavaScript Benchmark Results. | keyongtech()

  • In the meantime, do you have any numbers for Firefox 3 or even 3.1 beta? My experience was that Array#join()’s performance deteriorated compared to FF2. With FF3, my browser game started spending 95% computation time in Array#join(). Unfortunately, I could not find any other evidence on the Web. Does anybody know what has been changed?

  • Found out what was the problem. I do not recommend to use Array#join() with an array containing objects with a toString() method. For some reason, Firefox 3 is much less efficient when calling toString() implicitly while joining, compared to adding object.toString() to the array in the first place, then joining the array.

  • I’ve just found out that in Chrome 3, the concat method of String is x7000 SLOWER than the other two!!

    See my test below:
    http://blog.onthewings.net/2009/10/09/as3-js-string-concatenation-methods-performace-test/

  • Pingback: Garbage Collection in IE7 heavily impacted by number of JavaScript objects and string sizes Performance, Scalability and Architecture – Java and .NET Application Performance Management (dynaTrace Blog)()

  • The formatting of the article is all screwed up on FF 4 an Chrome on Macs

  • Thanks, this has been resolved.

  • Vitoc

    I know I’m late to the party, but this was very informative. There appears to be a great deal of bad^H^H^H horrible advice out there about the array/join method. When our team did some basic testing we came to the same conclusion in this article; that using += is almost always faster. What we still have yet to find is an explanation of why. If strings are immutable in javascript (and all resources I’ve seen indicate they are), it seems like it would be very expensive to concat any string onto a large and growing string in a lengthy loop. I’m guessing the browser creators have some sort of stringbuilder approach they use in their javascript engine implementation for string operations, so we’re not seeing any benefit by rolling our own, and in fact end up adding unnecessary complexity and inefficiency. Either that or none of the browser creators have bothered making the join method efficient with a buffered approach. I can’t imagine in this day and age that’s the case. Anyway, thanks for taking the time to benchmark this and documenting the results. ;)

  • Martin Vahi

    For

    s = “x” + “x” + “x” + “x” + “x”

    which is equivalent to

    s = ((((“x” + “x”) + “x”) + “x”) + “x”)

    the memory consumption of temporary, throw-away, strings is:

    i_len=(“x”.length)*5+
    (“xx”.length)+
    (“xxx”.length)+
    (“xxxx”.length)=5+2+3+4=14

    The memory consumption of temporary, throw-away, strings of

    s = (((“x” + “x”) + (“x” + “x”)) + (“x”)) // watershed concatenation

    is

    i_len=(“x”.length)*5+
    (“xx”.length)*2+
    (“x”.length)=5+4+1=10

    Speed-test kit with BSD-licensed watershed-concatenation implementations for
    Ruby, JavaScript, PHP is available at:
    https://github.com/martinvahi/mmmv_notes/tree/master/mmmv_notes/phenomenon_scrutinization/string_concatenation

  • Dennis Jakobsen

    Awesome, now you just need to learn how to make Graphs and there would be a point to this article! :P