[darcs-devel] announcing darcs 2.0.0pre1, the first prerelease for darcs 2

David Roundy droundy at darcs.net
Fri Dec 14 20:47:18 UTC 2007

On Fri, Dec 14, 2007 at 09:18:29AM -0800, David Roundy wrote:
> > Hmm, I have just tested the nested conflict issue. Now, the behaviour
> > is *much* better in darcs-2 than it has been in darcs one. I have
> > modified Pekka Pessi's misery.sh (from [darcs-users] unique features +
> > exponential time issue) to compare darcs with darcs2. In current
> > stable, it gets stuck for good around depth 7 or so. With --darcs-2
> > repos, it manages to get through to 19 but slows down considerably
> > there.
> > 
> > 15: 0m10.757s
> > 16: 0m24.504s
> > 17: 0m48.363s
> > 18: 1m46.241s
> > 19: 3m52.970s
> > (I have killed it at this point.)
> Hmmm.  I'll do some profiling and see what turns up.  Darcs is certainly
> going to slow down for deeply nested conflicts, but we may be able to do
> better.  Towards the end, I was pretty much exclusively focusing on getting
> the semantics right, with little or no thought of efficiency (apart from
> trying to ensure no worse than quadratic space use for a single conflicted
> patch).

Okay, I've found a couple of really stupid bits of code, and this goes a
lot faster now.  The "17" pull took under three seconds, and that's with
profiling running.  Fortunately (and perhaps unsurprisingly) the issue was
largely with the "easy" parts of the algorithm.  Well, one change (that
gave a 50% drop in time used) was a patch sequence comparison where we
didn't check first for the quick case in which the two sequences had
different lengths.  The other change, which made a much bigger difference
was being smarter when working out the possible sequences of
non-conflicting patches that led to a conflict.  In my defense, this code
was written just a few weeks before the prerelease darcs 2, while I was
working on a grant proposal...

Anyhow, it'll be a couple of hours before tests are passed and changes are
pushed, but then I'd appreciate it if you'd take another look at this! (I
could do it myself but right now I think I need a break... and it's far
easier to motivate myself to fix a problem pointed out by someone else than
to look for said problem myself.)

And thanks again for running these timings (and your helpful commentary,
which kept it interesting...)!
David Roundy
Department of Physics
Oregon State University

More information about the darcs-devel mailing list