Diff Engines

Diff 엔진

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

어느 게 실제로 도는가

matchers.py가 import 시점에 백엔드 하나를 정하고, commit()/checkout()은 그걸 쓴다. 순서는 이렇다.

SIMPLE_RCS_MATCHER (설정돼 있으면) -> Cython Myers (dmp -> ses) -> StreamSequenceMatcher

즉 C 툴체인이 있어 Cython 확장이 빌드돼 있으면 기본 백엔드는 Cython Myers(dmp_cython)이고, StreamSequenceMatcher는 그게 없을 때의 폴백이다. 확인은 이렇게 한다.

>>> from simple_rcs.matchers import ACTIVE_BACKEND
>>> ACTIVE_BACKEND
'dmp_cython'

폴백이 순수 파이썬 Myers 쌍둥이(myersdiff_*.py)로 가지 않는 것이 중요하다 — 그쪽은 초기 구현 레퍼런스이고 서로 다른 입력에서 O(ND) 최악을 밟는다. 이름으로는 선택할 수 있지만 폴백 대상은 아니다.

SIMPLE_RCS_MATCHER에 넣는 이름은 tools/bench_diff.py가 출력하는 id와 같아서, 벤치마크 결과를 그대로 설정으로 옮길 수 있다.

SIMPLE_RCS_MATCHER=ses_cython uv run tools/srcs_commit.py FILE -m msg

백엔드를 바꾸면 저장되는 델타 바이트가 달라진다. 똑같이 유효한 여러 opcode 시퀀스 중 어느 것을 고르느냐가 달라지기 때문이다. 블록 해시는 저장 표현이 아니라 논리적 전체 내용을 덮으므로, 백엔드를 갈아도 기존 이력의 검증은 계속 통과한다.

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으로 포팅한 것이고, 기본 백엔드가 바로 이것이다. pyproject.toml의 ext-modules에 등록돼 있어 uv sync 시 함께 빌드되며, setup.py가 컴파일 실패를 경고로 낮추므로 툴체인이 없는 환경에서도 설치는 된다 — 그 경우 StreamSequenceMatcher로 폴백한다.

실측

uv run tools/bench_diff.py --size 200 --diff-ratio 0.1 --runs 3 (2,409줄, 10% 변경):

엔진	시간	Peak	비고
Myers DMP (Cython)	3.3 ms	657 KB	기본 백엔드
Myers SES (Cython)	3.9 ms	787 KB
difflib (stdlib)	26.8 ms	338 KB	벤치마크 기준선
StreamSequenceMatcher	47.4 ms	1,146 KB	폴백
Myers DMP (순수 파이썬)	983.6 ms	660 KB
Myers SES (순수 파이썬)	990.8 ms	700 KB
Myers (linked-list)	1,295.2 ms	7,101 KB

읽을 점 셋이다.

• Cython Myers가 폴백보다 ~14배 빠르다. 기본 백엔드가 그쪽인 이유다.
• 같은 알고리즘인데 순수 파이썬은 ~300배 느리다 (983.6 → 3.3 ms). 이게 myersdiff_*.py가 폴백 대상이 아닌 이유고, 이 입력이 O(ND)에 불리한 조건(서로 다른 줄이 많음)이라 격차가 더 벌어진다.
• 네 엔진 모두 opcode 3개로 같은 결과를 낸다 — 속도 차이지 품질 차이가 아니다.

이 수치는 이 파라미터·이 머신 기준이다. 다른 크기·변경비율에서는 tools/bench_diff.py를 직접 돌려 확인할 것.

docs/parser_benchmark.md는 블록 파서(regex vs no_regex) 이야기이고 여기 diff 엔진 비교와는 다른 측정이다. 그 문서의 "Cython 5~10배"는 파서를 포팅했을 때의 추정치이며 파서 포팅은 착수되지 않았다.

그럼 뭘 써야 하나

• 기본값 그대로 두면 된다. 툴체인이 있으면 Cython Myers가, 없으면 StreamSequenceMatcher가 자동으로 잡힌다.
• 폴백으로 돌고 있는데 커밋이 느리다면 확장이 빌드됐는지부터 본다 (ACTIVE_BACKEND 확인). SIMPLE_RCS_MATCHER로 강제할 수도 있다.
• 순수 파이썬 Myers를 프로덕션에 쓰지 말 것 — 이름으로 선택은 되지만 레퍼런스 구현이고 O(ND) 최악에 노출된다.
• 새 알고리즘을 붙이려면 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

srcs_diff --engine의 이름(ses/dmp/...)은 이 도구 전용이고, SIMPLE_RCS_MATCHER가 받는 이름(ses_cython/dmp_cython/stream/...)과는 다르다. 헷갈리면 bench_diff.py가 출력하는 id 쪽이 환경변수용이다.