DEV Community

Cover image for This One Line Made My Python Queue 2,500x Slower (list.pop(0))
Muiduzzaman Lipu for Refactorly

Posted on

This One Line Made My Python Queue 2,500x Slower (list.pop(0))

A queue of one million tasks. Processing them took 58 seconds. Changing one line made it take 0.023 seconds.

All timings below are the best of 3 runs on Python 3.15.2, on an Apple M4.

Video version:

The code

tasks = list(range(1_000_000))

while tasks:
    task = tasks.pop(0)    # take the oldest task
    # ... process it
Enter fullscreen mode Exit fullscreen mode

First in, first out. It looks fine, and with a few hundred tasks you'd never notice a problem.

Measured

Items list.pop(0) deque.popleft()
10,000 0.004 s 0.0002 s
100,000 0.548 s 0.0018 s
1,000,000 57.96 s 0.023 s

Look at the left column: 10× more items, roughly 100× more time. That's the signature of O(n²). The deque column grows linearly: 10× the items, about 10× the time.

Why pop(0) is O(n)

A Python list is a dynamic array: one contiguous block of memory holding pointers.

# [ t0 | t1 | t2 | t3 | ... | t999999 ]

tasks.pop()     # remove the end: nothing moves → O(1)
tasks.pop(0)    # remove the front: 999,999 items move left → O(n)
Enter fullscreen mode Exit fullscreen mode

Removing the first element leaves a gap, so every remaining element shifts one slot left. Do that n times and you get about n²/2 moves: half a trillion for a million tasks.

The fix: collections.deque

from collections import deque

tasks = deque(range(1_000_000))

while tasks:
    task = tasks.popleft()
Enter fullscreen mode Exit fullscreen mode

deque (double-ended queue) supports O(1) appends and pops at both ends. If you write breadth-first search, this is the queue to use.

Trap 2: insert(0, x)

The mirror image has the same cost: inserting at the front shifts everything right.

items = []
for i in range(100_000):
    items.insert(0, i)       # 1.377 s

items = deque()
for i in range(100_000):
    items.appendleft(i)      # 0.002 s
Enter fullscreen mode Exit fullscreen mode

Trap 3: out = out + [x]

out = []
for i in range(50_000):
    out = out + [i]   # 1.988 s: builds a NEW list and copies everything
Enter fullscreen mode Exit fullscreen mode
out = []
for i in range(50_000):
    out.append(i)     # 0.0007 s
Enter fullscreen mode Exit fullscreen mode

out + [i] creates a brand-new list every iteration. out.append(i) and out += [i] modify the list in place (+= took 0.002 s in my test).

Trap 4 (half a myth): str +=

You'll often read that building a string with += in a loop is O(n²). I measured 300,000 iterations of s += 'x':

Case Time
plain local variable 0.008 s
with another reference (alias = s in the loop) 0.665 s
on an attribute (obj.s += 'x') 0.658 s

CPython has an optimization: when the string has only one reference, += can resize it in place. That's why the plain case is fast. As soon as anything else holds a reference, or the target is an attribute, the optimization can't apply, and every += copies the whole string: about 80× slower here. Other Python implementations (like PyPy) don't promise this optimization at all.

The reliable pattern:

parts = []
for chunk in chunks:
    parts.append(chunk)
result = "".join(parts)
Enter fullscreen mode Exit fullscreen mode

Recap

  • list.pop(0) and list.insert(0, x) are O(n). Use deque.popleft() / deque.appendleft().
  • out = out + [x] copies the list. Use append or +=.
  • s += ... is only fast on a plain local string. Build strings with "".join(parts).
  • Warning sign: 10× more data, ~100× slower means O(n²) is hiding somewhere.

Now go search your code for pop(0). 👀


I post one tested coding tip every day on YouTube at Refactorly. The 30-second version of this one is here.

Top comments (0)