{"thread":{"id":"5227","subject":"recur status on linux-2.6","startedAt":"2006-08-13T13:54:19Z","lastAt":"2006-08-22T13:57:58Z","messageCount":10,"participants":["Johannes Schindelin","Junio C Hamano","Fredrik Kuivinen"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"25184","messageId":"Pine.LNX.4.63.0608131550290.10541@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5227","inReplyTo":null,"subject":"recur status on linux-2.6","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-13T13:54:19Z","receivedAt":"2006-08-13T13:54:19Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nI tested git-merge-recur vs. git-merge-recursive on the linux-2.6 \nrepository last night. It contains 2298 two-head merges. _All_ of them \ncome out identically with -recur as compared to -recursive (looking at \nthe resulting index only).\n\nThat was the good news. The bad news is: it _seems_, that -recur is only \nabout 6x faster than -recursive, not 10x, and this number becomes smaller, \nthe longer the merge takes. So I see a startup effect here, probably.\n\nCiao,\nDscho\n"},{"id":"25186","messageId":"7v64gwmv2j.fsf@assigned-by-dhcp.cox.net","threadId":"5227","inReplyTo":"Pine.LNX.4.63.0608131550290.10541@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: recur status on linux-2.6","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-08-13T16:58:28Z","receivedAt":"2006-08-13T16:58:28Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> I tested git-merge-recur vs. git-merge-recursive on the linux-2.6 \n> repository last night. It contains 2298 two-head merges. _All_ of them \n> come out identically with -recur as compared to -recursive (looking at \n> the resulting index only).\n\nNice.\n\n> That was the good news. The bad news is: it _seems_, that -recur is only \n> about 6x faster than -recursive, not 10x, and this number becomes smaller, \n> the longer the merge takes. So I see a startup effect here, probably.\n\nRecreating the tip of \"next\" (10a6653) might be fun. I do not\nknow why, but it ended up having 14 merge bases. The speed-up\nis about 6x, and the resulting half-merge is worse than\nrecursive (not using rerere cache).\n"},{"id":"25188","messageId":"Pine.LNX.4.63.0608132006510.10541@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5227","inReplyTo":"7v64gwmv2j.fsf@assigned-by-dhcp.cox.net","subject":"Re: recur status on linux-2.6","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-13T18:16:29Z","receivedAt":"2006-08-13T18:16:29Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 13 Aug 2006, Junio C Hamano wrote:\n\n> Recreating the tip of \"next\" (10a6653) might be fun. I do not know why, \n> but it ended up having 14 merge bases. The speed-up is about 6x, and \n> the resulting half-merge is worse than recursive (not using rerere \n> cache).\n\nWell, my guess for these 14 merge bases is that you merge a lot between \ntopic branches.\n\nAs for the worse half-merge: I get only this difference:\n\n-100644 fad39ff609f3ea27981e7a9ffdfc29731d1065d0 1 upload-pack.c\n+100644 b6cc43c3c89c68e950c6d86298c928e9aab25e70 1 upload-pack.c\n\nSo, after both -recur and -recursive, upload-pack.c is in the index in an \nunmerged state.\n\nThe difference between fad39ff6 (from -recur) and b6cc43c3 (from \n-recursive) is that this block\n\n-- snip --\n\n if (nr_has < MAX_HAS) {\n struct object *o = lookup_object(sha1);\n if (!(o && o->parsed))\n o = parse_object(sha1);\n if (!o)\n die(\"oops (%s)\", sha1_to_hex(sha1));\n if (o->type == OBJ_COMMIT) {\n struct commit_list *parents;\n if (o->flags & THEY_HAVE)\n return 0;\n o->flags |= THEY_HAVE;\n for (parents = ((struct commit*)o)->parents;\n parents;\n parents = parents->next)\n parents->item->object.flags |= THEY_HAVE;\n }\n memcpy(has_sha1[nr_has++], sha1, 20);\n\n-- snap --\n\nis inserted after (-recur), instead of before (-recursive), the clashing \nblock\n\n-- snip --\n\n o = lookup_object(sha1);\n if (!(o && o->parsed))\n o = parse_object(sha1);\n if (!o)\n die(\"oops (%s)\", sha1_to_hex(sha1));\n if (o->type == TYPE_COMMIT) {\n struct commit_list *parents;\n if (o->flags & THEY_HAVE)\n return 0;\n o->flags |= THEY_HAVE;\n for (parents = ((struct commit*)o)->parents;\n parents;\n parents = parents->next)\n parents->item->object.flags |= THEY_HAVE;\n\n-- snap --\n\nSo, the order is actually saner, since one expects the upstream (newer) \nversion to come after the \"====\" line.\n\nI fail to see how this is worse than -recursive...\n\nCiao,\nDscho\n"},{"id":"25192","messageId":"7vveowl8sm.fsf@assigned-by-dhcp.cox.net","threadId":"5227","inReplyTo":"Pine.LNX.4.63.0608132006510.10541@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: recur status on linux-2.6","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-08-13T19:44:57Z","receivedAt":"2006-08-13T19:44:57Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> I fail to see how this is worse than -recursive...\n\nThese are what I got. ls-files -u output followed by git diff.\n\n\n\n100644 255988a47f56bfa9364c6aff54e45de252b376b8 1\tMakefile\n100644 07c421bd266724b966fdc92cbc24ef77d61c0d48 2\tMakefile\n100644 a538710ed6b53079f85582c83be11ae414380d15 3\tMakefile\n100644 fad39ff609f3ea27981e7a9ffdfc29731d1065d0 1\tupload-pack.c\n100644 bbd6bd60b52d806be0a69324009755f49b070082 2\tupload-pack.c\n100644 e8f4be373cfd0ce03617c5fa1494bf52d4babc6c 3\tupload-pack.c\ndiff --cc Makefile\nindex 07c421b,a538710..0000000\n--- a/Makefile\n+++ b/Makefile\n@@@ -253,7 -242,7 +253,11 @@@\n \tserver-info.o setup.o sha1_file.o sha1_name.o strbuf.o \\\n \ttag.o tree.o usage.o config.o environment.o ctype.o copy.o \\\n \tfetch-clone.o revision.o pager.o tree-walk.o xdiff-interface.o \\\n++<<<<<<< HEAD/Makefile\n +\talloc.o merge-file.o path-list.o unpack-trees.o help.o $(DIFF_OBJS)\n++=======\n+ \talloc.o merge-file.o path-list.o help.o unpack-trees.o $(DIFF_OBJS)\n++>>>>>>> 937a515a15f776aa84430574f71367292a52b978/Makefile\n \n BUILTIN_OBJS = \\\n \tbuiltin-add.o \\\ndiff --cc upload-pack.c\nindex bbd6bd6,e8f4be3..0000000\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@@ -327,7 -334,7 +334,11 @@@\n \tif (get_sha1_hex(hex, sha1))\n \t\tdie(\"git-upload-pack: expected SHA1 object, got '%s'\", hex);\n \tif (!has_sha1_file(sha1))\n++<<<<<<< HEAD/upload-pack.c\n +\t\treturn 0;\n++=======\n+ \t\treturn -1;\n++>>>>>>> 937a515a15f776aa84430574f71367292a52b978/upload-pack.c\n \n \to = lookup_object(sha1);\n \tif (!(o && o->parsed))\n@@@ -343,8 -354,73 +358,76 @@@\n \t\t parents;\n \t\t parents = parents->next)\n \t\t\tparents->item->object.flags |= THEY_HAVE;\n++<<<<<<< HEAD/upload-pack.c\n++=======\n+ \t}\n+ \tif (!we_knew_they_have) {\n+ \t\tadd_object_array(o, NULL, &have_obj);\n+ \t\treturn 1;\n+ \t}\n+ \treturn 0;\n+ }\n+ \n+ static int reachable(struct commit *want)\n+ {\n+ \tstruct commit_list *work = NULL;\n+ \n+ \tinsert_by_date(want, &work);\n+ \twhile (work) {\n+ \t\tstruct commit_list *list = work->next;\n+ \t\tstruct commit *commit = work->item;\n+ \t\tfree(work);\n+ \t\twork = list;\n+ \n+ \t\tif (commit->object.flags & THEY_HAVE) {\n+ \t\t\twant->object.flags |= COMMON_KNOWN;\n+ \t\t\tbreak;\n+ \t\t}\n+ \t\tif (!commit->object.parsed)\n+ \t\t\tparse_object(commit->object.sha1);\n+ \t\tif (commit->object.flags & REACHABLE)\n+ \t\t\tcontinue;\n+ \t\tcommit->object.flags |= REACHABLE;\n+ \t\tif (commit->date < oldest_have)\n+ \t\t\tcontinue;\n+ \t\tfor (list = commit->parents; list; list = list->next) {\n+ \t\t\tstruct commit *parent = list->item;\n+ \t\t\tif (!(parent->object.flags & REACHABLE))\n+ \t\t\t\tinsert_by_date(parent, &work);\n+ \t\t}\n+ \t}\n+ \twant->object.flags |= REACHABLE;\n+ \tclear_commit_marks(want, REACHABLE);\n+ \tfree_commit_list(work);\n+ \treturn (want->object.flags & COMMON_KNOWN);\n+ }\n+ \n+ static int ok_to_give_up(void)\n+ {\n+ \tint i;\n+ \n+ \tif (!have_obj.nr)\n+ \t\treturn 0;\n+ \n+ \tfor (i = 0; i < want_obj.nr; i++) {\n+ \t\tstruct object *want = want_obj.objects[i].item;\n+ \n+ \t\tif (want->flags & COMMON_KNOWN)\n+ \t\t\tcontinue;\n+ \t\twant = deref_tag(want, \"a want line\", 0);\n+ \t\tif (!want || want->type != OBJ_COMMIT) {\n+ \t\t\t/* no way to tell if this is reachable by\n+ \t\t\t * looking at the ancestry chain alone, so\n+ \t\t\t * leave a note to ourselves not to worry about\n+ \t\t\t * this object anymore.\n+ \t\t\t */\n+ \t\t\twant_obj.objects[i].item->flags |= COMMON_KNOWN;\n+ \t\t\tcontinue;\n+ \t\t}\n+ \t\tif (!reachable((struct commit *)want))\n+ \t\t\treturn 0;\n++>>>>>>> 937a515a15f776aa84430574f71367292a52b978/upload-pack.c\n \t}\n- \tadd_object_array(o, NULL, &have_obj);\n \treturn 1;\n }\n \n\n\n100644 99048d0a128186e70f329208a734cc9e72c1a3e7 1\tMakefile\n100644 07c421bd266724b966fdc92cbc24ef77d61c0d48 2\tMakefile\n100644 a538710ed6b53079f85582c83be11ae414380d15 3\tMakefile\n100644 b6cc43c3c89c68e950c6d86298c928e9aab25e70 1\tupload-pack.c\n100644 bbd6bd60b52d806be0a69324009755f49b070082 2\tupload-pack.c\n100644 e8f4be373cfd0ce03617c5fa1494bf52d4babc6c 3\tupload-pack.c\ndiff --cc Makefile\nindex 07c421b,a538710..0000000\n--- a/Makefile\n+++ b/Makefile\n@@@ -253,7 -242,7 +253,11 @@@\n \tserver-info.o setup.o sha1_file.o sha1_name.o strbuf.o \\\n \ttag.o tree.o usage.o config.o environment.o ctype.o copy.o \\\n \tfetch-clone.o revision.o pager.o tree-walk.o xdiff-interface.o \\\n++<<<<<<< HEAD/Makefile\n +\talloc.o merge-file.o path-list.o unpack-trees.o help.o $(DIFF_OBJS)\n++=======\n+ \talloc.o merge-file.o path-list.o help.o unpack-trees.o $(DIFF_OBJS)\n++>>>>>>> 937a515a15f776aa84430574f71367292a52b978/Makefile\n \n BUILTIN_OBJS = \\\n \tbuiltin-add.o \\\ndiff --cc upload-pack.c\nindex bbd6bd6,e8f4be3..0000000\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@@ -327,7 -334,7 +334,11 @@@\n \tif (get_sha1_hex(hex, sha1))\n \t\tdie(\"git-upload-pack: expected SHA1 object, got '%s'\", hex);\n \tif (!has_sha1_file(sha1))\n++<<<<<<< HEAD/upload-pack.c\n +\t\treturn 0;\n++=======\n+ \t\treturn -1;\n++>>>>>>> 937a515a15f776aa84430574f71367292a52b978/upload-pack.c\n \n \to = lookup_object(sha1);\n \tif (!(o && o->parsed))\n"},{"id":"25197","messageId":"Pine.LNX.4.63.0608132221030.10541@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5227","inReplyTo":"7vveowl8sm.fsf@assigned-by-dhcp.cox.net","subject":"Re: recur status on linux-2.6","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-13T20:43:41Z","receivedAt":"2006-08-13T20:43:41Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 13 Aug 2006, Junio C Hamano wrote:\n\n> Johannes Schindelin writes:\n> \n> > I fail to see how this is worse than -recursive...\n> \n> These are what I got. ls-files -u output followed by git diff.\n\nI am a little confused here: I thought it would be enough to compare the \noutputs of \"git-ls-files --stage\". But that seems wrong.\n\nWhat are the stages for, again?\n\nCiao,\nDscho\n"},{"id":"25517","messageId":"7vwt96d6s1.fsf@assigned-by-dhcp.cox.net","threadId":"5227","inReplyTo":"Pine.LNX.4.63.0608132221030.10541@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: recur status on linux-2.6","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-08-18T04:09:18Z","receivedAt":"2006-08-18T04:09:18Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> On Sun, 13 Aug 2006, Junio C Hamano wrote:\n>\n>> Johannes Schindelin writes:\n>> \n>> > I fail to see how this is worse than -recursive...\n>> \n>> These are what I got. ls-files -u output followed by git diff.\n>\n> I am a little confused here: I thought it would be enough to compare the \n> outputs of \"git-ls-files --stage\". But that seems wrong.\n>\n> What are the stages for, again?\n\nI do not offhand remember what git-merge-recursive and\ngit-merge-recur store in stage #1 when they recurse to create a\nvirtual common ancestor. I expected it would contain the blob\nused as the base for the final file-level three-way merge\n(i.e. the blob in the virtual common ancestor), and if that is\nthe case, i.e. if the blob matches the second argument for\n\"merge\" (from RCS), it should be enough to check that the stages\nmatch to verify two implementations do the same thing.\n\nBut in practice, stage #1 is not very interesting nor useful\nafter a conflicted merge (git diff --ours and git diff --theirs\nare more useful, so is git log -p --merge), so it is possible\nthat merge-recursive is leaving the blob from one of the true\ncommon ancestors there while using the blob from the virtual\ncommon ancestor to produce the final result in the working tree\nand nobody has noticed. I dunno.\n"},{"id":"25537","messageId":"Pine.LNX.4.63.0608181155130.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5227","inReplyTo":"7vwt96d6s1.fsf@assigned-by-dhcp.cox.net","subject":"Re: recur status on linux-2.6","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-18T10:00:18Z","receivedAt":"2006-08-18T10:00:18Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 17 Aug 2006, Junio C Hamano wrote:\n\n> Johannes Schindelin writes:\n> \n> > On Sun, 13 Aug 2006, Junio C Hamano wrote:\n> >\n> >> Johannes Schindelin writes:\n> >> \n> >> > I fail to see how this is worse than -recursive...\n> >> \n> >> These are what I got. ls-files -u output followed by git diff.\n> >\n> > I am a little confused here: I thought it would be enough to compare the \n> > outputs of \"git-ls-files --stage\". But that seems wrong.\n> >\n> > What are the stages for, again?\n> \n> I do not offhand remember what git-merge-recursive and\n> git-merge-recur store in stage #1 when they recurse to create a\n> virtual common ancestor. I expected it would contain the blob\n> used as the base for the final file-level three-way merge\n> (i.e. the blob in the virtual common ancestor), and if that is\n> the case, i.e. if the blob matches the second argument for\n> \"merge\" (from RCS), it should be enough to check that the stages\n> match to verify two implementations do the same thing.\n> \n> But in practice, stage #1 is not very interesting nor useful\n> after a conflicted merge (git diff --ours and git diff --theirs\n> are more useful, so is git log -p --merge), so it is possible\n> that merge-recursive is leaving the blob from one of the true\n> common ancestors there while using the blob from the virtual\n> common ancestor to produce the final result in the working tree\n> and nobody has noticed. I dunno.\n\nMakes sense.\n\nI finally got around to do updated tests, with both git-ls-files --stage \nand \"git diff\". It seems like the only issue in the git repository _is_ \n10a6653c8. I have not yet had the time to analyze this merge (it is \nhuge!), but I guess recur becomes confused by the timestamps.\n\nCiao,\nDscho\n"},{"id":"25603","messageId":"20060819104630.GA5213@c165.ib.student.liu.se","threadId":"5227","inReplyTo":"Pine.LNX.4.63.0608131550290.10541@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: recur status on linux-2.6","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2006-08-19T10:46:30Z","receivedAt":"2006-08-19T10:46:30Z","isPatch":false,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Sun, Aug 13, 2006 at 03:54:19PM +0200, Johannes Schindelin wrote:\n> Hi,\n> \n> I tested git-merge-recur vs. git-merge-recursive on the linux-2.6 \n> repository last night. It contains 2298 two-head merges. _All_ of them \n> come out identically with -recur as compared to -recursive (looking at \n> the resulting index only).\n\nAfter the latest updates to git-merge-recur it passes all the tests I\nhave too.\n \n> That was the good news. The bad news is: it _seems_, that -recur is only \n> about 6x faster than -recursive, not 10x, and this number becomes smaller, \n> the longer the merge takes. So I see a startup effect here, probably.\t\n\nThat is a quite nice improvement anyway :)\n\n- Fredrik\n"},{"id":"25731","messageId":"7virklp438.fsf@assigned-by-dhcp.cox.net","threadId":"5227","inReplyTo":"20060819104630.GA5213@c165.ib.student.liu.se","subject":"Re: recur status on linux-2.6","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-08-22T08:27:55Z","receivedAt":"2006-08-22T08:27:55Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Fredrik Kuivinen writes:\n\n> On Sun, Aug 13, 2006 at 03:54:19PM +0200, Johannes Schindelin wrote:\n>> Hi,\n>> \n>> I tested git-merge-recur vs. git-merge-recursive on the linux-2.6 \n>> repository last night. It contains 2298 two-head merges. _All_ of them \n>> come out identically with -recur as compared to -recursive (looking at \n>> the resulting index only).\n>\n> After the latest updates to git-merge-recur it passes all the tests I\n> have too.\n> \n>> That was the good news. The bad news is: it _seems_, that -recur is only \n>> about 6x faster than -recursive, not 10x, and this number becomes smaller, \n>> the longer the merge takes. So I see a startup effect here, probably.\n>\n> That is a quite nice improvement anyway :)\n\nMaybe we should welcome Linus back with a surprise change that\nmakes recur take over recursive ;-).\n\nWell, maybe not *that* fast.\n\nHere is what I have in mind.\n\n * Not in too distant future, like this weekend, we would:\n\n - remove \"TEST\" at toplevel;\n\n - merge the C merge-recur work in \"master\".\n\n At this stage, people still have to ask for \"recur\" by either\n explicitly saying \"-s recur\" or by exporting the environment\n variable GIT_USE_RECUR_FOR_RECURSIVE=YesPlease; git\n developers are encouraged to use this while running tests and\n production.\n\n * Before stabilization for 1.4.3, we would:\n\n - rename merge-recursive to merge-recursive-old and\n merge-recur to merge-recursive.\n\n - we remove GIT_USE_RECUR_FOR_RECURSIVE hack.\n\n - we make --no-python in t/ directory no-op and only test C\n recursive implementation by default.\n\n After this, people who would want to keep using the original\n recursive have to ask for it by \"-s recursive-old\".\n\n * We release 1.4.3 with C recursive as the default merge\n strategy.\n\nI am not at this moment thinking about removing recursive in\nPython altogether. We still have a few contrib scripts\n(p4import and gitview) that are in Python, so doing that would\nnot remove our dependency on Python anyway.\n"},{"id":"25745","messageId":"Pine.LNX.4.63.0608221555500.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5227","inReplyTo":"7virklp438.fsf@assigned-by-dhcp.cox.net","subject":"Re: recur status on linux-2.6","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-22T13:57:58Z","receivedAt":"2006-08-22T13:57:58Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 22 Aug 2006, Junio C Hamano wrote:\n\n> Maybe we should welcome Linus back with a surprise change that\n> makes recur take over recursive ;-).\n\n*holds his breath*\n\n> Well, maybe not *that* fast.\n\nPuh!\n\nI still have not had the time to figure out why 10a6653c goes bad. So I do \nnot know if that is a show stopper or not.\n\nCiao,\nDscho\n"}]}