Opensource internals

CPython Interns Strings

6 min read Jay Hubbert

Two equal strings, one object. CPython interns identifiers, latin-1 characters, and constants — and the bookkeeping that keeps refcounts honest.

TL;DR: String interning lets CPython compare equal strings by pointer instead of by content. Identifiers, single-byte characters, and constants all live in one of two tables, and the trick is in how the refcounts are fudged to keep them alive.

String interning is the trick that makes a = "foo"; b = "foo"; a is b sometimes true: two equal strings are represented by one object, so equality becomes pointer comparison and hashing is free. CPython does not intern everything – that would be expensive and pointless – but it interns aggressively where it pays off: identifiers, single-byte characters, attribute names, and constants. This article traces the two mechanisms behind it.

Two mechanisms

CPython has two kinds of interned strings:

  1. Singletons: runtime-global, lock-free, shared across interpreters.
    • 256 one-byte latin-1 strings.
    • _Py_ID(...) for identifier fragments.
    • _Py_STR(...) for other static strings.
  2. Dynamic interning: per-interpreter dict, for strings created at runtime.

The state of a string is recorded in two bits:

c 
// Include/cpython/unicodeobject.h
#define SSTATE_NOT_INTERNED 0
#define SSTATE_INTERNED_MORTAL 1
#define SSTATE_INTERNED_IMMORTAL 2
#define SSTATE_INTERNED_IMMORTAL_STATIC 3

stored in _PyASCIIObject_CAST(op)->state.interned.

Two bits, four states. NOT_INTERNED is the default; the other three say which table you’re in and whether the table owns your life.

Singletons: the global table

Singletons live in a global hashtable shared by all interpreters and threads without synchronization:

c 
// Objects/unicodeobject.c
#define INTERNED_STRINGS _PyRuntime.cached_objects.interned_strings

static PyStatus init_global_interned_strings(PyInterpreterState *interp) {
    INTERNED_STRINGS = _Py_hashtable_new_full(...);
    _PyUnicode_InitStaticStrings(interp);   // _Py_ID / _Py_STR
    for (int i = 0; i < 256; i++) {
        PyObject *s = LATIN1(i);
        _PyUnicode_InternStatic(interp, &s);
        assert(s == LATIN1(i));
    }
    ...
}

The macros that reach them are defined in Include/internal/pycore_global_strings.h:

c 
#define _Py_ID(NAME) \
     (_Py_SINGLETON(strings.identifiers._py_ ## NAME._ascii.ob_base))
#define _Py_STR(NAME) \
     (_Py_SINGLETON(strings.literals._py_ ## NAME._ascii.ob_base))
#define _Py_LATIN1_CHR(CH) \
    ((CH) < 128 \
     ? (PyObject*)&_Py_SINGLETON(strings).ascii[(CH)] \
     : (PyObject*)&_Py_SINGLETON(strings).latin1[(CH) - 128])

Static interning inserts into the global table and marks the string SSTATE_INTERNED_IMMORTAL_STATIC:

c 
// Objects/unicodeobject.c
static PyObject* intern_static(PyInterpreterState *interp, PyObject *s /* stolen */) {
    assert(_PyUnicode_STATE(s).statically_allocated);
    assert(!PyUnicode_CHECK_INTERNED(s));
    PyObject *r = (PyObject *)_Py_hashtable_get(INTERNED_STRINGS, s);
    assert(r == NULL);
    if (r != NULL && r != s) { ... return Py_NewRef(r); }
    if (_Py_hashtable_set(INTERNED_STRINGS, s, s) < 0) { ... }
    _PyUnicode_STATE(s).interned = SSTATE_INTERNED_IMMORTAL_STATIC;
    return s;
}

Dynamic interning: the per-interpreter dict

For strings created at runtime, each interpreter has its own dict:

c 
// Objects/unicodeobject.c
static inline PyObject *get_interned_dict(PyInterpreterState *interp) {
    return _Py_INTERP_CACHED_OBJECT(interp, interned_strings);
}

static int init_interned_dict(PyInterpreterState *interp) {
    interned = PyDict_New();   // or shared main-interpreter dict
    _Py_INTERP_CACHED_OBJECT(interp, interned_strings) = interned;
    return 0;
}

The core routine is intern_common(interp, s, immortalize):

c 
// Objects/unicodeobject.c (intern_common)
// steals a reference to s, returns a (possibly different) interned object.

Its steps, in order:

  1. Reject subclasses.
  2. If already interned, possibly immortalize it and return.
  3. Single-byte latin-1 strings are redirected to the _Py_LATIN1_CHR singleton.
  4. Check the global static cache for a static copy.
  5. Otherwise PyDict_SetDefaultRef on the per-interpreter dict. On first insert:
c 
// Objects/unicodeobject.c
if (!_Py_IsImmortal(s)) {
    /* The two references in interned dict (key and value) are not counted. */
    Py_DECREF(s);
    Py_DECREF(s);
}
FT_ATOMIC_STORE_UINT8(_PyUnicode_STATE(s).interned, SSTATE_INTERNED_MORTAL);
if (immortalize) { immortalize_interned(s); }

On a hit, the existing interned string is returned and s is discarded.

The two references in the dict (key and value) are deliberately not counted in ob_refcnt. That is the subtle part: an interned string’s reference count does not include the dict that keeps it alive, so the count reflects only external users. When the last external reference goes away, the count can reach zero even though the dict still holds the string; unicode_dealloc and _PyUnicode_ClearInterned restore the missing counts before freeing.

This is the part people get wrong. Those two Py_DECREF calls look like a bug. They aren’t: the dict holds two uncounted references to s, so the count has to be adjusted to match reality. Without this, every interned string would be freed the moment its last user dropped it.

Mortal vs immortal

c 
// Objects/unicodeobject.c
static void immortalize_interned(PyObject *s) {
    assert(PyUnicode_CHECK_INTERNED(s) == SSTATE_INTERNED_MORTAL);
    assert(!_Py_IsImmortal(s));
    ...
    _Py_SetImmortal(s);
    FT_ATOMIC_STORE_UINT8(_PyUnicode_STATE(s).interned, SSTATE_INTERNED_IMMORTAL);
}

The public entry points differ in whether they immortalize:

c 
// Objects/unicodeobject.c
void _PyUnicode_InternImmortal(PyInterpreterState *interp, PyObject **p);
void _PyUnicode_InternMortal(PyInterpreterState *interp, PyObject **p);
void _PyUnicode_InternStatic(PyInterpreterState *interp, PyObject **p);
void _PyUnicode_InternInPlace(PyInterpreterState *interp, PyObject **p);  // -> Immortal
void PyUnicode_InternInPlace(PyObject **p);                             // public -> Mortal

In the free-threaded build all interned strings become immortal, and a copy may be made if the original cannot be safely immortalized.

Shutdown bookkeeping

At interpreter shutdown, mortal interned strings are released by restoring the two dict references and removing the entry. Immortal interned strings are made mortal again with _Py_SetMortal(s, 2) so they can be collected; static strings stay in the global table until the main interpreter tears it down.

Where CPython uses it

Interning is not a user-facing feature; it is a compiler/runtime optimization. The places that call it are the ones where string identity matters:

  • Code objects (Objects/codeobject.c): identifier-like ASCII strings are interned via should_intern_string, and all names and constants are interned/immortalized in intern_strings / intern_constants.
  • Marshal (Python/marshal.c): TYPE_INTERNED strings are interned and immortalized on load.
  • The compiler and optimizer, plus many runtime sites (object, type, module, dict, pickle, …), call _PyUnicode_InternMortal / _PyUnicode_InternImmortal.

The payoff is that attribute lookup, global lookup, and constant loading can compare strings by pointer instead of by content, and interned constants never need to be hashed more than once.

The real win: obj.attr in a hot loop stops being a string comparison and becomes a pointer comparison. That’s the difference between a memcmp and a single load.

Inspecting it

c 
// Objects/unicodeobject.c
Py_ssize_t _PyUnicode_InternedSize(void) {
    PyObject *dict = get_interned_dict(_PyInterpreterState_GET());
    return _Py_hashtable_len(INTERNED_STRINGS) + PyDict_GET_SIZE(dict);
}

And PyUnicode_CHECK_INTERNED(obj) exposes the four states to C code. The distinction between mortal and immortal matters for reference counting and for whether a string can be shared across threads in the free-threaded build, which is why the API splits into InternMortal and InternImmortal rather than one call.

Wrapping up

Two tables, two lifetimes. The global table holds immortal static strings — the 256 latin-1 singletons, every _Py_ID identifier, every _Py_STR literal — and never needs a lock. The per-interpreter dict holds runtime interned strings, which are mortal by default and immortalized on request.

The one thing to remember: interning is an identity optimization, not a memory optimization in the usual sense. Two equal strings become one object, so you get pointer-equality and a cached hash. And the refcount fudge — two uncounted dict references — is the subtle part that keeps the whole scheme consistent.

PythonCpythonInternalsPerformanceStrings