The Python FAQ states the theory plainly: repeated string concatenation means “the total runtime cost is quadratic in the total string length”, because strings are immutable and each + allocates a new one and copies both operands.
And then you benchmark it and it is not quadratic, and you conclude the FAQ is out of date.
Why the benchmark lies
CPython has a special case. BINARY_OP_INPLACE_ADD_UNICODE mutates the left-hand string in place when it can prove nobody else can see it. The guard, in Python/bytecodes.c, requires two things:
-
the next instruction must be
STORE_FASTtargeting the same local variable, and - that local must still hold the string being extended, so the interpreter can prove the only reference is the one it is about to overwrite.
When both hold, the concatenation becomes a realloc-and-append and the loop is linear.
Measured, 50,000 concatenations of an 8-character string:
| time | |
|---|---|
s += x |
1.25 ms |
"".join(parts) |
0.57 ms |
s += x with a live alias |
131 ms |
The third row is the whole article. Add one line before the concatenation:
for chunk in chunks:
t = s # an alias -- maybe for logging, maybe a debug print
s += chunk
Now s is not the only reference, the guard fails, and every iteration allocates and copies the entire accumulated string. 105x slower, from a line that any reviewer would wave through.
The traps that follow from the guard
self.buffer += chunk never fires. The guard requires STORE_FAST — a local variable. An attribute store is STORE_ATTR. Accumulating onto an instance attribute is quadratic from the first iteration, always, with no cliff to fall off because you started at the bottom.
Same for a dict entry, a list element, a global, a closure cell, a nonlocal.
PEP 8 says this out loud, and it is worth quoting because it is the style guide, not a blog post: “This optimization is fragile even in CPython (it only works for some types) and isn’t present at all in implementations that don’t use refcounting.” PyPy, GraalPy and any future implementation are under no obligation.
💡The failure mode here is described as "a cliff, not a slope". Why does that distinction change how you should review code, compared with an ordinary O(n^2) mistake? click to reveal
An ordinary quadratic gets slower gradually as n grows, so it is caught by the thing that catches most performance problems: someone notices a trend. You can see it in a latency graph, you can catch it in a load test, and the growth gives you warning.
A cliff has no trend. The code is linear until an unrelated edit makes it quadratic, and then it is 100x slower from one deploy to the next, with no change to n and no change to the loop. The commit that caused it does not touch the loop — it adds a log line, or a debug assignment, or passes the accumulator to a helper. In the post-mortem, nobody suspects that line, because it does not do anything.
So the review consequence is that you cannot rely on measurement to protect you here. Measuring the current code tells you nothing about whether it will still be fast next month. The only durable defence is to not depend on the optimisation at all — accumulate into a list and join once, which is linear unconditionally, on every implementation, regardless of who else holds a reference.
What to write
For str: accumulate into a list, join once.
parts: list[str] = []
for row in rows:
parts.append(render(row))
return "".join(parts)
Linear, unconditional, portable, and faster than the optimised += anyway. join computes the total length in one pass and allocates exactly once.
For bytes: use a bytearray. This is the FAQ’s own recommendation. bytes is immutable and gets no in-place special case at all; bytearray is mutable and += genuinely appends into a growing buffer, amortised O(1). Convert once at the end with bytes(buffer) if you need immutability.
buffer = bytearray()
for row in rows:
buffer += render(row).encode("utf-8")
return bytes(buffer)
For a stream: yield, and let the caller join. A generator of lines composes with "".join(...), with file.writelines(...), and with a streaming HTTP response, without materialising the whole document.
💡"".join(parts) allocates the result exactly once. What does it have to do first in order to manage that, and what does that imply for joining a generator?
click to reveal
It has to know the total length, which means it has to look at every part before allocating. For a list that is a cheap first pass over the elements.
For a generator, it cannot do that without consuming it — and once consumed there is nothing left to copy from. So str.join materialises a generator argument into a list internally before joining. You get the correct answer, and you do not get the memory saving you may have thought you were getting: "".join(render(r) for r in rows) holds every rendered row in memory at once, exactly as the list version does.
The practical consequence: if the reason you reached for a generator was memory rather than style, join is not where you want to end. Write to a file or a response stream incrementally instead, so no full copy ever exists. If the reason was style, the generator form is fine and costs nothing extra.