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
I've been impressed with code written by Fable in my testing:
Difftastic: found small optimisations in a hot loop I'd already profiled extensively. Helped me prototype Dijkstra to A* too (hard to find a good heuristic).
Garden: Found some real bugs in my simplistic typechecker.
Today I learnt that A* doesn't work for an arbitrary non-planar graph, you need additional structure:
https://stackoverflow.com/q/26568552/509706
This matches my experience with difftastic so far. The graph is non-planar and my best heuristic only matches Dijkstra perf in typical cases.
I've started playing again with A* search instead of Dijkstra for difftastic. So far it's only saved me visiting 3% of graph nodes, which is negligible.
A* works best when you have a good heuristic, but finding a good heuristic is hard. Currently:


