{"thread":{"id":"53046","subject":"[PATCH 0/1] commit-graph: avoid unnecessary tag deference when merging","startedAt":"2020-03-21T03:44:36Z","lastAt":"2020-03-27T15:04:05Z","messageCount":31,"participants":["Taylor Blau","Junio C Hamano","Jeff King","Derrick Stolee","SZEDER Gábor"],"isPatch":true,"patchVersion":1,"patchTotal":1},"messages":[{"id":"393573","messageId":"cover.1584762087.git.me@ttaylorr.com","threadId":"53046","inReplyTo":null,"subject":"[PATCH 0/1] commit-graph: avoid unnecessary tag deference when merging","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-03-21T03:44:16Z","receivedAt":"2020-03-21T03:44:36Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Hi,\n\nHere's a patch that Peff and I were kicking around from a couple of\nmonths ago when we were investigating deploying commit-graphs at GitHub.\nParticularly, we were looking into why merging two commit-graphs after a\nwrite with '--split' took as much time as we were seeing in our\ninfrastructure.\n\nThis patch avoids an unnecessary tag dereference in\n'merge_commit_graph()', which can improve the running time of a\ncommit-graph write by around ~7.4% on average.\n\nThanks in advance for your review.\n\nTaylor Blau (1):\n commit-graph.c: avoid unnecessary tag dereference when merging\n\n commit-graph.c | 8 ++++++--\n 1 file changed, 6 insertions(+), 2 deletions(-)\n\n--\n2.26.0.rc2.311.g8e52d2684b\n"},{"id":"393574","messageId":"4c79a9ea909ebff8c0987bcf95692da92e79bda4.1584762087.git.me@ttaylorr.com","threadId":"53046","inReplyTo":"cover.1584762087.git.me@ttaylorr.com","subject":"[PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-03-21T03:44:23Z","receivedAt":"2020-03-21T03:44:36Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"When performing a 'git commit-graph write' with '--split', the\ncommit-graph machinery calls 'merge_commit_graph()' after deciding on a\nsplit strategy to optionally clean up any existing commit-graph\nlayers that were made obsolete by the split strategy [1].\n\nAt this time, 'merge_commit_graph()' checks each commit that it writes\ninto the merged graph to make sure that it still exists in the object\nstore.\n\nTo do this, it uses 'lookup_commit_reference_gently()', which accepts\neither a commit object, or a tag that refers to a commit. However, since\nall 'oid' arguments passed to this function are from within the\ncommit-graphs being merged, we never pass a commit reference, and so any\ntime we spend in 'deref_tag()' is wasted.\n\nImprove the situation by using 'repo_has_object_file' to check if the\nobject still exists, and '{lookup,repo_parse}_commit()' to turn it into\na bona-fide 'struct commit *'.\n\nIn my testing environment, this improves the time to \"merge\" a split\ncommit-graph containing all reachable commits in the kernel by\nre-writing the same commit-graph (effectively measuring the time it\ntakes to check that all of those commits still exist) from:\n\n Attempt 1: 9.614\n Attempt 2: 10.984\n Attempt 3: 10.39\n Attempt 4: 9.14\n Attempt 5: 9.439\n\n real\t0m9.140s\n user\t0m8.207s\n sys\t0m0.602s\n\nto:\n\n Attempt 1: 9.12\n Attempt 2: 8.904\n Attempt 3: 9.361\n Attempt 4: 9.288\n Attempt 5: 9.677\n\n real\t0m8.904s\n user\t0m8.208s\n sys\t0m0.596s\n\nyielding a modest ~2.6% improvement in the best timings from each run,\nand ~7.4% improvement on average.\n\n[1]: This can happen if, for example, the new commit-graph exceeds the\n maximum allowed factor on the number of commits.\n\nCo-authored-by: Jeff King \nSigned-off-by: Jeff King \nSigned-off-by: Taylor Blau \n---\n commit-graph.c | 8 ++++++--\n 1 file changed, 6 insertions(+), 2 deletions(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex f013a84e29..c7cfadc786 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -1599,14 +1599,18 @@ static void merge_commit_graph(struct write_commit_graph_context *ctx,\n \n \tfor (i = 0; i < g->num_commits; i++) {\n \t\tstruct object_id oid;\n-\t\tstruct commit *result;\n+\t\tstruct commit *result = NULL;\n \n \t\tdisplay_progress(ctx->progress, i + 1);\n \n \t\tload_oid_from_graph(g, i + offset, &oid);\n \n \t\t/* only add commits if they still exist in the repo */\n-\t\tresult = lookup_commit_reference_gently(ctx->r, &oid, 1);\n+\t\tif (repo_has_object_file(ctx->r, &oid)) {\n+\t\t\tresult = lookup_commit(ctx->r, &oid);\n+\t\t\tif (repo_parse_commit(ctx->r, result))\n+\t\t\t\tresult = NULL;\n+\t\t}\n \n \t\tif (result) {\n \t\t\tctx->commits.list[ctx->commits.nr] = result;\n-- \n2.26.0.rc2.311.g8e52d2684b\n"},{"id":"393576","messageId":"xmqqo8sq9uhb.fsf@gitster.c.googlers.com","threadId":"53046","inReplyTo":"cover.1584762087.git.me@ttaylorr.com","subject":"Re: [PATCH 0/1] commit-graph: avoid unnecessary tag deference when merging","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-03-21T04:56:16Z","receivedAt":"2020-03-21T04:56:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n> This patch avoids an unnecessary tag dereference in\n> 'merge_commit_graph()', which can improve the running time of a\n> commit-graph write by around ~7.4% on average.\n\nThat I suspect depends heavily on what portion of your total\ncommittishes consist of tags, no (in an absurdly extreme case, if\nthere is no tag in the repository, there won't be any improvement)?\n\nWhat tag-vs-commit ratio is the above \"average\" number based on?\n\nThanks.\n"},{"id":"393577","messageId":"20200321050025.GA1438317@coredump.intra.peff.net","threadId":"53046","inReplyTo":"4c79a9ea909ebff8c0987bcf95692da92e79bda4.1584762087.git.me@ttaylorr.com","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-21T05:00:25Z","receivedAt":"2020-03-21T05:00:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 20, 2020 at 09:44:23PM -0600, Taylor Blau wrote:\n\n> In my testing environment, this improves the time to \"merge\" a split\n> commit-graph containing all reachable commits in the kernel by\n> re-writing the same commit-graph (effectively measuring the time it\n> takes to check that all of those commits still exist) from:\n> \n> Attempt 1: 9.614\n> Attempt 2: 10.984\n> Attempt 3: 10.39\n> Attempt 4: 9.14\n> Attempt 5: 9.439\n> \n> real\t0m9.140s\n> user\t0m8.207s\n> sys\t0m0.602s\n> \n> to:\n> \n> Attempt 1: 9.12\n> Attempt 2: 8.904\n> Attempt 3: 9.361\n> Attempt 4: 9.288\n> Attempt 5: 9.677\n> \n> real\t0m8.904s\n> user\t0m8.208s\n> sys\t0m0.596s\n> \n> yielding a modest ~2.6% improvement in the best timings from each run,\n> and ~7.4% improvement on average.\n\nThat still seems really slow to me. If we were truly eliding the load of\nmost of the commit objects, I'd expect an order of magnitude or so\nimprovement. For example, with a fully constructed commit graph in\nlinux.git, I get:\n\n $ time git -c core.commitGraph=1 rev-list HEAD | wc -l\n 886922\n\n real\t0m1.088s\n user\t0m0.659s\n sys\t0m1.161s\n\n $ time git -c core.commitGraph=0 rev-list HEAD | wc -l\n 886922\n\n real\t0m7.185s\n user\t0m6.729s\n sys\t0m1.882s\n\nObviously not the same operation, but that should give us a rough idea\nthat commit graph lookups are 6-7 times cheaper than loading the actual\nobjects. I don't remember the details of the case that originally led us\ntowards this patch. Can you share more of the setup you used to generate\nthe numbers above (which repo, but more importantly the commands to\ncreate the initial state and then time the test).\n\nThe patch otherwise still makes sense to me, but I suspect there are\nother similar optimizations nearby that we'll need to do in tandem.\n\n-Peff\n"},{"id":"393578","messageId":"xmqqk13e9u7x.fsf@gitster.c.googlers.com","threadId":"53046","inReplyTo":"4c79a9ea909ebff8c0987bcf95692da92e79bda4.1584762087.git.me@ttaylorr.com","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-03-21T05:01:54Z","receivedAt":"2020-03-21T05:01:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n> When performing a 'git commit-graph write' with '--split', the\n> commit-graph machinery calls 'merge_commit_graph()' after deciding on a\n> split strategy to optionally clean up any existing commit-graph\n> layers that were made obsolete by the split strategy [1].\n>\n> At this time, 'merge_commit_graph()' checks each commit that it writes\n> into the merged graph to make sure that it still exists in the object\n> store.\n>\n> To do this, it uses 'lookup_commit_reference_gently()', which accepts\n> either a commit object, or a tag that refers to a commit. However, since\n> all 'oid' arguments passed to this function are from within the\n> commit-graphs being merged, we never pass a commit reference, and so any\n> time we spend in 'deref_tag()' is wasted.\n\nAhh, so my question on the cover letter was utterly off the mark.\nIt is that feeding a commit to deref_tag() is unneeded. It is quite\nsurprising to hear that deref_tag() call is _so_ expensive that it\nwastes 7% of the total cycles.\n\nThe patch itself looks good.\n\nThanks.\n\n\n> \tfor (i = 0; i < g->num_commits; i++) {\n> \t\tstruct object_id oid;\n> -\t\tstruct commit *result;\n> +\t\tstruct commit *result = NULL;\n> \n> \t\tdisplay_progress(ctx->progress, i + 1);\n> \n> \t\tload_oid_from_graph(g, i + offset, &oid);\n> \n> \t\t/* only add commits if they still exist in the repo */\n> -\t\tresult = lookup_commit_reference_gently(ctx->r, &oid, 1);\n> +\t\tif (repo_has_object_file(ctx->r, &oid)) {\n> +\t\t\tresult = lookup_commit(ctx->r, &oid);\n> +\t\t\tif (repo_parse_commit(ctx->r, result))\n> +\t\t\t\tresult = NULL;\n> +\t\t}\n> \n> \t\tif (result) {\n> \t\t\tctx->commits.list[ctx->commits.nr] = result;\n"},{"id":"393579","messageId":"20200321050455.GB1438317@coredump.intra.peff.net","threadId":"53046","inReplyTo":"xmqqo8sq9uhb.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 0/1] commit-graph: avoid unnecessary tag deference when merging","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-21T05:04:55Z","receivedAt":"2020-03-21T05:04:58Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 20, 2020 at 09:56:16PM -0700, Junio C Hamano wrote:\n\n> Taylor Blau writes:\n> \n> > This patch avoids an unnecessary tag dereference in\n> > 'merge_commit_graph()', which can improve the running time of a\n> > commit-graph write by around ~7.4% on average.\n> \n> That I suspect depends heavily on what portion of your total\n> committishes consist of tags, no (in an absurdly extreme case, if\n> there is no tag in the repository, there won't be any improvement)?\n> \n> What tag-vs-commit ratio is the above \"average\" number based on?\n\nI think the point is that in this code path we've already identified the\ncandidates as commits (because they were in an existing commit-graph\nfile), so treating the items as a committishes in the first place is\nunnecessary. If an object isn't itself a commit, we should be dropping\nit from the proposed output (possibly we ought to give a warning in such\na case, too, as it indicates the previous writer did something wrong).\n\n-Peff\n"},{"id":"393580","messageId":"20200321061231.GB30636@syl.local","threadId":"53046","inReplyTo":"20200321050455.GB1438317@coredump.intra.peff.net","subject":"Re: [PATCH 0/1] commit-graph: avoid unnecessary tag deference when merging","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-03-21T06:12:31Z","receivedAt":"2020-03-21T06:20:44Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sat, Mar 21, 2020 at 01:04:55AM -0400, Jeff King wrote:\n> On Fri, Mar 20, 2020 at 09:56:16PM -0700, Junio C Hamano wrote:\n>\n> > Taylor Blau writes:\n> >\n> > > This patch avoids an unnecessary tag dereference in\n> > > 'merge_commit_graph()', which can improve the running time of a\n> > > commit-graph write by around ~7.4% on average.\n> >\n> > That I suspect depends heavily on what portion of your total\n> > committishes consist of tags, no (in an absurdly extreme case, if\n> > there is no tag in the repository, there won't be any improvement)?\n> >\n> > What tag-vs-commit ratio is the above \"average\" number based on?\n>\n> I think the point is that in this code path we've already identified the\n> candidates as commits (because they were in an existing commit-graph\n> file), so treating the items as a committishes in the first place is\n> unnecessary. If an object isn't itself a commit, we should be dropping\n> it from the proposed output (possibly we ought to give a warning in such\n> a case, too, as it indicates the previous writer did something wrong).\n\nYes, exactly. Thank you.\n\n> -Peff\n\nThanks,\nTaylor\n"},{"id":"393581","messageId":"20200321061141.GA30636@syl.local","threadId":"53046","inReplyTo":"20200321050025.GA1438317@coredump.intra.peff.net","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-03-21T06:11:41Z","receivedAt":"2020-03-21T06:20:44Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sat, Mar 21, 2020 at 01:00:25AM -0400, Jeff King wrote:\n> On Fri, Mar 20, 2020 at 09:44:23PM -0600, Taylor Blau wrote:\n>\n> > In my testing environment, this improves the time to \"merge\" a split\n> > commit-graph containing all reachable commits in the kernel by\n> > re-writing the same commit-graph (effectively measuring the time it\n> > takes to check that all of those commits still exist) from:\n> >\n> > Attempt 1: 9.614\n> > Attempt 2: 10.984\n> > Attempt 3: 10.39\n> > Attempt 4: 9.14\n> > Attempt 5: 9.439\n> >\n> > real\t0m9.140s\n> > user\t0m8.207s\n> > sys\t0m0.602s\n> >\n> > to:\n> >\n> > Attempt 1: 9.12\n> > Attempt 2: 8.904\n> > Attempt 3: 9.361\n> > Attempt 4: 9.288\n> > Attempt 5: 9.677\n> >\n> > real\t0m8.904s\n> > user\t0m8.208s\n> > sys\t0m0.596s\n> >\n> > yielding a modest ~2.6% improvement in the best timings from each run,\n> > and ~7.4% improvement on average.\n>\n> That still seems really slow to me. If we were truly eliding the load of\n> most of the commit objects, I'd expect an order of magnitude or so\n> improvement. For example, with a fully constructed commit graph in\n> linux.git, I get:\n>\n> $ time git -c core.commitGraph=1 rev-list HEAD | wc -l\n> 886922\n>\n> real\t0m1.088s\n> user\t0m0.659s\n> sys\t0m1.161s\n>\n> $ time git -c core.commitGraph=0 rev-list HEAD | wc -l\n> 886922\n>\n> real\t0m7.185s\n> user\t0m6.729s\n> sys\t0m1.882s\n>\n> Obviously not the same operation, but that should give us a rough idea\n> that commit graph lookups are 6-7 times cheaper than loading the actual\n> objects. I don't remember the details of the case that originally led us\n> towards this patch. Can you share more of the setup you used to generate\n> the numbers above (which repo, but more importantly the commands to\n> create the initial state and then time the test).\n\nSure. I'm running best-of-five on the time it takes to re-generate and\nmerge a commit-graph based on in-pack commits.\n\nThe script is (in linux.git):\n\n $ best-of-five \\\n -p 'rm -rf .git/objects/info/commit-graph{,s/}; git commit-graph write --split=no-merge 2>/dev/null' \\\n git commit-graph write --split=merge-all\n\nSo we're measuring the time it takes to crawl all the packs, decide on\nthe splitting strategy, and then compare all commits in the new merged\ngraph to make sure that they don't already exist in the object store.\n\nBut, here's where things get... Bizarre. I was trying to come up with a\nway to do fewer things and spend proportionally more time in\n'merge_commit_graphs', so I did something like:\n\n - Generate a pack containing a single, empty commit.\n - Generate a split commit-graph containing commits in the single large\n pack containing all of history.\n - Generate a commit-graph of the small pack, and merge it with the\n large pack.\n\nThat script is:\n\n $ git --version\n $ git commit -m \"empty\" --allow-empty\n $ pack=\"pack-$(git rev-parse HEAD | git pack-objects .git/objects/pack/pack).idx\"\n $ best-of-five \\\n -p \"rm -rf .git/objects/info/commit-graphs && cp -r .git/objects/info/commit-graphs{.bak,}\" \\\n sh -c \"echo $pack | git commit-graph write --split=merge-all\"\n\nbut things get... slower with this patch? Here are the results before\nand after:\n\n Attempt 1: 8.444\n Attempt 2: 8.453\n Attempt 3: 8.391\n Attempt 4: 8.376\n Attempt 5: 7.859\n\n real\t0m7.859s\n user\t0m7.309s\n sys\t0m0.511s\n\nvs:\n\n Attempt 1: 8.69\n Attempt 2: 8.735\n Attempt 3: 8.619\n Attempt 4: 8.747\n Attempt 5: 8.695\n\n real\t0m8.619s\n user\t0m8.030s\n sys\t0m0.538s\n\nWithout more profiling, I'm puzzled by why this patch seems to make\nthings *worse* under this scenario.\n\nSo, I'd appreciate your thoughts: does this set-up seem reasonable? Is\nit introducing some latency that isn't being accounted for in the\noriginal setup?\n\n> The patch otherwise still makes sense to me, but I suspect there are\n> other similar optimizations nearby that we'll need to do in tandem.\n>\n> -Peff\n\nThanks,\nTaylor\n"},{"id":"393582","messageId":"20200321062419.GA37345@syl.local","threadId":"53046","inReplyTo":"20200321061141.GA30636@syl.local","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-03-21T06:24:19Z","receivedAt":"2020-03-21T06:24:25Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sat, Mar 21, 2020 at 12:11:41AM -0600, Taylor Blau wrote:\n> On Sat, Mar 21, 2020 at 01:00:25AM -0400, Jeff King wrote:\n> > On Fri, Mar 20, 2020 at 09:44:23PM -0600, Taylor Blau wrote:\n> >\n> > > In my testing environment, this improves the time to \"merge\" a split\n> > > commit-graph containing all reachable commits in the kernel by\n> > > re-writing the same commit-graph (effectively measuring the time it\n> > > takes to check that all of those commits still exist) from:\n> > >\n> > > Attempt 1: 9.614\n> > > Attempt 2: 10.984\n> > > Attempt 3: 10.39\n> > > Attempt 4: 9.14\n> > > Attempt 5: 9.439\n> > >\n> > > real\t0m9.140s\n> > > user\t0m8.207s\n> > > sys\t0m0.602s\n> > >\n> > > to:\n> > >\n> > > Attempt 1: 9.12\n> > > Attempt 2: 8.904\n> > > Attempt 3: 9.361\n> > > Attempt 4: 9.288\n> > > Attempt 5: 9.677\n> > >\n> > > real\t0m8.904s\n> > > user\t0m8.208s\n> > > sys\t0m0.596s\n> > >\n> > > yielding a modest ~2.6% improvement in the best timings from each run,\n> > > and ~7.4% improvement on average.\n> >\n> > That still seems really slow to me. If we were truly eliding the load of\n> > most of the commit objects, I'd expect an order of magnitude or so\n> > improvement. For example, with a fully constructed commit graph in\n> > linux.git, I get:\n> >\n> > $ time git -c core.commitGraph=1 rev-list HEAD | wc -l\n> > 886922\n> >\n> > real\t0m1.088s\n> > user\t0m0.659s\n> > sys\t0m1.161s\n> >\n> > $ time git -c core.commitGraph=0 rev-list HEAD | wc -l\n> > 886922\n> >\n> > real\t0m7.185s\n> > user\t0m6.729s\n> > sys\t0m1.882s\n> >\n> > Obviously not the same operation, but that should give us a rough idea\n> > that commit graph lookups are 6-7 times cheaper than loading the actual\n> > objects. I don't remember the details of the case that originally led us\n> > towards this patch. Can you share more of the setup you used to generate\n> > the numbers above (which repo, but more importantly the commands to\n> > create the initial state and then time the test).\n>\n> Sure. I'm running best-of-five on the time it takes to re-generate and\n> merge a commit-graph based on in-pack commits.\n>\n> The script is (in linux.git):\n>\n> $ best-of-five \\\n> -p 'rm -rf .git/objects/info/commit-graph{,s/}; git commit-graph write --split=no-merge 2>/dev/null' \\\n> git commit-graph write --split=merge-all\n>\n> So we're measuring the time it takes to crawl all the packs, decide on\n> the splitting strategy, and then compare all commits in the new merged\n> graph to make sure that they don't already exist in the object store.\n>\n> But, here's where things get... Bizarre. I was trying to come up with a\n> way to do fewer things and spend proportionally more time in\n> 'merge_commit_graphs', so I did something like:\n>\n> - Generate a pack containing a single, empty commit.\n> - Generate a split commit-graph containing commits in the single large\n> pack containing all of history.\n> - Generate a commit-graph of the small pack, and merge it with the\n> large pack.\n>\n> That script is:\n>\n> $ git --version\n> $ git commit -m \"empty\" --allow-empty\n> $ pack=\"pack-$(git rev-parse HEAD | git pack-objects .git/objects/pack/pack).idx\"\n> $ best-of-five \\\n> -p \"rm -rf .git/objects/info/commit-graphs && cp -r .git/objects/info/commit-graphs{.bak,}\" \\\n> sh -c \"echo $pack | git commit-graph write --split=merge-all\"\n>\n> but things get... slower with this patch? Here are the results before\n> and after:\n>\n> Attempt 1: 8.444\n> Attempt 2: 8.453\n> Attempt 3: 8.391\n> Attempt 4: 8.376\n> Attempt 5: 7.859\n>\n> real\t0m7.859s\n> user\t0m7.309s\n> sys\t0m0.511s\n>\n> vs:\n>\n> Attempt 1: 8.69\n> Attempt 2: 8.735\n> Attempt 3: 8.619\n> Attempt 4: 8.747\n> Attempt 5: 8.695\n>\n> real\t0m8.619s\n> user\t0m8.030s\n> sys\t0m0.538s\n>\n> Without more profiling, I'm puzzled by why this patch seems to make\n> things *worse* under this scenario.\n\nHmm. I tried roughly the same setup as the latter of the above two, but\nthis time under perf. On a warm cache, it does look like this parch is\nan improvement:\n\n $ sudo perf diff perf.data perf.data.patch | grep merge_commit\n 0.11% -0.02% git [.] merge_commit_graph\n\n(perf.data is from running 'next', perf.data.patch is from running\n'next' with this patch applied on top). So... a slight improvement, but\nnothing like what I had reported in the original patch.\n\nI am puzzled.\n\n> So, I'd appreciate your thoughts: does this set-up seem reasonable? Is\n> it introducing some latency that isn't being accounted for in the\n> original setup?\n>\n> > The patch otherwise still makes sense to me, but I suspect there are\n> > other similar optimizations nearby that we'll need to do in tandem.\n> >\n> > -Peff\n>\n> Thanks,\n> Taylor\n\nThanks,\nTaylor\n"},{"id":"393584","messageId":"20200321070333.GB1441446@coredump.intra.peff.net","threadId":"53046","inReplyTo":"20200321061141.GA30636@syl.local","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-21T07:03:33Z","receivedAt":"2020-03-21T07:03:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Mar 21, 2020 at 12:11:41AM -0600, Taylor Blau wrote:\n\n> Sure. I'm running best-of-five on the time it takes to re-generate and\n> merge a commit-graph based on in-pack commits.\n> \n> The script is (in linux.git):\n> \n> $ best-of-five \\\n> -p 'rm -rf .git/objects/info/commit-graph{,s/}; git commit-graph write --split=no-merge 2>/dev/null' \\\n> git commit-graph write --split=merge-all\n\nIf I build Git without your patch and run the \"--split=merge-all\"\ncommand under a debugger, and then break on parse_object() I find that\nall of the commits are already parsed. This happens in\nclose_reachable().\n\nSo we weren't actually reading all of the commits even under the old\ncode. We were just going into deref_tag(), seeing that the object is\nalready parsed, and then quickly returning when we see that we already\nhave an OBJ_COMMIT. I suspect most of your timing differences are mostly\nnoise.\n\nPerhaps a more interesting case is when you're _not_ adding all of the\nexisting packed commits as input. There we'd feed only a few objects to\nclose_reachable(), and it would stop traversing as soon as it hits a\nparent that's already in a graph file. So most of the existing objects\nwould remain unparsed.\n\nI'm not sure how to do that, though. Saying \"--input=none\" still puts\nall of those existing graphed objects into the list of oids to include.\nI think you'd need a case where you were legitimately only adding a few\ncommits, but the merge rules say we need to create one big commit-graph\nfile.\n\nI guess --input=stdin-commits is a good way to simulate that. Try this\n(assuming there's already a split-graph file with all of the commits in\nit):\n\n git rev-parse HEAD >input\n time git commit-graph write --input=stdin-commits --split=merge-all But, here's where things get... Bizarre. I was trying to come up with a\n> way to do fewer things and spend proportionally more time in\n> 'merge_commit_graphs', so I did something like:\n> \n> - Generate a pack containing a single, empty commit.\n> - Generate a split commit-graph containing commits in the single large\n> pack containing all of history.\n> - Generate a commit-graph of the small pack, and merge it with the\n> large pack.\n> \n> That script is:\n> \n> $ git --version\n> $ git commit -m \"empty\" --allow-empty\n> $ pack=\"pack-$(git rev-parse HEAD | git pack-objects .git/objects/pack/pack).idx\"\n> $ best-of-five \\\n> -p \"rm -rf .git/objects/info/commit-graphs && cp -r .git/objects/info/commit-graphs{.bak,}\" \\\n> sh -c \"echo $pack | git commit-graph write --split=merge-all\"\n\nI think you'd need --stdin-packs in the actual timed command?\n\nAt any rate, I think there is a demonstrable speedup there. But\nmoreover, I'm pretty sure this existing code is not doing what it\nexpects:\n\n /* only add commits if they still exist in the repo */\n result = lookup_commit_reference_gently(ctx->r, &oid, 1);\n\nThat won't look at the object database at all if the commit is already\nmarked as parsed. And that parsing might have come from the commit graph\nitself, as our earlier attempts showed. So switching to a real\nhas_object_file() call is an important _correctness_ fix, even leaving\naside the speed improvements.\n\n-Peff\n"},{"id":"393628","messageId":"20200321172716.GA39461@syl.local","threadId":"53046","inReplyTo":"20200321070333.GB1441446@coredump.intra.peff.net","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-03-21T17:27:16Z","receivedAt":"2020-03-21T17:27:22Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sat, Mar 21, 2020 at 03:03:33AM -0400, Jeff King wrote:\n> On Sat, Mar 21, 2020 at 12:11:41AM -0600, Taylor Blau wrote:\n>\n> > Sure. I'm running best-of-five on the time it takes to re-generate and\n> > merge a commit-graph based on in-pack commits.\n> >\n> > The script is (in linux.git):\n> >\n> > $ best-of-five \\\n> > -p 'rm -rf .git/objects/info/commit-graph{,s/}; git commit-graph write --split=no-merge 2>/dev/null' \\\n> > git commit-graph write --split=merge-all\n>\n> If I build Git without your patch and run the \"--split=merge-all\"\n> command under a debugger, and then break on parse_object() I find that\n> all of the commits are already parsed. This happens in\n> close_reachable().\n>\n> So we weren't actually reading all of the commits even under the old\n> code. We were just going into deref_tag(), seeing that the object is\n> already parsed, and then quickly returning when we see that we already\n> have an OBJ_COMMIT. I suspect most of your timing differences are mostly\n> noise.\n\nAha. Thanks for reasoning through this. That makes sense, and I think\nthat you're probably right.\n\n> Perhaps a more interesting case is when you're _not_ adding all of the\n> existing packed commits as input. There we'd feed only a few objects to\n> close_reachable(), and it would stop traversing as soon as it hits a\n> parent that's already in a graph file. So most of the existing objects\n> would remain unparsed.\n>\n> I'm not sure how to do that, though. Saying \"--input=none\" still puts\n> all of those existing graphed objects into the list of oids to include.\n> I think you'd need a case where you were legitimately only adding a few\n> commits, but the merge rules say we need to create one big commit-graph\n> file.\n\nYou have to be careful, since we're taking the reachability closure over\nany commits that you do give. So, one thing you could do to ensure that\nyou have an actually small graph is to take something from the output of\n'git rev-list --max-parents=0 HEAD'.\n\nTo try and reproduce your results, I used '1da177e4c3', which is the\nkernel's first commit in Git. If my interpretation of your setup is\nfaithful, it goes something like:\n\n $ graphdir=.git/objects/info/commit-graphs\n $ git rev-parse 1da177e4c3 |\n git commit-graph write --split=no-merge --stdin-commits\n $ cp -r \"$graphdir{,.bak}\"\n\n $ best-of-five -p \"rm -rf $graphdir && cp -r $graphdir{.bak,}\" \\\n 'git commit-graph write --split=merge-all'\n\nWhere the last step is taking all commits listed in any pack, which is\ncheap to iterate.\n\n> I guess --input=stdin-commits is a good way to simulate that. Try this\n> (assuming there's already a split-graph file with all of the commits in\n> it):\n>\n> git rev-parse HEAD >input\n> time git commit-graph write --input=stdin-commits --split=merge-all \n> Without your patch on linux.git I get:\n>\n> real\t0m11.713s\n> user\t0m11.349s\n> sys\t0m0.341s\n>\n> but with it I get:\n>\n> real\t0m2.305s\n> user\t0m2.177s\n> sys\t0m0.100s\n\nIn the above setup, I get something like:\n\n git version 2.26.0.rc2.221.ge327a58236\n Attempt 1: 16.933\n Attempt 2: 18.101\n Attempt 3: 17.603\n Attempt 4: 20.404\n Attempt 5: 18.871\n\n real\t0m16.933s\n user\t0m16.440s\n sys\t0m0.472s\n\nversus:\n\n git version 2.26.0.rc2.222.g295e7905ee\n Attempt 1: 5.34\n Attempt 2: 4.623\n Attempt 3: 5.263\n Attempt 4: 5.268\n Attempt 5: 5.606\n\n real\t0m4.623s\n user\t0m4.428s\n sys\t0m0.176s\n\nwhich is a best-case savings of ~72.7%, and a savings of ~71.5%. That\nseems much better.\n\nIf you think that this is a realistic setup, I'll amend the original\npatch text to include these updated numbers, along with the reproduction\nsteps.\n\n> A more realistic case would probably be feeding a new small pack to\n> --input=stdin-packs.\n>\n> > But, here's where things get... Bizarre. I was trying to come up with a\n> > way to do fewer things and spend proportionally more time in\n> > 'merge_commit_graphs', so I did something like:\n> >\n> > - Generate a pack containing a single, empty commit.\n> > - Generate a split commit-graph containing commits in the single large\n> > pack containing all of history.\n> > - Generate a commit-graph of the small pack, and merge it with the\n> > large pack.\n> >\n> > That script is:\n> >\n> > $ git --version\n> > $ git commit -m \"empty\" --allow-empty\n> > $ pack=\"pack-$(git rev-parse HEAD | git pack-objects .git/objects/pack/pack).idx\"\n> > $ best-of-five \\\n> > -p \"rm -rf .git/objects/info/commit-graphs && cp -r .git/objects/info/commit-graphs{.bak,}\" \\\n> > sh -c \"echo $pack | git commit-graph write --split=merge-all\"\n>\n> I think you'd need --stdin-packs in the actual timed command?\n>\n> At any rate, I think there is a demonstrable speedup there. But\n> moreover, I'm pretty sure this existing code is not doing what it\n> expects:\n>\n> /* only add commits if they still exist in the repo */\n> result = lookup_commit_reference_gently(ctx->r, &oid, 1);\n>\n> That won't look at the object database at all if the commit is already\n> marked as parsed. And that parsing might have come from the commit graph\n> itself, as our earlier attempts showed. So switching to a real\n> has_object_file() call is an important _correctness_ fix, even leaving\n> aside the speed improvements.\n\nThat's a great point. I hadn't thought of this myself, but I agree with\nyour reasoning here, too, and think that this is an important\ncorrectness fix even if it yielded no performance benefit (thankfully,\nwe get both :)).\n\n> -Peff\n\nThanks,\nTaylor\n"},{"id":"393651","messageId":"xmqqfte1a6ew.fsf@gitster.c.googlers.com","threadId":"53046","inReplyTo":"20200321070333.GB1441446@coredump.intra.peff.net","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-03-21T18:50:47Z","receivedAt":"2020-03-21T18:50:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> So we weren't actually reading all of the commits even under the old\n> code. We were just going into deref_tag(), seeing that the object is\n> already parsed, and then quickly returning when we see that we already\n> have an OBJ_COMMIT. I suspect most of your timing differences are mostly\n> noise.\n\nNoise that contributes largely to ~7% fluctuation? That sounds big.\n\n> I guess --input=stdin-commits is a good way to simulate that. Try this\n> (assuming there's already a split-graph file with all of the commits in\n> it):\n>\n> git rev-parse HEAD >input\n> time git commit-graph write --input=stdin-commits --split=merge-all ...\n> A more realistic case would probably be feeding a new small pack to\n> --input=stdin-packs.\n\nMakes sense.\n\n> At any rate, I think there is a demonstrable speedup there. But\n> moreover, I'm pretty sure this existing code is not doing what it\n> expects:\n>\n> /* only add commits if they still exist in the repo */\n> result = lookup_commit_reference_gently(ctx->r, &oid, 1);\n>\n> That won't look at the object database at all if the commit is already\n> marked as parsed. And that parsing might have come from the commit graph\n> itself, as our earlier attempts showed. So switching to a real\n> has_object_file() call is an important _correctness_ fix, even leaving\n> aside the speed improvements.\n\nTrue. has_object_file() asks the question without even\nlookup-replace flag set, so it would try to see if the object is\ntruly there (modulo the \"pretended\" ones are declared to exist via\nthe cached-object mechanism).\n\nDo we need to worry about INFO_QUICK and SKIP_FETCH_OBJECT in this\ncodepath, by the way?\n"},{"id":"393667","messageId":"a0de34e3-3f60-1838-dbaf-2ee3dddc7c89@gmail.com","threadId":"53046","inReplyTo":"xmqqfte1a6ew.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-03-22T00:03:01Z","receivedAt":"2020-03-22T00:05:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/21/2020 2:50 PM, Junio C Hamano wrote:\n> Do we need to worry about INFO_QUICK and SKIP_FETCH_OBJECT in this\n> codepath, by the way?\n\nI was coming back to this thread to bring up these exact flags for\nconsideration. The good news is that in a partial clone with any\namount of filtering we will still have all reachable commits, which\nare necessary for the commit-graph to make sense. The only ones that\nwould fail has_object_file() are ones removed by GC, but they may\nstill exist on the remote. So without SKIP_FETCH_OBJECT, we would\ngenerate a network call even if the server has GC'd to remove the\ncommits. This gets particularly bad when the server returns all\nreachable objects from that commit!\n\nThanks,\n-Stolee\n\n"},{"id":"393668","messageId":"20200322002005.GA48038@syl.local","threadId":"53046","inReplyTo":"a0de34e3-3f60-1838-dbaf-2ee3dddc7c89@gmail.com","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-03-22T00:20:05Z","receivedAt":"2020-03-22T00:20:09Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sat, Mar 21, 2020 at 08:03:01PM -0400, Derrick Stolee wrote:\n> On 3/21/2020 2:50 PM, Junio C Hamano wrote:\n> > Do we need to worry about INFO_QUICK and SKIP_FETCH_OBJECT in this\n> > codepath, by the way?\n>\n> I was coming back to this thread to bring up these exact flags for\n> consideration. The good news is that in a partial clone with any\n> amount of filtering we will still have all reachable commits, which\n> are necessary for the commit-graph to make sense. The only ones that\n> would fail has_object_file() are ones removed by GC, but they may\n> still exist on the remote. So without SKIP_FETCH_OBJECT, we would\n> generate a network call even if the server has GC'd to remove the\n> commits. This gets particularly bad when the server returns all\n> reachable objects from that commit!\n\nThat makes sense. Do you think something like this should be applied?\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex c7cfadc786..0097318798 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -1594,6 +1594,7 @@ static void merge_commit_graph(struct write_commit_graph_context *ctx,\n {\n uint32_t i;\n uint32_t offset = g->num_commits_in_base;\n+ int flags = OBJECT_INFO_QUICK | OBJECT_INFO_SKIP_FETCH_OBJECT;\n\n ALLOC_GROW(ctx->commits.list, ctx->commits.nr + g->num_commits, ctx->commits.alloc);\n\n@@ -1606,7 +1607,7 @@ static void merge_commit_graph(struct write_commit_graph_context *ctx,\n load_oid_from_graph(g, i + offset, &oid);\n\n /* only add commits if they still exist in the repo */\n- if (repo_has_object_file(ctx->r, &oid)) {\n+ if (repo_has_object_file_with_flags(ctx->r, &oid, flags)) {\n result = lookup_commit(ctx->r, &oid);\n if (repo_parse_commit(ctx->r, result))\n result = NULL;\n\n> Thanks,\n> -Stolee\n\nThanks,\nTaylor\n"},{"id":"393669","messageId":"1cb561fc-5bce-28f0-e5e1-886f590fba92@gmail.com","threadId":"53046","inReplyTo":"20200322002005.GA48038@syl.local","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-03-22T00:23:13Z","receivedAt":"2020-03-22T00:23:18Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/21/2020 8:20 PM, Taylor Blau wrote:\n> On Sat, Mar 21, 2020 at 08:03:01PM -0400, Derrick Stolee wrote:\n>> On 3/21/2020 2:50 PM, Junio C Hamano wrote:\n>>> Do we need to worry about INFO_QUICK and SKIP_FETCH_OBJECT in this\n>>> codepath, by the way?\n>>\n>> I was coming back to this thread to bring up these exact flags for\n>> consideration. The good news is that in a partial clone with any\n>> amount of filtering we will still have all reachable commits, which\n>> are necessary for the commit-graph to make sense. The only ones that\n>> would fail has_object_file() are ones removed by GC, but they may\n>> still exist on the remote. So without SKIP_FETCH_OBJECT, we would\n>> generate a network call even if the server has GC'd to remove the\n>> commits. This gets particularly bad when the server returns all\n>> reachable objects from that commit!\n> \n> That makes sense. Do you think something like this should be applied?\n\nYes, I think this is the appropriate update. Thanks!\n\n> diff --git a/commit-graph.c b/commit-graph.c\n> index c7cfadc786..0097318798 100644\n> --- a/commit-graph.c\n> +++ b/commit-graph.c\n> @@ -1594,6 +1594,7 @@ static void merge_commit_graph(struct write_commit_graph_context *ctx,\n> {\n> uint32_t i;\n> uint32_t offset = g->num_commits_in_base;\n> + int flags = OBJECT_INFO_QUICK | OBJECT_INFO_SKIP_FETCH_OBJECT;\n> \n> ALLOC_GROW(ctx->commits.list, ctx->commits.nr + g->num_commits, ctx->commits.alloc);\n> \n> @@ -1606,7 +1607,7 @@ static void merge_commit_graph(struct write_commit_graph_context *ctx,\n> load_oid_from_graph(g, i + offset, &oid);\n> \n> /* only add commits if they still exist in the repo */\n> - if (repo_has_object_file(ctx->r, &oid)) {\n> + if (repo_has_object_file_with_flags(ctx->r, &oid, flags)) {\n> result = lookup_commit(ctx->r, &oid);\n> if (repo_parse_commit(ctx->r, result))\n> result = NULL;\n"},{"id":"393686","messageId":"20200322053635.GA578498@coredump.intra.peff.net","threadId":"53046","inReplyTo":"20200321172716.GA39461@syl.local","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-22T05:36:35Z","receivedAt":"2020-03-22T05:36:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Mar 21, 2020 at 11:27:16AM -0600, Taylor Blau wrote:\n\n> > I'm not sure how to do that, though. Saying \"--input=none\" still puts\n> > all of those existing graphed objects into the list of oids to include.\n> > I think you'd need a case where you were legitimately only adding a few\n> > commits, but the merge rules say we need to create one big commit-graph\n> > file.\n> \n> You have to be careful, since we're taking the reachability closure over\n> any commits that you do give. So, one thing you could do to ensure that\n> you have an actually small graph is to take something from the output of\n> 'git rev-list --max-parents=0 HEAD'.\n\nI don't think you need to be that careful, though. In split-mode,\nclose_reachable() will stop traversing when it finds a graphed commit.\nThat's why using the tip of HEAD in my previous example worked.\n\n> To try and reproduce your results, I used '1da177e4c3', which is the\n> kernel's first commit in Git. If my interpretation of your setup is\n> faithful, it goes something like:\n> \n> $ graphdir=.git/objects/info/commit-graphs\n> $ git rev-parse 1da177e4c3 |\n> git commit-graph write --split=no-merge --stdin-commits\n> $ cp -r \"$graphdir{,.bak}\"\n> \n> $ best-of-five -p \"rm -rf $graphdir && cp -r $graphdir{.bak,}\" \\\n> 'git commit-graph write --split=merge-all'\n\nMy case is the opposite, isn't it? Here it looks like you've made a very\n_tiny_ commit-graph file (with one commit), and then you're going to end\nup adding in all of the new objects. I don't think it would be improved\nmuch by this patch (which makes me very confused by the numbers you got\nbelow).\n\nI also don't think it's that interesting a real-world case.\n\nThe more interesting one is where you do already have a big\ncommit-graph, and want to add just a bit more to it. In the real world,\nthat might look something like this:\n\n # create a fake server repo\n git clone --bare . dst.git\n\n # imagine the server already has everything in a graph file\n git -C dst.git commit-graph write --split=no-merge --reachable\n\n # and now do a small push\n git commit --allow-empty -m foo\n git push dst.git\n\n # the server might do an incremental immediately to cover the new\n # objects; here we'll use --stdin-commits with the new data, but a\n # real server might feed the new packfile. We'd probably just use\n # regular --split here in practice, but let's imagine that we're\n # starting to have a lot of graph files, and that triggers a desire to\n # merge. We'll force that state with --split=merge-all.\n git rev-list HEAD^..HEAD |\n git -C dst.git commit-graph write --split=merge-all --stdin-commits\n\nWithout your patch, that takes ~11s for me. With it, it takes ~2s.\n\nAnother equally interesting case is if the per-push generation _doesn't_\nmerge anything, and just creates a new, tiny graph file. And then later\nwe want to do a real maintenance, merging them all done. I think that\nwould be something like:\n\n git -C dst.git commit-graph write --input=none --split=merge-all\n\nBut that _isn't_ improved by your patch. For the simple reason that all\nof the commits will already have been parsed. The \"--input=none\" option\nisn't \"no input\"; it's actually \"take all existing graphed objects as\ninput\" (i.e., it implies --append). So each of those objects will\nalready have been examined in an earlier stage.\n\n> Where the last step is taking all commits listed in any pack, which is\n> cheap to iterate.\n\nI'm not sure it's all that cheap. It has to find the type of every\nobject in every pack. And finding types involves walking delta chains.\nThat's something like 7s on my machine for linux.git (compared to the 2s\nin which I can just merge down the existing graph files).\n\n> In the above setup, I get something like:\n> \n> git version 2.26.0.rc2.221.ge327a58236\n> Attempt 1: 16.933\n> Attempt 2: 18.101\n> Attempt 3: 17.603\n> Attempt 4: 20.404\n> Attempt 5: 18.871\n> \n> real\t0m16.933s\n> user\t0m16.440s\n> sys\t0m0.472s\n> \n> versus:\n> \n> git version 2.26.0.rc2.222.g295e7905ee\n> Attempt 1: 5.34\n> Attempt 2: 4.623\n> Attempt 3: 5.263\n> Attempt 4: 5.268\n> Attempt 5: 5.606\n> \n> real\t0m4.623s\n> user\t0m4.428s\n> sys\t0m0.176s\n> \n> which is a best-case savings of ~72.7%, and a savings of ~71.5%. That\n> seems much better.\n\nI'm still puzzled by this. In the setup you showed, hardly anything is\ngraphed. But the change is only in the graph-merge code.\n\n-Peff\n"},{"id":"393687","messageId":"20200322054916.GB578498@coredump.intra.peff.net","threadId":"53046","inReplyTo":"1cb561fc-5bce-28f0-e5e1-886f590fba92@gmail.com","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-22T05:49:16Z","receivedAt":"2020-03-22T05:49:20Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Mar 21, 2020 at 08:23:13PM -0400, Derrick Stolee wrote:\n\n> On 3/21/2020 8:20 PM, Taylor Blau wrote:\n> > On Sat, Mar 21, 2020 at 08:03:01PM -0400, Derrick Stolee wrote:\n> >> On 3/21/2020 2:50 PM, Junio C Hamano wrote:\n> >>> Do we need to worry about INFO_QUICK and SKIP_FETCH_OBJECT in this\n> >>> codepath, by the way?\n> >>\n> >> I was coming back to this thread to bring up these exact flags for\n> >> consideration. The good news is that in a partial clone with any\n> >> amount of filtering we will still have all reachable commits, which\n> >> are necessary for the commit-graph to make sense. The only ones that\n> >> would fail has_object_file() are ones removed by GC, but they may\n> >> still exist on the remote. So without SKIP_FETCH_OBJECT, we would\n> >> generate a network call even if the server has GC'd to remove the\n> >> commits. This gets particularly bad when the server returns all\n> >> reachable objects from that commit!\n> > \n> > That makes sense. Do you think something like this should be applied?\n> > + int flags = OBJECT_INFO_QUICK | OBJECT_INFO_SKIP_FETCH_OBJECT;\n> [...]\n> \n> Yes, I think this is the appropriate update. Thanks!\n\nI'm not so sure.\n\nIn a non-partial clone, when would expect QUICK to matter? If we find\nthe object is missing, then either:\n\n - we are racing with repack, and we would benefit from double-checking\n that the object really is gone\n\n - we used to have it (since it was mentioned in the graph file) but it\n went away\n\nUsing QUICK means we won't waste time double-checking in the second\ncase. But it means we won't catch the first case, and we may generate a\nnew graph file that omits the object. They're both optimizations, and I\ndon't think we're impacting correctness[1], but it's not clear to me\nwhether one is a win over the other. We don't generally expect objects\nwe have to go away often.\n\nSkipping fetching seems a little more straight-forward to me. If we had\nit in a graph file, presumably we had the actual object before, too. And\neither we're in the first case above (we really do have it and just need\nto double-check) in which case not saying QUICK would be enough. Or we\nintentionally got rid of it. In which case downloading it just to\ngenerate a cache is quite silly.\n\nSo it seems like SKIP_FETCH_OBJECT but _not_ QUICK might be reasonable\nhere.\n\n-Peff\n\n[1] I'm actually not quite sure about correctness here. It should be\n fine to generate a graph file without any given commit; readers will\n just have to load that commit the old-fashioned way. But at this\n phase of \"commit-graph write\", I think we'll already have done the\n close_reachable() check. What does it mean to throw away a commit at\n this stage? If we're the parent of another commit, then it will have\n trouble referring to us by a uint32_t. Will the actual writing phase\n barf, or will we generate an invalid graph file?\n"},{"id":"393688","messageId":"20200322060434.GC578498@coredump.intra.peff.net","threadId":"53046","inReplyTo":"20200322054916.GB578498@coredump.intra.peff.net","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-22T06:04:34Z","receivedAt":"2020-03-22T06:04:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Mar 22, 2020 at 01:49:16AM -0400, Jeff King wrote:\n\n> [1] I'm actually not quite sure about correctness here. It should be\n> fine to generate a graph file without any given commit; readers will\n> just have to load that commit the old-fashioned way. But at this\n> phase of \"commit-graph write\", I think we'll already have done the\n> close_reachable() check. What does it mean to throw away a commit at\n> this stage? If we're the parent of another commit, then it will have\n> trouble referring to us by a uint32_t. Will the actual writing phase\n> barf, or will we generate an invalid graph file?\n\nIt doesn't seem great. If I instrument Git like this to simulate an\nobject temporarily \"missing\" (if it were really missing the whole repo\nwould be corrupt; we're trying to see what would happen if a race causes\nus to momentarily not see it):\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 3da52847e4..71419c2532 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -1596,6 +1596,19 @@ static void split_graph_merge_strategy(struct write_commit_graph_context *ctx)\n \t}\n }\n \n+static int pretend_commit_is_missing(const struct object_id *oid)\n+{\n+\tstatic int initialized;\n+\tstatic struct object_id missing;\n+\tif (!initialized) {\n+\t\tconst char *x = getenv(\"PRETEND_COMMIT_IS_MISSING\");\n+\t\tif (x)\n+\t\t\tget_oid_hex(x, &missing);\n+\t\tinitialized = 1;\n+\t}\n+\treturn oideq(&missing, oid);\n+}\n+\n static void merge_commit_graph(struct write_commit_graph_context *ctx,\n \t\t\t struct commit_graph *g)\n {\n@@ -1612,6 +1625,11 @@ static void merge_commit_graph(struct write_commit_graph_context *ctx,\n \n \t\tload_oid_from_graph(g, i + offset, &oid);\n \n+\t\tif (pretend_commit_is_missing(&oid)) {\n+\t\t\twarning(\"pretending %s is missing\", oid_to_hex(&oid));\n+\t\t\tcontinue;\n+\t\t}\n+\n \t\t/* only add commits if they still exist in the repo */\n \t\tresult = lookup_commit_reference_gently(ctx->r, &oid, 1);\n \n\nand then I make a fully-graphed repo like this:\n\n git init repo\n cd repo\n for i in $(seq 10); do\n git commit --allow-empty -m $i\n done\n git commit-graph write --input=reachable --split=no-merge\n\nif we pretend a parent is missing, I get a BUG():\n\n $ git rev-parse HEAD |\n PRETEND_COMMIT_IS_MISSING=$(git rev-parse HEAD^) \\\n git commit-graph write --stdin-commits --split=merge-all\n warning: pretending 35e6e15c738cf2bfbe495957b2a941c2efe86dd9 is missing\n BUG: commit-graph.c:879: missing parent 35e6e15c738cf2bfbe495957b2a941c2efe86dd9 for commit d4141fb57a9bbe26b247f23c790d63d078977833\n Aborted\n\nSo it seems like just skipping here (either with the new patch or\nwithout) isn't really a good strategy.\n\n-Peff\n"},{"id":"393701","messageId":"20200322110424.GC2224@szeder.dev","threadId":"53046","inReplyTo":"20200322053635.GA578498@coredump.intra.peff.net","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2020-03-22T11:04:24Z","receivedAt":"2020-03-22T11:04:29Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Sun, Mar 22, 2020 at 01:36:35AM -0400, Jeff King wrote:\n> The \"--input=none\" option\n> isn't \"no input\"; it's actually \"take all existing graphed objects as\n> input\" (i.e., it implies --append). So each of those objects will\n> already have been examined in an earlier stage.\n\nYeah, we discussed it earlier that '--input=none' doesn't properly\ndescribe what it tries to accomplish, and suggested '--input=exists'\n(or was it 'existing'?) instead.\n\n> > Where the last step is taking all commits listed in any pack, which is\n> > cheap to iterate.\n> \n> I'm not sure it's all that cheap. It has to find the type of every\n> object in every pack. And finding types involves walking delta chains.\n\nIndeed, that's just about the most expensive way to find all commits,\nin my experience it can be well over a magnitude slower than\n'--reachable'.\n\n"},{"id":"393717","messageId":"20200322154439.GA53402@syl.local","threadId":"53046","inReplyTo":"20200322054916.GB578498@coredump.intra.peff.net","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-03-22T15:44:39Z","receivedAt":"2020-03-22T15:44:45Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sun, Mar 22, 2020 at 01:49:16AM -0400, Jeff King wrote:\n> On Sat, Mar 21, 2020 at 08:23:13PM -0400, Derrick Stolee wrote:\n>\n> > On 3/21/2020 8:20 PM, Taylor Blau wrote:\n> > > On Sat, Mar 21, 2020 at 08:03:01PM -0400, Derrick Stolee wrote:\n> > >> On 3/21/2020 2:50 PM, Junio C Hamano wrote:\n> > >>> Do we need to worry about INFO_QUICK and SKIP_FETCH_OBJECT in this\n> > >>> codepath, by the way?\n> > >>\n> > >> I was coming back to this thread to bring up these exact flags for\n> > >> consideration. The good news is that in a partial clone with any\n> > >> amount of filtering we will still have all reachable commits, which\n> > >> are necessary for the commit-graph to make sense. The only ones that\n> > >> would fail has_object_file() are ones removed by GC, but they may\n> > >> still exist on the remote. So without SKIP_FETCH_OBJECT, we would\n> > >> generate a network call even if the server has GC'd to remove the\n> > >> commits. This gets particularly bad when the server returns all\n> > >> reachable objects from that commit!\n> > >\n> > > That makes sense. Do you think something like this should be applied?\n> > > + int flags = OBJECT_INFO_QUICK | OBJECT_INFO_SKIP_FETCH_OBJECT;\n> > [...]\n> >\n> > Yes, I think this is the appropriate update. Thanks!\n>\n> I'm not so sure.\n>\n> In a non-partial clone, when would expect QUICK to matter? If we find\n> the object is missing, then either:\n>\n> - we are racing with repack, and we would benefit from double-checking\n> that the object really is gone\n>\n> - we used to have it (since it was mentioned in the graph file) but it\n> went away\n>\n> Using QUICK means we won't waste time double-checking in the second\n> case. But it means we won't catch the first case, and we may generate a\n> new graph file that omits the object. They're both optimizations, and I\n> don't think we're impacting correctness[1], but it's not clear to me\n> whether one is a win over the other. We don't generally expect objects\n> we have to go away often.\n>\n> Skipping fetching seems a little more straight-forward to me. If we had\n> it in a graph file, presumably we had the actual object before, too. And\n> either we're in the first case above (we really do have it and just need\n> to double-check) in which case not saying QUICK would be enough. Or we\n> intentionally got rid of it. In which case downloading it just to\n> generate a cache is quite silly.\n\nI was going to write that I'm not entirely sure of this, but I tried to\ntalk myself through it below, and I think that the right flag is *only*\nOBJECT_INFO_SKIP_FETCH_OBJECT.\n\nFirst, I agree with your reasoning that we shouldn't have\nOBJECT_INFO_QUICK, that much makes sense to me.\n\nTo consider OBJECT_INFO_SKIP_FETCH_OBJECT, let's say that we used to\nhave some commit, and it got GC'd away. This shouldn't happen unless a\ncommit is unreachable, so if we ever find ourselves in a situation where\nthe parent of some other commit is missing, we know that that represents\na true corruption, not the result of a normal 'git gc'.\n\nNow, if we do find ourselves in this case, we know that a 'git\ncommit-graph write --input=none --split' *would* work because we would\nfind that the unreachable commit (if it were in the graph) was missing,\nand 'OBJECT_INFO_SKIP_FETCH_OBJECT' would tell us not to go looking for\nit. Likewise, if the commit weren't already in the graph, this would\nwork fine, too.\n\nBut, most of the time we won't even get a chance to write a new\ncommit-graph based on existing ones, since 'gc.writeCommitGraph' will\ntake care of this for us in-process with 'git gc'. This uses\n'--reachable' without '--split', so we won't ever invoke\n'merge_commit_graph{s,}'.\n\n> So it seems like SKIP_FETCH_OBJECT but _not_ QUICK might be reasonable\n> here.\n\nI agree with your original reasoning that OBJECT_INFO_QUICK is the wrong\nchoice, but I think my reasoning above that\nOBJECT_INFO_SKIP_FETCH_OBJECT *is* an appropriate flag is sound.\n\n> -Peff\n>\n> [1] I'm actually not quite sure about correctness here. It should be\n> fine to generate a graph file without any given commit; readers will\n> just have to load that commit the old-fashioned way. But at this\n> phase of \"commit-graph write\", I think we'll already have done the\n> close_reachable() check. What does it mean to throw away a commit at\n> this stage? If we're the parent of another commit, then it will have\n> trouble referring to us by a uint32_t. Will the actual writing phase\n> barf, or will we generate an invalid graph file?\n\nThanks,\nTaylor\n"},{"id":"393718","messageId":"20200322154749.GB53402@syl.local","threadId":"53046","inReplyTo":"20200322060434.GC578498@coredump.intra.peff.net","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-03-22T15:47:49Z","receivedAt":"2020-03-22T15:47:53Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sun, Mar 22, 2020 at 02:04:34AM -0400, Jeff King wrote:\n> On Sun, Mar 22, 2020 at 01:49:16AM -0400, Jeff King wrote:\n>\n> > [1] I'm actually not quite sure about correctness here. It should be\n> > fine to generate a graph file without any given commit; readers will\n> > just have to load that commit the old-fashioned way. But at this\n> > phase of \"commit-graph write\", I think we'll already have done the\n> > close_reachable() check. What does it mean to throw away a commit at\n> > this stage? If we're the parent of another commit, then it will have\n> > trouble referring to us by a uint32_t. Will the actual writing phase\n> > barf, or will we generate an invalid graph file?\n>\n> It doesn't seem great. If I instrument Git like this to simulate an\n> object temporarily \"missing\" (if it were really missing the whole repo\n> would be corrupt; we're trying to see what would happen if a race causes\n> us to momentarily not see it):\n\nThis is definitely a problem on either side of this patch, which is\ndemonstrated by the fact that you applied your changes without my patch\non top (and that my patch isn't changing anything substantial in this\narea like removing the 'continue' statement).\n\nShould we address this before moving on with my patch? I think that we\n*could*, but I'd rather go forward with what we have for now, since it's\nonly improving the situation, and not introducing a new bug.\n\n> diff --git a/commit-graph.c b/commit-graph.c\n> index 3da52847e4..71419c2532 100644\n> --- a/commit-graph.c\n> +++ b/commit-graph.c\n> @@ -1596,6 +1596,19 @@ static void split_graph_merge_strategy(struct write_commit_graph_context *ctx)\n> \t}\n> }\n>\n> +static int pretend_commit_is_missing(const struct object_id *oid)\n> +{\n> +\tstatic int initialized;\n> +\tstatic struct object_id missing;\n> +\tif (!initialized) {\n> +\t\tconst char *x = getenv(\"PRETEND_COMMIT_IS_MISSING\");\n> +\t\tif (x)\n> +\t\t\tget_oid_hex(x, &missing);\n> +\t\tinitialized = 1;\n> +\t}\n> +\treturn oideq(&missing, oid);\n> +}\n> +\n> static void merge_commit_graph(struct write_commit_graph_context *ctx,\n> \t\t\t struct commit_graph *g)\n> {\n> @@ -1612,6 +1625,11 @@ static void merge_commit_graph(struct write_commit_graph_context *ctx,\n>\n> \t\tload_oid_from_graph(g, i + offset, &oid);\n>\n> +\t\tif (pretend_commit_is_missing(&oid)) {\n> +\t\t\twarning(\"pretending %s is missing\", oid_to_hex(&oid));\n> +\t\t\tcontinue;\n> +\t\t}\n> +\n> \t\t/* only add commits if they still exist in the repo */\n> \t\tresult = lookup_commit_reference_gently(ctx->r, &oid, 1);\n>\n>\n> and then I make a fully-graphed repo like this:\n>\n> git init repo\n> cd repo\n> for i in $(seq 10); do\n> git commit --allow-empty -m $i\n> done\n> git commit-graph write --input=reachable --split=no-merge\n>\n> if we pretend a parent is missing, I get a BUG():\n>\n> $ git rev-parse HEAD |\n> PRETEND_COMMIT_IS_MISSING=$(git rev-parse HEAD^) \\\n> git commit-graph write --stdin-commits --split=merge-all\n> warning: pretending 35e6e15c738cf2bfbe495957b2a941c2efe86dd9 is missing\n> BUG: commit-graph.c:879: missing parent 35e6e15c738cf2bfbe495957b2a941c2efe86dd9 for commit d4141fb57a9bbe26b247f23c790d63d078977833\n> Aborted\n>\n> So it seems like just skipping here (either with the new patch or\n> without) isn't really a good strategy.\n>\n> -Peff\nThanks,\nTaylor\n"},{"id":"393724","messageId":"20200322164531.GA55067@syl.local","threadId":"53046","inReplyTo":"20200322053635.GA578498@coredump.intra.peff.net","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-03-22T16:45:31Z","receivedAt":"2020-03-22T16:45:37Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sun, Mar 22, 2020 at 01:36:35AM -0400, Jeff King wrote:\n> On Sat, Mar 21, 2020 at 11:27:16AM -0600, Taylor Blau wrote:\n>\n> > > I'm not sure how to do that, though. Saying \"--input=none\" still puts\n> > > all of those existing graphed objects into the list of oids to include.\n> > > I think you'd need a case where you were legitimately only adding a few\n> > > commits, but the merge rules say we need to create one big commit-graph\n> > > file.\n> >\n> > You have to be careful, since we're taking the reachability closure over\n> > any commits that you do give. So, one thing you could do to ensure that\n> > you have an actually small graph is to take something from the output of\n> > 'git rev-list --max-parents=0 HEAD'.\n>\n> I don't think you need to be that careful, though. In split-mode,\n> close_reachable() will stop traversing when it finds a graphed commit.\n> That's why using the tip of HEAD in my previous example worked.\n>\n> > To try and reproduce your results, I used '1da177e4c3', which is the\n> > kernel's first commit in Git. If my interpretation of your setup is\n> > faithful, it goes something like:\n> >\n> > $ graphdir=.git/objects/info/commit-graphs\n> > $ git rev-parse 1da177e4c3 |\n> > git commit-graph write --split=no-merge --stdin-commits\n> > $ cp -r \"$graphdir{,.bak}\"\n> >\n> > $ best-of-five -p \"rm -rf $graphdir && cp -r $graphdir{.bak,}\" \\\n> > 'git commit-graph write --split=merge-all'\n>\n> My case is the opposite, isn't it? Here it looks like you've made a very\n> _tiny_ commit-graph file (with one commit), and then you're going to end\n> up adding in all of the new objects. I don't think it would be improved\n> much by this patch (which makes me very confused by the numbers you got\n> below).\n>\n> I also don't think it's that interesting a real-world case.\n>\n> The more interesting one is where you do already have a big\n> commit-graph, and want to add just a bit more to it. In the real world,\n> that might look something like this:\n>\n> # create a fake server repo\n> git clone --bare . dst.git\n>\n> # imagine the server already has everything in a graph file\n> git -C dst.git commit-graph write --split=no-merge --reachable\n>\n> # and now do a small push\n> git commit --allow-empty -m foo\n> git push dst.git\n>\n> # the server might do an incremental immediately to cover the new\n> # objects; here we'll use --stdin-commits with the new data, but a\n> # real server might feed the new packfile. We'd probably just use\n> # regular --split here in practice, but let's imagine that we're\n> # starting to have a lot of graph files, and that triggers a desire to\n> # merge. We'll force that state with --split=merge-all.\n> git rev-list HEAD^..HEAD |\n> git -C dst.git commit-graph write --split=merge-all --stdin-commits\n>\n> Without your patch, that takes ~11s for me. With it, it takes ~2s.\n>\n> Another equally interesting case is if the per-push generation _doesn't_\n> merge anything, and just creates a new, tiny graph file. And then later\n> we want to do a real maintenance, merging them all done. I think that\n> would be something like:\n>\n> git -C dst.git commit-graph write --input=none --split=merge-all\n>\n> But that _isn't_ improved by your patch. For the simple reason that all\n> of the commits will already have been parsed. The \"--input=none\" option\n> isn't \"no input\"; it's actually \"take all existing graphed objects as\n> input\" (i.e., it implies --append). So each of those objects will\n> already have been examined in an earlier stage.\n>\n> > Where the last step is taking all commits listed in any pack, which is\n> > cheap to iterate.\n>\n> I'm not sure it's all that cheap. It has to find the type of every\n> object in every pack. And finding types involves walking delta chains.\n> That's something like 7s on my machine for linux.git (compared to the 2s\n> in which I can just merge down the existing graph files).\n>\n> > In the above setup, I get something like:\n> >\n> > git version 2.26.0.rc2.221.ge327a58236\n> > Attempt 1: 16.933\n> > Attempt 2: 18.101\n> > Attempt 3: 17.603\n> > Attempt 4: 20.404\n> > Attempt 5: 18.871\n> >\n> > real\t0m16.933s\n> > user\t0m16.440s\n> > sys\t0m0.472s\n> >\n> > versus:\n> >\n> > git version 2.26.0.rc2.222.g295e7905ee\n> > Attempt 1: 5.34\n> > Attempt 2: 4.623\n> > Attempt 3: 5.263\n> > Attempt 4: 5.268\n> > Attempt 5: 5.606\n> >\n> > real\t0m4.623s\n> > user\t0m4.428s\n> > sys\t0m0.176s\n> >\n> > which is a best-case savings of ~72.7%, and a savings of ~71.5%. That\n> > seems much better.\n>\n> I'm still puzzled by this. In the setup you showed, hardly anything is\n> graphed. But the change is only in the graph-merge code.\n\nI agree with your reasoning. I tried to recreate these timings this\nmorning, and was unable to do so. Here's my setup (where 'git' is built\non the tip of 'next'):\n\n $ graphdir=\".git/objects/info/commit-graphs\"\n $ pack=\"pack-b10a98360eacb1f5a5ff67cb8d8113d8b3d0b39f.idx\"\n $ rm -rf \"$graphdir\"\n $ git rev-list --max-parents=0 HEAD | tail -1 |\n git commit-graph write --input=stdin-commits --split=no-merge\n $ cp -r \"$graphdir\" \"$graphdir.bak\"\n\n $ git version\n git version 2.26.0.rc2.221.ge327a58236\n\n # repeat the below twice to ensure a warm cache\n $ rm -rf \"$graphdir\" && cp -r \"$graphdir.bak\" \"$graphdir\" &&\n echo \"$pack\" |\n sudo perf record -F 997 ~ttaylorr/bin/git commit-graph write \\\n --split=merge-all --input=stdin-packs\n $ mv perf.data{,.base}\n\n $ git version\n git version 2.26.0.rc2.222.g1931b73955\n\n # do the above again, and mv perf.data{,.patch}\n\n $ sudo perf diff perf.data.base perf.data.patch\n # Event 'cpu-clock'\n #\n # Baseline Delta Shared Object Symbol\n # ........ ....... .................. ..........................................\n #\n 18.42% +0.34% libc-2.24.so [.] __memcmp_sse4_1\n 15.50% -0.45% libz.so.1.2.8 [.] 0x00000000000083c9\n 8.42% -0.01% libz.so.1.2.8 [.] inflate\n 6.33% +0.30% libc-2.24.so [.] __memmove_avx_unaligned_erms\n 4.67% -0.36% git [.] lookup_object\n 3.62% -0.28% git [.] unpack_object_header_buffer\n 2.64% +0.20% git [.] commit_to_sha1\n 2.41% -0.03% git [.] get_delta_base\n 2.05% -0.17% git [.] sha1_compression_states\n 2.00% +0.06% git [.] use_pack\n 1.66% +0.14% git [.] nth_packed_object_offset\n 1.63% +0.11% git [.] write_graph_chunk_extra_edges\n 1.44% +0.21% libz.so.1.2.8 [.] adler32\n 1.42% -0.03% git [.] sort_revindex\n 1.42% -0.06% git [.] parse_commit_date\n 1.41% -0.15% git [.] oidhash\n 1.37% +0.07% git [.] commit_list_count\n 1.11% -0.02% git [.] in_window\n 1.08% -0.05% git [.] packed_to_object_type\n 0.90% -0.18% git [.] ubc_check\n 0.82% -0.23% git [.] hex2chr\n 0.75% -0.02% git [.] hashcmp\n 0.71% +0.17% libc-2.24.so [.] msort_with_tmp.part.0\n 0.70% +0.25% git [.] sha1_pos\n 0.70% +0.12% git [.] repo_parse_commit_internal\n 0.66% -0.06% git [.] bsearch_hash\n 0.65% -0.11% git [.] compute_generation_numbers\n 0.64% +0.03% git [.] unpack_object_header\n 0.60% -0.06% git [.] find_entry_ptr\n 0.59% +0.09% libc-2.24.so [.] _int_malloc\n 0.55% -0.01% git [.] hexval\n 0.51% +0.07% git [.] entry_equals\n 0.44% +0.12% git [.] get_sha1_hex\n 0.41% -0.13% git [.] packed_object_info\n\n...and many other functions that have a delta that can be attributed to\nnoise, all comfortably less than 1%.\n\nSo, I'm not sure what was going on with my original measurements, other\nthan that I took them around midnight, so the chance for error was\nprobably high. I'll go with your measurements, since they are both\ncloser to what we'd see in the real world, and actually representative\nof the change here.\n\nI'll wait for some of the discussion in the sub-thread about\n'OBJECT_INFO_SKIP_FETCH' to settle, and then send v2 in the next couple\nof days or so.\n\n> -Peff\n\nThanks,\nTaylor\n"},{"id":"393732","messageId":"20200322184519.GA654322@coredump.intra.peff.net","threadId":"53046","inReplyTo":"20200322110424.GC2224@szeder.dev","subject":"looking up object types quickly, was Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-22T18:45:19Z","receivedAt":"2020-03-22T18:45:22Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Mar 22, 2020 at 12:04:24PM +0100, SZEDER Gábor wrote:\n\n> > > Where the last step is taking all commits listed in any pack, which is\n> > > cheap to iterate.\n> > \n> > I'm not sure it's all that cheap. It has to find the type of every\n> > object in every pack. And finding types involves walking delta chains.\n> \n> Indeed, that's just about the most expensive way to find all commits,\n> in my experience it can be well over a magnitude slower than\n> '--reachable'.\n\nThey don't necessarily produce the same set of commits, of course, but\nfor the purposes of \"commit-graph write\" I think they can generally be\nconsidered interchangeable.\n\nThe speed depends on a couple of factors. One is just the makeup of the\nrepository: tree size, how many are deltas, etc. But a big one is\nwhether commit-graphs are already enabled. :)\n\nOn linux.git without commit-graphs, both of these take about 7.5s for\nme:\n\n git cat-file --batch-all-objects --unordered --batch-check='%(objecttype) %(objectname)'\n\n git rev-list --all\n\nBut with graphs, the latter takes about 700ms.\n\nI was coincidentally thinking about this problem (\"show me all commits\")\nfor something unrelated recently, and I do think that cat-file\ninvocation could be sped up in some cases. Here are a few ideas:\n\n1. If the pack has a .bitmap file, it contains 4 \"type\" bitmaps that you\n can use to quickly determine the type of a given object. But:\n\n - the current code for loading bitmaps files is slower than we'd\n need; it indexes all of the commit bitmaps, but we wouldn't use\n them. So we'd want something that just loads the type bitmaps and\n stops.\n\n - you have to know the bit position of the object you're interested\n in, which implies computing the revidx. We could provide a \"bit\n position\" cache in the bitmap file (basically one uint32_t for each\n object giving the packfile order position, but stored in pack .idx\n order).\n\n Neither is too hard a problem, but it's clearly not just a small\n patch to consult the bitmap.\n\n It could be patched directly into oid_object_info_extended(), which\n could do individual type lookups this way. But it would be faster\n still if callers could say \"I'm only interested in commits\", in which\n case we could just quickly walk the commit-type bitmap in one pass\n (to get the commits in just that packfile, and then go through the\n other objects the old-fashioned way).\n\n2. The commit-graph file can quickly tell us whether an object is a\n commit. But unfortunately it can give us a definite \"yes\", but not a\n definite \"no\" (because it might be a commit that just isn't (yet) in\n the graph file). So we'd have to find the real type of any\n non-commits, and I think that's where we spend the bulk of our time\n anyway.\n\n3. To find the type of a delta object, we have to walk back to a base\n object with a concrete type. When we access the actual object\n contents, we cache intermediate bases to avoid digging down the same\n chain over and over. But I don't think there's any such cache for the\n type lookup. So if you have a 50-deep delta chain and want the type\n of each object, you'll walk down 49 links, then 48 links, and so on.\n It probably wouldn't be that hard to have a small type cache (or just\n allow the existing cache to have entries for \"I know the type, but\n don't have the contents\").\n\nI suspect (1) would give the biggest speedup, but is more work and\nrequires bitmaps. I think (3) is likely to give a moderate win and\nprobably isn't that big a patch.\n\n-Peff\n"},{"id":"393735","messageId":"20200322191838.GA671552@coredump.intra.peff.net","threadId":"53046","inReplyTo":"20200322184519.GA654322@coredump.intra.peff.net","subject":"Re: looking up object types quickly, was Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-22T19:18:38Z","receivedAt":"2020-03-22T19:18:41Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Mar 22, 2020 at 02:45:19PM -0400, Jeff King wrote:\n\n> 3. To find the type of a delta object, we have to walk back to a base\n> object with a concrete type. When we access the actual object\n> contents, we cache intermediate bases to avoid digging down the same\n> chain over and over. But I don't think there's any such cache for the\n> type lookup. So if you have a 50-deep delta chain and want the type\n> of each object, you'll walk down 49 links, then 48 links, and so on.\n> It probably wouldn't be that hard to have a small type cache (or just\n> allow the existing cache to have entries for \"I know the type, but\n> don't have the contents\").\n> \n> I suspect (1) would give the biggest speedup, but is more work and\n> requires bitmaps. I think (3) is likely to give a moderate win and\n> probably isn't that big a patch.\n\nSadly, it doesn't seem to help. Here's a hacky implementation (I tested\nit only on my limited cat-file case; I wouldn't be at all surprised if\nit causes problems for users of the delta cache that want the actual\nobject contents).\n\nAfter some rudimentary profiling (which I _should_ have done in the\nfirst place before opening my mouth), it looks like finding the types\nisn't actually the most expensive thing anyway: it's just dealing with\nthe sheer number of objects in the pack.\n\nThat implies that teaching packed_object_info() to use bitmaps to find\nthe individual types wouldn't help much either (but being able to ask\n\"just give me the commits\" and iterating over the commit-type bitmap\nprobably _would_).\n\nAnyway, here's the patch for the curious.\n\n---\ndiff --git a/packfile.c b/packfile.c\nindex f4e752996d..482733689a 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1273,6 +1273,13 @@ static int retry_bad_packed_offset(struct repository *r,\n \n #define POI_STACK_PREALLOC 64\n \n+/* some reordering of static functions could avoid these */\n+static enum object_type get_delta_base_cache_type(struct packed_git *p,\n+\t\t\t\t\t\t off_t curpos);\n+static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n+\t\t\t\t void *base, unsigned long base_size,\n+\t\t\t\t enum object_type type);\n+\n static enum object_type packed_to_object_type(struct repository *r,\n \t\t\t\t\t struct packed_git *p,\n \t\t\t\t\t off_t obj_offset,\n@@ -1287,6 +1294,14 @@ static enum object_type packed_to_object_type(struct repository *r,\n \twhile (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {\n \t\toff_t base_offset;\n \t\tunsigned long size;\n+\t\tenum object_type cached_type;\n+\n+\t\tcached_type = get_delta_base_cache_type(p, obj_offset);\n+\t\tif (cached_type > 0) {\n+\t\t\ttype = cached_type;\n+\t\t\tgoto out;\n+\t\t}\n+\n \t\t/* Push the object we're going to leave behind */\n \t\tif (poi_stack_nr >= poi_stack_alloc && poi_stack == small_poi_stack) {\n \t\t\tpoi_stack_alloc = alloc_nr(poi_stack_nr);\n@@ -1326,6 +1341,11 @@ static enum object_type packed_to_object_type(struct repository *r,\n \t}\n \n out:\n+\tif (type != OBJ_BAD) {\n+\t\tsize_t i;\n+\t\tfor (i = 0; i < poi_stack_nr; i++)\n+\t\t\tadd_delta_base_cache(p, poi_stack[i], NULL, 0, type);\n+\t}\n \tif (poi_stack != small_poi_stack)\n \t\tfree(poi_stack);\n \treturn type;\n@@ -1385,6 +1405,13 @@ get_delta_base_cache_entry(struct packed_git *p, off_t base_offset)\n \treturn e ? container_of(e, struct delta_base_cache_entry, ent) : NULL;\n }\n \n+static enum object_type get_delta_base_cache_type(struct packed_git *p, off_t curpos)\n+{\n+\tstruct delta_base_cache_entry *ent =\n+\t\tget_delta_base_cache_entry(p, curpos);\n+\treturn ent ? ent->type : OBJ_BAD;\n+}\n+\n static int delta_base_cache_key_eq(const struct delta_base_cache_key *a,\n \t\t\t\t const struct delta_base_cache_key *b)\n {\n@@ -1433,7 +1460,7 @@ static void *cache_or_unpack_entry(struct repository *r, struct packed_git *p,\n \tstruct delta_base_cache_entry *ent;\n \n \tent = get_delta_base_cache_entry(p, base_offset);\n-\tif (!ent)\n+\tif (!ent || !ent->data)\n \t\treturn unpack_entry(r, p, base_offset, type, base_size);\n \n \tif (type)\n@@ -1677,7 +1704,7 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n \t\tstruct delta_base_cache_entry *ent;\n \n \t\tent = get_delta_base_cache_entry(p, curpos);\n-\t\tif (ent) {\n+\t\tif (ent && ent->data) {\n \t\t\ttype = ent->type;\n \t\t\tdata = ent->data;\n \t\t\tsize = ent->size;\n"},{"id":"393808","messageId":"20200323201525.GA98905@syl.local","threadId":"53046","inReplyTo":"20200322110424.GC2224@szeder.dev","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-03-23T20:15:25Z","receivedAt":"2020-03-23T20:15:29Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sun, Mar 22, 2020 at 12:04:24PM +0100, SZEDER Gábor wrote:\n> On Sun, Mar 22, 2020 at 01:36:35AM -0400, Jeff King wrote:\n> > The \"--input=none\" option\n> > isn't \"no input\"; it's actually \"take all existing graphed objects as\n> > input\" (i.e., it implies --append). So each of those objects will\n> > already have been examined in an earlier stage.\n>\n> Yeah, we discussed it earlier that '--input=none' doesn't properly\n> describe what it tries to accomplish, and suggested '--input=exists'\n> (or was it 'existing'?) instead.\n\nGood idea. I don't remember discussing '--input=exist{s,ing}',\nspecifically, but I do think that '--input=none' is not as clear as it\ncould be.\n\nI sent [1], which I think may be a step in the right direction. I'll\nlook forward to your thoughts.\n\n> > > Where the last step is taking all commits listed in any pack, which is\n> > > cheap to iterate.\n> >\n> > I'm not sure it's all that cheap. It has to find the type of every\n> > object in every pack. And finding types involves walking delta chains.\n>\n> Indeed, that's just about the most expensive way to find all commits,\n> in my experience it can be well over a magnitude slower than\n> '--reachable'.\n\nThanks,\nTaylor\n\n[1]: https://lore.kernel.org/git/e0f42a2f3c0162a5d43bb2bce0f69264b59f92e9.1584994172.git.me@ttaylorr.com/\n"},{"id":"393857","messageId":"20200324060637.GB610977@coredump.intra.peff.net","threadId":"53046","inReplyTo":"20200322164531.GA55067@syl.local","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-24T06:06:37Z","receivedAt":"2020-03-24T06:06:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Mar 22, 2020 at 10:45:31AM -0600, Taylor Blau wrote:\n\n> So, I'm not sure what was going on with my original measurements, other\n> than that I took them around midnight, so the chance for error was\n> probably high. I'll go with your measurements, since they are both\n> closer to what we'd see in the real world, and actually representative\n> of the change here.\n\nI wondered if perhaps you had stray commit-graph files sitting around. I\ndon't think we'd look at them if they aren't mentioned in the\ncommit-graphs index, though. And anyway, feeding all of the packed\nobjects would mean those would all be parsed in the earlier stage, so\neven if we _did_ have a bunch of stuff to merge, it would have been fast\neven with the old code.\n\nSo...I dunno.\n\nOne other thing that's bitten me in the past is accidentally compiling\nwith the wrong optimization settings. I have my config.mak set up to\ncompile with -O0 by default (because it's faster and because I'm\nfrequently debugging anyway), and then I do a -O2 build for my daily\ndriver. But when performance testing, I sometimes accidentally compare\n-O0 and -O2 builds to each other. That's all very specific to my\nconfig.mak setup, but I know you've picked up some of it, so it's\npossible you inherited that subtlety. :)\n\n-Peff\n"},{"id":"393859","messageId":"20200324061159.GC610977@coredump.intra.peff.net","threadId":"53046","inReplyTo":"20200322154749.GB53402@syl.local","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-24T06:11:59Z","receivedAt":"2020-03-24T06:12:02Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Mar 22, 2020 at 09:47:49AM -0600, Taylor Blau wrote:\n\n> > > [1] I'm actually not quite sure about correctness here. It should be\n> > > fine to generate a graph file without any given commit; readers will\n> > > just have to load that commit the old-fashioned way. But at this\n> > > phase of \"commit-graph write\", I think we'll already have done the\n> > > close_reachable() check. What does it mean to throw away a commit at\n> > > this stage? If we're the parent of another commit, then it will have\n> > > trouble referring to us by a uint32_t. Will the actual writing phase\n> > > barf, or will we generate an invalid graph file?\n> >\n> > It doesn't seem great. If I instrument Git like this to simulate an\n> > object temporarily \"missing\" (if it were really missing the whole repo\n> > would be corrupt; we're trying to see what would happen if a race causes\n> > us to momentarily not see it):\n> \n> This is definitely a problem on either side of this patch, which is\n> demonstrated by the fact that you applied your changes without my patch\n> on top (and that my patch isn't changing anything substantial in this\n> area like removing the 'continue' statement).\n> \n> Should we address this before moving on with my patch? I think that we\n> *could*, but I'd rather go forward with what we have for now, since it's\n> only improving the situation, and not introducing a new bug.\n\nI do agree it's a problem before your patch. But I think your patch may\nmake it a lot more common, if only because it means we'd _actually_ be\ndropping entries for objects that went away, instead of accidentally\nkeeping them due to re-using the graph result. So it probably is worth\ntrying to deal with it now, or at least thinking hard about it.\n\nThe trouble is that I'm not sure what _should_ happen. Aborting the\nwhole commit-graph generation seems overboard (and would be annoying for\ncases where whole swaths of history became unreachable and went away;\npresumably we'd be dropping _all_ of those objects, and the write phase\nwould be just fine). I have a feeling the correct solution is to do this\nmerging pass earlier, before we check close_reachable(). Or if not a\ntrue merging pass, at least a pass to check which existing entries are\nstill valid. But I don't know how painful that reordering would be.\n\n-Peff\n"},{"id":"393862","messageId":"20200324061434.GD610977@coredump.intra.peff.net","threadId":"53046","inReplyTo":"20200322154439.GA53402@syl.local","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-24T06:14:34Z","receivedAt":"2020-03-24T06:14:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Mar 22, 2020 at 09:44:39AM -0600, Taylor Blau wrote:\n\n> > Using QUICK means we won't waste time double-checking in the second\n> > case. But it means we won't catch the first case, and we may generate a\n> > new graph file that omits the object. They're both optimizations, and I\n> > don't think we're impacting correctness[1], but it's not clear to me\n> > whether one is a win over the other. We don't generally expect objects\n> > we have to go away often.\n> >\n> > Skipping fetching seems a little more straight-forward to me. If we had\n> > it in a graph file, presumably we had the actual object before, too. And\n> > either we're in the first case above (we really do have it and just need\n> > to double-check) in which case not saying QUICK would be enough. Or we\n> > intentionally got rid of it. In which case downloading it just to\n> > generate a cache is quite silly.\n> \n> I was going to write that I'm not entirely sure of this, but I tried to\n> talk myself through it below, and I think that the right flag is *only*\n> OBJECT_INFO_SKIP_FETCH_OBJECT.\n\nRe-reading what I wrote, I think I didn't say it very well. But yes,\nthat's what I think we ought to do, too: only use SKIP_FETCH_OBJECT.\n\n-Peff\n"},{"id":"393907","messageId":"20200324230826.GA42939@syl.local","threadId":"53046","inReplyTo":"20200324061159.GC610977@coredump.intra.peff.net","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-03-24T23:08:26Z","receivedAt":"2020-03-24T23:08:31Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Mar 24, 2020 at 02:11:59AM -0400, Jeff King wrote:\n> On Sun, Mar 22, 2020 at 09:47:49AM -0600, Taylor Blau wrote:\n>\n> > > > [1] I'm actually not quite sure about correctness here. It should be\n> > > > fine to generate a graph file without any given commit; readers will\n> > > > just have to load that commit the old-fashioned way. But at this\n> > > > phase of \"commit-graph write\", I think we'll already have done the\n> > > > close_reachable() check. What does it mean to throw away a commit at\n> > > > this stage? If we're the parent of another commit, then it will have\n> > > > trouble referring to us by a uint32_t. Will the actual writing phase\n> > > > barf, or will we generate an invalid graph file?\n> > >\n> > > It doesn't seem great. If I instrument Git like this to simulate an\n> > > object temporarily \"missing\" (if it were really missing the whole repo\n> > > would be corrupt; we're trying to see what would happen if a race causes\n> > > us to momentarily not see it):\n> >\n> > This is definitely a problem on either side of this patch, which is\n> > demonstrated by the fact that you applied your changes without my patch\n> > on top (and that my patch isn't changing anything substantial in this\n> > area like removing the 'continue' statement).\n> >\n> > Should we address this before moving on with my patch? I think that we\n> > *could*, but I'd rather go forward with what we have for now, since it's\n> > only improving the situation, and not introducing a new bug.\n>\n> I do agree it's a problem before your patch. But I think your patch may\n> make it a lot more common, if only because it means we'd _actually_ be\n> dropping entries for objects that went away, instead of accidentally\n> keeping them due to re-using the graph result. So it probably is worth\n> trying to deal with it now, or at least thinking hard about it.\n>\n> The trouble is that I'm not sure what _should_ happen. Aborting the\n> whole commit-graph generation seems overboard (and would be annoying for\n> cases where whole swaths of history became unreachable and went away;\n> presumably we'd be dropping _all_ of those objects, and the write phase\n> would be just fine). I have a feeling the correct solution is to do this\n> merging pass earlier, before we check close_reachable(). Or if not a\n> true merging pass, at least a pass to check which existing entries are\n> still valid. But I don't know how painful that reordering would be.\n\nMaybe, but I'm not sure that moving 'close_reachable' up would\nnecessarily solve all of our problems. Or, at least, that it wouldn't\ncreate a set of new problems :).\n\nLet's say that you have (1) some connected component of your history\nthat is written to a commit-graph, where (2) part of that cluster has\nbeen dropped (e.g., due to corruption, a rogue 'git gc', etc), and (3)\nyou're writing a new graph with '--input=graphed'.\n\nWhat is 'close_reachable' supposed to do? If some of the now-missing\ncommits are in the reachability closure of the commits that still exist\nin the repository, then we're back to where we started. We *could* have\n'close_reachable' take all missing commits and drop their ancestors and\ndescendants, but this creates quite the headache for 'close_reachable',\nwhich now needs to keep track of such things.\n\nI'm hopeful that this isn't so common in practice, but I'm also not\nentirely sure one way or another. I can plan to deploy this patch to\nGitHub's servers for a ~month and see if we experience it. If it turns\nout to be common, I'll assume that others have this problem, too, in\nwhich case we can go back and think more about it.\n\nBut, I'm hopeful that this problem is rare enough that it isn't worth\nworrying about for anybody, GitHub or not.\n\n> -Peff\n\nThanks,\nTaylor\n"},{"id":"394158","messageId":"20200327084248.GA607390@coredump.intra.peff.net","threadId":"53046","inReplyTo":"20200324230826.GA42939@syl.local","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-27T08:42:48Z","receivedAt":"2020-03-27T08:42:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 24, 2020 at 05:08:26PM -0600, Taylor Blau wrote:\n\n> > The trouble is that I'm not sure what _should_ happen. Aborting the\n> > whole commit-graph generation seems overboard (and would be annoying for\n> > cases where whole swaths of history became unreachable and went away;\n> > presumably we'd be dropping _all_ of those objects, and the write phase\n> > would be just fine). I have a feeling the correct solution is to do this\n> > merging pass earlier, before we check close_reachable(). Or if not a\n> > true merging pass, at least a pass to check which existing entries are\n> > still valid. But I don't know how painful that reordering would be.\n> \n> Maybe, but I'm not sure that moving 'close_reachable' up would\n> necessarily solve all of our problems. Or, at least, that it wouldn't\n> create a set of new problems :).\n> \n> Let's say that you have (1) some connected component of your history\n> that is written to a commit-graph, where (2) part of that cluster has\n> been dropped (e.g., due to corruption, a rogue 'git gc', etc), and (3)\n> you're writing a new graph with '--input=graphed'.\n> \n> What is 'close_reachable' supposed to do? If some of the now-missing\n> commits are in the reachability closure of the commits that still exist\n> in the repository, then we're back to where we started. We *could* have\n> 'close_reachable' take all missing commits and drop their ancestors and\n> descendants, but this creates quite the headache for 'close_reachable',\n> which now needs to keep track of such things.\n\nYeah, I think my suggestion was dumb. I was thinking that\nclose_reachable() might somehow fix things up, but all it ever does with\nthe current code is _add_ commits to the graph. And we would want the\nopposite: removing ones which can no longer be present, because their\nancestors are gone. That would be possible, but would be quite a pain\n(you'd have to walk an inversion of the parent DAG).\n\n> I'm hopeful that this isn't so common in practice, but I'm also not\n> entirely sure one way or another. I can plan to deploy this patch to\n> GitHub's servers for a ~month and see if we experience it. If it turns\n> out to be common, I'll assume that others have this problem, too, in\n> which case we can go back and think more about it.\n\nIt _shouldn't_ be too common, because it implies that we have commit X\nbut not its ancestor X^. And the pruning and repacking code tries to\navoid throwing away X^ in such a case. It could still happen due to a\nrace, though.\n\nSo yeah, I think we should mostly ignore it. It's not a new problem with\nyour series (and the only reason it is more common with your series is\nthat the old code was actually incorrectly handling some cases). It\nmight be worth turning the \"missing parent\" BUG() into a die(), since we\nknow it's reachable. But that's largely academic, since in either case\ncommit-graph is going to barf and fail to write.\n\nAs a follow-up to this part for anyone else following the discussion:\n\n> I can plan to deploy this patch to GitHub's servers for a ~month and\n> see if we experience it.\n\n...I don't think we'll actually generate good data here. We're probably\ngoing to end up doing our \"big maintenance\" commit-graph roll-ups by\njust feeding --reachable as input, and dropping all of the existing\ngraphs.\n\n-Peff\n"},{"id":"394171","messageId":"20200327150358.GA30204@syl.local","threadId":"53046","inReplyTo":"20200327084248.GA607390@coredump.intra.peff.net","subject":"Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-03-27T15:03:58Z","receivedAt":"2020-03-27T15:04:05Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Mar 27, 2020 at 04:42:48AM -0400, Jeff King wrote:\n> On Tue, Mar 24, 2020 at 05:08:26PM -0600, Taylor Blau wrote:\n> > I can plan to deploy this patch to GitHub's servers for a ~month and\n> > see if we experience it.\n>\n> ...I don't think we'll actually generate good data here. We're probably\n> going to end up doing our \"big maintenance\" commit-graph roll-ups by\n> just feeding --reachable as input, and dropping all of the existing\n> graphs.\n\nFor what it's worth (and I'm not sure that it's worth much), but this\nis only true in the last day or so. Before, we were running:\n\n $ git commit-graph write --split=merge-all --input=none\n\nwhich *did* exercise this code quite frequently (and thus would have\nbeen helped by this patch). But now, we are running something like:\n\n $ git commit-graph write --split=replace --input=reachable\n\n...where '--split=replace' means \"write a split commit-graph, but drop\nall existing layers before writing it\". This case is obviously not\nhelped by this patch, although I think the patch is worthwhile for\ncallers who do the first thing.\n\nI'll post patches about that shortly after they've been a little more\nwell-vetted (we're only generating split commit-graphs on a percentage\nof repositories for now).\n\n> -Peff\n\nThanks,\nTaylor\n"}]}