{"thread":{"id":"1470","subject":"Speed up git-merge-base a lot","startedAt":"2005-08-10T23:26:32Z","lastAt":"2005-08-10T23:26:32Z","messageCount":1,"participants":["Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"7044","messageId":"Pine.LNX.4.58.0508101615520.3295@g5.osdl.org","threadId":"1470","inReplyTo":null,"subject":"Speed up git-merge-base a lot","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-08-10T23:26:32Z","receivedAt":"2005-08-10T23:26:32Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nIn commit 4f7eb2e5a351e0d1f19fd4eab7e92834cc4528c2 I fixed git-merge-base \ngetting confused by datestamps that caused it to traverse things in a \nnon-obvious order.\n\nHowever, my fix was a very brute-force one, and it had some really\nhorrible implications for more complex trees with lots of parallell\ndevelopment. It might end up traversing all the way to the root commit.\n\nNow, normally that isn't that horrible: it's used mainly for merging, and \nthe bad cases really tend to happen fairly rarely, so if it takes a few \nseconds, we're not in too bad shape.\n\nHowever, gitk will also do the git-merge-base for every merge it shows,\nbecause it basically re-does the trivial merge in order to show the\n\"interesting\" parts. And there we'd really like the result to be\ninstantaneous.\n\nThis patch does that by walking the tree more completely, and using the \nsame heuristic as git-rev-list to decide \"ok, the rest is uninteresting\".\n\nIn one - hopefully fairly extreme - case, it made a git-merge-base go from\njust under five seconds(!) to a tenth of a second on my machine.\n\nSigned-off-by: Linus Torvalds <torvalds@osdl.org>\n---\ndiff --git a/merge-base.c b/merge-base.c\n--- a/merge-base.c\n+++ b/merge-base.c\n@@ -2,6 +2,22 @@\n #include \"cache.h\"\n #include \"commit.h\"\n \n+#define PARENT1 1\n+#define PARENT2 2\n+#define UNINTERESTING 4\n+\n+static int interesting(struct commit_list *list)\n+{\n+\twhile (list) {\n+\t\tstruct commit *commit = list->item;\n+\t\tlist = list->next;\n+\t\tif (commit->object.flags & UNINTERESTING)\n+\t\t\tcontinue;\n+\t\treturn 1;\n+\t}\n+\treturn 0;\n+}\n+\n static struct commit *common_ancestor(struct commit *rev1, struct commit *rev2)\n {\n \tstruct commit_list *list = NULL;\n@@ -18,19 +34,18 @@ static struct commit *common_ancestor(st\n \tinsert_by_date(rev1, &list);\n \tinsert_by_date(rev2, &list);\n \n-\twhile (list) {\n+\twhile (interesting(list)) {\n \t\tstruct commit *commit = list->item;\n \t\tstruct commit_list *tmp = list, *parents;\n-\t\tint flags = commit->object.flags & 3;\n+\t\tint flags = commit->object.flags & 7;\n \n \t\tlist = list->next;\n \t\tfree(tmp);\n-\t\tswitch (flags) {\n-\t\tcase 3:\n+\t\tif (flags == 3) {\n \t\t\tinsert_by_date(commit, &result);\n-\t\t\tcontinue;\n-\t\tcase 0:\n-\t\t\tdie(\"git-merge-base: commit without either parent?\");\n+\n+\t\t\t/* Mark children of a found merge uninteresting */\n+\t\t\tflags |= UNINTERESTING;\n \t\t}\n \t\tparents = commit->parents;\n \t\twhile (parents) {\n"}]}