Patch Set 2:

Christian wrote:

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

Junio and I talked about that yesterday for a few minutes.  If I
can magically create more time, sure, I'd love to try porting it
over to C and see if its worthwhile there.

 > 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.

I'm starting to agree with your sentiment here.  The two are so
close in performance that it might be better to just have the one
HistogramDiff implementation to maintain.  I didn't expect that to
be the case.  Its good to be proven wrong.

 > >  > 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.

I assumed it was O(N^2) because of that compare all locations part
during the scan of sequence B.  But I hadn't put any real thought
into it beyond that.

 > > 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'll have to elaborate more in the class Javadoc then... especially
if we rip out PatienceDiff and keep HistogramDiff instead.

 > 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.

Well, right now our MyersDiff implementation has a bug where it
will never complete for certain inputs.  I suspect a logic error
in the implementation.  :-)

But yes, a O(N^2 * D) worst-case running time might never produce
results within a reasonable time bound, while an O(N * D) algorithm
still would.

One trick we do within DeltaIndex (the binary delta compression code)
is to limit the chain length within a hash bucket to a constant
number.  If a block occurs within the input more than 64 times,
we punt and drop all of the subsequent locations in the stream.
That converts the algorithm from O(N^2) to O(N * 64), and gives us
a nice linear running time, at the expense of a potentially larger
delta instruction sequence.

It might be acceptable to do the same thing with HistogramDiff: if
any chain is over 64 elements, cut the chain off.  Since we use only
the LCS from the fewest occurrance count chain there is no damage
to the result provided, that the best LCS for the current region
is actually centered around something with less than 64 occurrances.

If the fewest occurrances was actually this limit (or higher),    
we could recognize that and switch algorithms.

 > 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.

Yea, what you said.  :-)