need help optimizing a function

[Andrew J Bromage]

G'day all.

On Wed, Oct 09, 2002 at 02:29:26PM -0400, David Roundy wrote:

> I get a speedup of about a factor of 6 for the test files I was using (of
> course, this would depend on file size), and find that now only 2% of my
> time is spent in that function.  I'm still something like 100 times slower
> than GNU diff, so I think (hope, certainly!) there's still room for more
> improvement (another day).  I'm sure I'll have more questions in a few
> days, once I've tracked down what the new bottlenecks are.

If you understand logic languages, you might want to look at the diff
implementation which I wrote for the Mercury distribution:

	http://www.cs.mu.oz.au/research/mercury/

It's pretty close to GNU diff in speed.  In fact, it was
indistinguishable on every test case I could think of.

There are, two main differences to what I could gather from your 
implementation.

First thing was that I noticed that a lot of time was being spent
doing string comparisons.  I inserted a pre-pass which mapped strings
to (unboxed) integers with the constraint that the integers are equal
if and only if the strings are equal.  This also turned out to be
critical for implementing flags such as --ignore-space-change.

The other was I used a different algorithm than you did:

	Eugene W. Myers. "An O(ND) difference algorithm and its
		variations." Algorithmica, 1:251-266, 1986. 

I found it to be much faster than the O(n log n) algorithm, even
on cases where you would expect it to perform poorly (i.e. where
D is large), partly because the constant factors are really, really
low and because in the pre-pass you can optimise the case where you
have a number of consecutive lines none of which appear anywhere
else, which is typical for most uses of diff.

Cheers,
Andrew Bromage