difflib.HtmlDiff has quadratic line pairing for lopsided replacements #156505

difflib._mdiff() buffers unmatched lines in lists and consumes them using
pop(0). For lopsided replacement blocks, each removal shifts the remaining
items, making line pairing quadratic.

Reproducer:

import difflib

a = ["a\n"] * 64_000
b = ["b\n"]

list(difflib._mdiff(a, b))

Using matched release builds from CPython main:

The speedup increases with input size, reaching 7.94x at 128,000 lines. Patched
runtime scales approximately linearly.

Using collections.deque for the two pairing queues preserves FIFO behavior
while making removal constant-time. Focused tests, the complete test_difflib
suite, and randomized differential testing confirm identical output.

Tested on CPython main at ed1aa1f324f9 on Linux.

Linked PRs

• gh-156505: Speed up difflib.HtmlDiff for lopsided replacements #156506