[Phillip J. Eby, on
s = "" for e in iterable: s = s + e
Last question: is this actually faster when 'e' is replaced by an expression that causes memory allocation? That is, isn't this *still* going to be an O(n**2) operation if the string has to be relocated on each addition?
It can't guarantee worst-case linear time, regardless of whether e causes memory allocation. That's because it relies on the platform realloc() to get more memory (after the string gets too big for pymalloc), so its behavior depends on what the platform realloc() does. If the string gets "big enough", a number of realloc() implementations will move the string "to the end" of memory, and grow it thereafter via sbrk() calls. If e causes memory allocation too, it's likely to get satisfied by free blocks "before the end" of memory (for example, from the big block released at the time the string first got moved to the end). But there's no consistency across platforms in how the native realloc() behaves.
BTW, so long as the string object is small enough to be handled by pymalloc, it guarantees *to* copy the entire string object for each 8 characters added (pymalloc can never extend in-place when an 8-byte boundary is crossed).