Hi,
first of all, hats off for the progress you have made!
David Roundy <[EMAIL PROTECTED]> writes:
> The future of darcs is in the darcs-2 repository format, which features a
> new merge algorithm that introduces two major user-visible changes
>
> 1. It should no longer be possible to confuse darcs or freeze it
> indefinitely by merging conflicting changes. However, this feature
> '''needs to be tested''', so please, do your worst, and let us know how
> darcs can handle it!
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.)
Much better than darcs 1:
1, 2, 3, 4 all take around a second.
5: 0m9.520s
6: 5m11.640s (~300s)
7: (killed)
Here go the (rough) conflictor sizes:
12:06:08 | [EMAIL PROTECTED]:/tmp/misery-4005/R2 -> for i in `seq 0 19`; do
darcs changes -v -p p$i$ | wc -l; done
11
14
26
52
87
131
184
246
317
397
486
584
691
807
932
1066
1209
1361
1522
1692
So how it appears, the conflictor size is ~quadratic in conflict
nesting depth? Time is another matter, as from depth 15 on, it seems
to be somewhere around 2^{depth}. However, the darcs 1 timings much
more resemble double exponential than a simple one (ie. 2^2^{depth}).
Great!
Now the question is, what does this mean for darcs in practice. If
people are headstrong enough, they will eventually reach the nesting
depth of 15 or more and start to get significant slowdowns. How much
is this a theoretical problem and how much it is a practical one, I do
not know. However, the progress indicator work I have read somewhere
about may further mitigate this problem.
Another one could be printing a warning when one is reaching a
"dangerous" size and number of conflictor patches. However, in fact,
what I do not know is, whether an alternative conflict resolution
scheme (one that could gather more information than just diffs) will
further reduce the size (and possibly amount of) conflictors generated
here.
Yours,
Peter.
--
Peter Rockai | me()mornfall!net | prockai()redhat!com
http://blog.mornfall.net | http://web.mornfall.net
"In My Egotistical Opinion, most people's C programs should be
indented six feet downward and covered with dirt."
-- Blair P. Houghton on the subject of C program indentation
_______________________________________________
darcs-devel mailing list
darcs-devel@darcs.net
http://lists.osuosl.org/mailman/listinfo/darcs-devel
