[darcs-devel] Conflict fight exponential

[Pekka Pessi]

2007/12/29, David Roundy <droundy at darcs.net>:
> 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.

I added the --darcs-2 to init and put, and the times look much more
promising. Without conflict fight the times seem to grow
exponentially, but the exponent is now something like 1.05 or 1.06,
iow. the algorithm times O(1.05^N).

However, there was a bug in the script so that it did not generate a
conflict fight with --darcs-2. When I fixed script so that it would
create fighting conflict at each round I got as far as the 8th
fighting patch:

user	0m0.072s
user	0m0.068s
user	0m0.052s
user	0m0.048s
user	0m0.120s
user	0m0.452s
user	0m3.072s
user	0m22.269s
user	3m4.060s

Exponential with base something like 7.

The fixed script is attached, please see if I'm doing something wrong there...

-- 
Pekka.Pessi mail at nokia.com
-------------- next part --------------
A non-text attachment was scrubbed...
Name: conflict-fight
Type: application/octet-stream
Size: 2492 bytes
Desc: not available
Url : http://lists.osuosl.org/pipermail/darcs-devel/attachments/20080102/5f692ffa/attachment.obj