halostatue / diff-lcs / 42737450916

95%

push

github

feat: Speed up diff, sdiff and lcs with identical output

`Diff::LCS::Internals.lcs` (Hunt-Szymanski) is where `diff`, `sdiff`, `lcs`
and the traversals spend most of their time. Its output is unchanged, element
for element; only the work done to reach it changes:

- Positions of an element are visited in descending order, so each lands in a
  threshold slot no higher than the previous one. A run of positions landing
  in the same slot only keeps its smallest, found with a binary search, and
  records one link instead of one per position. On word-level diffs of source
  files, this skipped 304 million updates out of 305 million.

- The threshold search gallops down from the previous slot instead of
  bisecting the whole range: a frequent element (a space, a blank line) mostly
  lands next to its previous position.

The threshold check discussed in #72 and #78 becomes redundant: the run
skipping subsumes it.

Around the core:

- A plain String sequence is read once with `String#chars`: `String#[]`
  allocated a new String on every access, several times per element.
  Subclasses keep going through their own `[]`.

- `traverse_balanced` compares two booleans with `if`/`elsif` instead of
  `case [a, b]`, which allocated up to four Arrays per changed element.

- With their default callbacks, `diff` and `sdiff` build their result straight
  from the LCS instead of traversing it with events: `diff` no longer
  allocates a `ContextChange` per element only to drop it on matches, `sdiff`
  no longer allocates a second, simplified event per added or removed element.
  Callback instances, other callback classes and `ContextDiffCallbacks` keep
  going through the traversals, and a test holds both paths equal.

Related to: #78

Signed-off-by: Clément Joubert <czj@users.noreply.github.com>
Assisted-by: Claude Opus 5.5 [Claude Code]

528 of 675 branches covered (78.22%)

119 of 120 new or added lines in 2 files covered. (99.17%)

726 of 766 relevant lines covered (94.78%)

43909.08 hits per line