Re: Comments on recursive merge..

[Junio C Hamano <junkio@cox.net>]

Linus Torvalds <torvalds@osdl.org> writes:

>> Another thing to consider is if it is fast enough for everyday
>> trivial merges.
>
> Hmm. True. The _really_ trivial in-index case triggers for me pretty 
> often, but I haven't done any statistics. It might be only 50% of the 
> time.

Just for fun, I randomly picked two heads/master commits from
linux-2.6 repository (one was when I happened to have pulled the
last time, and the other was when I thought this might be an
interesting exercise and pulled again), and fed the commits
between the two to a little script that looks at commits and
tries to stat what they did (the script ignores renames so they
appear as deletes and adds).

Here is what the script spitted out:

        Total commit objects: 3957
        Trivial Merges: 72 (1.82%)
        Merges: 225 (5.69%)
        Number of paths touched by non-merge commits:
                average 4.50, median 2, min 2, max 199
        Number of merge parents:
                average 2.00, median 2, min 2, max 2
        Number of merge bases:
                average 1.00, median 1, min 1, max 1
        File level merges:
                average 37.61, median 8, min 0, max 555
        Number of changed paths from the first parent:
                average 379.09, median 66, min 1, max 7553
        File level 3-ways:
                average 1.96, median 1, min 0, max 37
        Paths deleted:
                average 47.56, median 15, min 0, max 554

This counts what happened in individual devleoper's trees,
subsystem maintainer trees and your tree, not just what you saw
yourself.

Some observations.

 - Trivial Merges count is surprisingly high.  About 1/3 of
   merges are pure in-index merges.

 - Most of the commits (developer commits, not merges) are
   small and touches only a couple of paths.

 - Nobody does octopus ;-).

 - We did not have multi-base merge case during the period
   looked at (but the sample count is very low).

 - merge-one-file was called for only a handful (median 8)
   files, which is negligibly small compared to the total 17K
   files in the kernel tree, and fairly small compared to the
   number of changed paths from the first parent (meaning,
   read-tree trivial collapsing helped majorly).  Among them,
   the number of paths that needed real file-level 3-way merges
   were even smaller (avg 1.96).

   All three of these points together is a fine demonstration
   that you designed git really right.

The samples were between these two commits:

commit 6693e74a16ef563960764bd963f1048392135c3c
Author: Linus Torvalds <torvalds@g5.osdl.org>
Date:   Tue Oct 25 20:40:09 2005 -0700

commit 388f7ef720a982f49925e7b4e96f216f208f8c03
Author: Linus Torvalds <torvalds@g5.osdl.org>
Date:   Fri Nov 11 09:26:39 2005 -0800