Patch Set 2:

Hi,

from the performance measurements you posted histogram
diff maybe also a good candidate for native git. I bet that's
on your list, right.

Without further improvements on patience diff histogram diff
seems to be a better choice. Having only one diff algorithm to
maintain/bugfix/improve would be a benefit. But maybe these
improvements will bring the extra performance boost to let
patience diff survive.

>  > Now we have a fallback algorithm which works with O(N^2) and there
>  > is still MyersDiff working with O(ND).
>
> I haven't analyzed the running time of either implementation yet,
> but lets give it a shot... they are nearly identical.

I also have not analyzed runtime of HistogramDiff (or PatienceDiff)
but your commit messages said HistogramDiff works in O(N^2). That's
why I assumed you calculated it already.

...
> Our memory usage is O(AN + D) in either algorithm, as we build a
> hash table of size AN to hold the elements of A, and use D memory
> to store the edits and the stack during recursion.

Thanks for the long explanation about runtime here. Not only that I
understand runtime behaviour better was also a good explanation
about how the algorithm really works (the javadocs often show only
purpose of single methods, but this text solved also some misunderstandings
about how all the pieces work together).


> I think Myers O(ND) algorithm has better worst case performance.
> Given the analysis above we both agree that HistogramDiff would be
> O(N^2 * D) if the hash function produced a high rate of collisions
> for the input sequence, Myers algorithm doesn't care.

Yes, I do agree on O(N^2 * D)

>  > we can't decide easily in HistogramDiff when to switch to our
>  > fallback
>
> Correct, and is why it doesn't have a fallback.  By the time we

I do see this as a minor problem. I know we are on very theoretical
ground here and normal source code diffs will not be a problem here.
But: what can happen will happen and the worst diff I can imagine is
one which simply doesn't return. O(N^2) compared to O(ND) can lead
to a basically not returning HistogramDiff while Myers works "only" for
minutes. Maybe some heuristics about our
histogram can trigger fallback here. Is ist really ok to do Histogram-Diff
if all lines have same occurence count? If the best line is occuring on
20% of the overall lines? Something like that.