Diff Engines

Diff 엔진

SimpleRCS 안에는 diff 알고리즘이 여러 벌 있다. 왜 이렇게 많고, 실제로 뭐가 돌아가고 있고, 나머지는 왜 아직도 붙어있는지를 정리한다.

실제로 쓰이는 건 하나뿐이다

commit()/checkout()이 델타를 계산할 때 부르는 건 pydifflib.py의 StreamSequenceMatcher 딱 하나다. 나머지(Myers 계열, Cython 버전)는 전부 tools/bench_diff.py를 통한 비교/벤치마크용으로만 존재한다.

StreamSequenceMatcher가 하는 일

해시 기반 그리디 매칭이다. 대략 이런 순서로 동작한다.

1. 양쪽 시퀀스를 해시로 인덱싱해서 동일한 라인들을 빠르게 찾는다
2. 매칭되는 블록들을 그리디하게 골라 붙인다
3. 매칭 안 되고 남은 "교체(replace)" 구간만 표준 difflib으로 다듬는다

최단 편집 거리를 수학적으로 보장하지는 않는다. 하지만 O(N)에 가깝게 빠르고, 실무에서 나오는 diff 결과가 대부분 충분히 자연스럽다. 커밋 경로처럼 "정확한 최소 편집 스크립트"보다 "빠르고 합리적인 델타"가 더 중요한 자리에 맞는 선택이다.

Myers 계열은 왜 따로 있나

myersdiff.py, myersdiff_ses.py, myersdiff_dmp.py는 전통적인 Myers O(ND) 알고리즘의 순수 파이썬 구현이다. 이쪽은 최단 편집 스크립트를 수학적으로 보장한다 — Git의 xdiff가 쓰는 것과 같은 계열의 알고리즘.

• SES 변형: 표준적인 최단 편집 스크립트 계산
• DMP 변형: Neil Fraser의 diff-match-patch 방식대로 "middle snake" 전략을 쓰되 리스트 슬라이싱 대신 오프셋을 계속 넘겨서 계산한다. 결과적으로 SES와 같은 편집 스크립트를 내지만 구현 방식이 다르다.

O(ND) 알고리즘의 약점은 두 입력이 많이 다를 때 성능이 나빠진다는 것이다 — 최악의 경우 500KB 정도 크기에 10% 정도만 달라도 초 단위로 느려질 수 있다. StreamSequenceMatcher가 이 케이스에서 훨씬 안전하다.

Cython 버전 (_myersdiff_ses.pyx, _myersdiff_dmp.pyx)

위 두 Myers 구현을 그대로 Cython으로 포팅한 것. 순수 파이썬 대비 15~26배 빠르다는 걸 벤치마크로 확인했지만, 지금은 커밋 경로에 연결돼 있지 않다. pyproject.toml의 ext-modules에 등록돼 있어서 uv sync 시 같이 빌드된다.

실측: 어느 게 실제로 더 빠른가

docs/parser_benchmark.md에 있는 벤치마크 결과를 요약하면:

• 작은 델타 블록(수백 바이트) 기준으로는 파서/diff 엔진 간 차이가 체감되지 않는다 — 오차범위 안.
• 블록이 커질수록(1.6KB → 92KB) 차이가 벌어진다. 이건 diff 엔진 자체보다는 블록 파싱 쪽 얘기지만, 같은 원리로 "큰 입력에서 벌어지는 격차"가 diff 엔진 선택에도 그대로 적용된다.
• Cython 포팅은 순수 파이썬 대비 5~10배 단축이 현실적인 범위 — 파이썬 바이트코드 디스패치 오버헤드를 없애는 효과가 크다.

그럼 뭘 써야 하나

• 지금 그대로 써도 된다. StreamSequenceMatcher는 이미 프로덕션 경로에서 검증됐고, 일반적인 텍스트 편집(줄 단위 수정)에서는 최단 편집 거리와 실질적으로 차이가 안 난다.
• Myers 계열(특히 Cython 버전)이 의미 있어지는 시점은 "정확히 최소 편집 스크립트가 필요하다"거나, "대량의 델타를 배치로 재계산해야 한다" 같은 특수한 요구가 생겼을 때다.
• 새로 diff 알고리즘을 붙이고 싶다면 tools/bench_diff.py가 이미 비교 프레임을 갖추고 있으니 거기에 케이스를 추가해서 실측부터 하는 걸 권한다.

직접 비교해보기

uv run tools/bench_diff.py

시간과 메모리(peak, tracemalloc 기준) 둘 다 비교해준다. 특정 엔진 하나로 두 버전 사이 diff를 직접 보고 싶으면:

uv run tools/srcs_diff.py <파일> --engine ses   # 또는 dmp, pydifflib, myers, difflib