Re: [PATCH] write-tree performance problems

[Olivier Galibert <galibert@pobox.com>]

On Tue, Apr 19, 2005 at 10:36:06AM -0700, Linus Torvalds wrote:
> In fact, git has all the same issues that BK had, and for the same 
> fundamental reason: if you do distributed work, you have to always 
> "append" stuff, and that means that you can never re-order anything after 
> the fact.

You can, moving a patch around is just a chain of merges.

[Warning, ascii "art" ahead]

A merge is traditionally seen as:

1- Start with (A, B, C... are nodes/trees..., Pn are patches/changesets):

     /--P1->B
    /
   A
    \
     \--P2->C

2- End with:

     /--P1->B
    /
   A----(P1+P2)->D
    \
     \--P2->C

   where D is the merge between B and C with A as common ancestor.

But you can also see the result as:

     /--P1->B--P2--\
    /               \
   A                 D
    \               /
     \--P2->C--P1--/

i.e. you have two patch chains, one being A-P1->B-P2->D and the other
A-P2->C-P1->D.  I.e. you have the two patches P1 and P2 in two
possible patching orders.  But you can do even more amusing.  Start
with a patch chain:

   E--P3-->F--P4-->G

and merge E and G with F as common ancestor.  You'll then get H where
E--P4-->H--P3-->G.  I.e. you inverted two patches in your patch chain.
Or, if you keep H instead of G as your head, you removed P3 from your
patch chain.

Of course you can permute blocs of patches that way by having E, F and
G further away from each other.  You just increase the merge conflict
probability.

That is, I think, the way to do quilt/arch patch handling with safe
distribution and safe backtracing procedures.

  OG.