{"thread":{"id":"49607","subject":"[PATCH 0/1] commit-reach: fix first-parent heuristic","startedAt":"2018-10-18T17:24:41Z","lastAt":"2018-10-22T02:30:00Z","messageCount":7,"participants":["Derrick Stolee via GitGitGadget","Junio C Hamano","Derrick Stolee","Jeff Hostetler"],"isPatch":true,"patchVersion":1,"patchTotal":1},"messages":[{"id":"360853","messageId":"pull.51.git.gitgitgadget@gmail.com","threadId":"49607","inReplyTo":null,"subject":"[PATCH 0/1] commit-reach: fix first-parent heuristic","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-10-18T17:24:38Z","receivedAt":"2018-10-18T17:24:41Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"I originally reported this fix [1] after playing around with the trace2\nseries for measuring performance. Since trace2 isn't merging quickly, I\npulled the performance fix patch out and am sending it on its own. The only\ndifference here is that we don't have the tracing to verify the performance\nfix in the test script.\n\nSee the patch message for details about the fix.\n\nThanks, -Stolee\n\n[1] \nhttps://public-inbox.org/git/20180906151309.66712-7-dstolee@microsoft.com/\n\n[RFC PATCH 6/6] commit-reach: fix first-parent heuristic\n\nDerrick Stolee (1):\n commit-reach: fix first-parent heuristic\n\n commit-reach.c | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\n\nbase-commit: a4b8ab5363a32f283a61ef3a962853556d136c0e\nPublished-As: https://github.com/gitgitgadget/git/releases/tags/pr-51%2Fderrickstolee%2Ffirst-parent-heuristic-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-51/derrickstolee/first-parent-heuristic-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/51\n-- \ngitgitgadget\n"},{"id":"360854","messageId":"53ebceb7f11d1e1ea39ae4ca86850190ae839eff.1539883476.git.gitgitgadget@gmail.com","threadId":"49607","inReplyTo":"pull.51.git.gitgitgadget@gmail.com","subject":"[PATCH 1/1] commit-reach: fix first-parent heuristic","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-10-18T17:24:40Z","receivedAt":"2018-10-18T17:24:44Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe algorithm in can_all_from_reach_with_flags() performs a depth-\nfirst-search, terminated by generation number, intending to use\na hueristic that \"important\" commits are found in the first-parent\nhistory. This heuristic is valuable in scenarios like fetch\nnegotiation.\n\nHowever, there is a problem! After the search finds a target commit,\nit should pop all commits off the stack and mark them as \"can reach\".\nThis logic is incorrect, so the algorithm instead walks all reachable\ncommits above the generation-number cutoff.\n\nThe existing algorithm is still an improvement over the previous\nalgorithm, as the worst-case complexity went from quadratic to linear.\nThe performance measurement at the time was good, but not dramatic.\nBy fixing this heuristic, we reduce the number of walked commits.\n\nWe can also re-run the performance tests from commit 4fbcca4e\n\"commit-reach: make can_all_from_reach... linear\".\n\nPerformance was measured on the Linux repository using\n'test-tool reach can_all_from_reach'. The input included rows seeded by\ntag values. The \"small\" case included X-rows as v4.[0-9]* and Y-rows as\nv3.[0-9]*. This mimics a (very large) fetch that says \"I have all major\nv3 releases and want all major v4 releases.\" The \"large\" case included\nX-rows as \"v4.*\" and Y-rows as \"v3.*\". This adds all release-candidate\ntags to the set, which does not greatly increase the number of objects\nthat are considered, but does increase the number of 'from' commits,\ndemonstrating the quadratic nature of the previous code.\n\nSmall Case:\n\n4fbcca4e~1: 0.85 s\n 4fbcca4e: 0.26 s (num_walked: 1,011,035)\n HEAD: 0.14 s (num_walked: 8,601)\n\nLarge Case:\n\n4fbcca4e~1: 24.0 s\n 4fbcca4e: 0.12 s (num_walked: 503,925)\n HEAD: 0.06 s (num_walked: 217,243)\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 9f79ce0a22..79419be8af 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -593,8 +593,10 @@ int can_all_from_reach_with_flag(struct object_array *from,\n \t\twhile (stack) {\n \t\t\tstruct commit_list *parent;\n \n-\t\t\tif (stack->item->object.flags & with_flag) {\n+\t\t\tif (stack->item->object.flags & (with_flag | RESULT)) {\n \t\t\t\tpop_commit(&stack);\n+\t\t\t\tif (stack)\n+\t\t\t\t\tstack->item->object.flags |= RESULT;\n \t\t\t\tcontinue;\n \t\t\t}\n \n-- \ngitgitgadget\n"},{"id":"360894","messageId":"xmqqk1me3bw0.fsf@gitster-ct.c.googlers.com","threadId":"49607","inReplyTo":"pull.51.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/1] commit-reach: fix first-parent heuristic","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-10-19T02:31:43Z","receivedAt":"2018-10-19T02:31:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> I originally reported this fix [1] after playing around with the trace2\n> series for measuring performance. Since trace2 isn't merging quickly, I\n> pulled the performance fix patch out and am sending it on its own. The only\n> difference here is that we don't have the tracing to verify the performance\n> fix in the test script.\n\nThanks for sending this separately. What's the current status of\nthe tracing patch series, by the way?\n"},{"id":"360900","messageId":"xmqqd0s61pat.fsf@gitster-ct.c.googlers.com","threadId":"49607","inReplyTo":"53ebceb7f11d1e1ea39ae4ca86850190ae839eff.1539883476.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/1] commit-reach: fix first-parent heuristic","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-10-19T05:24:58Z","receivedAt":"2018-10-19T05:25:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> We can also re-run the performance tests from commit 4fbcca4e\n> \"commit-reach: make can_all_from_reach... linear\".\n>\n> Performance was measured on the Linux repository using\n> 'test-tool reach can_all_from_reach'. The input included rows seeded by\n> tag values. The \"small\" case included X-rows as v4.[0-9]* and Y-rows as\n> v3.[0-9]*. This mimics a (very large) fetch that says \"I have all major\n> v3 releases and want all major v4 releases.\" The \"large\" case included\n> X-rows as \"v4.*\" and Y-rows as \"v3.*\". This adds all release-candidate\n> tags to the set, which does not greatly increase the number of objects\n> that are considered, but does increase the number of 'from' commits,\n> demonstrating the quadratic nature of the previous code.\n\nThese micro-benchmarks are interesting, but we should also remember\nto describe the impact of the bug being fixed in the larger picture.\nWhat end-user visible operations are affected? Computing merge-base?\nFinding if a push fast-forwards? Something else?\n"},{"id":"360911","messageId":"d8a21999-3080-0989-49ae-995074cf7672@gmail.com","threadId":"49607","inReplyTo":"xmqqd0s61pat.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 1/1] commit-reach: fix first-parent heuristic","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-10-19T12:32:19Z","receivedAt":"2018-10-19T12:32:25Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/19/2018 1:24 AM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n>\n>> We can also re-run the performance tests from commit 4fbcca4e\n>> \"commit-reach: make can_all_from_reach... linear\".\n>>\n>> Performance was measured on the Linux repository using\n>> 'test-tool reach can_all_from_reach'. The input included rows seeded by\n>> tag values. The \"small\" case included X-rows as v4.[0-9]* and Y-rows as\n>> v3.[0-9]*. This mimics a (very large) fetch that says \"I have all major\n>> v3 releases and want all major v4 releases.\" The \"large\" case included\n>> X-rows as \"v4.*\" and Y-rows as \"v3.*\". This adds all release-candidate\n>> tags to the set, which does not greatly increase the number of objects\n>> that are considered, but does increase the number of 'from' commits,\n>> demonstrating the quadratic nature of the previous code.\n> These micro-benchmarks are interesting, but we should also remember\n> to describe the impact of the bug being fixed in the larger picture.\n> What end-user visible operations are affected? Computing merge-base?\n> Finding if a push fast-forwards? Something else?\n\nSorry about that. Here is a description that could be inserted into the \ncommit message:\n\nThe can_all_from_reach() method synthesizes the logic for one iteration \nof can_all_from_reach_with_flags() which is used by the server during \nfetch negotiation to determine if more haves/wants are needed. The logic \nis also used by is_descendant_of() which is used to check if a \nforce-push is required and in 'git branch --contains'.\n\nThanks,\n-Stolee\n"},{"id":"360978","messageId":"c28702fa-f25c-08be-f061-1e5881e82f1a@jeffhostetler.com","threadId":"49607","inReplyTo":"xmqqk1me3bw0.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 0/1] commit-reach: fix first-parent heuristic","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2018-10-19T19:40:51Z","receivedAt":"2018-10-19T19:50:33Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 10/18/2018 10:31 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n> \n>> I originally reported this fix [1] after playing around with the trace2\n>> series for measuring performance. Since trace2 isn't merging quickly, I\n>> pulled the performance fix patch out and am sending it on its own. The only\n>> difference here is that we don't have the tracing to verify the performance\n>> fix in the test script.\n> \n> Thanks for sending this separately. What's the current status of\n> the tracing patch series, by the way?\n> \n\nI'm still working on it. I hope to reroll and submit a new version\nnext week. We are currently dogfooding a version of it with our gvfs\nusers.\n\nJeff\n"},{"id":"361111","messageId":"xmqqk1mayaql.fsf@gitster-ct.c.googlers.com","threadId":"49607","inReplyTo":"d8a21999-3080-0989-49ae-995074cf7672@gmail.com","subject":"Re: [PATCH 1/1] commit-reach: fix first-parent heuristic","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-10-22T02:29:54Z","receivedAt":"2018-10-22T02:30:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> On 10/19/2018 1:24 AM, Junio C Hamano wrote:\n>> \"Derrick Stolee via GitGitGadget\" writes:\n>>\n>>> We can also re-run the performance tests from commit 4fbcca4e\n>>> \"commit-reach: make can_all_from_reach... linear\".\n>>>\n>>> Performance was measured on the Linux repository using\n>>> 'test-tool reach can_all_from_reach'. The input included rows seeded by\n>>> tag values. The \"small\" case included X-rows as v4.[0-9]* and Y-rows as\n>>> v3.[0-9]*. This mimics a (very large) fetch that says \"I have all major\n>>> v3 releases and want all major v4 releases.\" The \"large\" case included\n>>> X-rows as \"v4.*\" and Y-rows as \"v3.*\". This adds all release-candidate\n>>> tags to the set, which does not greatly increase the number of objects\n>>> that are considered, but does increase the number of 'from' commits,\n>>> demonstrating the quadratic nature of the previous code.\n>> These micro-benchmarks are interesting, but we should also remember\n>> to describe the impact of the bug being fixed in the larger picture.\n>> What end-user visible operations are affected? Computing merge-base?\n>> Finding if a push fast-forwards? Something else?\n>\n> Sorry about that. Here is a description that could be inserted into\n> the commit message:\n>\n> The can_all_from_reach() method synthesizes the logic for one\n> iteration of can_all_from_reach_with_flags() which is used by the\n> server during fetch negotiation to determine if more haves/wants are\n> needed. The logic is also used by is_descendant_of() which is used to\n> check if a force-push is required and in 'git branch --contains'.\n\nI am afraid that it is still not end-user serving enough. The level\nof \"larger picture\" I had in mind was those that would appear as an\nentry in the release notes, e.g. (this is for illustration purposes\nonly; I do not claim its actual contents is correct).\n\n\tWe started using commit generation numbers in various\n\treachability computations, but due to a bug, negitiation\n\tbetween the \"git fetch\" and the server started to require\n\t30% more roundtrips than necessary, and it has become less\n\tefficient to see if a commit is a descendant of another\n\tcommit in certain cases, which has been corrected in this\n\trelease.\n\nThanks.\n"}]}