{"thread":{"id":"53702","subject":"[PATCH 0/2] Accelerate \"git merge-base --is-ancestor\"","startedAt":"2020-06-17T17:24:35Z","lastAt":"2020-06-30T01:45:36Z","messageCount":8,"participants":["Derrick Stolee via GitGitGadget","Junio C Hamano","Derrick Stolee","Abhishek Kumar","Taylor Blau"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"399977","messageId":"pull.664.git.1592414670.gitgitgadget@gmail.com","threadId":"53702","inReplyTo":null,"subject":"[PATCH 0/2] Accelerate \"git merge-base --is-ancestor\"","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-06-17T17:24:27Z","receivedAt":"2020-06-17T17:24:35Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"It was recently [1] reported (and not-so-recently [2] reported) that \"git\nmerge-base --is-ancestor\" can be pretty slow. In fact, it is regularly\nslower than \"git branch --contains\" or \"git tag --contains\", which are\nanswering a \"harder\" query.\n\n[1] https://lore.kernel.org/git/20200607195347.GA8232@szeder.dev/\n\n[2] https://lore.kernel.org/git/87608bawoa.fsf@evledraar.gmail.com/\n\nThe root cause is that the in_merge_base() implementation is skipping the\nfast can_all_from_reach() implementation and using paint_down_to_common()\ninstead. Note that these are equivalent: a commit A is in the set of\nmerge-bases between A and B if and only if B can reach A.\n\nThis fixes the issue, and makes the performance degradation reported by\nSzeder a non-issue.\n\nThanks, -Stolee\n\nDerrick Stolee (2):\n commit-reach: create repo_is_descendant_of()\n commit-reach: use fast logic in repo_in_merge_base\n\n commit-reach.c | 21 ++++++++++++++++++---\n 1 file changed, 18 insertions(+), 3 deletions(-)\n\n\nbase-commit: b3d7a52fac39193503a0b6728771d1bf6a161464\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-664%2Fderrickstolee%2Fmerge-base-is-ancestor-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-664/derrickstolee/merge-base-is-ancestor-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/664\n-- \ngitgitgadget\n"},{"id":"399978","messageId":"8f7fd8f5941426c3ed7fc28c6e4afd62bcd4bb8d.1592414670.git.gitgitgadget@gmail.com","threadId":"53702","inReplyTo":"pull.664.git.1592414670.gitgitgadget@gmail.com","subject":"[PATCH 1/2] commit-reach: create repo_is_descendant_of()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-06-17T17:24:28Z","receivedAt":"2020-06-17T17:24:36Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe next change will make repo_in_merge_bases() depend on the logic in\nis_descendant_of(), but we need to make the method independent of\nthe_repository first.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 11 +++++++++--\n 1 file changed, 9 insertions(+), 2 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 4ca7e706a18..13722430aa5 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -283,7 +283,9 @@ struct commit_list *repo_get_merge_bases(struct repository *r,\n /*\n * Is \"commit\" a descendant of one of the elements on the \"with_commit\" list?\n */\n-int is_descendant_of(struct commit *commit, struct commit_list *with_commit)\n+static int repo_is_descendant_of(struct repository *r,\n+\t\t\t\t struct commit *commit,\n+\t\t\t\t struct commit_list *with_commit)\n {\n \tif (!with_commit)\n \t\treturn 1;\n@@ -301,13 +303,18 @@ int is_descendant_of(struct commit *commit, struct commit_list *with_commit)\n \n \t\t\tother = with_commit->item;\n \t\t\twith_commit = with_commit->next;\n-\t\t\tif (in_merge_bases(other, commit))\n+\t\t\tif (repo_in_merge_bases(r, other, commit))\n \t\t\t\treturn 1;\n \t\t}\n \t\treturn 0;\n \t}\n }\n \n+int is_descendant_of(struct commit *commit, struct commit_list *with_commit)\n+{\n+\treturn repo_is_descendant_of(the_repository, commit, with_commit);\n+}\n+\n /*\n * Is \"commit\" an ancestor of one of the \"references\"?\n */\n-- \ngitgitgadget\n\n"},{"id":"399979","messageId":"ead5a0d9bd3b5c4a8c3fde970941c0e4a10025ab.1592414670.git.gitgitgadget@gmail.com","threadId":"53702","inReplyTo":"pull.664.git.1592414670.gitgitgadget@gmail.com","subject":"[PATCH 2/2] commit-reach: use fast logic in repo_in_merge_base","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-06-17T17:24:29Z","receivedAt":"2020-06-17T17:24:38Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe repo_is_descendant_of() method is aware of the existence of the\ncommit-graph file. It checks for generation_numbers_enabled() before\ndeciding on using can_all_from_reach() or repo_in_merge_bases()\ndepending on the situation. The reason here is that can_all_from_reach()\nuses a depth-first search that is limited by the minimum generation\nnumber of the target commits, and that algorithm can be very slow when\ngeneration numbers are not present. The alternative uses\npaint_down_to_common() which will walk the entire merge-base boundary,\nwhich is typically slower.\n\nThis method is used by commands like \"git tag --contains\" and \"git\nbranch --contains\" for very fast results when a commit-graph file\nexists. Unfortunately, it is _not_ used in commands like \"git merge-base\n--is-ancestor\" which is doing an even simpler request.\n\nThis issue was raised recently [1] with respect to a change to how\ngeneration numbers are stored, but was also reported much earlier [2]\nbefore commit-reach.c existed to simplify these reachability queries.\n\n[1] https://lore.kernel.org/git/20200607195347.GA8232@szeder.dev/\n[2] https://lore.kernel.org/git/87608bawoa.fsf@evledraar.gmail.com/\n\nThe root cause is that builtin/merge-base.c has a method\nhandle_is_ancestor() that calls in_merge_bases(), an older version of\nrepo_in_merge_bases(). It would be better if we have every caller to\nin_merge_bases() use the logic in can_all_from_reach() when possible.\n\nThis is where things get a little tricky: repo_is_descendant_of() calls\nrepo_in_merge_bases() in the non-generation numbers enabled case! If we\nsimply update repo_in_merge_bases() to call repo_is_descendant_of()\ninstead of repo_in_merge_bases_many(), then we will get a recursive call\nloop. Thankfully, this is caught by the test suite in the default mode\n(i.e. GIT_TEST_COMMIT_GRAPH=0).\n\nThe trick, then, is to make the non-generation number case for\nrepo_is_descendant_of() call repo_in_merge_bases_many() directly,\nskipping the non-_many version. This allows us to take advantage of this\nfaster code path, when possible.\n\nThe easiest way to measure the performance impact is to test the\nfollowing command on the Linux kernel repository:\n\n\tgit merge-base --is-ancestor \n\n | A | B | Time Before | Time After |\n |------|------|-------------|------------|\n | v3.0 | v5.7 | 0.459s | 0.028s |\n | v4.0 | v5.7 | 0.267s | 0.021s |\n | v5.0 | v5.7 | 0.074s | 0.013s |\n\nNote that each of these samples return success. The old code performed\nthe same operation when and are swapped. However,\ncan_all_from_reach() will return immediately if the generation numbers\nshow that has larger generation number than . Thus, the time for\nthe swapped case is universally 0.004s in each case.\n\nReported-by: Ævar Arnfjörð Bjarmason \nReported-by: SZEDER Gábor \nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 12 ++++++++++--\n 1 file changed, 10 insertions(+), 2 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 13722430aa5..43e303d5f25 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -303,7 +303,7 @@ static int repo_is_descendant_of(struct repository *r,\n \n \t\t\tother = with_commit->item;\n \t\t\twith_commit = with_commit->next;\n-\t\t\tif (repo_in_merge_bases(r, other, commit))\n+\t\t\tif (repo_in_merge_bases_many(r, other, 1, &commit))\n \t\t\t\treturn 1;\n \t\t}\n \t\treturn 0;\n@@ -355,7 +355,15 @@ int repo_in_merge_bases(struct repository *r,\n \t\t\tstruct commit *commit,\n \t\t\tstruct commit *reference)\n {\n-\treturn repo_in_merge_bases_many(r, commit, 1, &reference);\n+\tint res;\n+\tstruct commit_list *list = NULL;\n+\tstruct commit_list **next = &list;\n+\n+\tnext = commit_list_append(commit, next);\n+\tres = repo_is_descendant_of(r, reference, list);\n+\tfree_commit_list(list);\n+\n+\treturn res;\n }\n \n struct commit_list *reduce_heads(struct commit_list *heads)\n-- \ngitgitgadget\n"},{"id":"400002","messageId":"xmqqzh91s9mn.fsf@gitster.c.googlers.com","threadId":"53702","inReplyTo":"pull.664.git.1592414670.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/2] Accelerate \"git merge-base --is-ancestor\"","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-06-17T20:46:56Z","receivedAt":"2020-06-17T20:47:01Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> It was recently [1] reported (and not-so-recently [2] reported) that \"git\n> merge-base --is-ancestor\" can be pretty slow. In fact, it is regularly\n> slower than \"git branch --contains\" or \"git tag --contains\", which are\n> answering a \"harder\" query.\n>\n> [1] https://lore.kernel.org/git/20200607195347.GA8232@szeder.dev/\n>\n> [2] https://lore.kernel.org/git/87608bawoa.fsf@evledraar.gmail.com/\n>\n> The root cause is that the in_merge_base() implementation is skipping the\n> fast can_all_from_reach() implementation and using paint_down_to_common()\n> instead. Note that these are equivalent: a commit A is in the set of\n> merge-bases between A and B if and only if B can reach A.\n\nOK, so in short, this codepath was not taking advantage of the\ngeneration numbers and that was the difference?\n\n"},{"id":"400016","messageId":"9bdbd5f7-7c12-e71a-4e1c-747d247abdc9@gmail.com","threadId":"53702","inReplyTo":"xmqqzh91s9mn.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 0/2] Accelerate \"git merge-base --is-ancestor\"","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-06-18T01:37:31Z","receivedAt":"2020-06-18T01:37:37Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/17/2020 4:46 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n> \n>> It was recently [1] reported (and not-so-recently [2] reported) that \"git\n>> merge-base --is-ancestor\" can be pretty slow. In fact, it is regularly\n>> slower than \"git branch --contains\" or \"git tag --contains\", which are\n>> answering a \"harder\" query.\n>>\n>> [1] https://lore.kernel.org/git/20200607195347.GA8232@szeder.dev/\n>>\n>> [2] https://lore.kernel.org/git/87608bawoa.fsf@evledraar.gmail.com/\n>>\n>> The root cause is that the in_merge_base() implementation is skipping the\n>> fast can_all_from_reach() implementation and using paint_down_to_common()\n>> instead. Note that these are equivalent: a commit A is in the set of\n>> merge-bases between A and B if and only if B can reach A.\n> \n> OK, so in short, this codepath was not taking advantage of the\n> generation numbers and that was the difference?\n\nCorrect. We now use generation numbers more often, when\navailable. All callers of in_merge_bases() will become\nfaster, which includes callers in these builtins:\n\n\t- branch\n\t- fetch\n\t- log\n\t- merge-base\n\t- receive-pack\n\nand these libgit files:\n\n\t- fast-import.c\n\t- http-push.c\n\t- merge-recursive.c (several!)\n\t- pack-bitmap-write.c\n\nThanks,\n-Stolee\n\n"},{"id":"400100","messageId":"20200619061013.GA10213@Abhishek-Arch","threadId":"53702","inReplyTo":"pull.664.git.1592414670.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/2] Accelerate \"git merge-base --is-ancestor\"","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-19T06:10:13Z","receivedAt":"2020-06-19T06:12:03Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"On Wed, Jun 17, 2020 at 05:24:27PM +0000, Derrick Stolee via GitGitGadget wrote:\n> It was recently [1] reported (and not-so-recently [2] reported) that \"git\n> merge-base --is-ancestor\" can be pretty slow. In fact, it is regularly\n> slower than \"git branch --contains\" or \"git tag --contains\", which are\n> answering a \"harder\" query.\n> \n> [1] https://lore.kernel.org/git/20200607195347.GA8232@szeder.dev/\n> \n> [2] https://lore.kernel.org/git/87608bawoa.fsf@evledraar.gmail.com/\n> \n> The root cause is that the in_merge_base() implementation is skipping the\n> fast can_all_from_reach() implementation and using paint_down_to_common()\n> instead. Note that these are equivalent: a commit A is in the set of\n> merge-bases between A and B if and only if B can reach A.\n> \n> This fixes the issue, and makes the performance degradation reported by\n> Szeder a non-issue.\n> \n> Thanks, -Stolee\n> \n> Derrick Stolee (2):\n> commit-reach: create repo_is_descendant_of()\n> commit-reach: use fast logic in repo_in_merge_base\n> \n> commit-reach.c | 21 ++++++++++++++++++---\n> 1 file changed, 18 insertions(+), 3 deletions(-)\n> \n> \n> base-commit: b3d7a52fac39193503a0b6728771d1bf6a161464\n> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-664%2Fderrickstolee%2Fmerge-base-is-ancestor-v1\n> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-664/derrickstolee/merge-base-is-ancestor-v1\n> Pull-Request: https://github.com/gitgitgadget/git/pull/664\n> -- \n> gitgitgadget\n\nWow! Thanks for investigating through the issue and following up. The\nperformance numbers speak for themselves.\n\nBy applying this series on the commit-slab patch series, both are now\njust as fast (master: 0.048s, commit-slab: 0.050s). \n\nRegards\nAbhishek\n"},{"id":"400760","messageId":"20200629134035.GA59624@syl.lan","threadId":"53702","inReplyTo":"8f7fd8f5941426c3ed7fc28c6e4afd62bcd4bb8d.1592414670.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/2] commit-reach: create repo_is_descendant_of()","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-06-29T13:40:35Z","receivedAt":"2020-06-29T19:37:48Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Wed, Jun 17, 2020 at 05:24:28PM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n>\n> The next change will make repo_in_merge_bases() depend on the logic in\n> is_descendant_of(), but we need to make the method independent of\n> the_repository first.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> commit-reach.c | 11 +++++++++--\n> 1 file changed, 9 insertions(+), 2 deletions(-)\n>\n> diff --git a/commit-reach.c b/commit-reach.c\n> index 4ca7e706a18..13722430aa5 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -283,7 +283,9 @@ struct commit_list *repo_get_merge_bases(struct repository *r,\n> /*\n> * Is \"commit\" a descendant of one of the elements on the \"with_commit\" list?\n> */\n> -int is_descendant_of(struct commit *commit, struct commit_list *with_commit)\n> +static int repo_is_descendant_of(struct repository *r,\n> +\t\t\t\t struct commit *commit,\n> +\t\t\t\t struct commit_list *with_commit)\n> {\n> \tif (!with_commit)\n> \t\treturn 1;\n> @@ -301,13 +303,18 @@ int is_descendant_of(struct commit *commit, struct commit_list *with_commit)\n>\n> \t\t\tother = with_commit->item;\n> \t\t\twith_commit = with_commit->next;\n> -\t\t\tif (in_merge_bases(other, commit))\n> +\t\t\tif (repo_in_merge_bases(r, other, commit))\n> \t\t\t\treturn 1;\n> \t\t}\n> \t\treturn 0;\n> \t}\n> }\n>\n> +int is_descendant_of(struct commit *commit, struct commit_list *with_commit)\n> +{\n> +\treturn repo_is_descendant_of(the_repository, commit, with_commit);\n> +}\n> +\n\nI don't think that it makes a big deal either way, but I wonder about\nmoving 'repo_is_descendant_of' to the header file, and making\n'is_descendant_of' be 'static inline int' as you defined it here.\n\nSince this has already graduated up to master already, I don't think\nthat it's worth going back just to shuffle this code around, but I was\nwondering if you had any specific reason for doing it this way.\n\n> /*\n> * Is \"commit\" an ancestor of one of the \"references\"?\n> */\n> --\n> gitgitgadget\n>\nThanks,\nTaylor\n"},{"id":"400790","messageId":"8dc7ae37-8587-b055-d18f-75a153129026@gmail.com","threadId":"53702","inReplyTo":"20200629134035.GA59624@syl.lan","subject":"Re: [PATCH 1/2] commit-reach: create repo_is_descendant_of()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-06-30T01:45:32Z","receivedAt":"2020-06-30T01:45:36Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/29/2020 9:40 AM, Taylor Blau wrote:\n> On Wed, Jun 17, 2020 at 05:24:28PM +0000, Derrick Stolee via GitGitGadget wrote:\n>> +int is_descendant_of(struct commit *commit, struct commit_list *with_commit)\n>> +{\n>> +\treturn repo_is_descendant_of(the_repository, commit, with_commit);\n>> +}\n>> +\n> \n> I don't think that it makes a big deal either way, but I wonder about\n> moving 'repo_is_descendant_of' to the header file, and making\n> 'is_descendant_of' be 'static inline int' as you defined it here.\n> \n> Since this has already graduated up to master already, I don't think\n> that it's worth going back just to shuffle this code around, but I was\n> wondering if you had any specific reason for doing it this way.\n\nI have good news for you. [1]\n\n[1] https://lore.kernel.org/git/20200623184222.54201-1-carenas@gmail.com/\n\nThanks,\n-Stolee\n"}]}