Fascinating post on how diff algorithms actually work: https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ (multiple possible implementations!)
miniblog.
Related Posts
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!
One nice thing about quadratic algorithms: if you can reduce your N, you get a really nice speedup.
I've started seeing 'ort' merges in my git operations, which can apparently be hundreds of times faster than the previous merge algorithms: https://www.phoronix.com/scan.php?page=news_item&px=Git-2.33-Released