Pointer Walk

String Concatenation in a Loop

Every += copies everything written so far. The hidden O(n²), and the builder that removes it.

Languages and RuntimesBeginner6 min read

Building a string piece by piece

A very natural way to build up text is to start with nothing and keep adding to it.

java
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:

  1. Allocate a brand new string

    Big enough for the old text plus the new piece.

  2. Copy all of the old text into it

    Every character written so far.

  3. Copy the new piece after it

    A few more characters.

  4. Throw the old string away

    result now refers to the new one.

The second step is the problem. Every += copies everything written so far.

s += piece, in a loopInteractive
Method

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.

java
StringBuilder builder = new StringBuilder();
for (String piece : pieces) {
    builder.append(piece);
}
String result = builder.toString();
python
result = "".join(pieces)
js
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. join is 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.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    6 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress