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.

Answer 1

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)

Answer 2

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!

Answer 3

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.

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.

Answer 5

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.

Answer 6

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.