Patch Set 2:

> HistogramDiff will always produce the same results as a
 > PatienceDiff as long as the PatienceDiff always find uniqe lines.

Yes.  If PatienceDiff matches on an element, it means the
element is not only common, but is also unique in each sequence. 

For HistogramDiff that same element will have an occurrance count 
of 1 in sequence A, that is the lowest occurrance count possible,
and thus will also be within the LCS for HistogramDiff.

The only place HistogramDiff produces a different result is when  
sequence A has no unique elements, which means its minimum occurrance
count is at least 2.  Here PatienceDiff has to fallback to another
algorithm, while HistogramDiff will still try to generate something.

 > A PatienceDiff algorithm which fallbacks to HistogramDiff when
 > he finds no uniqe lines produces excactly the same result as if
 > you would use only HistogramDiff

Yes.  This is true because all of the passes where PatienceDiff
can produce a result are identical between both HistogramDiff
and PatienceDiff.  When PatienceDiff falls back to HistogramDiff,  
its doing so in exactly the same way that HistogramDiff would have
recursed on itself for that same region.

 > To some extend PatienceDiff is only a special case of the
 > HistogramDiff. The reason why we don't work always only with
 > Histogramm diff is the better performance of Patience diff.
 
Correct.  The optimized version of PatienceDiff (which I'm still 
working on) uses a smaller hash table and fewer steps for non-unique
elements.  This should improve performance avoiding elements that
are very common in source code (e.g. "\t}\n") and aren't very
interesting, while still allowing us to find the common but unique
elements quickly.

But as you can see by the performance posted in change
I3c3ec3abd24889faccd571d02c57331c907c0198 its only a small
improvement over HistogramDiff.  It almost doesn't seem to
be worth it, but it can be when summed up over multiple files    
within the same operation (e.g. to show a commit's full diff
or to merge two commits).
 
 > 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.
 
Lets use AN for the length of sequence A and BN be the length of
sequence B.  Myers' N is AN + BN.
 
The first step examines AN and stores it into a hash table.
This occurs in O(AN) time.  Each element is scanned once, and added
to the chain.  If we assume the hash function is reasonable, we have
nearly constant insertion performance, so the scan step is O(AN).  
If its horrible and gives lots of collisions, this scan is O(AN^2) 
as we consider all of the elements in the same hash bucket.

Once a position has been found for a single element, the
insertion cost is constant for both PatienceDiff and HistogramDiff.
In PatienceDiff we set a bit flag if the element already exists in
the table, otherwise we push it onto a list.  In HistogramDiff we 
push the element onto the head of a list, and increment a counter.
So the entire first step is O(AN)... or O(AN^2) if the hash sucks.


The second step scans BN and probes the hash table for each item.
This occurs in O(BN) time.  Each element is probed once, and again
the hash function determines if this is O(BN) or O(BN * AN) time.

For PatienceDiff we only have to consider unique elements, so the
compare cost is constant.

For HistogramDiff we have to compare to all matching locations,
so its O(AN * BN).  However I think we have a lower average running
time here because we won't consider an A chain that has occurrance  
counts longer than our current LCS segment.  As that approaches the
lowest occurrance count within A, the size of AN drops, and we get
closer to O(BN) time on average.  This is where PatienceDiff should
run better, it won't ever consider a location where AN > 1.

Once the LCS is found, we split the input around it and recursively
process AN/2 and BN/2 twice.  Each split is two Edits in the edit
script, and thus the number of splits we perform is Myers' D/2.
So we run O(D) recursive steps.

So assuming the hash function doesn't create a lot of collisions, 
we are around O((AN+BN) * D) or O(ND).  If all elements hash to
the same value (e.g. 0), yea, we're looking more at O(N^2 * D).
 
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.

Myers' paper states MyersDiff should be using O(ND) memory for the
O(ND) variant we have, but he also has a variant that uses O(N)    
space and O(N log N + D) running time.  I don't know how he gets  
the latter variant to work.

 > I guess the reason why we
 > don't have MyersDiff as last option (the third algorithm in the
 > fallback chain) are the following two reasons:
 
HistogramDiff doesn't support a fallback.  That is the primary   
reason.  :-)

 > real world tests show that it is with the expected size of sources
 > not worth the effort. Doesn't really bring performance benefits in
 > the real world.

I contend this is true, given the limited testing I have performed.

For line oriented inputs that are human written source files, the
current content hashes produce relatively few collisions, and there
are often a large number of unique or low occurrance count lines
we can anchor LCS searching around.  The hash function permits us
to find these points with relatively low effort, and we can get a
reasonable edit script by using those common points.
 
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.

 > 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
get around to concluding we have very few low occurrance elements,  
we've done the majority of the work we need anyway to find the LCS 
and split.  Switching over to MyersDiff on the recursion might not 
be an improvement at that point.