miniblog.

← Back to all posts
Jul 12, 2021 at 07:02
Spent some time today trying to replace difftastic's implementation of Dijkstra's algorithm with A* search. I got a working implementation that passes tests: https://github.com/Wilfred/difftastic/commit/9a271169f68cdb678efe2035f5a4e45daeb6533d but sadly it's no faster. My slowest files still take 1.5 seconds with similar memory.
Rewrite graph search as A* · Wilfred/difftastic@9a27116
Rewrite graph search as A* · Wilfred/difftastic@9a27116
a structural diff that understands syntax 🟥🟩. Contribute to Wilfred/difftastic development by creating an account on GitHub.

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...