Strings from the inside: three widths, four layout cases, interning, and the price of concatenation

One character sets the width

CPython, following PEP 393, stores a string in whichever of three widths suffices for its highest character. There is one width per string: a single emoji moves every character to four bytes, including all the Latin letters that would have fit in one.

The length is the same in all four positions of the switch — twenty. One character out of twenty changes.

There are three widths, and four cases visible in the size: ASCII lives in its own structure with a 40-byte header instead of 56 (the numbers are from this 64-bit build). An ASCII string's UTF-8 form is byte-for-byte itself, so there is nothing to cache; any other string has the fields for that cache. Hence one é growing a string from 61 to 77 bytes without changing the bytes per character.

Over a million sixteen-character strings that is 54.4 mebibytes for Latin and 118.3 for emoji — the same information written in different widths.

Why is sometimes "works"

CPython keeps a table in which a string value exists in one copy, and puts some strings there by itself. Nowhere is it promised which ones.

Not every single character is created at start-up — only the one-byte ones: chr(0x100) built twice gives two different objects, while chr(0xFF) gives the same one.

What is observed: a literal that looks like a name gets interned; a literal with a space or punctuation does not; a string assembled at run time does not.

literal = "some_attribute_name"
built = "".join(["some_attribute", "_name"])
 
literal == built      # True
literal is built      # False

The danger is not that is gives a wrong answer but that it gives the right one for as long as the strings come from the source. Code comparing strings with is will pass every test written on literals and break on the first string from a file, the network or a database — silently, answering False: "not the same object", though == would have said True.

"ab" + "cd" is "abcd" is a separate case, and it gives True. That is not interning but constant folding: adding two literals is done by the compiler, and one constant remains in the bytecode. Replace the literals with variables and is gives False.

Why concatenation is sometimes fast

"Strings are immutable, so concatenation in a loop is quadratic" is correct reasoning with a wrong conclusion: an ordinary loop with s += x runs linearly, because the string grows where it is.

There are two conditions for that. The first is the shape of the code: the accumulator must be a local variable of a function, and the result must be assigned straight back into it. The second is checked at run time: the string must have no extra references.

The second is the invisible one. Add the line keep = s to the loop — it computes nothing — and the opcode stays exactly the same while twenty thousand steps take 140.7 milliseconds instead of 0.8.

This is checked not by the ratio of times, which swings on this machine, but by the price of one step. On the fast path it does not move at all: 43, 42, 40, 39 nanoseconds as the length grows from 2500 to 20,000. On the slow path it grows with the length: 201, 442, 962, 4644. Every step copies everything already accumulated.

What to do about it

Reach for "".join(). In this measurement it is not faster than in-place concatenation — 0.6 ms against 0.8, the same order — but it is more dependable: its time does not depend on where the accumulator lives, on whether somebody kept a reference, or on whether this code gets moved into a method tomorrow.

Do not compare strings with is. No version promises which strings get interned automatically, and the boundaries of that behaviour have already moved between 3.12 and 3.13.

And keep the width in mind wherever strings are many: one character outside Latin costs not its own four bytes but four bytes for every character of the string.

A string's object size at the same length depends on what is inside it — and it depends SYSTEMATICALLY: on the highest character code, not on the object's history.

That contradicts what every other container teaches, which is why it slips past. A twenty-character string: twenty Latin letters are 61 bytes, the same twenty with one Cyrillic letter are 98, with one emoji 140. No character other than the replaced one changed.

A string is not the only such type, and that is worth saying up front so the causes do not get mixed up later. An integer's size depends on the magnitude of the number: 0 takes 28 bytes, 2**1000 takes 160. A list's size at the same length depends on how the list was built: list(range(100)) is 856 bytes, while the same length assembled with append is 920. What is different about a string is that this is neither history nor spare room but a direct consequence of the contents: the same twenty characters in the same alphabet always give the same number.

The article has three parts on the mechanism and a fourth with exercises. Each of the three answers its own question. Why strings of equal length take different amounts of memory. Why is sometimes works for strings — and why it must not be relied on. And why s += x in a loop is sometimes linear and sometimes quadratic: the fast path has two conditions, and the second one is nowhere visible in the code.

Part I. Three widths and four layout cases

The width is chosen by the highest character

PEP 393 named both the problem and the answer in one sentence:

"With the largest ordinal" is the load-bearing part. The width is not chosen per character: there is one width per string, and the highest character decides it. One emoji in the middle of Latin text moves EVERY character to four bytes, including all the Latin letters that would have fit in one.

The length is the same in all four positions of the switch — twenty. One character out of twenty changes, and with it the width of all of them. The switch shows Greek α where the text above says Cyrillic: both live in the same range, and the run prints them side by side to show that they give the same 98.

The fourth case, and it is not a width

PEP 393 has three widths: one, two and four bytes per character. The cases visible in the size of the object are four, and the fourth is not a width: an ASCII string lives in a separate structure with a shorter header. From here on "four" in this article means exactly that — four layout cases for a compact string, not four widths. Measured by bench/strings/layout.py:

The first two rows differ not in the width of a character — both are one byte — but in the header: 40 against 56. Those sixteen bytes are two fields for a cached UTF-8 form, which an ASCII string does not have, because its UTF-8 is byte-for-byte itself.

Two different things are worth separating here, because they glue together easily. The canonical representation — the one the string is stored in and the one len counts — is one, two or four bytes per character. The cached UTF-8 is a separate representation of the same string that may sit beside it once somebody has asked for it. One byte per character in the first sense does not mean "the string is stored as UTF-8": for Latin-1 the canonical byte and the UTF-8 byte are different things, which is exactly why it has fields for the cache.

Hence the thing that surprises first: one é in a string of twenty Latin letters grows it from 61 to 77 bytes without changing the bytes per character. What grew was not the contents but the header.

"Quadruples", likewise, is about the character buffer rather than the size of the whole object: getsizeof also covers the header and the terminating zero, so for a short string the total does not grow exactly fourfold — 61 bytes against 140 at twenty characters.

The run puts the same thing in absolute numbers: an empty string is 41 bytes, 'x' * 10 is 51 and 'é' * 10 is 67 — a difference of sixteen, and all of it header. A single é must not be used for this check: a lone one-character string is a static string with its UTF-8 form already cached, and it gives 61 rather than 58.

How the width is established in the measurement

The script does not rely on reading a struct field alone: a field offset is an assumption, and a wrong number looks exactly like a right one. So the width is computed twice and both answers are printed side by side.

The first way is measurement, requiring no knowledge of internals:

per_char = sys.getsizeof(ch * 11) - sys.getsizeof(ch * 10)

The second reads the kind field in the object header through ctypes. The run prints both and states on a separate line whether they agree. On 3.12.3, 3.13.7 and 3.14.7 they did.

What it costs

A million short strings is an ordinary scale for a log, a cache or a parsed file. This is what the choice of width means there — a million sixteen-character strings, the strings themselves only, with no container around them. The same run of bench/strings/layout.py prints it:

The first row and the last are the same information written in four different widths, and between them is more than double. And it is settled not by optimisation but by what characters the data contains: a string with a single emoji at the end costs what a string of nothing but emoji costs.

Part II. Interning

Four states, not two

"Interned or not" is the simplification that keeps the observations from adding up. There are four states, listed in InternalDocs/string_interning.md — the only InternalDocs file present in both 3.13 and 3.14:

The state can be checked two ways: through the private sys._is_interned (which appeared in 3.13) and by reading the two low bits of the state field in the object header. The run prints both.

Three of the four states go by the single word "interned", and that loses the main point: interning and immortality are different things. The documentation of sys.intern warns about it outright:

So state 1 is "interned and mortal": the string is in the table but will go away with the last reference to it. State 2 is "interned and immortal". State 3 is "static" — created when the interpreter starts and owned by no code. From 3.14 onwards a separate function, sys._is_immortal, tells the first two apart; before it, the only way was the field.

What gets interned on its own

Measured on 3.13.7 by bench/strings/interning.py. On 3.12.3 three of these rows show a different state; the reason comes a few sections down:

What is visible here is not a rule of the language but the behaviour of this build: a literal that looks like a name gets interned. A space or an exclamation mark, and the string stays ordinary. The empty string does exist in one copy, created when the interpreter starts.

But "any single character exists in one copy" is wrong, and the boundary is not where it is expected. Static single-character strings exist only for one-byte characters. The run builds the characters at run time so that a literal and constant folding cannot answer for it. The table was taken on 3.13.7; on 3.12.3 both is columns are the same while the state field reads zero for all seven characters — the "static" state for single-character strings appeared in 3.13. Block 6 of bench/strings/interning.py:

The last column is empty for a reason: sys._is_immortal only appeared in 3.14, and the run was taken on 3.13.7.

The boundary falls exactly between U+00FF and U+0100. A Greek α built twice is two different objects, and is on it gives False. So "a single character" is about Latin-1, not about Unicode.

And the important one: a string assembled at run time was not interned in any of the cases checked. Hence the difference code breaks on:

literal = "some_attribute_name"
built = "".join(["some_attribute", "_name"])
 
literal == built      # True
literal is built      # False

Where is breaks silently

The danger is not that is gives a wrong answer. The danger is that it gives the RIGHT answer for as long as the strings come from the source, and stops the moment they come from anywhere else. Block 4 of the same run of bench/strings/interning.py:

They compare equal and are not identical. Code that compares strings with is will pass every test written on literals and break on the first string that arrives from a file, from the network or from a database. The failure does not look like a failure: is simply answers False — "not the same object" — and a branch quietly goes the wrong way, while == would have said True.

The language promises nothing here. All it says is that is compares identity:

Not a word about equal literals yielding one object. Everything observed about that is implementation behaviour, and it has changed.

The same literal, different states

Here is direct evidence that the boundaries of "interned" get moved between versions. The literal "some_attribute_name", the very same one:

Nothing follows from this for code: the string is interned either way, and is answers the same for two such literals. What does follow is that "interned" is not one state but a family, and its internals are not something to build a comparison on.

Part III. Concatenation

Two conditions, not one

"Strings are immutable, so concatenation in a loop is quadratic" is correct reasoning with a wrong conclusion: an ordinary loop with s += x runs linearly. The reason is the BINARY_OP_INPLACE_ADD_UNICODE specialisation, and it has two conditions.

The boundaries of this section first. Everything described here is a CPython optimisation, not a property of strings: immutability has not gone anywhere, and mutating a string in place is permitted precisely because nobody else is looking at it. No version promises this behaviour, and its conditions are narrow: a specific shape of code, a specific reference count, and a specific specialisation name that changes between releases. The numbers below were taken on 3.13.7 and the opcodes read on the same build.

The first is the shape of the code. The specialisation is chosen by what stands as the NEXT instruction, and Python/bytecodes.c says so directly:

tier1 op(_BINARY_OP_INPLACE_ADD_UNICODE, (left, right --)) {
    assert(next_instr->op.code == STORE_FAST);
    PyObject **target_local = &GETLOCAL(next_instr->op.arg);
    DEOPT_IF(*target_local != left);

So the accumulator must be a local variable of a function, and the result must be assigned straight back into it. An accumulator in a list element or in an attribute does not qualify, and ordinary addition is what stays.

The second condition is checked at run time, and its purpose is named in the same file:

One line of code that does nothing

The second condition is what the second position of the switch above shows. Two functions:

def local_var():
    s = ""
    for _ in range(N):
        s += X
    return s
 
 
def extra_reference():
    s = ""
    for _ in range(N):
        keep = s
        s += X
    return s

The difference is the line keep = s, which computes nothing and is passed nowhere. The run of bench/strings/concat.py prints the opcode of all four functions after warm-up, and for these two it is THE SAME:

The time is not the same at all. In the same run the first function makes twenty thousand steps in 0.8 milliseconds and the second in 140.7.

Does the price of one step depend on what is already accumulated

On this machine quadratic behaviour cannot be checked by the ratio of times: the ratio between neighbouring sizes swings from 4.4 to 9.7, and at lengths of hundreds of kilobytes it most likely also contains a change in allocation strategy, which the measurement does not separate. Something else, though, can be checked cleanly — the price of ONE step, from the same run of bench/strings/concat.py:

The left "ns per step" column does not move: the length of the accumulator has no effect at all on the price of a step. The right one grows with N — every step copies everything already accumulated. That is the difference between "the string grew where it was" and "the string was copied whole", shown rather than named.

What to do about it

The comment in the source names what the optimisation is for: This attempts to avoid quadratic behavior when one neglects to use str.join(). That is, the fast path is a safety net for code written the second-best way, not a licence to always write it that way.

Numbers from the same run:

In THIS measurement join wins little, and the win is not the point: 0.6 ms against 0.8 is the same order. On other data the ratio comes out differently: pieces of another length, another number of them, another alphabet, and the gap can move either way — so neither "join is faster" nor "join is slower" follows from here.

What does follow is that join is more DEPENDABLE. Its time does not depend on where the accumulator lives, nor on whether somebody kept a reference to the string, nor on whether this code gets moved into a method tomorrow. In-place concatenation depends on all of that, and breaks silently.

Part IV. Practice

import sys

left = "ab"
right = "cd"

one = "abcd"
two = left + right
three = "ab" + "cd"

print(one == two, one is two)
print(one == three, one is three)
print(sys.getsizeof("ab"), sys.getsizeof("αβ"))

True False
True True
43 62

True True
True True
43 62

True False
True False
43 43

True False
True True
43 44

Version history

How this was measured

The numbers in this article come from these scripts. Each opens from here, together with the record of its run.

Bytes and states — comparable across versions, recorded on all three:

• bench/strings/layout.py
• bench/strings/interning.py

Time — one record, one build:

• bench/strings/concat.py

The basis for the exercises in "Practice":

• bench/strings/practice.py

Python 3.12.3 (GCC 13.3.0), 3.13.7 (Clang 20.1.4), 3.14.7 (Clang 22.1.3); Intel Xeon 2.80 GHz, 2 vCPU. Bytes are comparable across versions — that is object layout. Time is not: the builds have different compilers and different flags.

Fragments of Python/bytecodes.c are quoted verbatim at tag v3.13.7.