Skip to content

Diff Engines en

Jump to bottom
Won-Kyu Park edited this page Aug 28, 2026 · 2 revisions

Diff Engines

There are several diff algorithms living inside SimpleRCS. Here's why there are so many, which one actually runs, and why the rest are still sitting there.

Which one actually runs

matchers.py resolves one backend at import time, and that is what commit()/checkout() use. The order is:

SIMPLE_RCS_MATCHER (if set) -> Cython Myers (dmp -> ses) -> StreamSequenceMatcher

So when a C toolchain was available and the extensions got built, the default backend is the Cython Myers matcher (dmp_cython); StreamSequenceMatcher is the fallback for when they were not. Check it with:

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

Note what the fallback is not: the pure-Python Myers twins (myersdiff_*.py). Those are first-cut reference implementations that hit an O(ND) worst case on dissimilar inputs. They stay selectable by name, never by fallback.

The names SIMPLE_RCS_MATCHER accepts match the ids tools/bench_diff.py prints, so a benchmark run turns into a setting directly:

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

Switching backends changes the stored delta bytes, since it changes which of several equally valid opcode sequences a delta is built from. Block hashes cover the logical content rather than the stored representation, so existing history stays verifiable across the switch.

What StreamSequenceMatcher does

Greedy hash-based matching. Roughly:

  1. Hash-index both sequences to find identical lines quickly
  2. Greedily stitch together the matching blocks
  3. Run the leftover "replace" regions (the parts that didn't match) through standard difflib for refinement

It doesn't mathematically guarantee the shortest edit distance. But it's close to O(N) and fast, and in practice most real-world diffs come out looking perfectly reasonable anyway. For a commit path, where "fast, sensible delta" matters more than "provably minimal edit script," it's the right tradeoff.

Why the Myers family exists separately

myersdiff.py, myersdiff_ses.py, and myersdiff_dmp.py are pure-Python implementations of the classic Myers O(ND) algorithm. This family mathematically guarantees the shortest edit script — the same family of algorithm Git's xdiff uses.

  • SES variant: standard shortest-edit-script computation
  • DMP variant: follows Neil Fraser's diff-match-patch approach, using the "middle snake" strategy but passing offsets around instead of slicing lists. Produces the same edit script as SES, just implemented differently.

The catch with O(ND) algorithms is that they degrade badly when the two inputs are very different — worst case, something around 500KB with 10% changed can take seconds. StreamSequenceMatcher is much safer in that scenario.

The Cython versions (_myersdiff_ses.pyx, _myersdiff_dmp.pyx)

Direct Cython ports of the two Myers implementations above, and this is the default backend. They are registered in pyproject.toml's ext-modules so uv sync builds them, and setup.py downgrades a failed compile to a warning — an install without a toolchain still works, it just falls back to StreamSequenceMatcher.

Real numbers

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

Engine Time Peak
Myers DMP (Cython) 3.3 ms 657 KB default backend
Myers SES (Cython) 3.9 ms 787 KB
difflib (stdlib) 26.8 ms 338 KB benchmark baseline
StreamSequenceMatcher 47.4 ms 1,146 KB fallback
Myers DMP (pure Python) 983.6 ms 660 KB
Myers SES (pure Python) 990.8 ms 700 KB
Myers (linked-list) 1,295.2 ms 7,101 KB

Three things to read out of it:

  • The Cython Myers is ~14x faster than the fallback, which is why it is the default.
  • The same algorithm in pure Python is ~300x slower (983.6 → 3.3 ms). That is why myersdiff_*.py is not a fallback target, and this input is unfavourable for O(ND) (many differing lines), which widens the gap further.
  • All four produce the same 3 opcodes — this is a speed difference, not a quality one.

These numbers are for these parameters on this machine. Run tools/bench_diff.py for other sizes and change ratios.

docs/parser_benchmark.md is about the block parser (regex vs no_regex), a different measurement from this one. Its "5–10x from Cython" is an estimate for porting the parser, and that port was never done.

So what should you actually use

  • Leave the default alone. With a toolchain you get the Cython Myers, without one you get StreamSequenceMatcher, automatically.
  • If commits feel slow, check whether you are on the fallback (ACTIVE_BACKEND) before anything else. SIMPLE_RCS_MATCHER can force a choice.
  • Do not run the pure-Python Myers in production — selectable by name, but they are reference implementations exposed to the O(ND) worst case.
  • To wire in a new algorithm, add a case to tools/bench_diff.py and measure first.

Try it yourself

uv run tools/bench_diff.py

Compares both time and peak memory (via tracemalloc). To see a diff between two versions through one specific engine:

uv run tools/srcs_diff.py <file> --engine ses   # or dmp, pydifflib, myers, difflib

Clone this wiki locally