[cpython] Python difflib의 성능 개선: 비대칭 변경 시 발생하는 Quadratic Time 복잡도 문제 해결

2026년 9월 7일수정: 2026년 9월 7일

PR 링크: python/cpython#156506 상태: Merged | 변경: +24 / -4

들어가며

소프트웨어 개발 과정에서 코드 변경 사항을 추적하고 비교하는 것은 매우 중요합니다. Python의 표준 라이브러리인 difflib는 이러한 요구를 충족시키기 위해 다양한 기능을 제공합니다. 특히 HtmlDiff 클래스는 변경된 내용을 HTML 형식으로 시각화하여 보여주는 유용한 도구입니다. 하지만 difflib 내부의 _mdiff 함수에서 발생하는 성능 병목 현상이 특정 상황에서 사용자 경험을 저해할 수 있었습니다. 바로 코드의 한쪽은 크게 변경되었지만 다른 한쪽은 거의 변경되지 않은, 즉 '비대칭적인(lopsided) 변경'이 발생했을 때입니다. 이러한 경우 _mdiff 함수는 Quadratic Time 복잡도를 가지게 되어, 입력 크기가 커질수록 처리 시간이 기하급수적으로 증가하는 문제가 있었습니다. 이번 PR (gh-156505)은 이 성능 문제를 효과적으로 해결하여 difflib의 효율성을 크게 향상시켰습니다.

코드 변경 분석

이번 PR의 핵심은 difflib 내부의 _mdiff 함수에서 사용하던 리스트 기반의 FIFO(First-In, First-Out) 큐 구현을 collections.deque로 교체한 것입니다. 이를 통해 비대칭적인 변경 시 발생하는 성능 저하를 해결했습니다.

Lib/difflib.py

가장 중요한 변경은 Lib/difflib.py 파일의 _line_pair_iterator 함수 내부에 있습니다.

Before:

-from collections import namedtuple as _namedtuple
+from collections import deque as _deque, namedtuple as _namedtuple
...
-def _line_pair_iterator():
    ...
-    fromlines,tolines=[],[]
+    fromlines, tolines = _deque(), _deque()
    while True:
        # Collecting lines of text until we have a from/to pair
        while (len(fromlines)==0 or len(tolines)==0):
            ...
        # Once we have a pair, remove them from the collection and yield it
-        from_line, fromDiff = fromlines.pop(0)
-        to_line, to_diff = tolines.pop(0)
+        from_line, fromDiff = fromlines.popleft()
+        to_line, to_diff = tolines.popleft()
        yield (from_line,to_line,fromDiff or to_diff)

After:

+from collections import deque as _deque, namedtuple as _namedtuple
...
 def _line_pair_iterator():
    ...
-    fromlines,tolines=[],[]
+    fromlines, tolines = _deque(), _deque()
    while True:
        # Collecting lines of text until we have a from/to pair
        while (len(fromlines)==0 or len(tolines)==0):
            ...
        # Once we have a pair, remove them from the collection and yield it
-        from_line, fromDiff = fromlines.pop(0)
-        to_line, to_diff = tolines.pop(0)
+        from_line, fromDiff = fromlines.popleft()
+        to_line, to_diff = tolines.popleft()
        yield (from_line,to_line,fromDiff or to_diff)

설명:

from collections import deque as _deque: collections.deque를 임포트하여 _deque라는 별칭으로 사용합니다. deque는 양쪽 끝에서 항목을 추가하거나 제거하는 데 효율적인 자료구조입니다.
fromlines, tolines = _deque(), _deque(): 기존의 빈 리스트 [] 대신 deque 객체를 초기화하여 사용합니다. 이는 _mdiff 함수가 처리해야 할 줄들을 저장하는 큐 역할을 합니다.
fromlines.popleft() 및 tolines.popleft(): 기존의 list.pop(0) 메서드는 리스트의 첫 번째 요소를 제거하고 나머지 모든 요소를 앞으로 한 칸씩 이동시키는 연산입니다. 이는 리스트의 크기에 비례하는 시간 복잡도 O(N)를 가집니다. 특히 _mdiff 함수에서 이 pop(0) 연산이 반복적으로 발생할 때, 입력 데이터가 비대칭적인 경우(예: 한쪽은 64,000줄인데 다른 한쪽은 1줄) 큐에 쌓인 나머지 요소들을 계속해서 이동시켜야 하므로 전체적으로 Quadratic Time 복잡도 O(N^2)가 발생하게 됩니다.

반면, deque.popleft()는 큐의 왼쪽(시작)에서 요소를 제거하는 연산으로, 리스트의 pop(0)과 동일한 기능을 하지만 시간 복잡도는 O(1)입니다. deque는 내부적으로 이중 연결 리스트와 유사한 구조를 사용하여 양쪽 끝에서의 삽입/삭제를 상수 시간 안에 처리할 수 있습니다.

이 변경을 통해 _mdiff 함수는 비대칭적인 변경이 발생하더라도 각 줄 쌍을 처리하는 데 걸리는 시간이 거의 일정하게 유지되어, 전체적인 성능이 선형 시간 복잡도 O(N)에 가깝게 개선됩니다.

Lib/test/test_difflib.py

PR에는 새로운 테스트 케이스가 추가되어 이 변경의 정확성을 검증합니다.

Before: (기존 테스트)

 # No relevant changes for this specific optimization

After: (새로운 테스트 추가)

+    def test_mdiff_lopsided_replace(self):
+        self.assertEqual(
+            list(difflib._mdiff(["a\n"] * 4, ["b\n"])),
+            [
+                ((1, '\x00-a\n\x01'), (1, '\x00+b\n\x01'), True),
+                ((2, '\x00-a\n\x01'), ('', '\n'), True),
+                ((3, '\x00-a\n\x01'), ('', '\n'), True),
+                ((4, '\x00-a\n\x01'), ('', '\n'), True),
+            ],
+        )
+        self.assertEqual(
+            list(difflib._mdiff(["a\n"], ["b\n"] * 4)),
+            [
+                ((1, '\x00-a\n\x01'), (1, '\x00+b\n\x01'), True),
+                (('', '\n'), (2, '\x00+b\n\x01'), True),
+                (('', '\n'), (3, '\x00+b\n\x01'), True),
+                (('', '\n'), (4, '\x00+b\n\x01'), True),
+            ],
+        )

설명:

test_mdiff_lopsided_replace라는 새로운 테스트 함수가 추가되었습니다. 이 테스트는 _mdiff 함수에 한쪽은 여러 줄이고 다른 한쪽은 한 줄인 비대칭적인 입력을 제공하여, 예상되는 결과가 올바르게 나오는지 검증합니다. 이는 이전에는 성능 문제로 인해 제대로 테스트되지 못했거나, 테스트하더라도 매우 느렸을 시나리오를 커버합니다. 또한, randomized differential testing을 통해 _mdiff와 HtmlDiff의 출력이 모든 모드에서 동일함을 확인했다고 PR 설명에 명시되어 있어, 기능적 변경 없이 성능만 개선되었음을 뒷받침합니다.

왜 이게 좋은가?

성능 향상

PR 설명에 포함된 벤치마크 결과는 이 변경이 가져온 성능 향상을 명확하게 보여줍니다.

Case	Before	After	Speedup
`_mdiff()`, 64,000-to-1	264 ms	61.9 ms	4.26x
`HtmlDiff.make_table()`, 64,000-to-1	398 ms	206 ms	1.93x
`_mdiff()`, 128,000-to-1	999 ms	126 ms	7.94x

특히 _mdiff() 함수에서 64,000 대 1의 비율로 비대칭적인 변경이 발생했을 때 4.26배, 128,000 대 1의 비율에서는 무려 7.94배의 속도 향상을 보였습니다. HtmlDiff.make_table() 전체에서도 1.93배의 향상이 있었습니다. 이는 기존의 Quadratic Time 복잡도가 선형에 가까운 시간 복잡도로 개선되었기 때문입니다. 이로 인해 대규모 파일 비교 시 difflib의 성능이 크게 향상되어, 사용자들은 더 빠르고 효율적으로 코드 변경 사항을 확인할 수 있게 되었습니다.

일반적인 교훈

자료구조 선택의 중요성: 특정 연산(여기서는 큐의 앞에서 제거)에 최적화된 자료구조를 사용하는 것이 전체 알고리즘의 성능에 지대한 영향을 미칠 수 있습니다. Python의 collections 모듈은 리스트 외에도 deque, heapq, defaultdict 등 다양한 고성능 자료구조를 제공하며, 문제에 적합한 자료구조를 선택하는 것이 중요합니다.
시간 복잡도 분석: 알고리즘의 시간 복잡도를 이해하고, 특히 비정상적인(edge) 케이스에서의 성능 저하 가능성을 파악하는 것이 중요합니다. list.pop(0)의 O(N) 복잡도는 잘 알려져 있지만, 이것이 반복적으로 사용될 때 발생하는 O(N^2) 복잡도는 실제 코드에서 성능 병목의 원인이 될 수 있습니다.
테스트의 중요성: 이번 PR은 비대칭적인 변경이라는 특정 시나리오를 위한 테스트 케이스를 추가함으로써, 이러한 성능 문제가 재발하지 않도록 보장하고 코드의 견고성을 높였습니다. 다양한 엣지 케이스를 커버하는 테스트는 필수적입니다.

리뷰 피드백 반영

리뷰 과정에서 eendebakpt님이

참고 자료

https://docs.python.org/3/library/collections.html#collections.deque

⚠️ 알림: 이 분석은 AI가 실제 코드 diff를 기반으로 작성했습니다.

PR Analysis 의 다른글

이전글 [vllm] vLLM Qwen3.8-Flash-Next: QSA Indexer 캐시를 위한 FP8 지원으로 메모리 효율 및 성능 최적화
현재글 : [cpython] Python difflib의 성능 개선: 비대칭 변경 시 발생하는 Quadratic Time 복잡도 문제 해결
다음글 [flashinfer] FlashInfer NVFP4 KV 타일 리팩(Repack)을 통한 성능 최적화