Sets — Professional Level¶

# Verify PySet_MINSIZE behavior
import sys

small = {1, 2, 3}
medium = {1, 2, 3, 4, 5, 6, 7, 8, 9}
print(f"Small set (3 items):  {sys.getsizeof(small)} bytes")
print(f"Medium set (9 items): {sys.getsizeof(medium)} bytes")
# The jump happens when items exceed what smalltable can hold

# Demonstrate dummy slot behavior
import dis

s = {1, 2, 3, 4, 5}
s.remove(3)  # Slot for 3 becomes "dummy"
# Now 'in' checks must probe past the dummy when looking for elements
# that had the same probe chain as 3
print(4 in s)  # True — probing continues past dummy

# The resize threshold
def will_resize(fill: int, table_size: int) -> bool:
    """Check if adding one more element triggers a resize."""
    return (fill + 1) * 5 >= table_size * 3

# Table size 8: resizes when fill > 4 (8 * 3 / 5 = 4.8)
# Table size 16: resizes when fill > 9
# Table size 32: resizes when fill > 19
for size in [8, 16, 32, 64, 128]:
    threshold = size * 3 // 5
    print(f"Table size {size:>4}: resize when fill > {threshold}")

def simulate_probe_sequence(hash_val: int, table_size: int, max_steps: int = 20) -> list[int]:
    """Simulate CPython's set probe sequence."""
    mask = table_size - 1
    i = hash_val & mask
    perturb = hash_val
    sequence = [i]

    for _ in range(max_steps - 1):
        perturb >>= 5
        i = (i * 5 + perturb + 1) & mask
        sequence.append(i)
        if perturb == 0 and len(set(sequence)) == table_size:
            break

    return sequence

# Example: hash=42 in table of size 8
print(simulate_probe_sequence(42, 8))
# Shows how CPython distributes probes across the table

# Small integers: hash(x) == x
print(hash(42))    # 42
print(hash(-1))    # -2 (special case: -1 is reserved for errors in C)
print(hash(0))     # 0

# Large integers use a more complex hash
import sys
print(hash(sys.maxsize + 1))  # Different from the value itself

# String hashes change between runs (PYTHONHASHSEED randomization)
import os
print(f"PYTHONHASHSEED = {os.environ.get('PYTHONHASHSEED', 'random')}")
print(f"hash('hello') = {hash('hello')}")
# Run twice — different results each time (unless PYTHONHASHSEED is fixed)

import dis

class Point:
    __slots__ = ("x", "y")

    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y

    def __hash__(self) -> int:
        return hash((self.x, self.y))

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Point):
            return NotImplemented
        return self.x == other.x and self.y == other.y

# Analyze the bytecode of hash computation
dis.dis(Point.__hash__)

import sys
import ctypes


def set_memory_breakdown(n: int) -> None:
    """Analyze memory usage at different set sizes."""
    s = set(range(n))
    set_size = sys.getsizeof(s)

    # Each element is also a Python object
    element_overhead = sum(sys.getsizeof(x) for x in s)

    print(f"Elements:         {n:>10,}")
    print(f"Set object:       {set_size:>10,} bytes")
    print(f"Element objects:  {element_overhead:>10,} bytes")
    print(f"Total:            {set_size + element_overhead:>10,} bytes")
    print(f"Per element:      {(set_size + element_overhead) / n:>10.1f} bytes")
    print()


for n in [10, 100, 1000, 10000]:
    set_memory_breakdown(n)

import sys


def track_set_resizes():
    """Track when the set internally resizes."""
    s = set()
    prev_size = sys.getsizeof(s)
    resizes = []

    for i in range(200):
        s.add(i)
        curr_size = sys.getsizeof(s)
        if curr_size != prev_size:
            resizes.append({
                "n_elements": len(s),
                "old_bytes": prev_size,
                "new_bytes": curr_size,
                "ratio": curr_size / prev_size if prev_size else 0,
            })
            prev_size = curr_size

    for r in resizes:
        print(
            f"At {r['n_elements']:>4} elements: "
            f"{r['old_bytes']:>6} -> {r['new_bytes']:>6} bytes "
            f"({r['ratio']:.1f}x)"
        )


track_set_resizes()

import dis

# Set literal — uses BUILD_SET opcode
def create_literal():
    return {1, 2, 3}

# set() constructor — function call overhead
def create_constructor():
    return set([1, 2, 3])

print("=== Set Literal ===")
dis.dis(create_literal)
print("\n=== Set Constructor ===")
dis.dis(create_constructor)

import dis

def set_comp():
    return {x**2 for x in range(10)}

print("=== Set Comprehension ===")
dis.dis(set_comp)
# Creates a nested code object with SET_ADD opcode

import dis

def membership_test(s, x):
    return x in s

dis.dis(membership_test)
# CONTAINS_OP 0  (for 'in')
# This eventually calls set.__contains__ -> set_lookkey in C

import timeit

# Benchmark: int lookup (fastest — hash is identity)
s_int = set(range(1_000_000))
t_int = timeit.timeit(lambda: 999_999 in s_int, number=1_000_000)

# Benchmark: string lookup (slower — SipHash computation)
s_str = {str(i) for i in range(1_000_000)}
t_str = timeit.timeit(lambda: "999999" in s_str, number=1_000_000)

print(f"int lookup:    {t_int:.4f}s per 1M lookups")
print(f"string lookup: {t_str:.4f}s per 1M lookups")
print(f"string/int ratio: {t_str/t_int:.1f}x")

import timeit

small = set(range(100))
large = set(range(1_000_000))

# Both directions are equally fast due to optimization
t1 = timeit.timeit(lambda: small & large, number=10_000)
t2 = timeit.timeit(lambda: large & small, number=10_000)
print(f"small & large: {t1:.4f}s")
print(f"large & small: {t2:.4f}s")
# Nearly identical — CPython swaps internally

import timeit

fs = frozenset(range(10_000))

# First hash computation (slower)
hash(fs)

# Subsequent calls use cached value
t = timeit.timeit(lambda: hash(fs), number=1_000_000)
print(f"Cached frozenset hash: {t:.4f}s per 1M calls")
# Nearly zero cost after first computation

a = frozenset()
b = frozenset()
print(a is b)  # True — same object in memory

import dis

def check_and_add(s: set, x: int) -> None:
    if x not in s:   # CONTAINS_OP — GIL can release after this
        s.add(x)     # CALL_METHOD — another thread may have added x

dis.dis(check_and_add)
# Multiple bytecodes — NOT atomic

# CPython prevents this with a RuntimeError
s = {1, 2, 3, 4, 5}
try:
    for item in s:
        s.add(item * 10)  # RuntimeError: Set changed size during iteration
except RuntimeError as e:
    print(f"Caught: {e}")

# Internal mechanism: set iterator stores a version counter
# If set's version changes during iteration, RuntimeError is raised