set vs frozenset vs list: Membership Lookup Lab

Intro — what this post promises

Is x in my_list fine until “it gets big”? Folklore says switch to a set “eventually.” This lab measures membership (x in container) for set, frozenset, list, and dict keys across N on Linux localhost, and reports the crossover.

Related links:

• sorted vs heapq vs bisect localhost lab
• pathlib vs os.path localhost lab
• dataclass vs slots vs dict localhost lab
• json vs orjson vs msgpack localhost lab
• python re vs str methods localhost lab
• tempfile NamedTemporaryFile localhost lab
• uuid4 vs secrets token localhost lab
• Why your average latency graph is lying (p50 / p95 / p99)

Lab honesty (1 Oct 2026 IST): Python 3.13.5. String keys; ~50% hit / 50% miss probes. Affiliates: 0. Not a perfect-hash / bloom-filter study.

Verdict up front: set is already ~2.1× list at N=8, ~20× at N=128, and ~3917× at N=32 768. frozenset ≈ set; dict keys ≈ set. The “wait until N is huge” story does not survive this curve.

What we measure

Same probe sequence for every arm. ops/s = probes ÷ p50 batch wall. We do not time construction — containers are built once before the timed loop.

Lab topology

N in {8, 32, 128, 512, 2048, 8192, 32768}
Members: "k0"…"kN-1" strings
Probes: alternating hit/miss (miss keys "m*")
Probe counts: 200k down to 2k as list slows
Metric: p50 ops/s (membership checks)

Why scale probe counts? A fair ns/op comparison still holds (ops ÷ wall). Leaving list at 200k probes for N=32k would dominate wall time without teaching more. Script: lab-evidence/48-set-vs-list-membership/results/run_lab.py.

Lead table — membership ops/s (p50)

Crossover flags from this run: set ≥ 2× list at N=8; ≥ 10× at N=128.

ns/op for list at N=32 768: ~133196 ns vs set ~34 ns.

Reading the curve

• Hash containers stay ~30–38 ns/op across this N range (string hash + table probe). Set at N=8 was ~31.5 ns; at N=32k ~34.0 ns.
• List falls roughly with N — classic linear scan; at N=32 already ~5.5× behind set; at N=512 ~73×; at N=8 192 ~1081×.
• frozenset tracks set within a few percent (immutable, same hash machinery) — use it when you need a hashable set-of-sets or a constant allowlist.
• dict in is the same hash story as set — slightly slower here (~0.85× set at N=2048) from value payload / table layout, not a different asymptotic.

If you already have a dict of payloads, key in d is enough — do not build a parallel set “for speed” unless profiling says so.

Methodology notes

Probes are a fixed sequence shared across arms so hit-rate and key distribution cannot favor one container. Warmup runs discard first-touch noise. ops/s uses p50 batch wall, not sum-of-repeats. Miss keys are distinct strings (m*) so we exercise both sides of the branch — a hits-only bench would understate list cost when early elements match.

Pitfalls

1. Building a set once, probing once. Construction cost is real; this lab times lookup only after containers exist. Hot-path “build set every request” needs a different bench.
2. Integer keys vs strings. Hash cost differs; ratios stay the same shape.
3. Sorted list + bisect. Different tool — see the ordered-insert lab; not in on a plain list.
4. Tiny allowlists (N=2–3). Absolute list time may still be fine; the 2× crossover already at N=8 is the warning for growing codepaths.
5. Identity vs equality. These are equality membership checks on strings — not is.

When to pick what

Reproduce

python3 lab-evidence/48-set-vs-list-membership/results/run_lab.py

Evidence: /workspace/lab-evidence/48-set-vs-list-membership/results/.

Closing

List membership does not stay “fine.” On this box set is already ~2.1× at N=8, ~20× at N=128, and ~3917× at N=32k. frozenset and dict keys ride with set. Convert allowlists that grow — don’t wait for a production cliff.