Difftastic update: I've rewritten the tree diffing logic to use Dijkstra's algorithm similar to Autochrome.
It works amazingly well! Note how it recognises both parent and children unchanged nodes in the lisp example. You can even see me refactoring Rust to use if-let.
miniblog.
Related Posts
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!
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.
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.


