Patch Set 6: (5 inline comments)

FWIW, I'm still not done speeding up PatienceDiff.  I think we can do even better than we are doing right now.  Some of the ideas may even be leveraged back into MyersDiff.  I just haven't thought about doing that yet because its still a big ugly black box to me.

Coming up with D=793 on PatienceDiff when MyersDiff comes up with D=4210 is because we are only looking at unique common lines.  When PatienceDiff cannot find a unique line in a region, it just bails and does a giant replace, while MyersDiff continues to look for context.

If we plugged in MyersDiff at this point as a fallback, we should get D=4210 again.  But I'm not sure that is the best immediate fallback strategy.  We could instead build a histogram of the common lines and pick the least duplicated common lines and try to find the LCS around those.  By using least duplicated we should still avoid nasty cases like "\t}\n" as being an anchor point for the matching, but would still be able to break out of the degenerate case.

Thus far I have done only very limited testing of PatienceDiff on real-world input.  I did wire it into DiffFormatter and run `jgit log -p` to scan through the diffs.  I didn't see any obvious variations from MyersDiff, but I don't think recent JGit history is a poster child for where patience diff is supposed to produce more readable results.

In case you didn't know, my motivation behind PatienceDiff was to find another solution to Gerrit issue 487 [1], infinite loop in MyersDiff.  Unfortunately patience diff really fails on single-character sequences (due to insufficient common unique points), but the algorithm is trivially simple and easy to prove that it will terminate.  I'm probably going to try and do a word-level variant of RawText and see if we can get a word-level thing to work better under PatienceDiff for the intraline difference coloring in Gerrit.

Also, MyersDiff is really slow for Gerrit.  For some patches it takes 2.5s to display the page.  Of that 2.5s, 2.450s is spent in MyersDiff doing the intraline work.  Getting a faster algorithm under it would be nice.

[1] http://code.google.com/p/gerrit/issues/detail?id=487