vault

CPython String Internals

15 min read

CPython String Internals

A Python str is not a single thing: it is one of several different in-memory shapes, chosen at construction time according to the largest code point the string contains. Under PEP 393 — Flexible String Representation (PEP 393), CPython stores the characters of a string in a fixed-width array whose element size is 1, 2, or 4 bytes — exactly wide enough to hold the biggest character and not a byte wider. A pure-ASCII string spends one byte per character; a string containing one emoji is promoted wholesale to four bytes per character. This single design decision explains nearly every surprising memory number and the fact that s[i] is genuinely O(1) random access, not a UTF-8 scan. The layout is encoded in a small state bitfield and realized through a three-level C struct hierarchy: PyASCIIObject → PyCompactUnicodeObject → PyUnicodeObject.

The model here is as-of CPython 3.14.0 (Include/cpython/unicodeobject.h, Objects/unicodeobject.c). This matters: PEP 393’s original 3.3-era struct has since changed materially. The wstr and ready machinery PEP 393 describes was removed in Python 3.12 by PEP 623, and kind widened from 2 bits to 3. Read PEP 393 for the rationale; read the 3.14 header for the current shape.

Mental Model

Think of a str object as a header struct followed by a contiguous, fixed-width character array. The header records the length (in code points, not bytes), a cached hash, and a state bitfield. Two questions decide everything about the layout:

  1. How wide is each character? Determined by the maximum code point: ≤ U+00FF → 1 byte (Py_UCS1), ≤ U+FFFF → 2 bytes (Py_UCS2), otherwise 4 bytes (Py_UCS4). This is the kind.
  2. Is the character array glued onto the header (one allocation), or held by a separate pointer (two allocations)? This is the compact flag.
flowchart TD
    S["new str via PyUnicode_New(length, maxchar)"] --> Q1{maxchar?}
    Q1 -->|"&le; 0x7F"| ASCII["kind=1BYTE, ascii=1, compact=1<br/>layout: PyASCIIObject + UCS1[ ]<br/>utf8 == data (shared)"]
    Q1 -->|"0x80..0xFF"| L1["kind=1BYTE, ascii=0, compact=1<br/>layout: PyCompactUnicodeObject + UCS1[ ]"]
    Q1 -->|"0x100..0xFFFF"| L2["kind=2BYTE, compact=1<br/>layout: PyCompactUnicodeObject + UCS2[ ]"]
    Q1 -->|"&ge; 0x10000"| L4["kind=4BYTE, compact=1<br/>layout: PyCompactUnicodeObject + UCS4[ ]"]
    LEG["legacy str (PyUnicode_FromStringAndSize(NULL, n))"] --> NC["compact=0<br/>layout: PyUnicodeObject, data via data.any pointer<br/>(separate allocation)"]

Diagram: how the constructor picks a representation. The insight: there is no “the” string layout — the same Python type has four common physical forms (compact-ASCII, compact-Latin1, compact-UCS2, compact-UCS4) plus a rarer non-compact “legacy” form. Compact strings put the characters in the same heap block as the header; the leftmost branch (ASCII) is the most optimized of all because its UTF-8 encoding is identical to its stored bytes, so the utf8 cache pointer is aliased onto the data and costs nothing.

The crucial subtlety the diagram encodes: kind and ascii are independent. ASCII strings and Latin-1 strings are both PyUnicode_1BYTE_KIND — one byte per character either way. The ascii flag distinguishes them, because pure-ASCII strings get an extra optimization (the shared UTF-8 cache) and a leaner struct.

The Struct Hierarchy

CPython uses C struct embedding to build three nested layouts, each adding fields the previous one lacked. Here is the base from Include/cpython/unicodeobject.h (3.14.0), with the free-threaded #ifdef Py_GIL_DISABLED conditionals elided for readability (the differences are described after the field walk):

typedef struct {
    PyObject_HEAD
    Py_ssize_t length;          /* Number of code points in the string */
    Py_hash_t hash;             /* Hash value; -1 if not set */
    struct {
        unsigned int interned:2;
        unsigned int kind:3;
        unsigned int compact:1;
        unsigned int ascii:1;
        unsigned int statically_allocated:1;
        unsigned int :24;           /* padding (non-free-threaded build) */
    } state;
} PyASCIIObject;

Reading it field by field:

  • PyObject_HEAD — the universal object header: a reference count (ob_refcnt) and a type pointer (ob_type). Every Python object begins this way.
  • length — the number of code points, not bytes. For a UCS-4 string of three emoji, length == 3 even though the data array is 12 bytes. This is why len(s) is O(1).
  • hash — cached hash, -1 until first computed. Strings are immutable, so the hash can be memoized forever once calculated.
  • state.interned (2 bits) — interning state, four values (covered below; the table of values lives in unicodeobject.h and the interning machinery is detailed in Object Identity and Interning, not here).
  • state.kind (3 bits) — character width: 1, 2, or 4 (the literal byte count). It is 3 bits rather than the 2 bits PEP 393 originally specified, a 3.12-era change.
  • state.compact (1 bit) — whether the character buffer is glued to the header (1) or held by a separate pointer (0).
  • state.ascii (1 bit) — set iff every character is in U+0000..U+007F. Implies kind == 1.
  • state.statically_allocated (1 bit) — set for strings baked into the interpreter binary (e.g. interned identifiers from _Py_STR), which must never be freed.
  • unsigned int :24 — anonymous padding. The bitfield occupies a 32-bit word; the explicit padding is there so that the character data immediately following an ASCII object is 4-byte aligned (gh-63736 on m68k). In the free-threaded build (Py_GIL_DISABLED) the layout differs slightly — interned becomes a full unsigned char so it can be loaded atomically, and the padding is replaced by _Py_ALIGN_AS(4).

The ASCII layout has no extra fields

For a compact ASCII string the object is exactly a PyASCIIObject followed by the Py_UCS1 character array — there are no utf8/utf8_length fields at all. The header comment in the 3.14 source spells this out: “ASCII-only strings created through PyUnicode_New use the PyASCIIObject structure. state.ascii and state.compact are set, and the data immediately follow the structure. utf8_length can be found in the length field; the utf8 pointer is equal to the data pointer.”

The next level adds the UTF-8 cache, used by non-ASCII compact strings:

typedef struct {
    PyASCIIObject _base;
    Py_ssize_t utf8_length;     /* Number of bytes in utf8, excluding the terminating \0. */
    char *utf8;                 /* UTF-8 representation (null-terminated) */
} PyCompactUnicodeObject;
  • _base — an embedded PyASCIIObject. C struct embedding means a PyCompactUnicodeObject* can be cast to PyASCIIObject* and the header fields line up.
  • utf8 / utf8_length — a lazily computed, cached UTF-8 encoding of the string. Many C API consumers want UTF-8 bytes (e.g. to pass a filename to the OS); caching avoids re-encoding on every call. For ASCII strings this cache is redundant (the stored bytes already are UTF-8), which is exactly why ASCII strings skip these fields and alias utf8 onto data.

The full level adds the indirection pointer used only by non-compact (legacy) strings:

typedef struct {
    PyCompactUnicodeObject _base;
    union {
        void *any;
        Py_UCS1 *latin1;
        Py_UCS2 *ucs2;
        Py_UCS4 *ucs4;
    } data;
} PyUnicodeObject;
  • data — a union of typed pointers to a separately allocated character buffer. Compact strings never use this; their data lives right after the header. Only legacy strings — created via the C API as PyUnicode_FromStringAndSize(NULL, n) and filled in afterward — store their characters at the end of a second pointer.

So the four common physical forms are: (1) compact ASCII = PyASCIIObject + UCS1 data; (2) compact Latin-1 = PyCompactUnicodeObject + UCS1 data; (3) compact UCS-2/UCS-4 = PyCompactUnicodeObject + wider data; (4) non-compact legacy = PyUnicodeObject with data.any pointing elsewhere.

Choosing the Kind: the Constructor Walk-through

The width decision happens in PyUnicode_New(Py_ssize_t size, Py_UCS4 maxchar) (Objects/unicodeobject.c). The caller passes the string length and the maximum code point it will need to hold; the function picks the narrowest kind that fits and computes the allocation size. Here is the decision ladder, verbatim from the 3.14.0 source:

    is_ascii = 0;
    struct_size = sizeof(PyCompactUnicodeObject);
    if (maxchar < 128) {
        kind = PyUnicode_1BYTE_KIND;
        char_size = 1;
        is_ascii = 1;
        struct_size = sizeof(PyASCIIObject);
    }
    else if (maxchar < 256) {
        kind = PyUnicode_1BYTE_KIND;
        char_size = 1;
    }
    else if (maxchar < 65536) {
        kind = PyUnicode_2BYTE_KIND;
        char_size = 2;
    }
    else {
        if (maxchar > MAX_UNICODE) { /* ... raise SystemError ... */ }
        kind = PyUnicode_4BYTE_KIND;
        char_size = 4;
    }

Walking it:

  • maxchar < 128 → kind = 1BYTE, char_size = 1, is_ascii = 1, and crucially struct_size = sizeof(PyASCIIObject) — the leaner header with no UTF-8 cache fields.
  • maxchar < 256 → still kind = 1BYTE, char_size = 1, but is_ascii stays 0 and struct_size remains sizeof(PyCompactUnicodeObject) — one byte per character, yet the bigger header with the UTF-8 cache slot. This is the Latin-1 case.
  • maxchar < 65536 → kind = 2BYTE, char_size = 2.
  • otherwise → kind = 4BYTE, char_size = 4 (after rejecting maxchar > MAX_UNICODE).

The single allocation is then PyObject_Malloc(struct_size + (size + 1) * char_size) — header plus (length + 1) characters of char_size bytes each (the +1 reserves the trailing NUL terminator). So char_size is literally the per-character byte count and equals the kind value, and struct_size switches between the compact-ASCII and compact-non-ASCII headers exactly as the is_ascii flag dictates.

The kind constants themselves are an enum (verbatim from the header), and note that the values are the literal byte widths — 1, 2, 4, not 1, 2, 3:

enum PyUnicode_Kind {
    PyUnicode_1BYTE_KIND = 1,
    PyUnicode_2BYTE_KIND = 2,
    PyUnicode_4BYTE_KIND = 4
};

Because the enum value equals the bytes-per-character, code that needs the data size can multiply length * kind directly. (PEP 393’s original draft used 1/2/3 for the enum; the shipped and current implementation uses 1/2/4.)

A consequence worth internalizing: the width is fixed at creation and never narrowed. When you build a string by concatenation or formatting, CPython computes the maximum code point across all inputs first, then allocates one buffer at that width. Take a 1000-character ASCII string and append a single '😀' (U+1F600): the result is a brand-new UCS-4 string, four bytes per character — roughly 4 KB of data for 1001 characters, where the original was ~1 KB. Strings are never “demoted” back to a narrower kind after the fact; a substring operation, however, recomputes maxchar for the slice and may produce a narrower result.

Why Indexing Is O(1) and Width-Dependent

The payoff of fixed-width storage is constant-time random access. The header macros (verbatim from unicodeobject.h) make this explicit. First, fetching the kind:

#define PyUnicode_KIND(op) _Py_RVALUE(_PyASCIIObject_CAST(op)->state.kind)

This just reads the 3-bit kind field — a single masked load, no scan. Then PyUnicode_DATA returns the pointer to the first character. For a compact string it computes the address right after the header (no dereference of a stored pointer); for non-compact it returns data.any:

static inline void* _PyUnicode_COMPACT_DATA(PyObject *op) {
    if (PyUnicode_IS_ASCII(op)) {
        return _Py_STATIC_CAST(void*, (_PyASCIIObject_CAST(op) + 1));
    }
    return _Py_STATIC_CAST(void*, (_PyCompactUnicodeObject_CAST(op) + 1));
}
  • The pointer arithmetic (_PyASCIIObject_CAST(op) + 1) means “the byte just past the end of the PyASCIIObject struct” — i.e. where the character array begins for a compact ASCII string.
  • For a non-ASCII compact string the data begins past the (larger) PyCompactUnicodeObject, because that struct carries the extra utf8/utf8_length fields. This is why the ascii flag must be checked: the data offset differs between the two compact shapes.

Finally, the actual read of a single character (verbatim):

static inline Py_UCS4 PyUnicode_READ(int kind,
                                     const void *data, Py_ssize_t index)
{
    assert(index >= 0);
    if (kind == PyUnicode_1BYTE_KIND) {
        return _Py_STATIC_CAST(const Py_UCS1*, data)[index];
    }
    if (kind == PyUnicode_2BYTE_KIND) {
        return _Py_STATIC_CAST(const Py_UCS2*, data)[index];
    }
    assert(kind == PyUnicode_4BYTE_KIND);
    return _Py_STATIC_CAST(const Py_UCS4*, data)[index];
}

Each branch casts the raw data pointer to the correct fixed-width element type and indexes it directly: data[index]. Because every element is the same width, the address of character i is data + i * kind — pure pointer arithmetic, no decoding. That is the whole reason s[5_000_000] on a multi-million-character string is instantaneous. The kind is supplied by the caller, which is expected to cache it via PyUnicode_KIND outside a loop; the convenience wrapper PyUnicode_READ_CHAR fetches the kind itself and is “less efficient … because it calls PyUnicode_KIND() and might call it twice”, per the source comment. The mirror-image PyUnicode_WRITE does the same with bounds assertions (value <= 0xffU for 1-byte, <= 0x10ffffU for 4-byte) — writing is only legal during construction, never on a finished string, since str is immutable.

Contrast this with UTF-8 or UTF-16, where characters are variable-width: there, finding character i requires scanning from the start decoding each preceding character, an O(i) operation. PEP 393 explicitly chose constant-width storage to keep indexing O(1). The cost is that a single wide character “infects” the entire string’s width.

The Interning and Caching Connection

The state.interned field has four values, defined verbatim in unicodeobject.h as:

#define SSTATE_NOT_INTERNED 0
#define SSTATE_INTERNED_MORTAL 1
#define SSTATE_INTERNED_IMMORTAL 2
#define SSTATE_INTERNED_IMMORTAL_STATIC 3

These map to the header comment’s categorization: Not Interned (0), Interned (1), Interned and Immortal (2), Interned, Immortal, and Static (3). The mechanics of which strings get interned, the global interning dictionary, and how this enables is-comparison shortcuts are the subject of Object Identity and Interning — this note deliberately does not re-explain interning; it only records that the per-string flag lives in the same state bitfield as kind/ascii.

Separately, CPython keeps a single-character Latin-1 cache: the 256 one-character strings for code points 0–255 are pre-allocated immortal singletons (LATIN1(ch) / get_latin1_char in unicodeobject.c), and the empty string "" is a singleton too (unicode_get_empty). So chr(65) always returns the same object, and slicing out a single ASCII character is a cheap singleton fetch rather than an allocation. The full treatment of these caches, alongside the small-integer cache, is in Small Integer and String Caching.

Failure Modes and Common Misunderstandings

“len(s) counts bytes.” No — length is code points. len('héllo') is 5 even though the UTF-8 encoding is 6 bytes. To get the byte size of a particular encoding you must len(s.encode('utf-8')).

“A str always costs N bytes per character for the same N.” No — it depends on the widest character. sys.getsizeof('a' * 100) is far smaller than sys.getsizeof('😀' * 100). The per-character cost is 1, 2, or 4 bytes, and the base struct overhead differs too (ASCII strings have the smallest header because they omit the utf8/utf8_length fields). Concatenating a wide character onto a narrow string quadruples the data size of the entire result.

“Slicing reuses the parent’s buffer.” No — CPython strings are not slice-views the way some languages’ strings are. A slice allocates a new string and copies the relevant characters, recomputing the kind for the slice (so ('a'*100 + '😀')[:100] produces a fresh compact-ASCII string, not a UCS-4 one).

“PyUnicode_READY must be called before reading.” Obsolete advice from the PEP 393 / pre-3.12 era. Since 3.12, all strings are “ready” the moment they exist; the header defines PyUnicode_IS_READY to a soft-deprecated function that simply return 1;. Code still calling PyUnicode_READY() works but does nothing.

“wstr gives me a wchar_t* view.” Removed. PEP 623 deleted the wstr pointer and wstr_length field in 3.12. The deprecated Py_UNICODE type is now just a typedef to wchar_t, and APIs that handed back the old representation are gone.

Alternatives and Trade-offs

PEP 393 replaced two earlier all-or-nothing schemes. Before it, a CPython build was compiled either “narrow” (UCS-2, two bytes per character, but unable to represent non-BMP characters as single code points — they appeared as surrogate pairs, breaking len() and indexing for astral characters) or “wide” (UCS-4, four bytes per character always, wasting 4× memory for the overwhelmingly common ASCII text). PEP 393’s flexible representation gets the best of both: ASCII text pays one byte, astral text is correctly single-code-point-indexable, and you choose per string rather than per interpreter build.

Other languages make different trade-offs. Rust’s String and Go’s strings store UTF-8 internally: compact for non-ASCII text and zero-cost to write to a socket, but O(n) to index by code point (you index bytes, and character iteration decodes). Java and C# use UTF-16, which makes BMP indexing O(1) but mishandles astral characters as surrogate pairs (the same bug CPython’s old narrow build had). CPython’s choice optimizes for the language’s semantics — s[i] means the i-th code point, and that must be O(1) — at the cost of width amplification and a UTF-8 re-encode (cached) whenever bytes are needed.

Production Notes

The practical memory lesson: if you hold millions of short strings, keeping them ASCII (or at least sub-256 Latin-1) saves 2–4× over letting a stray wide character promote them. Per-object overhead also matters — every str carries the ~40–50 byte header before any characters, so a list of single-character strings is dominated by headers, not data (which is partly why the single-char Latin-1 cache exists). When profiling with tracemalloc or sys.getsizeof, remember the lazily materialized utf8 cache: a string that has been .encode('utf-8')’d or passed to a C API expecting UTF-8 may carry a second buffer it did not have at birth, so getsizeof can grow after such an operation for non-ASCII strings.

For C extension authors: always go through PyUnicode_KIND + PyUnicode_DATA + PyUnicode_READ rather than assuming a representation, because the same str value may be 1-, 2-, or 4-byte depending on its content. Caching kind and the data pointer outside a hot loop and using PyUnicode_READ (not PyUnicode_READ_CHAR) is the documented fast path.

See Also

Graph View

Backlinks