🚀 Case Study: When Python Dict Crash at Scale (100M Elements)

We often benchmark small-scale scenarios and conclude:

“Sets and dicts are faster than sorting.”

But what happens when we scale from 10k → 100M elements?

I ran a benchmark comparing:

• Numpy Sort (baseline, contiguous array, O(n log n))
• Python Set (hash table, O(1) inserts)
• Python Dict (hash table with key-value overhead)

import time
import numpy as np
import psutil
import os

def memory_usage_mb():
    process = psutil.Process(os.getpid())
    return process.memory_info().rss / (1024 * 1024)

def benchmark(n):
    print(f"\n--- Benchmark with {n:,} elements ---")

    # --- Generate Data ---
    arr = np.random.randint(0, n*10, size=n, dtype=np.int64)

    # --- Numpy Sort ---
    mem_before = memory_usage_mb()
    start = time.perf_counter()
    _ = np.sort(arr)
    end = time.perf_counter()
    mem_after = memory_usage_mb()
    print(f"Numpy Sort: {1000*(end-start):.3f} ms, Mem +{mem_after - mem_before:.2f} MB")

    # --- Python Set ---
    data_list = arr.tolist()
    mem_before = memory_usage_mb()
    start = time.perf_counter()
    _ = set(data_list)
    end = time.perf_counter()
    mem_after = memory_usage_mb()
    print(f"Python Set: {1000*(end-start):.3f} ms, Mem +{mem_after - mem_before:.2f} MB")

    # --- Python Dict ---
    mem_before = memory_usage_mb()
    start = time.perf_counter()
    _ = {x: True for x in data_list}
    end = time.perf_counter()
    mem_after = memory_usage_mb()
    print(f"Python Dict: {1000*(end-start):.3f} ms, Mem +{mem_after - mem_before:.2f} MB")

if __name__ == "__main__":
    for n in [10_000, 100_000, 1_000_000, 10_000_000, 100_000_000]:
        benchmark(n)

⚡ Results

🔥 Key Takeaways

1. Small scale → Sets/dicts look efficient.
2. Large scale (10M+) →

• Numpy sort scales much better in both time and memory.
• Python sets/dicts balloon in memory overhead and eventually crash.

3. Lesson: When working with hundreds of millions of elements, Numpy (or other array-based structures) is the only safe choice.

👉 This flips the usual intuition: At huge scale, O(n log n) Numpy Sort beats O(1) Python hash tables because constant factors and memory blow-ups dominate.