[darcs-users] Re: Darcs spins

[David Roundy]

On Tue, Oct 26, 2004 at 01:59:47AM +0200, Juliusz Chroboczek wrote:
> > BTW, I should also add, I've posted a file here that you can use to
> > reproduce the problem:
> > 
> > http://www.complete.org/~jgoerzen/problems.tar.gz
> 
> Yes, it appears to be the same bug as the one I'm hitting: darcs is
> spinning in commute_recursive_merger.

The problem is that when conflicts aren't resolved promptly, they can start
taking exponential time and space.  In your polipo test case, there are
definitely a lot of merge conflicts that have been fixed already, but the
new patch which is causing the spinning needs to be merged with 80 patches,
many of which have merge conflicts, so you're going to get another
conflict.

Making conflicts less painful is a definite goal post-1.0, but for the
moment the only solution is just to avoid them.  The trouble is that when a
conflict does happen, the only "correct" algorithms are exponentially
expensive in the number of primitive patches involved--at least in the
"bad" cases.
-- 
David Roundy
http://www.abridgegame.org