Building a string piece by piece
A very natural way to build up text is to start with nothing and keep adding to it.
String result = "";
for (String piece : pieces) {
result += piece;
}It is clear and it is correct. With a few dozen pieces it is fine. With a hundred thousand, the program slows to a crawl, and the reason is hidden inside +=.
Strings cannot be changed
In Java, Python, JavaScript, C# and many other languages, a string is immutable: once created, it can never be altered. That makes strings safe to share and to use as dictionary keys.
It also means result += piece cannot add to the existing string. What actually happens:
Allocate a brand new string
Big enough for the old text plus the new piece.
Copy all of the old text into it
Every character written so far.
Copy the new piece after it
A few more characters.
Throw the old string away
resultnow refers to the new one.
The second step is the problem. Every += copies everything written so far.
The string, rebuilt on this step
(empty)
Pink: copied on this step. Violet: newly added.
Start. Strings cannot be changed once made. So s += piece does not extend s. It builds a completely new string and copies everything into it.
- Pieces added
- 0 / 8
- Characters copied in total
- 0
Doing the sum
Each piece gets copied again every time a later piece is added. The first piece is copied on every single step.
Example
1,000 pieces of 10 characters
The final text is 10,000 characters long.
With +=: the first step copies 10 characters, the second copies 20, the third 30, up to 10,000 on the last. Added together: 5,005,000 characters copied.
With a builder: 10,000.
Now double it to 2,000 pieces. The builder copies 20,000. += copies about 20 million: four times as much for twice the work.
Twice the input, four times the cost. That is O(n²), hiding in a loop that looks linear.
The fix: collect, then join once
Keep the pieces in something that can grow cheaply, and build the final string a single time at the end, when the total length is known.
StringBuilder builder = new StringBuilder();
for (String piece : pieces) {
builder.append(piece);
}
String result = builder.toString();result = "".join(pieces)const result = pieces.join("");Each character is now copied about once.
Does my language do this?
It depends, which is a good reason to use the safe pattern everywhere.
- Java: the loop above is quadratic. The compiler does not rescue it.
- Python:
+=on strings is sometimes optimised by the standard interpreter and sometimes not."".join()is always fast and is the recommended way. - JavaScript: modern engines postpone the copying internally, so
+=is often fine.joinis still dependable. - C#: same as Java. Use
StringBuilder.
The same trap with other things
Anything immutable or copied on change behaves this way: building a list with result = result + [item], extending a tuple in a loop, or creating a new array with one more element each time. If each step copies everything so far, the total is quadratic.
Key takeaways
- Strings are immutable in most languages, so += builds a new string and copies everything into it.
- In a loop, that means every earlier piece is copied again on every step.
- The total copying grows with the square of the number of pieces.
- Collect the pieces and join them once: StringBuilder in Java, join in Python and JavaScript.
- Joining a few strings with + is fine. The problem is a string that grows inside a loop.