JavaScript string concatenation speed

Question

Can someone explain this one to me:

http://jsperf.com/string-concatenation-1/2

If you're lazy, I tested A) vs B):

A)

var innerHTML = "";

items.forEach(function(item) {
    innerHTML += item;
});

B)

var innerHTML = items.join("");

Where items for both tests is the same 500-element array of strings, with each string being random and between 100 and 400 characters in length.

A) ends up being 10x faster. How can this be--I always thought concatenating using join("") was an optimization trick. Is there something flawed with my tests?

Answer 1

Using join("") was an optimization trick for composing large strings on IE6 to avoid O(n**2) buffer copies. It was never expected to be a huge performance win for composing small strings since the O(n**2) only really dominates the overhead of an array for largish n.

Modern interpreters get around this by using "dependent strings". See this mozilla bug for an explanation of dependent strings and some of the advantages and drawbacks.

Basically, modern interpreters knows about a number of different kinds of strings:

1. An array of characters
2. A slice (substring) of another string
3. A concatenation of two other strings

This makes concatenation and substring O(1) at the cost of sometimes keeping too much of a substringed buffer alive resulting in inefficiency or complexity in the garbage collector.

Some modern interpreters have played around with the idea of further decomposing (1) into byte[]s for ASCII only strings, and arrays of uint16s when a string contains a UTF-16 code unit that can't fit into one byte. But I don't know if that idea is actually in any interpreter.