[darcs-devel] Conflict fight exponential

David Roundy droundy at darcs.net
Sat Dec 29 19:23:49 UTC 2007


On Fri, Dec 21, 2007 at 02:10:15PM +0200, Pekka Pessi wrote:
> I've run some of my scripts triggering conflicts with
> darcs-2.0.0pre3. It seems to me that at least the conflict fight
> scenario is still exponential O(2^N). The times spent on resolving
> each new conflict in involved in the conflict fight grow like
> this:

I can confirm that as Nicolas suggested, the problem was that your script
ran using the old merge code, since the --darcs-2 flag wasn't given to
darcs initialize.  Adding that flag enables the code to run up to 200
conflicting patches (just by making all=`seq 0 200`) in about 44 seconds of
CPU time on my 700 MHz PIII).  I haven't worked out the exact scaling, but
this definitely does not look exponential.
-- 
David Roundy
Department of Physics
Oregon State University


More information about the darcs-devel mailing list