Why is string concatenation faster than array join?

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

Solution 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)

Solution 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!

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

Solution 5:

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!