Quadratic String Building

Problem

A client library accumulates a streamed HTTP response body into a string. It works fine for small responses:

class ResponseBuffer:
    def __init__(self):
        self.body = ""

    def feed(self, chunk: str) -> None:
        self.body += chunk

    def finish(self) -> str:
        return self.body


def download(stream) -> str:
    buf = ResponseBuffer()
    for chunk in stream:          # 8 KB chunks from the socket
        buf.feed(chunk)
    return buf.finish()

Symptom: a 5 MB export downloads in under a second. A 200 MB export takes over twenty minutes with one CPU core pinned at 100%, and the network is idle most of that time. A profiler attributes almost all the time to the self.body += chunk line. A colleague tried to reproduce it in a script with a plain local variable (body += chunk in a loop) and it ran in seconds, so they concluded the profiler was wrong. Explain what is happening, why the local-variable repro did not show it, and fix it.

Examples

• 5 MB in 8 KB chunks is 640 chunks. Total bytes copied ≈ 8 KB × (1 + 2 + ... + 640) ≈ 8 KB × 205,000 ≈ 1.6 GB. Fast enough to go unnoticed.
• 200 MB in 8 KB chunks is 25,600 chunks. Total bytes copied ≈ 8 KB × 25,600 × 25,601 / 2 ≈ 2.6 TB. At a generous 10 GB/s of memcpy that is about 260 seconds of pure copying, before allocator overhead and cache misses; twenty minutes is entirely plausible.
• Expected after the fix: 200 MB copied roughly twice (once into the list of chunks, once into the joined result), on the order of a second.

Hints

1. Strings in Python are immutable. What does a += b have to do when a is a string?
2. Write down how many bytes are copied on the k-th feed call, then sum over all k.
3. The local-variable version has a CPython-specific fast path. Under what condition can CPython resize a string in place?