Split-Table vs Combined-Table Dictionaries in CPython

CPython utilizes two distinct internal storage strategies for dictionaries: combined-table dictionaries and split-table dictionaries. Introduced in PEP 412 (Key-Sharing Dictionary), this distinction optimizes memory consumption across object-oriented programs. While combined-table dictionaries store keys, hash values, and values together for general-purpose use, split-table dictionaries separate the shared keys from instance-specific values, drastically reducing the memory footprint of multiple instances of the same class.

The Underlying Dict Architecture in CPython

In modern CPython (3.6+), a standard dictionary consists of two primary internal arrays:

1. Hash Indices Table: A sparse array mapping hash values to entries.
2. Entries Table: A dense array of PyDictKeyEntry structs containing the hash, the key pointer, and the value pointer.

The C-level representation is governed by the PyDictObject structure, which contains pointers to a keys object (PyDictKeysObject *ma_keys) and an optional values array (PyObject **ma_values).

Combined-Table Dictionaries

A combined-table dictionary is the default layout for standard dictionaries, such as those created using dictionary literals ({}) or dict().

• Memory Layout: The keys and values reside in the same memory block. The ma_keys field points to a PyDictKeysObject containing both the keys and their corresponding values in its entries array. The ma_values pointer in PyDictObject is set to NULL.
• Coupling: Every combined dictionary owns its own distinct set of keys, hash values, and mapped values.
• Use Cases: Explicit dictionary instantiations, module namespaces, and dynamic mappings where keys vary significantly between instances.

Split-Table Dictionaries (Key-Sharing Dictionaries)

Split-table dictionaries are designed primarily for object attribute dictionaries (instance.__dict__). In typical object-oriented code, hundreds or thousands of instances of a class share the exact same attribute names in the exact same initialization order, differing only in the values assigned to those attributes.

• Memory Layout: The keys table (PyDictKeysObject) is separated from the values. The keys table is stored once—typically referenced by the class's type object—and holds the attribute names, hash values, and entry indices. The individual instance's PyDictObject contains a pointer to this shared ma_keys struct, while its ma_values pointer points to a separate, compact array containing only the values corresponding to those keys.
• Decoupling: Multiple PyDictObject instances share a single read-only PyDictKeysObject. Each instance maintains only an array of PyObject* pointers corresponding to the indices defined in the shared keys table.
• Use Cases: Instance attribute storage created during __init__ when attributes are assigned in a uniform sequence.

Key Architectural Differences

Mutability and Table Conversion

A split-table dictionary requires that all participating instances preserve an identical key ordering. CPython manages this dynamically:

1. Creation: When an instance is initialized, its __dict__ is allocated as a split-table dictionary sharing keys with the type.
2. Mutation: As attributes are assigned in __init__, the shared PyDictKeysObject registers the keys.
3. De-optimization (Combined Conversion): If an individual instance adds an attribute that was not registered in the shared keys table, or if an attribute is deleted (del inst.attr), the instance can no longer share the key layout. CPython automatically converts that specific instance's dictionary into a combined-table dictionary, allocating a private PyDictKeysObject and merging the values back into it. Once converted to a combined table, an instance dictionary cannot revert to a split table.