[darcs-users] darcs merging time in the absence of conflicts?

[Eric Kow]

Hi Ian,

I have a potentially silly question: is it fair to characterise
darcs-style merging in the absence of conflicts as being O(n * m) time,
with n and m being the number of uncommon patches on each side?  My
informal way of arriving at this characterisation of things is that we
can say the cost of commutation is constant (wrt # of patches, provided
no conflicts), and that the only work you have to do is to commute each
one of m patches past one of the m patches.  Is that the correct way of
looking at things?

Deep down, this is a marketing question.  I want people to have a
clearer picture of when the exponential merge problem will and will not
strike.  And part of this picture is knowing where it is NOT a problem,
and what exactly will happen in those cases.  To be clear, I do not
intend this to be flippant about this and say something like, 'oh, it
"only" happens when there are conflicts' as if it was just a corner
case.  Of course, conflicts are a problem and of course we need to keep
working on them, but I just wanted to remove the feeling of uncertainty
from darcs by pinning things down a bit better.

  http://www.ericsink.com/entries/merge_history.html

Ideally, we would also have a more precise characterisation of what
kinds of conflicts we think darcs-2 handles better than darcs-1, and
where things can blow up.

Thanks!

Eric

Background for not-Ian
======================
For the interested darcs merging works like this: you have two
repositories that have some patches in common, and some patches
that are in one repository and not the other.

  Repo 1 : c c c c c m1 m2 m3 m4
  Repo 2 : c c c c c n1 n2 n3

If repo 2 pulls from repo 1 (i.e. if we have to merge the repositories),
we simply have to invertthe patches on one side...

  Repo 2: c c c c c c n1 n2 n3 n3^ n2^ n1^

Slap on the patches from the other patches (which you can now do because
inverting the patches gets you back to zero)...

  Repo 2: c c c c c c n1 n2 n3 n3^ n2^ n1^ m1 m2 m3 m4

Commute the patches past each other

  Repo 2: c c c c c c n1 n2 n3 m1' m2' m3' m4' n3^' n2^' n1^'

Then remove the commuted inverses

  Repo 2: c c c c c c n1 n2 n3 m1' m2' m3' m4'

-- 
Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow>
PGP Key ID: 08AC04F9
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: Digital signature
URL: <http://lists.osuosl.org/pipermail/darcs-users/attachments/20090326/6c7da656/attachment.pgp>