CPython String Interning, Compact Dicts & Hash Table Mechanics

BACKEND SERIES

Day 43: CPython String Interning, Compact Dicts & Hash Table Mechanics

15 min read

Series: Logic & Legacy

Day 43 / 50

Level: Senior / CPython Internals

⏳ Context: Python dictionaries and strings are the lifeblood of the language. Every module namespace, class attribute lookup, function call keyword argument, and JSON payload is powered by dictionaries and strings. Because dictionary lookups occur millions of times per second inside the CPython evaluation loop, the core developers engineered profound C-level optimizations: **String Interning** for $O(1)$ identity checks, and the **Compact Dict layout** (PEP 468) that reduced dictionary memory usage by up to 40% while preserving insertion order. Today, we dissect how CPython represents strings and hash tables under the hood.

1. String Interning: Transforming O(N) Equality into O(1) Identity

Comparing two long strings byte-by-byte with == takes $O(N)$ linear time in the length of the string. But Python's internal interpreter must verify attribute names (like obj.my_variable_name) inside dictionaries on every single opcode execution. To make this instantaneous, CPython maintains an internal string interning hash table (interned_dict). All identifier strings and valid Python variable names are **interned** at compile time so they point to the exact same PyASCIIObject memory address.

The Compiler Optimization

When strings are interned, dictionary key lookup bypasses byte-by-byte string comparison entirely. CPython simply compares the 64-bit memory pointer: if (key1 == key2). What would have been a 50-byte character scan becomes a single assembly CMP instruction.

The Mental Model: The VIP Wristband

Imagine a security guard verifying IDs. If they read every full legal name letter-by-letter (standard string comparison), lines move slowly. Interning assigns everyone the exact same unique colored wristband. The guard doesn't read the name; they instantly verify the wristband color ($O(1)$ pointer comparison).

String Interning Inspection & Manual Optimization with sys.intern

import sys

# Valid Python identifiers are interned automatically by CPython compiler
s1 = "user_id"
s2 = "user_id"
print(s1 is s2) # True! Same PyObject memory address

# Dynamically constructed strings with spaces/symbols are NOT interned by default
s3 = "hello " + "world!"
s4 = "hello " + "world!"
print(s3 is s4) # False (Different heap allocations)

# Manual Interning for High-Performance Key Dictionaries
s3_interned = sys.intern(s3)
s4_interned = sys.intern(s4)
print(s3_interned is s4_interned) # True! Pointer identity restored

2. The Compact Dict Revolution (PEP 468 & Raymond Hettinger)

Prior to Python 3.6, a dictionary was a single large sparse table where each slot held three 8-byte pointers: [hash, key_ptr, value_ptr]. To maintain low collision rates, the table was kept at least 33% empty. This meant empty slots wasted 24 bytes of memory each!

The **Compact Dict** design separated dictionary storage into two distinct data structures:

• 1. Sparse Indices Array (1 to 2 bytes per slot): A compact integer array (int8_t or int16_t) indexed by hash modulo, storing the index pointing into the dense entries table.
• 2. Dense Entries Array (`PyDictKeyEntry`): A tightly packed array where items are appended in chronological insertion order: [me_hash, me_key, me_value] with ZERO unused slots!

Legacy vs. Compact Dict Memory Architecture

# Old Sparse Dict Layout (Pre-Python 3.6):
# entries = [
#   [-34829384, "apple", 10],
#   [NULL, NULL, NULL],        <-- 24 bytes of wasted memory!
#   [829384729, "banana", 20],
#   [NULL, NULL, NULL]         <-- 24 bytes of wasted memory!
# ]

# Modern Compact Dict Layout (Python 3.7+):
# indices = [0, -1, 1, -1]    <-- Tiny 1-byte integer array!
# entries = [
#   [-34829384, "apple", 10],  <-- Dense, contiguous memory
#   [829384729, "banana", 20]  <-- Preserves exact insertion order!
# ]

3. Open Addressing & Perturbation Probing

When two dictionary keys produce hash collisions, CPython does not use linked lists (chaining). Instead, it uses **Open Addressing** with a dynamic pseudo-random probe sequence based on perturbing the upper bits of the 64-bit hash: perturb >>= 5; j = (5*j + 1 + perturb) & mask. This ensures all bits of the hash function contribute to collision resolution.

The Shareable Quote: "Python dictionaries are not magic; they are masterclasses in data structure mechanical sympathy."

🛠️ Day 43 Project: Dict Memory & Interning Profiler

Write a Python benchmark comparing memory consumption and lookup latency across millions of dictionary entries with and without string interning.

• Generate a dictionary with 500,000 randomized string keys and record its exact size using sys.getsizeof().
• Apply sys.intern() across key sets and measure memory delta.
• Benchmark dictionary key lookup times ($10^6$ lookups) comparing raw uninterned strings vs. interned pointer checks.

🔥 PRO UPGRADE / TEASER

Tomorrow, we dive into CPython bytecode compilation and execution mechanics: Day 44: CPython Bytecode Internals — dis Module, Opcode Evaluation Loop, and Python 3.11+ Specialized Adaptive Interpreter (PEP 659).

Architectural Consulting

If you are building high-concurrency Python backends or microservices and need senior architectural guidance, I am available for direct contracting.

Explore Enterprise Engagements →

← Previous

Day 42: Cyclic Garbage Collection & Generational GC

Next →

Day 44: Bytecode & Specialized Adaptive Interpreter