deque vs list: Queue FIFO Lab

Intro — what this post promises

Need a FIFO queue in Python? Folklore says “use collections.deque” because list.pop(0) is O(n). This lab times append + popleft vs append + pop(0) with a prefill of size S, plus drain and append-only baselines, on Linux localhost.

Related links:

• lru_cache hit vs miss localhost lab
• struct pack vs to_bytes localhost lab
• set vs list membership localhost lab
• sorted vs heapq vs bisect localhost lab
• copy vs deepcopy localhost lab
• string concat vs join localhost lab
• dataclass vs slots vs dict localhost lab
• logging vs print localhost lab

Lab honesty (1 Oct 2026 IST): Python 3.13.5. Affiliates: 0. FIFO cycle = one append + one front pop, keeping length ≈ S.

Verdict up front: at S=0–100 deque is only ~1.2–1.2× list. At S=1 000 already ~2.6×. At S=10 000 ~31× (18.6M vs 605k cycles/s). Draining 50k with pop(0) is ~255k/s vs deque ~31.6M.

Arms

Lab topology

FIFO S in {0, 100, 1000, 10000, 50000}
M scaled down for large S (still p50 ops/s)
Drain N in {1000, 10000, 50000}
Metric: p50 wall → cycles/s or pops/s

Script: lab-evidence/54-deque-vs-list-queue/results/run_lab.py.

Lead table — FIFO cycles/s (p50)

At S=10k, list pays ~1654 ns/cycle vs deque ~54 ns.

Drain and append baselines

list.pop() from the end matches deque drain speed — the bug is front removal, not “lists are slow.”

Pitfalls

1. Benchmarking empty-queue FIFO only — S≈0 hides the O(n) shift.
2. Using list as a queue “until it hurts” — at S=1k it already hurts on this box.
3. Confusing stack (pop()) with queue (pop(0)) — different asymptotics.
4. Indexing into a deque — O(n) for middle access; use a list if you need random access.

When to pick what

Reproduce

python3 lab-evidence/54-deque-vs-list-queue/results/run_lab.py

Evidence: /workspace/lab-evidence/54-deque-vs-list-queue/results/.

Closing

list.pop(0) does not stay fine. On this box deque FIFO is ~2.6× at S=1k and ~31× at S=10k. Drain 50k: deque ~32M/s vs list pop(0) ~255k. Use deque for queues; keep list for stacks and random access.