{"thread":{"id":"49261","subject":"[PATCH 0/1] v2.19.0-rc1 Performance Regression in 'git merge-base'","startedAt":"2018-08-30T12:58:11Z","lastAt":"2018-10-06T16:54:07Z","messageCount":5,"participants":["Derrick Stolee via GitGitGadget","Junio C Hamano","Jakub Narebski"],"isPatch":true,"patchVersion":1,"patchTotal":1},"messages":[{"id":"356969","messageId":"pull.28.git.gitgitgadget@gmail.com","threadId":"49261","inReplyTo":null,"subject":"[PATCH 0/1] v2.19.0-rc1 Performance Regression in 'git merge-base'","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-08-30T12:58:07Z","receivedAt":"2018-08-30T12:58:11Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"As I was testing the release candidate, I stumbled across a regression in\n'git merge-base' as a result of the switch to generation numbers. The commit\nmessage in [PATCH 1/1] describes the topology involved, but you can test it\nyourself by comparing 'git merge-base v4.8 v4.9' in the Linux kernel. The\nregression does not show up when running merge-base for tags at least v4.9,\nwhich is why I didn't see it when I was testing earlier.\n\nThe solution is simple, but also will conflict with ds/reachable in next. I\ncan send a similar patch that applies the same diff into commit-reach.c.\n\nWith the integration of generation numbers into most commit walks coming to\na close [1], it will be time to re-investigate other options for\nreachability indexes [2]. As I was digging into the issue with this\nregression, I discovered a way we can modify our generation numbers and pair\nthem with commit dates to give us a simple-to-compute, immutable\ntwo-dimensional reachability index that would be immune to this regression.\nI will investigate that more and report back, but it is more important to\nfix this regression now.\n\nThanks, -Stolee\n\n[1] https://public-inbox.org/git/pull.25.git.gitgitgadget@gmail.com/[PATCH\n0/6] Use generation numbers for --topo-order\n\n[2] https://public-inbox.org/git/86muxcuyod.fsf@gmail.com/[RFC] Other chunks\nfor commit-graph, part 2 - reachability indexes\n\nCc: gitster@pobox.comCc: peff@peff.net\n\nDerrick Stolee (1):\n commit: don't use generation numbers if not needed\n\n commit.c | 5 ++++-\n 1 file changed, 4 insertions(+), 1 deletion(-)\n\n\nbase-commit: 2f743933341f276111103550fbf383a34dfcfd38\nPublished-As: https://github.com/gitgitgadget/git/releases/tags/pr-28%2Fderrickstolee%2Fmerge-base-regression-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-28/derrickstolee/merge-base-regression-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/28\n-- \ngitgitgadget\n"},{"id":"356970","messageId":"efa3720fb40638e5d61c6130b55e3348d8e4339e.1535633886.git.gitgitgadget@gmail.com","threadId":"49261","inReplyTo":"pull.28.git.gitgitgadget@gmail.com","subject":"[PATCH 1/1] commit: don't use generation numbers if not needed","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-08-30T12:58:09Z","receivedAt":"2018-08-30T12:58:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nIn 3afc679b \"commit: use generations in paint_down_to_common()\",\nthe queue in paint_down_to_common() was changed to use a priority\norder based on generation number before commit date. This served\ntwo purposes:\n\n 1. When generation numbers are present, the walk guarantees\n correct topological relationships, regardless of clock skew in\n commit dates.\n\n 2. It enables short-circuiting the walk when the min_generation\n parameter is added in d7c1ec3e \"commit: add short-circuit to\n paint_down_to_common()\". This short-circuit helps commands\n like 'git branch --contains' from needing to walk to a merge\n base when we know the result is false.\n\nThe commit message for 3afc679b includes the following sentence:\n\n This change does not affect the number of commits that are\n walked during the execution of paint_down_to_common(), only\n the order that those commits are inspected.\n\nThis statement is incorrect. Because it changes the order in which\nthe commits are inspected, it changes the order they are added to\nthe queue, and hence can change the number of loops before the\nqueue_has_nonstale() method returns true.\n\nThis change makes a concrete difference depending on the topology\nof the commit graph. For instance, computing the merge-base between\nconsecutive versions of the Linux kernel has no effect for versions\nafter v4.9, but 'git merge-base v4.8 v4.9' presents a performance\nregression:\n\n v2.18.0: 0.122s\nv2.19.0-rc1: 0.547s\n HEAD: 0.127s\n\nTo determine that this was simply an ordering issue, I inserted\na counter within the while loop of paint_down_to_common() and\nfound that the loop runs 167,468 times in v2.18.0 and 635,579\ntimes in v2.19.0-rc1.\n\nThe topology of this case can be described in a simplified way\nhere:\n\n v4.9\n | \\\n | \\\n v4.8 \\\n | \\ \\\n | \\ |\n ... A B\n | / /\n | / /\n |/__/\n C\n\nHere, the \"...\" means \"a very long line of commits\". By generation\nnumber, A and B have generation one more than C. However, A and B\nhave commit date higher than most of the commits reachable from\nv4.8. When the walk reaches v4.8, we realize that it has PARENT1\nand PARENT2 flags, so everything it can reach is marked as STALE,\nincluding A. B has only the PARENT1 flag, so is not STALE.\n\nWhen paint_down_to_common() is run using\ncompare_commits_by_commit_date, A and B are removed from the queue\nearly and C is inserted into the queue. At this point, C and the\nrest of the queue entries are marked as STALE. The loop then\nterminates.\n\nWhen paint_down_to_common() is run using\ncompare_commits_by_gen_then_commit_date, B is removed from the\nqueue only after the many commits reachable from v4.8 are explored.\nThis causes the loop to run longer. The reason for this regression\nis simple: the queue order is intended to not explore a commit\nuntil everything that _could_ reach that commit is explored. From\nthe information gathered by the original ordering, we have no\nguarantee that there is not a commit D reachable from v4.8 that\ncan also reach B. We gained absolute correctness in exchange for\na performance regression.\n\nThe performance regression is probably the worse option, since\nthese incorrect results in paint_down_to_common() are rare. The\ntopology required for the performance regression are less rare,\nbut still require multiple merge commits where the parents differ\ngreatly in generation number. In our example above, the commit A\nis as important as the commit B to demonstrate the problem, since\notherwise the commit C will sit in the queue as non-stale just as\nlong in both orders.\n\nThe solution provided uses the min_generation parameter to decide\nif we should use generation numbers in our ordering. When\nmin_generation is equal to zero, it means that the caller has no\nknown cutoff for the walk, so we should rely on our commit-date\nheuristic as before; this is the case with merge_bases_many().\nWhen min_generation is non-zero, then the caller knows a valuable\ncutoff for the short-circuit mechanism; this is the case with\nremove_redundant() and in_merge_bases_many().\n\nSigned-off-by: Derrick Stolee \n---\n commit.c | 5 ++++-\n 1 file changed, 4 insertions(+), 1 deletion(-)\n\ndiff --git a/commit.c b/commit.c\nindex 1a6e632185..449c1f4920 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -874,6 +874,9 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n,\n \tint i;\n \tuint32_t last_gen = GENERATION_NUMBER_INFINITY;\n \n+\tif (!min_generation)\n+\t\tqueue.compare = compare_commits_by_commit_date;\n+\n \tone->object.flags |= PARENT1;\n \tif (!n) {\n \t\tcommit_list_append(one, &result);\n@@ -891,7 +894,7 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n,\n \t\tstruct commit_list *parents;\n \t\tint flags;\n \n-\t\tif (commit->generation > last_gen)\n+\t\tif (min_generation && commit->generation > last_gen)\n \t\t\tBUG(\"bad generation skip %8x > %8x at %s\",\n \t\t\t commit->generation, last_gen,\n \t\t\t oid_to_hex(&commit->object.oid));\n-- \ngitgitgadget\n"},{"id":"356984","messageId":"xmqqd0tz7u5p.fsf@gitster-ct.c.googlers.com","threadId":"49261","inReplyTo":"pull.28.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/1] v2.19.0-rc1 Performance Regression in 'git merge-base'","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-08-30T15:26:10Z","receivedAt":"2018-08-30T15:26:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> As I was testing the release candidate, I stumbled across a regression in\n> 'git merge-base' as a result of the switch to generation numbers. The commit\n> message in [PATCH 1/1] describes the topology involved,...\n\nI do not recall having seen this kind of updates during the\npre-release freeze of previous development cycles, and you are\nstarting a new trend with two findings so far in this cycle.\nHopefully this can become a good tradition.\n\nThanks.\n"},{"id":"359769","messageId":"865zyfys3f.fsf@gmail.com","threadId":"49261","inReplyTo":"pull.28.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/1] v2.19.0-rc1 Performance Regression in 'git merge-base'","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-10-06T16:09:40Z","receivedAt":"2018-10-06T16:11:10Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> As I was testing the release candidate, I stumbled across a regression in\n> 'git merge-base' as a result of the switch to generation numbers. The commit\n> message in [PATCH 1/1] describes the topology involved, but you can test it\n> yourself by comparing 'git merge-base v4.8 v4.9' in the Linux kernel. The\n> regression does not show up when running merge-base for tags at least v4.9,\n> which is why I didn't see it when I was testing earlier.\n\nStrange that it happens; I'll take a look.\n\n> The solution is simple, but also will conflict with ds/reachable in next. I\n> can send a similar patch that applies the same diff into commit-reach.c.\n>\n> With the integration of generation numbers into most commit walks coming to\n> a close [1], it will be time to re-investigate other options for\n> reachability indexes [2]. As I was digging into the issue with this\n> regression, I discovered a way we can modify our generation numbers and pair\n> them with commit dates to give us a simple-to-compute, immutable\n> two-dimensional reachability index that would be immune to this regression.\n> I will investigate that more and report back, but it is more important to\n> fix this regression now.\n\nI am interested in what you have created, especially because commit\ncreation dates are imperfect indicators because of clock skew etc.\n\n>\n> Thanks, -Stolee\n>\n> [1] https://public-inbox.org/git/pull.25.git.gitgitgadget@gmail.com/[PATCH\n> 0/6] Use generation numbers for --topo-order\n>\n> [2] https://public-inbox.org/git/86muxcuyod.fsf@gmail.com/[RFC] Other chunks\n> for commit-graph, part 2 - reachability indexes\n\nSince then I have found few more possible approaches:\n- working with repository metagraph[1], where all chains of commits were\n replaced by edge, perhaps together with DAG Reduction[2] boosting\n framework on this metagraph\n- using FELINE-like index (the Graph+Label approch, also known as online\n search), and for those where this index have false results, use Labels\n only approach[3]\n\n[1] Xian Tang et. al., \"An Optimized Labeling Scheme for Reachability\n Queries\", CMC, vol.55, no.2, pp.267-283, 2018\n[2] Marco Biazzini, Martin Monperrus, Benoit Baudry \"On Analyzing the\n Topology of Commit Histories in Decentralized Version Control\n Systems\", ICSME 2014 (conference paper)\n[3] Junfeng Zhou et. al., \"Accelerating reachability query processing\n based on DAG reduction\", The VLDB Journal (2018) 27: 271\n\n--\nJakub Narębski\n"},{"id":"359771","messageId":"86woqvxbh2.fsf@gmail.com","threadId":"49261","inReplyTo":"efa3720fb40638e5d61c6130b55e3348d8e4339e.1535633886.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/1] commit: don't use generation numbers if not needed","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-10-06T16:54:01Z","receivedAt":"2018-10-06T16:54:07Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> From: Derrick Stolee \n>\n> In 3afc679b \"commit: use generations in paint_down_to_common()\",\n> the queue in paint_down_to_common() was changed to use a priority\n> order based on generation number before commit date. This served\n> two purposes:\n>\n> 1. When generation numbers are present, the walk guarantees\n> correct topological relationships, regardless of clock skew in\n> commit dates.\n\nWhich means that we would walk no more commits that there are on the\n_longest_ path...\n\n> 2. It enables short-circuiting the walk when the min_generation\n> parameter is added in d7c1ec3e \"commit: add short-circuit to\n> paint_down_to_common()\". This short-circuit helps commands\n> like 'git branch --contains' from needing to walk to a merge\n> base when we know the result is false.\n>\n> The commit message for 3afc679b includes the following sentence:\n>\n> This change does not affect the number of commits that are\n> walked during the execution of paint_down_to_common(), only\n> the order that those commits are inspected.\n>\n> This statement is incorrect. Because it changes the order in which\n> the commits are inspected, it changes the order they are added to\n> the queue, and hence can change the number of loops before the\n> queue_has_nonstale() method returns true.\n\n...which does not mean that it would walk no more commits than on\nshortest path; thus it can give performance regression if it chooses to\nwalk longer path first, compared to date-based heuristic if it chooses\nshorter one (but can walk few commits more that strictly necessary on\nchosen path).\n\nO.K., I can understand that.\n\n>\n> This change makes a concrete difference depending on the topology\n> of the commit graph. For instance, computing the merge-base between\n> consecutive versions of the Linux kernel has no effect for versions\n> after v4.9, but 'git merge-base v4.8 v4.9' presents a performance\n> regression:\n>\n> v2.18.0: 0.122s\n> v2.19.0-rc1: 0.547s\n> HEAD: 0.127s\n\nNow I will wonder if the 0.005s difference between v2.18.0 and HEAD\nversion is within the noise (within the standard deviation), or\nnot... (just kidding).\n\n>\n> To determine that this was simply an ordering issue, I inserted\n> a counter within the while loop of paint_down_to_common() and\n> found that the loop runs 167,468 times in v2.18.0 and 635,579\n> times in v2.19.0-rc1.\n\nNice analysis.\n\n>\n> The topology of this case can be described in a simplified way\n> here:\n>\n> v4.9\n> | \\\n> | \\\n> v4.8 \\\n> | \\ \\\n> | \\ |\n> ... A B\n> | / /\n> | / /\n> |/__/\n> C\n>\n> Here, the \"...\" means \"a very long line of commits\". By generation\n> number, A and B have generation one more than C. However, A and B\n> have commit date higher than most of the commits reachable from\n> v4.8. When the walk reaches v4.8, we realize that it has PARENT1\n> and PARENT2 flags, so everything it can reach is marked as STALE,\n> including A. B has only the PARENT1 flag, so is not STALE.\n>\n> When paint_down_to_common() is run using\n> compare_commits_by_commit_date, A and B are removed from the queue\n> early and C is inserted into the queue. At this point, C and the\n> rest of the queue entries are marked as STALE. The loop then\n> terminates.\n>\n> When paint_down_to_common() is run using\n> compare_commits_by_gen_then_commit_date, B is removed from the\n> queue only after the many commits reachable from v4.8 are explored.\n> This causes the loop to run longer. The reason for this regression\n> is simple: the queue order is intended to not explore a commit\n> until everything that _could_ reach that commit is explored. From\n> the information gathered by the original ordering, we have no\n> guarantee that there is not a commit D reachable from v4.8 that\n> can also reach B.\n\nSo the problem is with shortcuts, i.e. merges of short-length branches\n(like e.g. fixup topic branches) based on an older commits (like best\npractices recommend: base off oldest applicable commit). Due to the\nbottom-up nature of generation numbers examining such shortcut is\npostponed, compared to \"heuristic\" ordering by the creation date.\n\nBy problem I mean that generation-number based code gives worse\nperformance than commitdate-based code.\n\n> We gained absolute correctness in exchange for\n> a performance regression.\n\nOr rather we gained better worst case performance in exchange for worse\naverage case performance (thus a performance regression).\n\n> The performance regression is probably the worse option, since\n> these incorrect results in paint_down_to_common() are rare. The\n> topology required for the performance regression are less rare,\n> but still require multiple merge commits where the parents differ\n> greatly in generation number. In our example above, the commit A\n> is as important as the commit B to demonstrate the problem, since\n> otherwise the commit C will sit in the queue as non-stale just as\n> long in both orders.\n\nAll right, that is good explanation of why the change. Worst case\nperformance is rare, performance in case of \"shortcuts\" is more\nimportant: they are more often (I guess -- are there any tests for\nthis?).\n\n> The solution provided uses the min_generation parameter to decide\n> if we should use generation numbers in our ordering. When\n> min_generation is equal to zero, it means that the caller has no\n> known cutoff for the walk, so we should rely on our commit-date\n> heuristic as before; this is the case with merge_bases_many().\n> When min_generation is non-zero, then the caller knows a valuable\n> cutoff for the short-circuit mechanism; this is the case with\n> remove_redundant() and in_merge_bases_many().\n\nTLDR; use compare_commits_by_commit_date() if there is no min generation\ncutoff, compare_commits_by_gen_then_commit_date() otherwise, right?\n\n> Signed-off-by: Derrick Stolee \n> ---\n> commit.c | 5 ++++-\n> 1 file changed, 4 insertions(+), 1 deletion(-)\n>\n> diff --git a/commit.c b/commit.c\n> index 1a6e632185..449c1f4920 100644\n> --- a/commit.c\n> +++ b/commit.c\n> @@ -874,6 +874,9 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n,\n> \tint i;\n> \tuint32_t last_gen = GENERATION_NUMBER_INFINITY;\n> \n> +\tif (!min_generation)\n> +\t\tqueue.compare = compare_commits_by_commit_date;\n> +\n> \tone->object.flags |= PARENT1;\n> \tif (!n) {\n> \t\tcommit_list_append(one, &result);\n> @@ -891,7 +894,7 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n,\n> \t\tstruct commit_list *parents;\n> \t\tint flags;\n> \n> -\t\tif (commit->generation > last_gen)\n> +\t\tif (min_generation && commit->generation > last_gen)\n> \t\t\tBUG(\"bad generation skip %8x > %8x at %s\",\n> \t\t\t commit->generation, last_gen,\n> \t\t\t oid_to_hex(&commit->object.oid));\n"}]}