Python Tuples — Under the Hood¶

import dis
import ast

# Constant tuple — folded at compile time
code1 = compile("t = (1, 2, 3)", "<string>", "exec")
print("=== Constant tuple ===")
dis.dis(code1)
# LOAD_CONST               0 ((1, 2, 3))
# STORE_NAME               0 (t)

# Non-constant tuple — built at runtime
code2 = compile("x = 1; y = 2; t = (x, y)", "<string>", "exec")
print("\n=== Non-constant tuple ===")
dis.dis(code2)
# LOAD_NAME                0 (x)
# LOAD_NAME                1 (y)
# BUILD_TUPLE              2
# STORE_NAME               2 (t)

import dis

def create_dynamic_tuple(a, b, c):
    return (a, b, c)

def create_constant_tuple():
    return (1, 2, 3)

def create_mixed_tuple(x):
    return (1, x, 3)

print("=== Dynamic (all variables) ===")
dis.dis(create_dynamic_tuple)
# LOAD_FAST     0 (a)
# LOAD_FAST     1 (b)
# LOAD_FAST     2 (c)
# BUILD_TUPLE   3
# RETURN_VALUE

print("\n=== Constant (all literals) ===")
dis.dis(create_constant_tuple)
# LOAD_CONST    1 ((1, 2, 3))     <- pre-built!
# RETURN_VALUE

print("\n=== Mixed (literal + variable) ===")
dis.dis(create_mixed_tuple)
# LOAD_CONST    1 (1)
# LOAD_FAST     0 (x)
# LOAD_CONST    2 (3)
# BUILD_TUPLE   3                  <- built at runtime
# RETURN_VALUE

import dis

def unpack_basic():
    t = (1, 2, 3)
    a, b, c = t

def unpack_star():
    t = (1, 2, 3, 4, 5)
    a, *b, c = t

print("=== Basic unpacking ===")
dis.dis(unpack_basic)
# LOAD_CONST      1 ((1, 2, 3))
# STORE_FAST      0 (t)
# LOAD_FAST       0 (t)
# UNPACK_SEQUENCE 3              <- unpacks exactly 3 elements
# STORE_FAST      1 (a)
# STORE_FAST      2 (b)
# STORE_FAST      3 (c)

print("\n=== Star unpacking ===")
dis.dis(unpack_star)
# LOAD_CONST        1 ((1, 2, 3, 4, 5))
# STORE_FAST        0 (t)
# LOAD_FAST         0 (t)
# UNPACK_EX         257          <- 1 before + 1 after (encoded as 256*1 + 1)
# STORE_FAST        1 (a)
# STORE_FAST        2 (b)
# STORE_FAST        3 (c)

import dis

# CPython folds constant expressions involving tuples
def constant_folding_examples():
    # These are ALL folded at compile time:
    a = (1, 2) + (3, 4)        # -> (1, 2, 3, 4)
    b = (0,) * 5               # -> (0, 0, 0, 0, 0)
    c = (True, False, None)    # -> already a constant

dis.dis(constant_folding_examples)
# Only LOAD_CONST instructions — no runtime computation!

# Verify: check co_consts
code = compile("x = (1, 2) + (3, 4)", "<string>", "exec")
print(f"\nco_consts: {code.co_consts}")
# ((1, 2, 3, 4), ...) — already folded

import sys
import ctypes

# Verify the structure
t = (1, 2, 3)

# sys.getsizeof returns the full size including GC header
size = sys.getsizeof(t)
print(f"sys.getsizeof((1,2,3)) = {size} bytes")

# Calculate: base overhead + 8 bytes per element
base_size = sys.getsizeof(())  # empty tuple overhead
per_element = 8  # pointer size on 64-bit
calculated = base_size + 3 * per_element
print(f"Calculated: {base_size} + 3*{per_element} = {calculated} bytes")

# Show sizes for different tuple lengths
for n in range(11):
    t = tuple(range(n))
    print(f"  tuple(range({n:2d})): {sys.getsizeof(t):4d} bytes "
          f"(overhead={sys.getsizeof(t) - n*8} bytes)")

# CPython source (simplified from tupleobject.c):
#
# #define PyTuple_MAXSAVESIZE 20      // cache tuples up to length 20
# #define PyTuple_MAXFREELIST 2000    // max free list size per length
#
# static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];
# static int numfree[PyTuple_MAXSAVESIZE];

# The empty tuple is a SINGLETON — always the same object
a = ()
b = ()
c = tuple()
print(f"() is (): {a is b}")           # True
print(f"() is tuple(): {a is c}")       # True
print(f"id(()): {id(a)}")

# Small integer tuples may be cached as constants
x = (1,)
y = (1,)
print(f"(1,) is (1,): {x is y}")       # May be True (constant interning)

# But dynamically created tuples use the free list
def show_free_list_reuse():
    """Demonstrate memory reuse from the free list."""
    ids = []
    for i in range(5):
        t = (i, i+1)   # Create a 2-element tuple
        ids.append(id(t))
        del t           # Return to free list

    new_ids = []
    for i in range(5):
        t = (i*10, i*10+1)  # Create another 2-element tuple
        new_ids.append(id(t))
        del t

    reused = set(ids) & set(new_ids)
    print(f"Addresses reused from free list: {len(reused)}/{len(ids)}")

show_free_list_reuse()

# When a tuple of size N (0 <= N < 20) is deallocated:
# 1. If numfree[N] < 2000: tuple is added to free_list[N]
# 2. Otherwise: memory is freed with PyObject_GC_Del
#
# When a new tuple of size N is requested:
# 1. If free_list[N] is not empty: reuse it (just update ob_item pointers)
# 2. Otherwise: allocate new memory with PyObject_GC_NewVar
#
# This avoids malloc/free overhead for common tuple sizes.

import gc

# Force garbage collection to populate free lists
gc.collect()

# Benchmark: free list hit vs miss
import timeit

# Small tuples (likely free list hit)
small_time = timeit.timeit("(1, 2, 3)", number=10_000_000)

# Large tuples (no free list, size >= 20)
large_time = timeit.timeit(
    "tuple(range(25))",
    number=1_000_000,
)

print(f"Small tuple (3 elem, 10M): {small_time:.3f}s")
print(f"Large tuple (25 elem, 1M): {large_time:.3f}s")
# Small tuples benefit from both constant folding and free list

import sys
import ctypes


def get_refcount(obj):
    """Get the actual refcount (sys.getrefcount adds 1 for the argument)."""
    return sys.getrefcount(obj) - 1


# Creating a tuple increments refcounts of its elements
a = 42
print(f"Refcount of 42 before tuple: {get_refcount(a)}")

t = (a, a, a)  # Three references to the same object
print(f"Refcount of 42 after tuple:  {get_refcount(a)}")

del t
print(f"Refcount of 42 after del:    {get_refcount(a)}")

import gc

# Tuples CAN participate in reference cycles (if they contain mutable objects)
# CPython's cyclic GC handles this

# Example: indirect cycle via tuple -> list -> tuple
def create_cycle():
    lst = []
    t = (lst,)     # tuple references the list
    lst.append(t)  # list references the tuple -> CYCLE
    return t

gc.set_debug(gc.DEBUG_STATS)
gc.collect()

t = create_cycle()
del t

# GC will detect and clean up the cycle
collected = gc.collect()
print(f"Objects collected by GC: {collected}")

gc.set_debug(0)


# IMPORTANT: Tuples containing ONLY immutable objects are NOT tracked by GC
# CPython has an optimization: if all elements are atomic (int, str, float, bool, None),
# the tuple is untracked from GC to reduce overhead.

import gc

t_immutable = (1, 2, "hello", True)
t_mutable = (1, [2, 3])

print(f"Immutable tuple tracked by GC: {gc.is_tracked(t_immutable)}")  # False!
print(f"Mutable-element tuple tracked: {gc.is_tracked(t_mutable)}")     # True

# Tuple operations and the GIL:
#
# 1. CREATING a tuple: GIL is held throughout PyTuple_New + element assignment
#    -> Thread-safe: no other thread can see a partially-constructed tuple
#
# 2. READING a tuple element (t[i]): Single bytecode instruction (BINARY_SUBSCR)
#    -> Thread-safe: atomic under GIL
#
# 3. UNPACKING (a, b = t): UNPACK_SEQUENCE is a single bytecode operation
#    -> Thread-safe: GIL protects the entire unpack
#
# 4. SHARING a tuple reference: Assignment is a single STORE instruction
#    -> Thread-safe: reference swap is atomic under GIL

import threading
import dis

# Verify that tuple access is a single bytecode instruction
def access_tuple(t):
    return t[0]

print("Tuple access bytecode:")
dis.dis(access_tuple)
# LOAD_FAST    0 (t)
# LOAD_CONST   1 (0)
# BINARY_SUBSCR           <- single instruction, protected by GIL

# IMPORTANT: While individual tuple operations are atomic,
# COMPOUND operations (check-then-act) are NOT:

shared = (1, 2, 3)

def unsafe_pattern():
    global shared
    # NOT atomic: check and replace are separate bytecodes
    if len(shared) == 3:        # GIL may release here
        shared = shared + (4,)  # Another thread may have changed shared

# For compound operations, use a lock:
lock = threading.Lock()
def safe_pattern():
    global shared
    with lock:
        if len(shared) == 3:
            shared = shared + (4,)

# Since CPython 3.8+, tuple hashing uses a variant of xxHash/SipHash
# The algorithm combines hashes of individual elements

# Simplified view of the C implementation:
# static Py_uhash_t
# tuplehash(PyTupleObject *v)
# {
#     Py_uhash_t acc = _PyHASH_XXPRIME_5;
#     for each element:
#         lane = hash(element)
#         acc += lane * _PyHASH_XXPRIME_2
#         acc = _PyHASH_XXROTATE(acc)
#         acc *= _PyHASH_XXPRIME_1
#     acc += len ^ (_PyHASH_XXPRIME_5 ^ 3527539)
#     return acc
# }

# Demonstrate hash properties:
print(f"hash((1, 2, 3)):    {hash((1, 2, 3))}")
print(f"hash((1, 3, 2)):    {hash((1, 3, 2))}")   # Different! Order matters
print(f"hash((3, 2, 1)):    {hash((3, 2, 1))}")   # Different!
print(f"hash((1, 2, 3)) == hash((1, 2, 3)): {hash((1, 2, 3)) == hash((1, 2, 3))}")

# Hash caching: unlike strings, tuples do NOT cache their hash
# Each call to hash() recomputes it
import timeit

t = tuple(range(100))
s = "a" * 100

tuple_hash = timeit.timeit(lambda: hash(t), number=1_000_000)
string_hash = timeit.timeit(lambda: hash(s), number=1_000_000)
print(f"\nhash() benchmark (1M calls):")
print(f"  Tuple (100 elem): {tuple_hash:.3f}s")
print(f"  String (100 char): {string_hash:.3f}s")
# Strings are faster because they cache the hash value


# Empty tuple hash
print(f"\nhash(()): {hash(())}")  # Fixed value based on algorithm constants

# A tuple is hashable if and only if ALL its elements are hashable.
# CPython checks this at hash time, not at creation time.

def check_hashable(obj, name: str) -> None:
    try:
        h = hash(obj)
        print(f"  {name}: hashable (hash={h})")
    except TypeError as e:
        print(f"  {name}: NOT hashable ({e})")

check_hashable((1, 2, 3), "(1, 2, 3)")              # hashable
check_hashable((1, (2, 3)), "(1, (2, 3))")           # hashable (nested tuple)
check_hashable((1, frozenset({2})), "(1, frozenset)") # hashable
check_hashable((1, [2, 3]), "(1, [2, 3])")           # NOT hashable
check_hashable((1, {2: 3}), "(1, {2: 3})")           # NOT hashable
check_hashable((1, {2, 3}), "(1, {2, 3})")           # NOT hashable

import dis

# Tuple indexing vs list indexing — same bytecode, different C paths
def tuple_access():
    t = (1, 2, 3)
    return t[1]

def list_access():
    l = [1, 2, 3]
    return l[1]

print("=== Tuple access ===")
dis.dis(tuple_access)

print("\n=== List access ===")
dis.dis(list_access)

# Both use BINARY_SUBSCR, but the C implementation differs:
# - tuple: tuplesubscript() in tupleobject.c — direct pointer lookup
# - list:  list_subscript() in listobject.c — bounds check + pointer lookup
# Tuple is slightly faster because the size is fixed (no growth checks needed)

import dis

# + operator on tuples
def concat_tuples():
    a = (1, 2)
    b = (3, 4)
    return a + b

dis.dis(concat_tuples)

# The C function tupleconcat() in tupleobject.c:
# 1. Allocates a new tuple of size len(a) + len(b)
# 2. Copies all pointers from a, then from b
# 3. Increfs each element
# Result: O(n+m) time and space

# This is why tuple concatenation in loops is O(n^2):
import timeit

def build_concat(n):
    result = ()
    for i in range(n):
        result = result + (i,)  # O(n) each iteration -> O(n^2) total
    return result

def build_from_list(n):
    items = list(range(n))
    return tuple(items)  # O(n) total

for n in [1000, 5000, 10000]:
    t1 = timeit.timeit(lambda: build_concat(n), number=1)
    t2 = timeit.timeit(lambda: build_from_list(n), number=1)
    print(f"  n={n:5d}: concat={t1:.4f}s, from_list={t2:.6f}s, ratio={t1/t2:.0f}x")

import dis

def membership_test():
    t = (1, 2, 3, 4, 5)
    return 3 in t

dis.dis(membership_test)

# CONTAINS_OP uses tuplecontains() in tupleobject.c:
# - Iterates through all elements calling PyObject_RichCompareBool
# - Returns as soon as a match is found (short-circuits)
# - Worst case: O(n) for element not in tuple

import timeit

# Membership test: tuple vs set vs frozenset
data_tuple = tuple(range(10000))
data_set = set(range(10000))
data_frozenset = frozenset(range(10000))

for target in [0, 5000, 9999, -1]:
    tt = timeit.timeit(lambda: target in data_tuple, number=10000)
    ts = timeit.timeit(lambda: target in data_set, number=10000)
    tf = timeit.timeit(lambda: target in data_frozenset, number=10000)
    print(f"  target={target:5d}: tuple={tt:.4f}s, set={ts:.4f}s, frozenset={tf:.4f}s")

import dis

# The famous tuple += gotcha explained at bytecode level
def tuple_iadd_gotcha():
    t = ([1, 2],)
    t[0] += [3, 4]

# Let's look at the bytecode:
dis.dis(tuple_iadd_gotcha)

# Key bytecodes for t[0] += [3, 4]:
# 1. LOAD_FAST       t           <- load the tuple
# 2. LOAD_CONST      0           <- load index 0
# 3. BINARY_SUBSCR                <- get t[0] (the list) -> succeeds
# 4. LOAD_CONST      [3, 4]      <- load the RHS list
# 5. BINARY_OP       IADD (+=)   <- calls list.__iadd__([3, 4]) -> MUTATES the list, succeeds
# 6. STORE_SUBSCR                 <- tries t[0] = result -> FAILS with TypeError!
#
# Step 5 mutates the list BEFORE step 6 fails.
# This is why the list is modified even though an exception is raised.

# Demonstrate:
t = ([1, 2],)
try:
    t[0] += [3, 4]
except TypeError:
    pass
print(f"After failed +=: {t}")  # ([1, 2, 3, 4],) — list was mutated!

import gc

# CPython optimization: tuples containing only immutable elements
# are UNTRACKED from the cyclic garbage collector

# This reduces GC overhead significantly for data-heavy applications

t1 = (1, 2, 3)              # All ints -> untracked
t2 = ("a", "b", "c")        # All strings -> untracked
t3 = ((1, 2), (3, 4))       # Nested immutable tuples
t4 = (1, [2, 3])            # Contains a list -> TRACKED
t5 = (1, 2, None, True)     # All atomic -> untracked

for name, obj in [("ints", t1), ("strings", t2), ("nested", t3),
                   ("with_list", t4), ("mixed_atomic", t5)]:
    print(f"  {name:15s}: gc.is_tracked = {gc.is_tracked(obj)}")

# The untracking happens in _PyTuple_MaybeUntrack()
# Called after all elements are set during tuple creation

import sys

# Strings can be interned, but tuples cannot
s1 = sys.intern("hello")
s2 = sys.intern("hello")
print(f"Interned strings: {s1 is s2}")  # True

# No tuple interning API exists
# But CPython does intern some constant tuples via constant folding:
def f():
    return (1, 2, 3)

def g():
    return (1, 2, 3)

# Same module: constant folding may share the tuple
print(f"Same constant tuple: {f() is g()}")  # Likely True (shared co_consts)

# Different modules or dynamic creation: no sharing
t1 = tuple([1, 2, 3])
t2 = tuple([1, 2, 3])
print(f"Dynamic tuples: {t1 is t2}")  # False — different objects
print(f"Equal: {t1 == t2}")           # True — same content