recur status on linux-2.6

recur status on linux-2.6

[Johannes Schindelin]

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

Re: recur status on linux-2.6

[Junio C Hamano]

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

> 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).

Nice.

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

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).

Re: recur status on linux-2.6

[Johannes Schindelin]

Hi,

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

> 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).

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

Re: recur status on linux-2.6

[Junio C Hamano]

[-- Attachment #1: Type: text/plain, Size: 177 bytes --]

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

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

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


[-- Attachment #2: output from recur --]
[-- Type: text/plain, Size: 3377 bytes --]

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
--- a/Makefile
+++ b/Makefile
@@@ -253,7 -242,7 +253,11 @@@
  	server-info.o setup.o sha1_file.o sha1_name.o strbuf.o \
  	tag.o tree.o usage.o config.o environment.o ctype.o copy.o \
  	fetch-clone.o revision.o pager.o tree-walk.o xdiff-interface.o \
++<<<<<<< HEAD/Makefile
 +	alloc.o merge-file.o path-list.o unpack-trees.o help.o $(DIFF_OBJS)
++=======
+ 	alloc.o merge-file.o path-list.o help.o unpack-trees.o $(DIFF_OBJS)
++>>>>>>> 937a515a15f776aa84430574f71367292a52b978/Makefile
  
  BUILTIN_OBJS = \
  	builtin-add.o \
diff --cc upload-pack.c
index bbd6bd6,e8f4be3..0000000
--- a/upload-pack.c
+++ b/upload-pack.c
@@@ -327,7 -334,7 +334,11 @@@
  	if (get_sha1_hex(hex, sha1))
  		die("git-upload-pack: expected SHA1 object, got '%s'", hex);
  	if (!has_sha1_file(sha1))
++<<<<<<< HEAD/upload-pack.c
 +		return 0;
++=======
+ 		return -1;
++>>>>>>> 937a515a15f776aa84430574f71367292a52b978/upload-pack.c
  
  	o = lookup_object(sha1);
  	if (!(o && o->parsed))
@@@ -343,8 -354,73 +358,76 @@@
  		     parents;
  		     parents = parents->next)
  			parents->item->object.flags |= THEY_HAVE;
++<<<<<<< HEAD/upload-pack.c
++=======
+ 	}
+ 	if (!we_knew_they_have) {
+ 		add_object_array(o, NULL, &have_obj);
+ 		return 1;
+ 	}
+ 	return 0;
+ }
+ 
+ static int reachable(struct commit *want)
+ {
+ 	struct commit_list *work = NULL;
+ 
+ 	insert_by_date(want, &work);
+ 	while (work) {
+ 		struct commit_list *list = work->next;
+ 		struct commit *commit = work->item;
+ 		free(work);
+ 		work = list;
+ 
+ 		if (commit->object.flags & THEY_HAVE) {
+ 			want->object.flags |= COMMON_KNOWN;
+ 			break;
+ 		}
+ 		if (!commit->object.parsed)
+ 			parse_object(commit->object.sha1);
+ 		if (commit->object.flags & REACHABLE)
+ 			continue;
+ 		commit->object.flags |= REACHABLE;
+ 		if (commit->date < oldest_have)
+ 			continue;
+ 		for (list = commit->parents; list; list = list->next) {
+ 			struct commit *parent = list->item;
+ 			if (!(parent->object.flags & REACHABLE))
+ 				insert_by_date(parent, &work);
+ 		}
+ 	}
+ 	want->object.flags |= REACHABLE;
+ 	clear_commit_marks(want, REACHABLE);
+ 	free_commit_list(work);
+ 	return (want->object.flags & COMMON_KNOWN);
+ }
+ 
+ static int ok_to_give_up(void)
+ {
+ 	int i;
+ 
+ 	if (!have_obj.nr)
+ 		return 0;
+ 
+ 	for (i = 0; i < want_obj.nr; i++) {
+ 		struct object *want = want_obj.objects[i].item;
+ 
+ 		if (want->flags & COMMON_KNOWN)
+ 			continue;
+ 		want = deref_tag(want, "a want line", 0);
+ 		if (!want || want->type != OBJ_COMMIT) {
+ 			/* no way to tell if this is reachable by
+ 			 * looking at the ancestry chain alone, so
+ 			 * leave a note to ourselves not to worry about
+ 			 * this object anymore.
+ 			 */
+ 			want_obj.objects[i].item->flags |= COMMON_KNOWN;
+ 			continue;
+ 		}
+ 		if (!reachable((struct commit *)want))
+ 			return 0;
++>>>>>>> 937a515a15f776aa84430574f71367292a52b978/upload-pack.c
  	}
- 	add_object_array(o, NULL, &have_obj);
  	return 1;
  }
  

[-- Attachment #3: output from recursive --]
[-- Type: text/plain, Size: 1389 bytes --]

100644 99048d0a128186e70f329208a734cc9e72c1a3e7 1	Makefile
100644 07c421bd266724b966fdc92cbc24ef77d61c0d48 2	Makefile
100644 a538710ed6b53079f85582c83be11ae414380d15 3	Makefile
100644 b6cc43c3c89c68e950c6d86298c928e9aab25e70 1	upload-pack.c
100644 bbd6bd60b52d806be0a69324009755f49b070082 2	upload-pack.c
100644 e8f4be373cfd0ce03617c5fa1494bf52d4babc6c 3	upload-pack.c
diff --cc Makefile
index 07c421b,a538710..0000000
--- a/Makefile
+++ b/Makefile
@@@ -253,7 -242,7 +253,11 @@@
  	server-info.o setup.o sha1_file.o sha1_name.o strbuf.o \
  	tag.o tree.o usage.o config.o environment.o ctype.o copy.o \
  	fetch-clone.o revision.o pager.o tree-walk.o xdiff-interface.o \
++<<<<<<< HEAD/Makefile
 +	alloc.o merge-file.o path-list.o unpack-trees.o help.o $(DIFF_OBJS)
++=======
+ 	alloc.o merge-file.o path-list.o help.o unpack-trees.o $(DIFF_OBJS)
++>>>>>>> 937a515a15f776aa84430574f71367292a52b978/Makefile
  
  BUILTIN_OBJS = \
  	builtin-add.o \
diff --cc upload-pack.c
index bbd6bd6,e8f4be3..0000000
--- a/upload-pack.c
+++ b/upload-pack.c
@@@ -327,7 -334,7 +334,11 @@@
  	if (get_sha1_hex(hex, sha1))
  		die("git-upload-pack: expected SHA1 object, got '%s'", hex);
  	if (!has_sha1_file(sha1))
++<<<<<<< HEAD/upload-pack.c
 +		return 0;
++=======
+ 		return -1;
++>>>>>>> 937a515a15f776aa84430574f71367292a52b978/upload-pack.c
  
  	o = lookup_object(sha1);
  	if (!(o && o->parsed))

Re: recur status on linux-2.6

[Johannes Schindelin]

Hi,

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

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> 
> > I fail to see how this is worse than -recursive...
> 
> These are what I got.  ls-files -u output followed by git diff.

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

Re: recur status on linux-2.6

[Junio C Hamano]

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

> On Sun, 13 Aug 2006, Junio C Hamano wrote:
>
>> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
>> 
>> > I fail to see how this is worse than -recursive...
>> 
>> These are what I got.  ls-files -u output followed by git diff.
>
> 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?

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.

Re: recur status on linux-2.6

[Johannes Schindelin]

Hi,

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

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> 
> > On Sun, 13 Aug 2006, Junio C Hamano wrote:
> >
> >> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> >> 
> >> > I fail to see how this is worse than -recursive...
> >> 
> >> These are what I got.  ls-files -u output followed by git diff.
> >
> > 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?
> 
> 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.

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

Re: recur status on linux-2.6

[Fredrik Kuivinen]

On Sun, Aug 13, 2006 at 03:54:19PM +0200, Johannes Schindelin wrote:
> 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).

After the latest updates to git-merge-recur it passes all the tests I
have too.
 
> 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.	

That is a quite nice improvement anyway :)

- Fredrik

Re: recur status on linux-2.6

[Junio C Hamano]

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

> On Sun, Aug 13, 2006 at 03:54:19PM +0200, Johannes Schindelin wrote:
>> 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).
>
> After the latest updates to git-merge-recur it passes all the tests I
> have too.
>  
>> 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.
>
> That is a quite nice improvement anyway :)

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.

Re: recur status on linux-2.6

[Johannes Schindelin]

Hi,

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

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

*holds his breath*

> Well, maybe not *that* fast.

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