[darcs-users] revert slowness

[Andrew Pimlott]

On Sat, Sep 25, 2004 at 09:46:37AM -0400, David Roundy wrote:
> On Sat, Sep 25, 2004 at 02:56:19AM -0400, Andrew Pimlott wrote:
> > I took a stab at reproducing the conflict slowness reported by Lee
> > Cantey, and ran into slowness in revert.  I was trying to simulate the
> > case of merging a small change with a large "reindent" change.
> 
> The problem here is in the LCS (longest common substring) algorithm used.
> (And this is distinct from Lee's problem.)  The trouble is twofold.  First,
> I use a "real" LCS algorithm, while GNU diff (for example) uses only an
> approximate LCS.

I should have clarified that the following operations are relatively
"fast":

- whatsnew on a large (10000 line) working diff
- revert on a large working diff
- resolving the conflict in my example in darcs pull
- reresolving with "darcs resolve"

Also, whatsnew after coflict resolution in my example took 36
seconds--bad, but not nearly as bad as revert.

> Then secondly, the particular LCS algorithm I used is O(nlogn) when all
> lines in the files are unique (i.e. appear only once in each file), but is
> O(n^2logn) in the limit where a small finite set of lines are used, which
> is the limit that your test case stresses.

So I don't believe this is the only factor involved--something is making
revert take four times as long as whatsnew in the conflict example.  But
maybe a factor of four is not important when it's already this slow.

> > I don't know if this is important in practice, but I thought it could
> > provide a clue to Lee's issue.
> 
> Mostly, I suspect that this isn't much of a problem in practice.  Usually,
> the fraction of lines in a file that are repeated is pretty small.

Probably right.

Andrew