{"thread":{"id":"4897","subject":"git merge performance problem..","startedAt":"2006-07-15T21:48:45Z","lastAt":"2006-07-16T06:57:28Z","messageCount":6,"participants":["Linus Torvalds","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"23866","messageId":"Pine.LNX.4.64.0607151445270.5623@g5.osdl.org","threadId":"4897","inReplyTo":null,"subject":"git merge performance problem..","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-07-15T21:48:45Z","receivedAt":"2006-07-15T21:48:45Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nJunio, I think there is something wrong with git-merge. It sometimes takes \nup to ten seconds, and it's stuck at the\n\n\tgit-show-branch --independent \"$head\" \"$@\"\n\ncall.\n\nI don't know quite what that thing is even meant to do (we do already know \nthe parents, why do we do something special here?) but even apart from \nthat, the whole thing must be doing something seriously wrong, since it \ntakes so long. Does it check the whole commit history?\n\n\t\tLinus\n"},{"id":"23868","messageId":"7v7j2eme3u.fsf@assigned-by-dhcp.cox.net","threadId":"4897","inReplyTo":"Pine.LNX.4.64.0607151445270.5623@g5.osdl.org","subject":"Re: git merge performance problem..","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-07-16T03:18:45Z","receivedAt":"2006-07-16T03:18:45Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> Junio, I think there is something wrong with git-merge. It sometimes takes \n> up to ten seconds, and it's stuck at the\n>\n> \tgit-show-branch --independent \"$head\" \"$@\"\n>\n> call.\n>\n> I don't know quite what that thing is even meant to do (we do already know \n> the parents, why do we do something special here?) but even apart from \n> that, the whole thing must be doing something seriously wrong, since it \n> takes so long. Does it check the whole commit history?\n\nThe code is to cull redundant parents primarily in octopus and\nis not strictly necessary.  Can I have the $head and $@ (the\nother merge parents, but in your case you never do an octopus so\nthat would be the other branch head) to see what is going on\nplease?  It should not descend down the history all the way but\nwith the recent changes to the object marking/unmarking code it\nis possible we might have broken something.\n"},{"id":"23870","messageId":"7vlkqukwhb.fsf@assigned-by-dhcp.cox.net","threadId":"4897","inReplyTo":"7v7j2eme3u.fsf@assigned-by-dhcp.cox.net","subject":"Re: git merge performance problem..","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-07-16T04:24:48Z","receivedAt":"2006-07-16T04:24:48Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <junkio@cox.net> writes:\n\n> Linus Torvalds <torvalds@osdl.org> writes:\n>\n>> Junio, I think there is something wrong with git-merge. It sometimes takes \n>> up to ten seconds, and it's stuck at the\n>>\n>> \tgit-show-branch --independent \"$head\" \"$@\"\n>>\n>> call.\n>>\n>> I don't know quite what that thing is even meant to do (we do already know \n>> the parents, why do we do something special here?) but even apart from \n>> that, the whole thing must be doing something seriously wrong, since it \n>> takes so long. Does it check the whole commit history?\n>\n> The code is to cull redundant parents primarily in octopus and\n> is not strictly necessary.\n\nWrong.  The commit log says it was to remove redundant parents;\nI think this as a reaction after seeing a few incorrectly made\nmerge commits in the kernel archive.\n\n> ..., but in your case you never do an octopus so\n> that would be the other branch head) to see what is going on\n> please?\n\nDisregard this request please.  I see a few commits that this\nstep takes a long time to process in the kernel archive.  The\nlast merge before you left to Ottawa was one of them.\n\nb5032a5 48ce8b0\n\nI do not think we need to do the --independent check there\nespecially for two-head cases because we have already done\nfast-forward and up-to-date tests when we get there, so let's\nrevert that part from commit 6ea2334.\n\n-- >8 --\n\ndiff --git a/git-merge.sh b/git-merge.sh\nindex 24e3b50..ee41077 100755\n--- a/git-merge.sh\n+++ b/git-merge.sh\n@@ -314,7 +314,11 @@ # If we have a resulting tree, that mean\n # auto resolved the merge cleanly.\n if test '' != \"$result_tree\"\n then\n-    parents=$(git-show-branch --independent \"$head\" \"$@\" | sed -e 's/^/-p /')\n+    parents=\"-p $head\"\n+    for remote\n+    do\n+\tparents=\"$parents -p $remote\"\n+    done\n     result_commit=$(echo \"$merge_msg\" | git-commit-tree $result_tree $parents) || exit\n     finish \"$result_commit\" \"Merge $result_commit, made by $wt_strategy.\"\n     dropsave\n"},{"id":"23871","messageId":"Pine.LNX.4.64.0607152119510.2438@evo.osdl.org","threadId":"4897","inReplyTo":"7v7j2eme3u.fsf@assigned-by-dhcp.cox.net","subject":"Re: git merge performance problem..","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-07-16T04:26:41Z","receivedAt":"2006-07-16T04:26:41Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 15 Jul 2006, Junio C Hamano wrote:\n> \n> The code is to cull redundant parents primarily in octopus and\n> is not strictly necessary.  Can I have the $head and $@ (the\n> other merge parents, but in your case you never do an octopus so\n> that would be the other branch head) to see what is going on\n> please?\n\nI think it was commit b20e481 that I reacted to this time, merging b5032a5 \nand 48ce8b0.\n\nIe, lookie here:\n\n\t[torvalds@evo linux]$ time git merge-base --all b5032a5 48ce8b0\n\t672c6108a51bf559d19595d9f8193dfd81f0f752\n\t\n\treal    0m1.426s\n\tuser    0m1.404s\n\tsys     0m0.016s\n\nso it can find a merge-base in 1.4 seconds, which should certainly \nguarantee that they are independent. Then:\n\n\t[torvalds@evo linux]$ time git-show-branch --independent b5032a5 48ce8b0\n\tb5032a50aea76b6230db74b1d171a7f56b204bb7\n\t48ce8b056c88920c8ac187781048f5dae33c81b9\n\t\n\treal    0m30.657s\n\tuser    0m30.414s\n\tsys     0m0.076s\n\nWhee. Half a minute. Ok, so this is on my laptop (I'm oat the airport \nright now), so it was probably twice as fast on my desktop, but that is \nstill not acceptable.\n\nI really don't know what it's doing, because\n\n\t[torvalds@evo linux]$ time git-rev-list b5032a5 48ce8b0 > /dev/null \n\t\n\treal    0m3.248s\n\tuser    0m2.588s\n\tsys     0m0.036s\n\nso it's really doing something very expensive - more so than just parsing \nthe commits.\n\n\t\tLinus\n"},{"id":"23872","messageId":"Pine.LNX.4.64.0607152136010.2438@evo.osdl.org","threadId":"4897","inReplyTo":"7vlkqukwhb.fsf@assigned-by-dhcp.cox.net","subject":"Re: git merge performance problem..","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-07-16T04:43:49Z","receivedAt":"2006-07-16T04:43:49Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 15 Jul 2006, Junio C Hamano wrote:\n> Junio C Hamano <junkio@cox.net> writes:\n> >\n> > The code is to cull redundant parents primarily in octopus and\n> > is not strictly necessary.\n> \n> Wrong.  The commit log says it was to remove redundant parents;\n> I think this as a reaction after seeing a few incorrectly made\n> merge commits in the kernel archive.\n\nArguing with yourself? ;)\n\nBut that should already have been handled by the fact that we did the \nmerge-base improvements. So I don't really see why we'd need the extremely \nheavy git-show-branch.\n\nI think the problems we had with rmk generating patches that had two \nparents but really were _meant_ to be regular patches were due to an \nindependent problem, namely that we'd commit with a stale MERGE_HEAD from \na previous (failed) merge that was never done.\n\nI think. It's a long time ago.\n\n> Disregard this request please.  I see a few commits that this\n> step takes a long time to process in the kernel archive.  The\n> last merge before you left to Ottawa was one of them.\n> \n> b5032a5 48ce8b0\n\nYup.\n\nAnd your patch will obviously fix it (by not calling git-show-branch at \nall), but I'm still left wondering why git-show-branch took that long in \nthe first place. Half a minute when traversing the whole commit history \nonly takes three seconds (as per my previous email)?\n\nNow, as long as nothing I use actually ends up using git-show-branch, I \nwon't care, but maybe a sign that something else can be improved?\n\nTraditionally, what has made things _that_ slow has almost always been \nlogic that traverses all sides of a merge, without having the logic to \nignore already-seen commits (so each merge basically doubles the number of \ncommits we will traverse, and the problem size goes from O(n+m) to O(m^2) \nwhere 'n' is number of commits, and 'm' is number of merges.\n\nOr is git-show-branch doing something else really expensive?\n\n\t\tLinus\n"},{"id":"23873","messageId":"7vsll2jauf.fsf@assigned-by-dhcp.cox.net","threadId":"4897","inReplyTo":"Pine.LNX.4.64.0607152136010.2438@evo.osdl.org","subject":"Re: git merge performance problem..","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-07-16T06:57:28Z","receivedAt":"2006-07-16T06:57:28Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> On Sat, 15 Jul 2006, Junio C Hamano wrote:\n>> Junio C Hamano <junkio@cox.net> writes:\n>> >\n>> > The code is to cull redundant parents primarily in octopus and\n>> > is not strictly necessary.\n>> \n>> Wrong.  The commit log says it was to remove redundant parents;\n>> I think this as a reaction after seeing a few incorrectly made\n>> merge commits in the kernel archive.\n>\n> Arguing with yourself? ;)\n\nYes, I was kind of tired ;-)\n\n> And your patch will obviously fix it (by not calling git-show-branch at \n> all), but I'm still left wondering why git-show-branch took that long in \n> the first place. Half a minute when traversing the whole commit history \n> only takes three seconds (as per my previous email)?\n>\n> Now, as long as nothing I use actually ends up using git-show-branch, I \n> won't care, but maybe a sign that something else can be improved?\n\nI instrumented builtin-show-branch.c::join_revs() and\ncommit.c::merge-bases(), and run another problematic case\nbetween commits 1d3737 and 7f2857.  They traverse exactly the\nsame commits in the same order.  After all in two head case they\nare essentially the same algorithm, modulo that the heuristics\nwith horizon effect has not been removed from join_revs() yet.\n\nSimilarly, \"merge-base --all\" vs \"show-branch --merge-base\"\nbetween these commits has the same issue.  Although they\ntraverse exactly the same set of commits, the former takes 10x\nlonger for some reason.\n\nAnd (drumroll please), thanks to gprof, the guilty party turns\nout to be insert_by_date() in mark_seen().\n\nI think this will fix both problems.\n\n-- >8 --\nshow-branch: fix performance problem.\n\nThe core function used in show-branch, join_revs(), was supposed\nto be exactly the same algorithm as merge_bases(), except that\nit was a version enhanced for use with more than two heads.\nHowever, it needed to mark and keep a list of all the commits it\nhas seen, because it needed them for its semi-graphical output.\nThe function to implement this list, mark_seen(), stupidly used\ninsert_by_date(), when it did not need to keep the list sorted\nduring its processing.  This made \"show-branch --merge-base\"\nmore than 20x slower compared to \"merge-base --all\" in some\ncases (e.g. between b5032a5 and 48ce8b0 in the Linux 2.6 kernel\narchive).  The performance of \"show-branch --independent\"\nsuffered from the same reason.\n\nThis patch sorts the resulting list after the list traversal\njust once to fix these problems.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n\n---\ndiff --git a/builtin-show-branch.c b/builtin-show-branch.c\nindex 260cb22..3d240ca 100644\n--- a/builtin-show-branch.c\n+++ b/builtin-show-branch.c\n@@ -172,7 +172,7 @@ static void name_commits(struct commit_l\n static int mark_seen(struct commit *commit, struct commit_list **seen_p)\n {\n \tif (!commit->object.flags) {\n-\t\tinsert_by_date(commit, seen_p);\n+\t\tcommit_list_insert(commit, seen_p);\n \t\treturn 1;\n \t}\n \treturn 0;\n@@ -218,9 +218,8 @@ static void join_revs(struct commit_list\n \t * Postprocess to complete well-poisoning.\n \t *\n \t * At this point we have all the commits we have seen in\n-\t * seen_p list (which happens to be sorted chronologically but\n-\t * it does not really matter).  Mark anything that can be\n-\t * reached from uninteresting commits not interesting.\n+\t * seen_p list.  Mark anything that can be reached from\n+\t * uninteresting commits not interesting.\n \t */\n \tfor (;;) {\n \t\tint changed = 0;\n@@ -701,6 +700,8 @@ int cmd_show_branch(int ac, const char *\n \tif (0 <= extra)\n \t\tjoin_revs(&list, &seen, num_rev, extra);\n \n+\tsort_by_date(&seen);\n+\n \tif (merge_base)\n \t\treturn show_merge_base(seen, num_rev);\n \n"}]}