Patch Set 2:

Shawn wrote:

 > Christian wrote:
 > > 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.
 >
 > 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.

I tried doing this last night.  The RawText hash() implementation
is horrible.  IIRC its one of DJB's function for strings, and its
producing a ton of collisions for a JGit source file.

A chain length of 64 elements with the same hash code is too short;
HistogramDiff has to give up during the first step of scanning A
because too many elements fell into the same hash bucket.

I tried replacing the element with the highest occurrence count in
the chain, but this causes some thrashing as very common elements
are discarded and then put right back.  The side effect is a common
element can be mistaken as unique in A because we threw away its
prior occurrence counter when the chain got too big.

So putting a limit on the scan+insert of A into the hash table
seems to be a challenge.  If the hash function performs poorly for
our input, we're stuck with an O(AN^2) insertion time.

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

This turned out to be easy; during the scan of B we just have
to initialize the LCS counter to the maximum chain length, and
the scan would automatically avoid any elements with a higher
occurrence count.

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

But we're still O(AN^2) during insertion of A into the hash table.  
We can't avoid that horrible running time when fed a poor hash.