9.11 Memory and Performance

Why Immutability Matters Here

Immutability makes strings safe to share across functions, threads, and dict/set keys without defensive copying, and it’s what allows CPython to intern and cache strings safely (see 9.1 Introduction to Strings). It’s also the direct cause of the single most important string performance rule below.

String Memory Optimization

Since PEP 393, CPython stores each string at 1, 2, or 4 bytes per character depending on its widest code point — a pure-ASCII log line costs far less memory than one containing emoji or CJK text.

Efficient Concatenation: `join()` as StringBuilder

Because strings are immutable, each += inside a loop allocates a brand-new string and copies everything seen so far into it — costing O(n²) overall for n pieces. join() instead collects all the pieces first and allocates the final buffer exactly once, costing O(n).

# Inefficient: allocates a new string object every iteration -- O(n^2)
result = ""
for word in word_list:
    result += word + " "

# Efficient: build a list, join once -- O(n)
result = " ".join(word_list)

When to Use f-Strings

Default choice for readability and speed in Python 3.6+.
Prefer .format() when the template string itself is data (loaded from a config file) — see 9.6 String Formatting.
Prefer string.Template when the template comes from an untrusted source, since f-strings evaluate arbitrary expressions.

Time Complexity of String Operations

Knowing the Big-O cost of each operation is what separates code that works on a small test from code that stays fast on a million-line log file:

Operation	Time Complexity	Notes
Indexing `s[i]`	O(1)	Direct memory offset
Slicing `s[a:b]`	O(k)	k = length of the slice
Concatenation `s1 + s2`	O(n)	n = combined length; O(n²) if repeated in a loop
`len(s)`	O(1)	Length is cached on the object
`in` / `not in`	O(n)	Linear scan
`str.join(list)`	O(n)	n = total combined length
`str.replace()` / `.split()`	O(n)	Single pass
`hash(s)`	O(n) first time, O(1) after	Hash is cached on the object

Quick Interview Answer

“The single most important performance rule for strings: building one incrementally with += inside a loop is O(n²), because every += allocates a brand-new string and copies everything accumulated so far. ''.join(pieces) is O(n) instead, since it computes the total length once and allocates exactly one buffer. This follows directly from immutability — there’s no in-place append the way a list has. Beyond that, indexing and len() are O(1) since strings cache their length, while in, replace(), and split() are all O(n) linear scans.”

Common Mistakes

Building a large string with += in a loop instead of accumulating pieces in a list and calling "".join(...) once at the end.
Assuming len(s) re-scans the string each call — it’s O(1) because the length is cached on the object at creation time.
Ignoring memory cost differences between ASCII and wide-Unicode strings when processing huge volumes of text — a string full of emoji or CJK characters can use 2-4x the memory of an equivalent-length ASCII string.