Why is string concatenation faster than array join?

Question

Today, I read this thread about the speed of string concatenation.

Surprisingly, string concatenation was the winner:

http://jsben.ch/#/OJ3vo

The result was opposite of what I thought. Besides, there are many articles about this which explain oppositely like this.

I can guess that browsers are optimized to string concat on the latest version, but how do they do that? Can we say that it is better to use + when concatenating strings?

---

Update

So, in modern browsers string concatenation is optimized so using + signs is faster than using join when you want to concatenate strings.

But @Arthur pointed out that join is faster if you actually want to join strings with a separator.

---

Update - 2020
Chrome: Array join is almost 2 times faster is String concat + See: https://mcmap.net/q/37231/-why-is-string-concatenation-faster-than-array-join

As a note:

• Array join is better if you have large strings
• If we need generate several small strings in final output, it is better to go with string concat +, as otherwise going with Array will need several Array to String conversions at the end which is performance overload.

---

Covering

This code is supposed to produce 500 terabytes of garbage, but it runs in 200 ms. I think that they just allocate slightly more space for a string, and when you add a short string to it, it usually fits into an extra space. – Neckwear

Answer 1

Browser string optimizations have changed the string concatenation picture.

Firefox was the first browser to optimize string concatenation. Beginning with version 1.0, the array technique is actually slower than using the plus operator in all cases. Other browsers have also optimized string concatenation, so Safari, Opera, Chrome, and Internet Explorer 8 also show better performance using the plus operator. Internet Explorer prior to version 8 didn’t have such an optimization, and so the array technique is always faster than the plus operator.

— Writing Efficient JavaScript: Chapter 7 – Even Faster Websites

The V8 javascript engine (used in Google Chrome) uses this code to do string concatenation:

// ECMA-262, section 15.5.4.6
function StringConcat() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined", ["String.prototype.concat"]);
  }
  var len = %_ArgumentsLength();
  var this_as_string = TO_STRING_INLINE(this);
  if (len === 1) {
    return this_as_string + %_Arguments(0);
  }
  var parts = new InternalArray(len + 1);
  parts[0] = this_as_string;
  for (var i = 0; i < len; i++) {
    var part = %_Arguments(i);
    parts[i + 1] = TO_STRING_INLINE(part);
  }
  return %StringBuilderConcat(parts, len + 1, "");
}

So, internally they optimize it by creating an InternalArray (the parts variable), which is then filled. The StringBuilderConcat function is called with these parts. It's fast because the StringBuilderConcat function is some heavily optimized C++ code. It's too long to quote here, but search in the runtime.cc file for RUNTIME_FUNCTION(MaybeObject*, Runtime_StringBuilderConcat) to see the code.

Bader

You left the really interesting thing out, the array is only used to call Runtime_StringBuilderConcat with different argument counts. But the real work is done there. – Barstow

It's fast because [it's] heavily optimized But in which ways? That is the question. – Fukuoka

Optimization 101: You should aim for the least slow! for example, arr.join vs str+, on chrome you get (in operations per second) 25k/s vs 52k/s. on firefox new you get 76k/s vs 212k/s. so str+ is FASTER. but lets look other browsers. Opera gives 43k/s vs 26k/s. IE gives 1300/s vs 1002/s. see what happens? the only browser that NEED optimization would be better off using what is slower on all the others, where it doesn't matter at all. So, None of those articles understand anything about performance. – Epitomize

@gcb, the only browsers for which join is faster shouldn't be used. 95% of my users have FF and Chrome. I'm going to optimize for the 95% use case. – Lining

@Epitomize - That's a view that's narrow to the point of being ridiculous. Does the % of users on each browser play zero role in the decision of how to optimize for various browsers? To this day should I sacrifice the optimization of 99% of my users for the sake of 1%? What about when it's 99.9% to 0.1%? – Melody

@PaulDraper if 90% of users are on a fast browser and either option you choose will gain them 0.001s, but 10% of your users will gain 2s if you choose to penalize the other users out of that 0.001s... the decision is clear. if you can't see it, i am sorry for whoever you code for. – Epitomize

@gcb, your hypothetical example is true, but the case at hand just doesn't match. Chrome and IE is not a 2000x differences; it's a 25x difference. And IE will only be 2s slower with + if you're optimizing 7s of string concatenation. I agree with your statement in principle, but not in this case. (Also FYI, I should have said Chrome, FF, and IE 8+ were my 95%.) – Lining

@PaulDraper, 95% is not enough. With just a billion users you get 5% = 50 million people complaining about slow. The problem is, how slow is slow? If it's slow to the extent that it's unmanageable, then you can't even afford to let 5% of your users face that. Also, how fast is fast? There's such a thing as fast enough because humans can't perceive the difference between 0.1ms and 0.2ms. – Biparty

Older browsers will eventually go away, but the odds of someone going back to convert all those array joins isn’t likely. It’s better to code for the future as long as it isn’t a major inconvenience to your current users. Odds are there are more important things to worry about than concatenation performance when dealing with old browsers. – Graphomotor

This is an old answer. As of ~Aug 2020, it is reverse. Array Join is almost 2 times faster than String concat (+). See: https://mcmap.net/q/37231/-why-is-string-concatenation-faster-than-array-join – Ellanellard

Answer 2

Firefox is fast because it uses something called Ropes (Ropes: an Alternative to Strings). A rope is basically just a DAG, where every Node is a string.

So for example, if you would do a = 'abc'.concat('def'), the newly created object would look like this. Of course this is not exactly how this looks like in memory, because you still need to have a field for the string type, length and maybe other.

a = {
 nodeA: 'abc',
 nodeB: 'def'
}

And b = a.concat('123')

b = {
  nodeA: a, /* {
             nodeA: 'abc',
             nodeB: 'def'
          } */
  nodeB: '123'
}           

So in the simplest case the VM has to do nearly no work. The only problem is that this slows down other operations on the resulting string a little bit. Also this of course reduces memory overhead.

On the other hand ['abc', 'def'].join('') would usually just allocate memory to lay out the new string flat in memory. (Maybe this should be optimized)

Barstow

Answer 3

For large amount of data join is faster, so the question is stated incorrectly.

let result = "";
let startTime = new Date().getTime();
for (let i = 0; i < 2000000; i++) {
    result += "x";
}
console.log("concatenation time: " + (new Date().getTime() - startTime));

startTime = new Date().getTime();
let array = new Array(2000000);
for (let i = 0; i < 2000000; i++) {
    array[i] = "x";
}
result = array.join("");
console.log("join time: " + (new Date().getTime() - startTime));

Tested on Chrome 72.0.3626.119, Firefox 65.0.1, Edge 42.17134.1.0. Note that it is faster even with the array creation included!

Stapes

~Aug 2020. True. In Chrome: Array Join time: 462. String Concat (+) time: 827. Join is almost 2 times faster. – Ellanellard

Press "run code snippet" a few more times and see what happens. – Eulogium

Answer 4

I know this is an old thread, but your test is incorrect. You are doing output += myarray[i]; while it should be more like output += "" + myarray[i]; because you've forgot, that you have to glue items together with something. The concat code should be something like:

var output = myarray[0];
for (var i = 1, len = myarray.length; i<len; i++){
    output += "" + myarray[i];
}

That way, you are doing two operations instead of one due to glueing elements together.

Array.join() is faster.

Mcnew

I don't get your answer. What is difference between putting "" + and the original? – Covering

It's two operations instead of one on each iteration which takes more time. – Mcnew

And why do we need to put that? We are already glueing items to output without it. – Covering

Because this is how join works. For example, you can also do Array.join(",") which will not work with your for loop – Mcnew

Oh I got it. Have you already tested to see if join() is faster? – Covering

Yep, if you use "" it is just 3% faster, but if you use at least " ", the difference is much more dramatic. Also, concat wins on the first run, but loses every consecutive run after that (I think it's due to code optimisation during the first run). – Mcnew

This is important point. Let me update my question to include this finding. Thanks for letting me know this. – Covering

This is not the case, you should not add extra empty line "" + into string add test. (It would be better to add random input of random size btw). join() defaults to , as separator, join('') however internally optimized, in V8 see SparseJoin (+ StringBuilderConcat, StringBuilderConcatHelper) implementation it doesn't use separator at all. So for the given input + is faster in certain browsers. Also you can take a look on Runtime_StringAdd vs StringBuilderConcat implementation. – Lowestoft

Answer 5

I would say that with strings it's easier to preallocate a bigger buffer. Each element is only 2 bytes (if UNICODE), so even if you are conservative, you can preallocate a pretty big buffer for the string. With arrays each element is more "complex", because each element is an Object, so a conservative implementation will preallocate space for less elements.

If you try to add a for(j=0;j<1000;j++) before each for you'll see that (under chrome) the difference in speed becomes smaller. In the end it was still 1.5x for the string concatenation, but smaller than the 2.6 that was before.

AND having to copy the elements, an Unicode character is probably smaller than a reference to a JS Object.

Be aware that there is the possibility that many implementations of JS engines have an optimization for single-type arrays that would make all I have written useless :-)

Brunel

Answer 6

The benchmarks there are trivial. Concatenating the same three items repeatedly will be inlined, the results will proven deterministic and memoized, the garbage handler will be just throwing away array objects (which will be next to nothing in size) and probably just pushed and popped off the stack due to no external references and because the strings never change. I would be more impressed if the test was a large number of randomly generated strings. As in a gig or two's worth of strings.

Array.join FTW!

Sherysherye

Answer 7

This test shows the penalty of actually using a string made with assignment concatenation vs made with array.join method. While the overall speed of assignment is still twice as fast in Chrome v31 but it is no longer as huge as when not using the resultant string.

Ramakrishna

Answer 8

As of 2021 on Chrome, array push+join is about 10x slower for 10^4 or 10^5 strings, but only 1.2x slower for 10^6 strings.

Try it on https://jsben.ch/dhIy

Bowman

there is no test on the link – Resale

Answer 9

This clearly depends on the javascript engine implementation. Even for different versions of one engine you can get significally different results. You should do your own benchmark to verify this.

I would say that String.concat has better performance in the recent versions of V8. But for Firefox and Opera, Array.join is a winner.

Eyot

Answer 10

My guess is that, while every version is wearing the cost of many concatenations, the join versions are building arrays in addition to that.

Taw