graphlib Topo vs Manual Kahn: Localhost Lab

Intro — what this post promises

Topologically sort a DAG via graphlib.TopologicalSorter vs a manual Kahn algorithm (deque + indegree). This lab reports sorts/s (and nodes/s) on Linux localhost. Affiliates: 0.

Related links:

• tomllib vs json localhost lab
• path glob vs fnmatch localhost lab
• heapq merge vs sorted localhost lab
• islice vs list slice localhost lab
• dataclass replace vs manual localhost lab
• zoneinfo vs utc offset localhost lab
• stat vs path stat localhost lab
• mmap write vs write localhost lab

Lab honesty (1 Oct 2026 IST): Python 3.13.5. Random DAGs with edges only i→j for i<j (acyclic by construction).

Verdict up front (1000 nodes / 3000 edges): Kahn ~841.9 sorts/s (~0.84 Mnodes/s); static_order ~317.7; prepare/get_ready ~302.7. Prefer graphlib for API/cycle errors; Kahn when topo is on the hottest path.

Arms

Lab topology

n200/e400 · n1000/e3000 · n5000/e15000 · 7 rounds · p50
metric: sorts/s = 1/p50_s · nodes/s = n/p50_s

Script: lab-evidence/114-graphlib-topo-vs-manual/results/run_lab.py.

Lead table — 1000 nodes / 3000 edges (p50)

Scale sketch (sorts/s)

Why graphlib still wins designs

• Clear CycleError instead of a silent partial Kahn list (ours raises on length mismatch; easy to forget).
• Incremental get_ready for schedulers that launch ready tasks as they unlock.
• Readable predecessor add(node, *preds) API for build graphs / package deps.

Build-system angle

Package resolvers and CI job graphs usually prefer graphlib’s incremental API (get_ready) so workers can start as soon as predecessors finish. Raw Kahn lists shine when you need one static order for a batch compiler pass — measure your shape before rewriting.

Reading it

• Library/default code → TopologicalSorter.
• Proven hot path on large static DAGs → consider Kahn (here ~2.7× on the 1k graph).
• static_order ≈ prepare/get_ready throughput when both rebuild the sorter each call.
• Validate edge direction conventions (predecessor vs successor maps).

Edge-list conventions

Teams disagree on whether an edge A→B means “A must run before B” or “A depends on B.” TopologicalSorter.add(node, *predecessors) makes the predecessor story explicit. When porting a Kahn that stored successors, invert carefully or you will “pass” tests that only check length, not relative order — this lab asserts predecessor indices for both arms.

Multi-component DAGs

Disconnected nodes are fine: both algorithms emit them when indegree hits zero. Very wide ready-sets stress get_ready batching differently than a long chain. If your production graph is a deep pipeline, re-run with a chain fixture before declaring Kahn universally faster.

Error handling product note

graphlib raises CycleError with diagnostic detail. A bare Kahn that only checks len(out) == n is easy to omit under deadline pressure. Correctness features are why stdlib graphlib exists even when this microbench favors the hand roll.

Pitfalls

• Forgetting cycle detection in a hand-rolled Kahn.
• Rebuilding the graph every call when you could reuse structures.
• Mixing successor-list and predecessor-list mental models.
• Using topo sort where a simple priority queue would do.

Reproduce

python3 lab-evidence/114-graphlib-topo-vs-manual/results/run_lab.py

Evidence: summary.json, summary.txt.

Limits

One Linux box. Synthetic DAGs (no multi-component stress beyond random edges). Not parallel task execution timing.

Takeaway

At 1000 nodes / 3000 edges, Kahn ~841.9 sorts/s beat graphlib ~317.7 sorts/s. Default to graphlib for correctness/API; drop to Kahn when profiles say the constant factors matter.