CPython Internals: String Interning and Dictionary Optimization

When comparing two strings in Python using the == operator, a naive implementation would rely on strcmp-style behavior—traversing both strings character by character until finding a mismatch or reaching the end ($O(N)$ time complexity).

However, Python executes string comparisons in high-throughput environments (such as dictionary key lookups) orders of magnitude faster. It accomplishes this through String Interning—an optimization technique where Python guarantees that identical immutable string values share the exact same memory address. This transforms costly character-by-character scans into a single, near-instantaneous pointer equality comparison ($O(1)$).

This deep-dive walks through the CPython source code (tracing version 3.10) to uncover how string interning works under the hood, how the global intern table is structured, and why some strings are interned automatically while others are not.

---

1. What is String Interning?

String interning is an object caching mechanism. Instead of allocating distinct memory buffers for every string instance with identical character sequences, the runtime reuses existing string references.

In CPython, the built-in id(obj) function returns the memory address where the underlying PyObject resides in memory.

a = "the_honest_python"
b = "the_honest_python"

print(id(a))  # e.g., 43432449712
print(id(b))  # 43432449712
print(a is b) # True

Even though a and b were initialized separately, both point to the exact same memory location. When evaluating a == b, Python first checks if their memory pointers are identical (a is b). If they match, the equality test returns True immediately without ever inspecting the individual characters.

Why Interning Matters for Python Dictionaries

In Python, dictionaries are everywhere: module namespaces, class attribute lookups, instance state (__dict__), and local/global execution scopes. The vast majority of dictionary keys are strings representing variable and function names.

If Python had to hash and compare character arrays sequentially during every attribute access (obj.attribute) or function resolution, overhead would degrade application performance. By ensuring identifier strings are interned, dictionary key resolution drops to pointer comparison after an initial hash match.

---

2. Exploring sys.intern in the CPython Codebase

Python provides explicit access to this subsystem via the sys module:

import sys
help(sys.intern)
# intern(string) -> string
# "Enter string in the table of interned strings and return the string object..."

The implementation lives in Python/sysmodule.c under sys_intern_impl:

static PyObject *
sys_intern_impl(PyObject *module, PyObject *s)
{
    if (!PyUnicode_CheckExact(s)) {
        PyErr_Format(PyExc_TypeError,
                     "can't intern %.400s", Py_TYPE(s)->tp_name);
        return NULL;
    }
    Py_INCREF(s);
    PyUnicode_InternInPlace(&s);
    return s;
}

Key observations from sys_intern_impl:

1. Strict Unicode Type Check: Python only interns exact unicode instances (PyUnicode_CheckExact). Subclasses are rejected to prevent mutated behavior.
2. Reference Increment: It increments the reference count before modifying the pointer.
3. Pointer-to-Pointer Signature: It calls PyUnicode_InternInPlace(&s), passing the address of the pointer s (PyObject **).

Passing a pointer-to-a-pointer is critical: if an identical string has already been interned earlier, the function must overwrite the caller’s pointer so that it points to the already existing canonical string instance in memory.

---

3. Deep Dive: PyUnicode_InternInPlace

The core interning logic resides in Objects/unicodeobject.c. Below is the architectural flow of PyUnicode_InternInPlace(PyObject **p):

flowchart TD
    A[Receive PyObject **p] --> B[Deref to PyObject *s]
    B --> C{Is s already interned?}
    C -- Yes --> D[Return immediately]
    C -- No --> E[Fetch interpreter unicode state: state->interned]
    E --> F{interned dict initialized?}
    F -- No --> G[Allocate new PyDict for interned]
    F -- Yes --> H[Execute PyDict_SetDefault(interned, s, s)]
    G --> H
    H --> I{Returned object t == s?}
    I -- No (Already Existed) --> J[Increment refcount of t]
    J --> K[Py_SETREF(*p, t) overwrite caller pointer]
    I -- Yes (Newly Added) --> L[Mark s as interned: state.interned = SSTATE_INTERNED_...]

The Global Intern Dictionary

CPython stores interned strings inside the global interpreter state (PyInterpreterState).

struct _Py_unicode_state *state = get_unicode_state();
if (state->interned == NULL) {
    state->interned = PyDict_New();
    if (state->interned == NULL) {
        PyErr_Clear();
        return;
    }
}

The intern table is a standard Python dictionary (PyDict), where both the key and the value are pointers to the exact same string object (s : s). Because Python dictionaries store pointers rather than full string payloads, mapping s -> s uses minimal memory while providing $O(1)$ amortized lookups.

The PyDict_SetDefault Technique

CPython coordinates lookup and registration in a single operation using PyDict_SetDefault:

PyObject *t = PyDict_SetDefault(state->interned, s, s);

PyDict_SetDefault behaves as follows:

• If key s is not present in the dictionary, it inserts the mapping s: s and returns s.
• If key s already exists, it leaves the dictionary untouched and returns the value already associated with s (let’s call it t).

This leads to two execution branches:

Case 1: The String Was Already Interned (t != s)

If t != s, an identical string literal was previously registered:

if (t != s) {
    Py_INCREF(t);
    Py_SETREF(*p, t);
    return;
}

1. It increments the reference count of the existing canonical instance t.
2. It calls Py_SETREF(*p, t), updating the caller’s pointer (*p) to reference t instead of s.
3. The redundant duplicate string s drops in reference count and can be garbage collected.

Case 2: First Encounter of the String (t == s)

If t == s, this is the first time Python has encountered this string sequence:

_PyUnicode_STATE(s).interned = SSTATE_INTERNED_MORTAL;

The string has already been placed in state->interned by PyDict_SetDefault. CPython marks the internal metadata of s as interned and exits.

---

4. Metadata Storage: The 2-Bit Intern State

How does CPython keep track of whether a string is interned without consuming excessive memory per object?

Inside the CPython string structure (PyASCIIObject in Include/cpython/unicodeobject.h), string metadata is packed using bitfields:

typedef struct {
    PyObject_HEAD
    Py_ssize_t length;
    Py_hash_t hash;
    struct {
        unsigned int compact:1;
        unsigned int is_ascii:1;
        unsigned int ready:1;
        unsigned int interned:2;
        /* ... other flags ... */
    } state;
} PyASCIIObject;

The state.interned field takes up only 2 bits of space and tracks three distinct states:

Value	Constant	Meaning
0	SSTATE_NOT_INTERNED	Regular string; eligible for standard garbage collection.
1	SSTATE_INTERNED_MORTAL	Interned string that can be deallocated when references reach zero.
2	SSTATE_INTERNED_IMMORTAL	Interned permanently; immune to standard GC (lives for interpreter duration).

When checking whether a string has been interned, CPython inspects this bitfield directly:

static inline int
PyUnicode_CHECK_INTERNED(PyObject *op) {
    return (((PyASCIIObject *)(op))->state.interned);
}

---

5. Automatic vs. Manual Interning

CPython does not automatically intern every string created at runtime. Doing so would bloat the global dictionary with transient, unique strings (such as long file contents, network payloads, or user input), causing memory leaks.

Consider this experiment in the interactive shell:

# Case A: String with only alphanumeric characters and underscores
a = "the_honest_python"
b = "the_honest_python"
print(a is b)  # True (Automatically interned)

# Case B: String containing whitespace
x = "the honest python"
y = "the honest python"
print(x is y)  # False (NOT automatically interned)

The Identifier Heuristic: all_name_chars

During code compilation (Python/compile.c and Objects/codeobject.c), CPython scans string constants and applies a heuristic before deciding to invoke PyUnicode_InternInPlace.

In Objects/codeobject.c, CPython filters candidates via the all_name_chars function:

static int
all_name_chars(PyObject *o)
{
    if (!PyUnicode_IS_ASCII(o)) {
        return 0;
    }
    
    Py_ssize_t len = PyUnicode_GET_LENGTH(o);
    const void *data = PyUnicode_DATA(o);
    
    for (Py_ssize_t i = 0; i < len; i++) {
        Py_UCS4 ch = PyUnicode_READ_CHAR(o, i);
        if (!Py_ISALNUM(ch) && ch != '_') {
            return 0;
        }
    }
    return 1;
}

Rules for Automatic Interning

1. Python Identifiers: Strings that resemble valid Python identifiers—composed exclusively of ASCII alphanumeric characters ([a-zA-Z0-9]) and underscores (_)—are automatically interned at compile time. These strings are likely to be used as attribute names, module functions, or dictionary keys.
2. Arbitrary Strings: Strings containing spaces, punctuation marks, emojis, or non-ASCII characters fail the all_name_chars validation and are not interned during compilation.
3. Manual Override: Developers can force any arbitrary string (regardless of characters) to be interned using sys.intern(my_string).

---

6. Summary and Practical Takeaways

• Algorithmic Benefit: String interning converts $O(N)$ character comparison operations into $O(1)$ memory address comparisons via pointer matching.
• Implementation Architecture: CPython maintains a dictionary in the interpreter state (state->interned) mapping strings to themselves (s : s).
• In-Place Mutation: PyUnicode_InternInPlace takes a pointer-to-pointer (PyObject **p) to directly overwrite the caller’s reference with the canonical interned string pointer.
• Selective Caching: CPython limits automatic interning to identifier-like ASCII strings (isalnum + _) to balance dictionary lookup speeds against unbounded memory growth.