Skip to content

Diff Engines en

Jump to bottom
Won-Kyu Park edited this page Aug 4, 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.

Only one is actually wired in

commit()/checkout() compute deltas through exactly one engine: StreamSequenceMatcher in pydifflib.py. Everything else — the Myers family, the Cython versions — exists purely for comparison through tools/bench_diff.py.

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. Benchmarks show they're 15–26x faster than their pure-Python equivalents, but they're not connected to the commit path today. They're registered in pyproject.toml's ext-modules, so they get built as part of uv sync.

Real numbers: what's actually faster

Summarizing the benchmark results in docs/parser_benchmark.md:

  • For small delta blocks (a few hundred bytes), the difference between parsers/diff engines isn't really noticeable — well within noise.
  • The gap widens as blocks get bigger (1.6KB → 92KB). That's mostly about block parsing rather than the diff engine itself, but the same underlying pattern — "the gap widens on large input" — applies to diff engine choice too.
  • Cython porting realistically buys 5–10x over pure Python, mostly by eliminating Python bytecode dispatch overhead in the inner loop.

So what should you actually use

  • Keep using what's there. StreamSequenceMatcher is already proven on the production path, and for ordinary line-level text edits, the practical difference from a minimal edit script is negligible.
  • The Myers family (especially the Cython versions) starts to matter when you have a specific need for a provably minimal edit script, or you're recomputing a large batch of deltas offline.
  • If you want to wire in a new diff algorithm, tools/bench_diff.py already has the comparison harness — add your case there and measure before deciding anything.

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