recur status on linux-2.6

Hi,

I tested git-merge-recur vs. git-merge-recursive on the linux-2.6 repository last night. It contains 2298 two-head merges. _All_ of them come out identically with -recur as compared to -recursive (looking at the resulting index only).

That was the good news. The bad news is: it _seems_, that -recur is only about 6x faster than -recursive, not 10x, and this number becomes smaller, the longer the merge takes. So I see a startup effect here, probably.

Ciao, Dscho

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

Nice.

Recreating the tip of "next" (10a6653) might be fun. I do not know why, but it ended up having 14 merge bases. The speed-up is about 6x, and the resulting half-merge is worse than recursive (not using rerere cache).

Hi,

On Sun, 13 Aug 2006, Junio C Hamano wrote:

Well, my guess for these 14 merge bases is that you merge a lot between topic branches.

As for the worse half-merge: I get only this difference:

-100644 fad39ff609f3ea27981e7a9ffdfc29731d1065d0 1 upload-pack.c +100644 b6cc43c3c89c68e950c6d86298c928e9aab25e70 1 upload-pack.c

So, after both -recur and -recursive, upload-pack.c is in the index in an unmerged state.

The difference between fad39ff6 (from -recur) and b6cc43c3 (from -recursive) is that this block

-- snip --

        if (nr_has < MAX_HAS) {
                struct object *o = lookup_object(sha1);
                if (!(o && o->parsed))
                        o = parse_object(sha1);
                if (!o)
                        die("oops (%s)", sha1_to_hex(sha1));
                if (o->type == OBJ_COMMIT) {
                        struct commit_list *parents;
                        if (o->flags & THEY_HAVE)
                                return 0;
                        o->flags |= THEY_HAVE;
                        for (parents = ((struct commit*)o)->parents;
                             parents;
                             parents = parents->next)
                                parents->item->object.flags |= THEY_HAVE;
                }
                memcpy(has_sha1[nr_has++], sha1, 20);

-- snap --

is inserted after (-recur), instead of before (-recursive), the clashing block

-- snip --

        o = lookup_object(sha1);
        if (!(o && o->parsed))
                o = parse_object(sha1);
        if (!o)
                die("oops (%s)", sha1_to_hex(sha1));
        if (o->type == TYPE_COMMIT) {
                struct commit_list *parents;
                if (o->flags & THEY_HAVE)
                        return 0;
                o->flags |= THEY_HAVE;
                for (parents = ((struct commit*)o)->parents;
                     parents;
                     parents = parents->next)
                        parents->item->object.flags |= THEY_HAVE;

-- snap --

So, the order is actually saner, since one expects the upstream (newer) version to come after the "====" line.

I fail to see how this is worse than -recursive...

Ciao, Dscho

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

These are what I got.  ls-files -u output followed by git diff.

100644 255988a47f56bfa9364c6aff54e45de252b376b8 1 Makefile 100644 07c421bd266724b966fdc92cbc24ef77d61c0d48 2 Makefile 100644 a538710ed6b53079f85582c83be11ae414380d15 3 Makefile 100644 fad39ff609f3ea27981e7a9ffdfc29731d1065d0 1 upload-pack.c 100644 bbd6bd60b52d806be0a69324009755f49b070082 2 upload-pack.c 100644 e8f4be373cfd0ce03617c5fa1494bf52d4babc6c 3 upload-pack.c diff --cc Makefile index 07c421b,a538710..0000000

Hi,

On Sun, 13 Aug 2006, Junio C Hamano wrote:

I am a little confused here: I thought it would be enough to compare the outputs of "git-ls-files --stage". But that seems wrong.

What are the stages for, again?

Ciao, Dscho

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

I do not offhand remember what git-merge-recursive and git-merge-recur store in stage #1 when they recurse to create a virtual common ancestor. I expected it would contain the blob used as the base for the final file-level three-way merge (i.e. the blob in the virtual common ancestor), and if that is the case, i.e. if the blob matches the second argument for "merge" (from RCS), it should be enough to check that the stages match to verify two implementations do the same thing.

But in practice, stage #1 is not very interesting nor useful after a conflicted merge (git diff --ours and git diff --theirs are more useful, so is git log -p --merge), so it is possible that merge-recursive is leaving the blob from one of the true common ancestors there while using the blob from the virtual common ancestor to produce the final result in the working tree and nobody has noticed. I dunno.

Hi,

On Thu, 17 Aug 2006, Junio C Hamano wrote:

Makes sense.

I finally got around to do updated tests, with both git-ls-files --stage and "git diff". It seems like the only issue in the git repository _is_ 10a6653c8. I have not yet had the time to analyze this merge (it is huge!), but I guess recur becomes confused by the timestamps.

Ciao, Dscho

On Sun, Aug 13, 2006 at 03:54:19PM +0200, Johannes Schindelin wrote:

After the latest updates to git-merge-recur it passes all the tests I
have too.
 

That is a quite nice improvement anyway :)

- Fredrik

Fredrik Kuivinen <freku045@student.liu.se> writes:

Maybe we should welcome Linus back with a surprise change that makes recur take over recursive ;-).

Well, maybe not *that* fast.

Here is what I have in mind.

 * Not in too distant future, like this weekend, we would:

   - remove "TEST" at toplevel;

   - merge the C merge-recur work in "master".

   At this stage, people still have to ask for "recur" by either
   explicitly saying "-s recur" or by exporting the environment
   variable GIT_USE_RECUR_FOR_RECURSIVE=YesPlease; git
   developers are encouraged to use this while running tests and
   production.

 * Before stabilization for 1.4.3, we would:

   - rename merge-recursive to merge-recursive-old and
     merge-recur to merge-recursive.

   - we remove GIT_USE_RECUR_FOR_RECURSIVE hack.

   - we make --no-python in t/ directory no-op and only test C
     recursive implementation by default.

   After this, people who would want to keep using the original
   recursive have to ask for it by "-s recursive-old".

 * We release 1.4.3 with C recursive as the default merge
   strategy.

I am not at this moment thinking about removing recursive in Python altogether. We still have a few contrib scripts (p4import and gitview) that are in Python, so doing that would not remove our dependency on Python anyway.

Hi,

On Tue, 22 Aug 2006, Junio C Hamano wrote:

*holds his breath*

Puh!

I still have not had the time to figure out why 10a6653c goes bad. So I do not know if that is a show stopper or not.

Ciao, Dscho