3 ms·

IMHO the limiting factor can be described as "semantic density". If you look at non-LCS diff algorithms like patience diff [1] and think about where it falls do

IMHO the limiting factor can be described as "semantic density". If you look at non-LCS diff algorithms like patience diff [1] and think about where it falls down, its on cases where its very arguable that the code is poor - too much duplication therefore low semantic density. I think (and am attempting to further this at work for non-code) that the effective key is to do something like patience diff on characters but looking at the context of the individual characters when determining whether they are unique. The benefit here is that you don't need to know about the parse tree, don't depend on special characters to delimit elements (newlines), and don't get LCS type diffs that aren't based on any sort of semantic intuition beyond that the minimal change is probably what was meant. [1] http://bramcohen.livejournal.com/73318.html http://bramcohen.livejournal.com/73318.html

cpeterso 15y ago
I've read about Patience diff, but could not find good, real-world examples where LCS diff choked but Patience succeeded. Just last week, however, I had a small code change that produced a crazy diff that would give my code reviewer an unnecessary headache. I tried Patience diff on a whim and it produced a clean diff. Admittedly, it just entirely -removed the old code block and +added the new one, but at least it was readable.
- tsewlliw 15y ago
  I work on a code review tool, and we've been shipping patience diff for a few years now, and it has really cut down on complaints about the resulting diff being incomprehensible, and on the one or two occasions people have complained its been really easy to point at the data explain why - and that has always been because there was a "missed opportunity to write better code" or a big pile of copy-pasta. I know its sort of a silly argument to make, but LCS's algorithmic intiution leaves me cold.
  - cpeterso 15y ago
    Very interesting. Is patience diff your tool's default algorithm? Do you support diff algorithms (perhaps for different file types) other than patience or LCS?
    - tsewlliw 15y ago
      If by default you mean only available, yes :) Non-code review is really what is driving my delving into non-crlf delimited diff elements. Breaking prose into big enough chunks to diff well and still find small copies is my current target. Once it works for prose I might try to use it on code. I've been itching to figure out how to combine perceptual hashing, computer vision like opensurf, and stable marriages to do something really interesting for image diffs, but until I can shed some less sexy responsiblities I don't think I'll get to play with that.

cpeterso 15y ago

I've read about Patience diff, but could not find good, real-world examples where LCS diff choked but Patience succeeded. Just last week, however, I had a small code change that produced a crazy diff that would give my code reviewer an unnecessary headache. I tried Patience diff on a whim and it produced a clean diff. Admittedly, it just entirely -removed the old code block and +added the new one, but at least it was readable.

tsewlliw 15y ago
I work on a code review tool, and we've been shipping patience diff for a few years now, and it has really cut down on complaints about the resulting diff being incomprehensible, and on the one or two occasions people have complained its been really easy to point at the data explain why - and that has always been because there was a "missed opportunity to write better code" or a big pile of copy-pasta. I know its sort of a silly argument to make, but LCS's algorithmic intiution leaves me cold.
- cpeterso 15y ago
  Very interesting. Is patience diff your tool's default algorithm? Do you support diff algorithms (perhaps for different file types) other than patience or LCS?
  - tsewlliw 15y ago
    If by default you mean only available, yes :) Non-code review is really what is driving my delving into non-crlf delimited diff elements. Breaking prose into big enough chunks to diff well and still find small copies is my current target. Once it works for prose I might try to use it on code. I've been itching to figure out how to combine perceptual hashing, computer vision like opensurf, and stable marriages to do something really interesting for image diffs, but until I can shed some less sexy responsiblities I don't think I'll get to play with that.