miniblog.

← Back to all posts
Dec 6, 2016 at 21:47
I'm particularly impressed with the quantitative fitting process used to tune git's diff algorithm in 2.11:
diff: improve positioning of add/delete blocks in diffs · git/git@433860f
diff: improve positioning of add/delete blocks in diffs · git/git@433860f
Some groups of added/deleted lines in diffs can be slid up or down, because lines at the edges of the group are not unique. Picking good shifts for such groups is not a matter of correctness but de...

Related Posts

Mar 10, 2025 at 07:03
12
Spent a bunch of time learning about text diffing algorithms this evening. "Myers Algorithm" refers to a specific paper written by Eugene Myers, and he published faster algorithms later!
LCS Algorithms
LCS Algorithms
a structural diff that understands syntax 🟥🟩. Contribute to Wilfred/difftastic development by creating an account on GitHub.
Nov 7, 2023 at 01:35
There's a class of performance bugs that you can feel. Today I inadvertently implemented "Schlemiel the Painter's algorithm", and it's obvious: performance was great at first, and then it gradually deteriorates.
Jan 15, 2023 at 09:21
Today I learnt about a cunning trick used by GNU diff to make Myer's algorithm faster: https://github.com/mitsuhiko/similar/issues/15 If you do an initial pass to find items that only occur on one side, you can discard them before diffing! They'll always be shown as changed.
Implement Myers Heuristics · Issue #15 · mitsuhiko/similar
Implement Myers Heuristics · Issue #15 · mitsuhiko/similar
GNU diff and others have some internal heuristics to bail if there are too many changes. There are basically two optimizations: Discard lines which are completely distinct between two files: this h...