7 ms·
Ask HN: I just wrote an O(N) diffing algorithm – what am I missing?
Hey folks,
I've been building a rendering engine for a code editor the past couple of days. Rendering huge chunks of highlighted syntax can get laggy. It's not worth switching to React at this stage, so I wanted to just write a quick diff algorithm that would selectively update only changed lines.
I found this article:
https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/
With a link to this paper, the initial Git diff implementation:
http://www.xmailserver.org/diff2.pdf
I couldn't find the PDF to start with, but read "edit graph" and immediately thought — why don't I just use a hashtable to store lines from LEFT_TEXT and references to where they are, then iterate over RIGHT_TEXT and return matches one by one, also making sure that I keep track of the last match to prevent jumbling?
The algorithm I produced is only a few lines and seems accurate. It's O(N) time complexity, whereas the paper above gives a best case of O(ND) where D is minimum edit distance.
function lineDiff (left, right) {
left = left.split('\n');
right = right.split('\n');
let lookup = {};
// Store line numbers from LEFT in a lookup table
left.forEach(function (line, i) {
lookup[line] = lookup[line] || [];
lookup[line].push(i);
});
// Last line we matched
var minLine = -1;
return right.map(function (line) {
lookup[line] = lookup[line] || [];
var lineNumber = -1;
if (lookup[line].length) {
lineNumber = lookup[line].shift();
// Make sure we're looking ahead
if (lineNumber > minLine) {
minLine = lineNumber;
} else {
lineNumber = -1
}
}
return {
value: line,
from: lineNumber
};
});
}
RunKit link:
https://runkit.com/keithwhor/line-diff
What am I missing? I can't find other references to doing diffing like this. Everything just links back to that one paper.
- pratchett 7y agoYour approach is called hash join in databases. Not sure about the diffing research though.
- hhmc 7y agohash map worst case insertion/search is O(N) so this is potentially worst case O(N^2). IIRC a typical implementation would be more likely to be O(N log N) for some high log factor in the limit, but still worse than O(ND). And this is before we account for the fact that hashing a line probably has an implicit factor of D in it.
- heavenlyblue 7y agoI have just been interviewing at several companies that have highly technical interviews in London, and about 80% of the interviewers who asked questions about hash maps expected me to assume that hashmaps imply constant-time lookups. People tend to dismiss the statistics related to hash collisions because they think they are absolutely irrelevant to “real-life scenarios”.
- Shoop 7y agoThis is because hash tables resize when they are filled with too many elements. Assuming a suitably good hash function, this gives O(1) lookup w.h.p. and insertion stays O(1) amortized. The mathematics of hash collision probabilities is factored into the resizing thresholds. Many standard library implementations of hash tables (such as rust's) also include special hash functions which are salted with random values to prevent DoS attacks which create large numbers of hash collisions.
- eru 7y agoIf you are really paranoid, you can even use a salted cryptographic hash function. But the constant factors for those are usually worse than for simpler salted hashes, so they are not worth it for hashtables. Your fallback for collisions could also be something with O(log size_of_bucket) runtime, instead of linked lists. But again, when you don't have many collisions, that's going to be slower than something simpler. (I half remember a result that if you tune your parameters right, you can get away with a hashtable that only has enough size for storing one element in each slot; and if a collision happens, you replace that element with a tomb stone, and store put the elements involved in a single global linked list. Basically, for that to work you need to keep your total number of collision smaller than a constant with high probability.)
- LgWoodenBadger 7y agoOnce your hashes collide, you have no other mechanism to use besides equality. How can you use something other than a list in order to find the actual value? This being for the general case where items don't have an "order/rank/sort" property between them.
- ysleepy 7y agoDoes this algorithm find the shortest edit script? Finding any diff is not really the problem.
- mattb314 7y agoThis is basically the issue. If a single line from the bottom of left is present at the top of right, it will fast-forward all the way through left and fail to match anything else from right. The hard part with diffing isn't finding differences, it's deciding whether they're inserts, edits, or deletions.
- deleted 7y ago[deleted]
- keithwhor 7y agoNope! That's related to the Longest Common Substring Problem I think, I mentioned it in another comment [0]. Though I have a feeling you could find the shortest edit script with a few easy tweaks, I might check it out. I imagine the tweaks are going to make the the difference between O(N) and O(ND) though. The problem I had was that I just wanted a simple diff! It's for HTML rendering and not ultra complex at that: usually folks are only changing a few lines at a time, max, between any re-render. [0] https://en.wikipedia.org/wiki/Longest_common_substring_problem https://en.wikipedia.org/wiki/Longest_common_substring_probl...
- dllthomas 7y agoI think shortest is probably a good proxy if we can't find something better but I think in an editor "easiest to understand" is probably what's actually important. Not that I have any particular expectation that this algorithm does unexpectedly well at that.
- eru 7y agoYes. That reminds me of lossy image compression: the real goal is to find a representation that looks as close as possible to the input image to the human eye. In practice, we use proxies. Not all proxies are equally good. Eg just going by Hamming distance or L2 norm distance would be awful. Proxies that take more features of our visual system into account are going to fare better.
- GoodGOYIM 7y agowhor
- ridiculous_fish 7y agoDiffing means computing the longest common subsequence (LCS); the edit script is everything that's not part of the LCS. The proposed algorithm greedily finds a matching element. However it may be that it would be better to skip this element, and not incorporate it into your sequence. Consider the following sequences (here each letter represents a line). AAAB BAAA Where the first one is "left" and the second one is "right". The LCS is AAA. The minimal edit script from left to right is: 1. Insert B at beginning. 2. Delete B at end. The proposed O(N) algorithm finds B as the first matching line, and thereby exhaust `left`. So it finds the common subsequence of just "B" and its edit script is: 1. Delete 3 As at beginning 2. Insert 3 As at end which is longer.
- keithwhor 7y agoThanks! Yep, definitely not finding the LCS and associated edits with the current implementation. From my view right now, I'm basically going to have to use a suffix tree to efficiently find the LCS and go from there - which means it's likely that I'm just going to end up approaching Myers' algorithm.
- leshow 7y agoIs it subsequence or substring? Don't you want to find the longest common substring, i.e. contiguous block? I always understood subsequence to be non-contiguous.
- ruds 7y agoIt's subseqence. For instance, in ABXCDYEFGZ QARBCSTDEFG You want to find [Q]A[R]B(X)C[ST]D(Y)EFG(Z) ABCDEFG is the longest common subsequence, QRST are the additions and XYZ are the deletions.
- im3w1l 7y agoSince the problem has already been resolved, I'll go on a slight tangent and mention there are some very interesting probabilistic diffing algorithms invented by the bio-informatics people. E.g https://en.wikipedia.org/wiki/BLAST_(biotechnology) https://en.wikipedia.org/wiki/BLAST_(biotechnology)
- robertelder 7y agoI spent a bit of time learning the Myers Diff algorithm, (I made this page: https://blog.robertelder.org/diff-algorithm/ https://blog.robertelder.org/diff-algorithm/) Like someone else said, I think the key is that you're not getting the shortest edit script, you're just getting a edit script. Interestingly, even git's implementation of diff (which uses a variant of the Myers Diff algorithm) doesn't actually find the shortest edit script by default. It has a hard-coded heuristic that just quits early if it finds a 'good enough' solution: https://github.com/git/git/blob/master/xdiff/xdiffi.c#L143 https://github.com/git/git/blob/master/xdiff/xdiffi.c#L143 Same this for unix diff (unless you specify the commandline flag to find shortest): https://github.com/Distrotech/diffutils/blob/distrotech-diffutils/lib/diffseq.h#L255 https://github.com/Distrotech/diffutils/blob/distrotech-diff... Having said that, if you're still confident that you've made an improvement, you can port the function to python and try it out as a test case in my unit test file that I wrote when I developed my variant of the Myers Diff algorithm: https://github.com/RobertElderSoftware/roberteldersoftwarediff/blob/master/myers_diff_and_variations.py https://github.com/RobertElderSoftware/roberteldersoftwaredi... On that topic, I'm pretty sure my variant of the Myers Diff algorithm is actually slightly faster/uses less memory than the original (I'd be happy to be proved wrong). At least, I've had my blog post up for a few years and no one has corrected me, but then again, I think the original paper has a few mistakes/obvious flaws and it still has hundreds of citations and no one has written much about improvements.
- ridiculous_fish 7y agoNice work on your visualization! Thank you for rebutting the Fraser article; I came to the same conclusion as you (that Myers algorithm is in fact correct) but had never written it up. I wrote a vectorized Myers implementation for diffing binary files. Perhaps the most interesting aspect is the progress bar: it's not obvious how to create a monotonic progress estimate for Myers diff. https://github.com/ridiculousfish/HexFiend/blob/master/framework/sources/HFByteArrayEditScript.m https://github.com/ridiculousfish/HexFiend/blob/master/frame...
- robertelder 7y agoCool. You've got a fairly impressive following on that tool. I wish more people took an interest in studying these sorts of algorithms. Most people assume that some genius figured out the optimal way to do things years ago, but more often than not if you spent a few weeks focusing on a specific paper/algorithm, you'll come up with ideas for improvement (although it might not always be in the way you initially expected). Sometimes the improvement is just figuring out a better way to explain it and that in itself can lead other people to create breakthroughs. I think there are still a few improvements that could be done the the Myers algorithms. One specifically, is that I'm pretty sure it's tail recursive. You won't get any big O improvements off of that, but less stack space is still an improvement. Plus better cache locality. I'd work on some demos, but too many things to do these days...
- jacquesm 7y agoThis doesn't answer your question but you really should read up on Needleman-Wunsch for matching up strings. Love this post by the way, wished we would see more of these on HN.
- bodeadly 7y agoAh, no, the Myers algorithm is also known as the "Sortest Edit Script" and your algo does not follow the shortest path or produce a script (just -1 for mismatches). More specifically, it's not just something at the end appearing at the beginning causing skipping like others have pointed out. The skipping can happen in the middle. Consider the two sequences A B B C and B C A. Your algo will match the first Bs and then the Cs and skip the common B C together. Even if you could somehow make it work, it would be O(N) but note that with all of the split() and map() and array indexing, it starts to be more like O(N+NX) where X is that potentially non-insignificant overhead. Don't let me pooh-pooh you from trying but if you do give-in and use the Myers' algo, here's my C diff implementation: http://www.ioplex.com/~miallen/libmba/dl/src/diff.c This is actually pretty compact as diff implementations go and would probably be a reference for implementing diff in JS.
- keithwhor 7y agoThank you: I'll definitely reference this if (and when) the bottleneck becomes our diffing implementation, or if as part of the editing experience we want to be able to show diffs between files that aren't stored in git. Keep in mind that right now the implementation is for an in-browser code editor. The importance of the diff algorithm is primarily to quickly determine which HTML elements to re-render on a line-by-line basis. The changes a user makes between frames are at best single-grouping insertions / deletions (cut, paste, delete, insert). For a 2k LOC file, the render step (pre-diff) was on the order of 200ms: I was repopulating thousands of DOM elements every time a line was changed. Now it's at like 3ms, so under the 16.67ms frame cutoff. I'm floored by the responses here though, this has been super helpful! I knew I was missing something academic here. :)
- anonytrary 7y agoYou're most likely not getting a minimal diff, but it's highly likely that your diff is good enough for your use-case. React and most other similar VDOM libraries also fail to achieve minimal diffs, however, that's not necessarily a bad thing. Just because a diff isn't minimal doesn't mean it's wrong. The ideal trade-off (diff-size vs space-time characteristics) depends on the use-case. It might be more important for a VDOM library to obtain a good-enough diff in O(N) time, as opposed to an LCS in O(NM) space and time. Linear diffing for VDOMs works well, especially with heuristics and things like explicit and implicit key matching. Sometimes the asymptotic characteristics of a program are irrelevant if your system is bounded.
- victorNicollet 7y agoReact also doesn't need a diff to be of the "longest common subsequence" kind. For instance, the diff between "AB" and "BA" involves no insertion or deletion, just transposition, which React supports but traditional diffs don't.
- anonytrary 7y agoWhat you're talking about is called "implicit key matching" in React-speak. AFAIK it isn't implemented as a transposition, rather an "insert before" because the DOM API supports it directly. I have written a VDOM algorithm that relies only on swaps, deletions and insertions, but it doesn't map well to the DOM API.
- devit 7y agoReact doesn't compute diffs, and it would be wrong for it to do so since components are stateful, and so it matters how they are matched (the idea that VDOM diffing is just an optimization is a very common misconception). Instead, you just specify keys for elements (either explicitly or by index in the sequence) and it matches elements with the same key in the old and new trees.
- heavenlyblue 7y agoBut elements with ids and their attributes can be changed after a re-render and you need to sync those with DOM.
- terrelln 7y agoSlightly off topic, but one great way to diff is to compress the new file using the old file as a dictionary. Both zlib and zstd support this (but zlib is limited to a 32KB file). You can tune how much CPU you want to spend getting a better diff by adjusting the compression ratio, the compressor is well tuned for speed and is generally more efficient than a diffing algorithm, it can find repetitions in the new content, and you get entropy coding.
- andai 7y agoThat's really neat, do you maybe have any links on this?
- kazinator 7y agoI just found an O(M + N) diffing algorithm: $ my-diff yours mine --- yours 2019-10-28 15:11:07.150118090 -0700 +++ mine 2019-10-28 16:46:42.093923066 -0700 @@ -1,50 +1,75 @@ - yours - yours [...] - yours + mine + mine [...] + mine Spit out the diff and hunk header, then dump yours preceded by "- " and then mine preceded by "+ ".
- phinnaeus 7y agoThis is pretty great, the edit script is always two steps. 1. delete left 2. insert right
- jerf 7y agoThere's a non-trivial sense in which you'd be justified calling this O(1), inasmuch as the edit script "delete yours, insert mine" can be yielded up as an edit script without even reading "yours" or "mine", simply yielding "yours" and "mine" by reference. That's in a more abstract sense than something "diff" could take. However, with at most a slight change to "diff" (and I'm not sure it's even that, I think it may have this already I'm just not checking for an HN post), you can yield an O(1) "delete yours" and then insert mine, so it's O(N) without the M [1]. In UNIX terms you can just spec out "cp mine yours" as the edit script, which is O(1) from the perspective of the diff algorithm. Applying that script is O(N), of course, but generating it is constant. 1: Super pedants will note that O(N + M) isn't terribly meaningful here since adding two linear terms means you can reduce that to O(N) under the big-O rules. However, I've always like keeping the information like that in the O notation, in some sense precisely because O(N+M) is-equivalent-to O(N) in big-O terms, but if you have additional knowledge like for some reason, M is exponential in a term you care about you can generate the new big-O term that you care about. In graph theory, my professor tended to want to express O(edges) as O(nodes^2), but I always liked retaining the O(edges) because O(edges) yields useful information if you know you have a sparse graph, for instance, whereas O(nodes^2) removes that. To his credit, he never marked me down for it, which puts him ahead of a lot of professors and their personal preferences...
- syrak 7y agoO(N + M) is not equivalent to O(N) if you make no assumptions about the relative growths of N and M, that's why it's actually meaningful to keep both terms around. You can only reduce it to O(N) when N dominates M (M = O(N)).
- username90 7y agoAre we posting our homework on HN now?
- StreamBright 7y agoWhich school gives your the problem to implement a diffing algo as homework?
- username90 7y agoWhich doesn't?
- StreamBright 7y agoAll the ones I went to.
- ian0 7y agoNot sure about the rest of the folks on this thread but I was delighted to read through this and the comments.
- username90 7y agoSorry, I didn't realize that HN was full of people for which this thread was insightful. We really need to separate software engineers from software engineers. The side which mostly works on algorithms will find this thread mostly stupid or ignorant. The side which focuses on gluing together things will find it at the edge of their understanding and therefore both novel but understandable. Also just proves that we need algorithm interviews to separate the two. Note that I am not saying that gluing together things is easier or less important, just that it is another job so requires other skills and therefore it doesn't make sense to give them the same title.
- deleted 7y ago[deleted]
- victorNicollet 7y agoQuestion: why do you ensure that you are only moving forward? Does it matter, for line highlighting, that a line has moved up, or now appears twice?
- vince14 7y agoReact has absolutely nothing to do with that.