Python Compact Dictionaries and Lookup Optimization

Python optimizes dictionary performance and memory usage through a compact dictionary layout first introduced in CPython 3.6 and standardized in Python 3.7. By decoupling the sparse hash table structure from the actual key-value storage, Python reduces memory consumption by 20% to 25%, improves CPU cache locality, maintains insertion ordering, and retains average \(O(1)\) time complexity for key lookups.

The Traditional Dictionary Layout

Prior to Python 3.6, dictionaries were implemented as a single sparse hash table. The table consisted of an array of 24-byte entries, where each entry stored:

• me_hash (the cached hash of the key)
• me_key (a pointer to the key object)
• me_value (a pointer to the value object)

To minimize hash collisions, the table remained roughly one-third empty at all times. This design wasted substantial memory because empty slots still reserved the full 24 bytes of memory, leading to sparse memory footprints and poor CPU cache utilization during lookups.

The Compact Dictionary Structure

The modern compact dictionary splits the single sparse table into two separate arrays:

1. indices Array: A sparse array that acts as the primary hash table, containing only integer offsets (indices). Depending on the total dictionary size, these integers are stored using the smallest possible C data type: int8_t (for tables up to 128 items), int16_t, int32_t, or int64_t.
2. entries Array: A dense array that stores the actual hash, key, and value tuples. Entries are appended sequentially in the exact order they are inserted.

Empty slots are confined exclusively to the indices array, where each unused slot consumes only 1 to 4 bytes rather than the full 24 bytes of a traditional entry.

How Lookup Optimization Works

When looking up a key, Python executes the following steps:

1. Compute Hash: Python computes hash(key).
2. Locate Index: Python applies a bitmask to the hash (hash & mask) to calculate a slot position inside the small indices array.
3. Resolve Collisions: If the value at indices[slot] is empty (represented by -1 or DKIX_EMPTY), the key does not exist. If occupied, Python retrieves the integer index i = indices[slot].
4. Fetch Entry: Python directly accesses entries[i] to verify whether the stored hash and key match the requested key. If a collision occurs (the key at entries[i] does not match), Python follows its standard pseudo-random probing sequence within the indices array until the key is matched or an empty slot is encountered.

Performance and Cache Benefits

Lookups in compact dictionaries remain \(O(1)\) on average, with several tangible runtime advantages:

• Enhanced Cache Locality: Because the indices table is small and composed of compact integers, a larger portion of the lookup table fits directly into L1/L2 CPU caches, reducing cache misses during the probing phase.
• Faster Iteration: Iterating over keys, values, or items no longer requires skipping empty slots in a sparse array. Python simply scans the contiguous entries array from beginning to end.
• Guaranteed Insertion Order: Storing entries sequentially in the order of insertion guarantees deterministic key ordering without requiring auxiliary linked lists or secondary tracking structures.