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

Ian Lynagh igloo at earth.li
Sat Mar 28 15:10:15 UTC 2009

On Thu, Mar 26, 2009 at 09:41:30AM +0000, Eric Kow wrote:
> 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?

I think it's a reasonable approximation.

If you have

    As Bs + As Cs

then you need to do (#Bs * #Cs) commutes.

Commutes are more-or-less constant time. There are some examples where
that isn't true, e.g. commuting a replace patch with a hunk (where you
need to see if the replace touches anything anywhere in the hunk).

If you have the pathological case

    Bs' As' + Cs' As''

then you need to do (#As * #Bs + #As * #Cs + #Bs * #Cs) commutes.

> 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?



More information about the darcs-users mailing list