Ask HN: I just wrote an O(N) diffing algorithm – what am I missing?
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
};
});
}
What am I missing? I can't find other references to doing diffing like this. Everything just links back to that one paper.
63 comments
[ 3.5 ms ] story [ 134 ms ] threadNot sure about the diffing research though.
People tend to dismiss the statistics related to hash collisions because they think they are absolutely irrelevant to “real-life scenarios”.
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.
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.)
What mechanisms you have available depends on your implementation.
For example Cuckoo Hashing (https://en.wikipedia.org/wiki/Cuckoo_hashing) relies on having two different hash functions available.
And yes, for having something like a balanced tree, having a comparison would be useful.
In general, most hash functions work by consuming something like a stream of bits. So for your implementation it makes a lot of sense for the datatypes you want to use as keys to export a way to convert themselves into that stream, and leave the actual hashing into a fixed size as a detail of your hashtable.
That way you can eg do fall-back comparisons directly on stream of bits (including for equality). Or you can transparently support multiple hash functions.
Even in languages where the hashable interface works by giving you a method to spit out eg a 64 bit number only, you still have to map that number to one of your buckets. So for your fall-back, you can choose a different mapping.
If you have a second (or a third, or a fourth...) hashing algorithm, then make it hash tables all the way down. At the end, you still need some data structure to store hash-colliding values. And if so, what other structure could you possibly use besides a list (linked-, array-, etc.) ?
Why? You can have just two layers: the primary hash table and your buckets are made up of one small secondary hashtable each. If there's a collision in the bucket hashtable, pick a now random hash function for that bucket and re-hash everything in the bucket.
If that fails after trying a few times, pick a new random hash for the primary hash table and consider resizing.
I bet you can make that scheme workable in O(1) expected amortised time for inserts and lookups.
Cuckoo hashing (https://en.wikipedia.org/wiki/Cuckoo_hashing) is a related idea: you just have to hash functions. If you had three elements that collide for both hash functions each, you just re-hash your entire table.
(From Wikipedia:)
> When a new key is inserted, and one of its two cells is empty, it may be placed in that cell. However, when both cells are already full, it will be necessary to move other keys to their second locations (or back to their first locations) to make room for the new key. A greedy algorithm is used: The new key is inserted in one of its two possible locations, "kicking out", that is, displacing, any key that might already reside in this location. This displaced key is then inserted in its alternative location, again kicking out any key that might reside there. The process continues in the same way until an empty position is found, completing the algorithm. However, it is possible for this insertion process to fail, by entering an infinite loop or by finding a very long chain (longer than a preset threshold that is logarithmic in the table size). In this case, the hash table is rebuilt in-place using new hash functions: [...]
You say:
> And if so, what other structure could you possibly use besides a list (linked-, array-, etc.) ?
Any datastructure you feel like. You can also use a balanced search tree, if you want to. See eg https://en.wikipedia.org/wiki/Hash_table#Separate_chaining_w...
That can be bad for memory locality, especially if you outgrow your main memory (or just various smaller caches before that.) All without changing the O(1) w.h.p. asymptotics.
Merge sort will mostly just work, because all its memory access patterns are sequential. Hashtables would need to pay for seeks all the time.
So O(n log n) mergesort would be faster than O(n) hashtable approach in this case.
(There are ways to improve the absolute running time further compared to these naive approaches.)
Python's old hashtables used to be good enough for most practical uses; but when the input data was controlled by an adversary, it was easy to run a Denial of Service attack.
See https://bugs.python.org/issue13703 They started randomising the hash function at runtime.
Hashtables can be made to run in O(1) with arbitrarily high probability for insert and lookup, if you are willing to be very careful with the implementation, and willing to endure slightly worse constant factors in some cases. (Of course, it also depends on what model of computation you are using. At some scale your keys have to grow like O(log n) of the number of elements, just so that you can distinguish all elements. But we usually abstract away from that.)
But yes, just programming any old hashtable doesn't magically give you O(1) performance, you need to work for it.
I've been looking through a little bit more literature and it's clear to me that my implementation as it stands is not equipped to solve the Longest Common Substring problem [0]. Right now it's too greedy. I think with a tweak it could.
I think I'm mostly just surprised because when I sat down at my computer today, I had the impression that diffing was a "hard problem" -- to be able to implement something that (apparently) works in a short timeframe made me feel as though I did something wrong. (I have this code running in a staging environment now with a code editor, and it seems to be working smoothly and as expected.)
[0] https://en.wikipedia.org/wiki/Longest_common_substring_probl...
A sandwich means you have a slice of bread on the upper side.
I appreciate that in the typical case this won't happen, but big O denotes limiting behaviour, which in this case in O(N^2) or O(N log N) depending on your hash map implementation.
Finding any diff is not really the problem.
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_probl...
Not that I have any particular expectation that this algorithm does unexpectedly well at that.
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.
Consider the following sequences (here each letter represents a line).
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.
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.
E.g https://en.wikipedia.org/wiki/BLAST_(biotechnology)
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
Same this for unix diff (unless you specify the commandline flag to find shortest):
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/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.
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/frame...
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...
Love this post by the way, wished we would see more of these on HN.
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:
This is actually pretty compact as diff implementations go and would probably be a reference for implementing diff in JS.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. :)
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.
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.
I think this is a bit pedantic. React computes what is essentially an edit path from one tree to another, so yes, it is computing diffs for all intents and purposes. That said, you're right that implicit and explicit key matching are not only for optimizations; they're for persisting state as well.
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.
1. delete left
2. insert right
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...
By contrast, graphs can have significantly different relationships between nodes and edges, for instance, with sparse vs. dense graphs.
One could construct a situation in which file size inputs are varying related to each other in some O(...)-significant way, but it would be very strained, especially in the context of a diff algorithm (why are you trying to diff things significantly different in size at all?). You can fiddle with almost any O(...) pronouncement that way, e.g., "adding two integers isn't O(1)". True enough, but generally, more detail then we are looking for.
There is valuable information in running time being linear in the size of both files. You could define n as the combined size if you wanted to, but that could be confusing.
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.