[darcs-users] unique features + exponential time issue

[Stephen J. Turnbull]

On 10/16/07, Alexander Staubo <alex at purefiction.net> wrote:
> On 10/16/07, Hilary Oliver <h.oliver at niwa.co.nz> wrote:
> > We have used darcs at my workplace for a couple of years now, and it has
> > proved to be an extremely useful tool.  In my opinion darcs was the
> > first system to make revision control so easy that only an idiot
> > wouldn't do it (and I could never return to a centralized system).   We
> > have, however, run into the infamous "exponential time" merge problem
> > twice, and when that happens it is effectively an insurmountable barrier
> > to most users.

It's insurmountable, period; you have to go outside of Darcs.  As far as I know,
nobody has yet claimed that the merge problem isn't fundamentally
exponential.  Note that that doesn't keep the simplex algorithm from being
the method of choice for linear programming in most cases even today.  There
are probably equally good algorithms for merging (sez the optimist in me).

> Darcs has many good things going for it; development momentum is not
> one of them, I am afraid. (If you're curious, nobody took up the
> bounty offer.)

I think that's unfair.  There's plenty of activity going on, but
mostly on routine
programming stuff: better testing, refactoring, using new features of GHC to
prepare for algorithmic revisions, etc.

Combinatoric explosion is just a hard nut to crack.  Again, look at linear
programming, which has the advantage of a number of simple canonical
examples of bad-to-worst case behavior.  As people come to understand
those examples, modern programs learn to avoid, mitigate, or at least warn
about them.  AFAIK, there are no simple examples of how to generate
exponential merge problems.

This might be something non-Haskell programmers could help with, in
fact.  If you do encounter an exponential merge, create partial repos both
in history terms and in terms of the file tree dealt with, until you've reduced
the problem to a "small" example.  Then the patch theorists can work on
exposing the features of the tree that lead to the exponential behavior.

(This is a way-off-the-wall suggestion, you probably should wait for comments
from David et al before spending time and effort on it!)