{"thread":{"id":"47922","subject":"[PATCH] revision.c: reduce object database queries","startedAt":"2018-02-25T01:35:12Z","lastAt":"2018-02-28T13:34:32Z","messageCount":7,"participants":["Derrick Stolee","Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"340190","messageId":"1519522496-73090-1-git-send-email-dstolee@microsoft.com","threadId":"47922","inReplyTo":null,"subject":"[PATCH] revision.c: reduce object database queries","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-02-25T01:34:56Z","receivedAt":"2018-02-25T01:35:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"In mark_parents_uninteresting(), we check for the existence of an\nobject file to see if we should treat a commit as parsed. The result\nis to set the \"parsed\" bit on the commit.\n\nModify the condition to only check has_object_file() if the result\nwould change the parsed bit.\n\nWhen a local branch is different from its upstream ref, \"git status\"\nwill compute ahead/behind counts. This uses paint_down_to_common()\nand hits mark_parents_uninteresting(). On a copy of the Linux repo\nwith a local instance of \"master\" behind the remote branch\n\"origin/master\" by ~60,000 commits, we find the performance of\n\"git status\" went from 1.42 seconds to 1.32 seconds, for a relative\ndifference of -7.0%.\n\nSigned-off-by: Derrick Stolee <dstolee@microsoft.com>\n---\n revision.c | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/revision.c b/revision.c\nindex 5ce9b93..bc7def5 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -113,7 +113,8 @@ void mark_parents_uninteresting(struct commit *commit)\n \t\t\t * it is popped next time around, we won't be trying\n \t\t\t * to parse it and get an error.\n \t\t\t */\n-\t\t\tif (!has_object_file(&commit->object.oid))\n+\t\t\tif (!commit->object.parsed &&\n+\t\t\t    !has_object_file(&commit->object.oid))\n \t\t\t\tcommit->object.parsed = 1;\n \n \t\t\tif (commit->object.flags & UNINTERESTING)\n-- \n2.7.4\n\n"},{"id":"340191","messageId":"e70fe6eb-994a-66b0-3c20-d19ea6635e07@gmail.com","threadId":"47922","inReplyTo":"1519522496-73090-1-git-send-email-dstolee@microsoft.com","subject":"Re: [PATCH] revision.c: reduce object database queries","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-02-25T01:41:02Z","receivedAt":"2018-02-25T01:41:11Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/24/2018 8:34 PM, Derrick Stolee wrote:\n> In mark_parents_uninteresting(), we check for the existence of an\n> object file to see if we should treat a commit as parsed. The result\n> is to set the \"parsed\" bit on the commit.\n>\n> Modify the condition to only check has_object_file() if the result\n> would change the parsed bit.\n>\n> When a local branch is different from its upstream ref, \"git status\"\n> will compute ahead/behind counts. This uses paint_down_to_common()\n> and hits mark_parents_uninteresting(). On a copy of the Linux repo\n> with a local instance of \"master\" behind the remote branch\n> \"origin/master\" by ~60,000 commits, we find the performance of\n> \"git status\" went from 1.42 seconds to 1.32 seconds, for a relative\n> difference of -7.0%.\n\nI do want to add that the exact same \"git status\" performance test with \nthe commit-graph feature goes from 0.29 seconds to 0.21 seconds for a \nrelative change of -27.5%.\n\nThanks,\n\n-Stolee\n\n\n"},{"id":"340272","messageId":"20180226013048.GA8677@sigill.intra.peff.net","threadId":"47922","inReplyTo":"1519522496-73090-1-git-send-email-dstolee@microsoft.com","subject":"Re: [PATCH] revision.c: reduce object database queries","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-02-26T01:30:48Z","receivedAt":"2018-02-26T01:30:56Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Feb 24, 2018 at 08:34:56PM -0500, Derrick Stolee wrote:\n\n> In mark_parents_uninteresting(), we check for the existence of an\n> object file to see if we should treat a commit as parsed. The result\n> is to set the \"parsed\" bit on the commit.\n> \n> Modify the condition to only check has_object_file() if the result\n> would change the parsed bit.\n> \n> When a local branch is different from its upstream ref, \"git status\"\n> will compute ahead/behind counts. This uses paint_down_to_common()\n> and hits mark_parents_uninteresting(). On a copy of the Linux repo\n> with a local instance of \"master\" behind the remote branch\n> \"origin/master\" by ~60,000 commits, we find the performance of\n> \"git status\" went from 1.42 seconds to 1.32 seconds, for a relative\n> difference of -7.0%.\n\nThis looks like an obvious and easy optimization, and I'm OK with this\npatch.\n\nBut looking at the existing code, it makes me wonder a few things:\n\n> diff --git a/revision.c b/revision.c\n> index 5ce9b93..bc7def5 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -113,7 +113,8 @@ void mark_parents_uninteresting(struct commit *commit)\n>  \t\t\t * it is popped next time around, we won't be trying\n>  \t\t\t * to parse it and get an error.\n>  \t\t\t */\n> -\t\t\tif (!has_object_file(&commit->object.oid))\n> +\t\t\tif (!commit->object.parsed &&\n> +\t\t\t    !has_object_file(&commit->object.oid))\n>  \t\t\t\tcommit->object.parsed = 1;\n\nWe don't actually need the object contents at all right here. This is\njust faking the \"parsed\" flag for later so that calls to parse_object()\ndon't barf.\n\nThis code comes originally form 454fbbcde3 (git-rev-list: allow missing\nobjects when the parent is marked UNINTERESTING, 2005-07-10). But later,\nin aeeae1b771 (revision traversal: allow UNINTERESTING objects to be\nmissing, 2009-01-27), we marked dealt with calling parse_object() on the\nparents more directly.\n\nSo what I wonder is whether this code is simply redundant and can go\naway entirely. That would save the has_object_file() call in all cases.\nWe'd stop setting the fake commit->object.parsed flag, which in theory\nmeans we'd make repeated failed calls to parse_commit_gently() if we\nvisited the same commit over and over. I wonder if add_parents_to_list()\nshould skip already-UNINTERESTING parents, which would mean we only try\nto access each missing candidate once (OTOH missing ones are probably\nrare enough that it doesn't make much difference either way).\n\nProbably the fake commit->object.parsed flag isn't hurting anything in\npractice, but it seems pretty nasty to lie about having loaded the\ncommit in the global store. E.g., imagine a follow-up traversal in the\nsame process in which that commit _isn't_ UNINTERESTING, and we'd\nerroneously treat it as an available commit with no parents.\n\n-Peff\n"},{"id":"340273","messageId":"20180226013822.GA9385@sigill.intra.peff.net","threadId":"47922","inReplyTo":"20180226013048.GA8677@sigill.intra.peff.net","subject":"Re: [PATCH] revision.c: reduce object database queries","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-02-26T01:38:22Z","receivedAt":"2018-02-26T01:38:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Feb 25, 2018 at 08:30:48PM -0500, Jeff King wrote:\n\n> > diff --git a/revision.c b/revision.c\n> > index 5ce9b93..bc7def5 100644\n> > --- a/revision.c\n> > +++ b/revision.c\n> > @@ -113,7 +113,8 @@ void mark_parents_uninteresting(struct commit *commit)\n> >  \t\t\t * it is popped next time around, we won't be trying\n> >  \t\t\t * to parse it and get an error.\n> >  \t\t\t */\n> > -\t\t\tif (!has_object_file(&commit->object.oid))\n> > +\t\t\tif (!commit->object.parsed &&\n> > +\t\t\t    !has_object_file(&commit->object.oid))\n> >  \t\t\t\tcommit->object.parsed = 1;\n> \n> We don't actually need the object contents at all right here. This is\n> just faking the \"parsed\" flag for later so that calls to parse_object()\n> don't barf.\n> \n> This code comes originally form 454fbbcde3 (git-rev-list: allow missing\n> objects when the parent is marked UNINTERESTING, 2005-07-10). But later,\n> in aeeae1b771 (revision traversal: allow UNINTERESTING objects to be\n> missing, 2009-01-27), we marked dealt with calling parse_object() on the\n> parents more directly.\n> \n> So what I wonder is whether this code is simply redundant and can go\n> away entirely. That would save the has_object_file() call in all cases.\n\nThere's a similar case for trees. In mark_tree_contents_uninteresting()\nwe do:\n\n   if (!has_object_file(&obj->oid))\n\treturn;\n   if (parse_tree(tree) < 0)\n\tdie(\"bad tree %s\", oid_to_hex(&obj->oid));\n\nwhich seems wasteful. Probably this could be:\n\n  if (parse_tree_gently(tree, 1) < 0)\n\treturn; /* missing uninteresting trees ok */\n\nthough technically the existing code allows _missing_ trees, but\nnot on corrupt ones.\n\nI guess this is perhaps less interesting, because we only mark trees\ndirectly fed from the pending array, not every tree of commits that we\ntraverse. Though if you had a really gigantic tree, it might be\nmeasurable.\n\n-Peff\n"},{"id":"340483","messageId":"xmqqefl6nhud.fsf@gitster-ct.c.googlers.com","threadId":"47922","inReplyTo":"20180226013822.GA9385@sigill.intra.peff.net","subject":"Re: [PATCH] revision.c: reduce object database queries","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-02-27T23:16:58Z","receivedAt":"2018-02-27T23:17:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n>> This code comes originally form 454fbbcde3 (git-rev-list: allow missing\n>> objects when the parent is marked UNINTERESTING, 2005-07-10). But later,\n>> in aeeae1b771 (revision traversal: allow UNINTERESTING objects to be\n>> missing, 2009-01-27), we marked dealt with calling parse_object() on the\n>> parents more directly.\n>>\n>> So what I wonder is whether this code is simply redundant and can go\n>> away entirely. That would save the has_object_file() call in all cases.\n\nHmm, interesting. I forgot all what I did around this area, but you\nare right.  \n\n> There's a similar case for trees. ...\n> though technically the existing code allows _missing_ trees, but\n> not on corrupt ones.\n\nTrue, but the intention of these \"do not care too much about missing\nstuff while marking uninteresting\" effort is aligned better with\nignoring corrupt ones, too, I would think, as \"missing\" in that\nsentence is in fact about \"not availble\", and stuff that exists in\ncorrupt form is still not available anyway.  So I do not think it\nmakes a bad change to start allowing corrupt ones.\n\n> I guess this is perhaps less interesting, because we only mark trees\n> directly fed from the pending array, not every tree of commits that we\n> traverse. Though if you had a really gigantic tree, it might be\n> measurable.\n\nI tend to agree that this is less interesting case than commits.\n\nA huge tree with millions of entries in a single level would spend\nquite a lot of cycle in slurping the tree data to in-core buffer,\nbut we do not actually parse these million entries upon opening the\ntree, so it may not be too bad.\n\n"},{"id":"340542","messageId":"20180228063707.GA4409@sigill.intra.peff.net","threadId":"47922","inReplyTo":"xmqqefl6nhud.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH] revision.c: reduce object database queries","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-02-28T06:37:07Z","receivedAt":"2018-02-28T06:37:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Feb 27, 2018 at 03:16:58PM -0800, Junio C Hamano wrote:\n\n> >> This code comes originally form 454fbbcde3 (git-rev-list: allow missing\n> >> objects when the parent is marked UNINTERESTING, 2005-07-10). But later,\n> >> in aeeae1b771 (revision traversal: allow UNINTERESTING objects to be\n> >> missing, 2009-01-27), we marked dealt with calling parse_object() on the\n> >> parents more directly.\n> >>\n> >> So what I wonder is whether this code is simply redundant and can go\n> >> away entirely. That would save the has_object_file() call in all cases.\n> \n> Hmm, interesting. I forgot all what I did around this area, but you\n> are right.\n\nI'll leave it to Stolee whether he wants to dig into removing the\nhas_object_file() call. I think it would do the right thing, but the\nmost interesting bit would be how it impacts the timings.\n\n> > There's a similar case for trees. ...\n> > though technically the existing code allows _missing_ trees, but\n> > not on corrupt ones.\n> \n> True, but the intention of these \"do not care too much about missing\n> stuff while marking uninteresting\" effort is aligned better with\n> ignoring corrupt ones, too, I would think, as \"missing\" in that\n> sentence is in fact about \"not availble\", and stuff that exists in\n> corrupt form is still not available anyway.  So I do not think it\n> makes a bad change to start allowing corrupt ones.\n\nAgreed. Here it is in patch form, though as we both said, it probably\ndoesn't matter that much in practice. So I'd be OK dropping it out of\na sense of conservatism.\n\n-- >8 --\nSubject: [PATCH] mark_tree_contents_uninteresting: drop has_object check\n\nIt's generally acceptable for UNINTERESTING objects in a\ntraversal to be unavailable (e.g., see aeeae1b771). When\nmarking trees UNINTERESTING, we access the object database\ntwice: once to check if the object is missing (and return\nquietly if it is), and then again to actually parse it.\n\nWe can instead just try to parse; if that fails, we can then\nreturn quietly. That halves the effort we spend on locating\nthe object.\n\nNote that this isn't _exactly_ the same as the original\nbehavior, as the parse failure could be due to other\nproblems than a missing object: it could be corrupted, in\nwhich case the original code would have died. But the new\nbehavior is arguably better, as it covers the object being\nunavailable for any reason. We'll also still issue a warning\nto stderr in such a case.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n revision.c | 5 +----\n 1 file changed, 1 insertion(+), 4 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 5ce9b93baa..221d62c52b 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -51,12 +51,9 @@ static void mark_tree_contents_uninteresting(struct tree *tree)\n {\n \tstruct tree_desc desc;\n \tstruct name_entry entry;\n-\tstruct object *obj = &tree->object;\n \n-\tif (!has_object_file(&obj->oid))\n+\tif (parse_tree_gently(tree, 1) < 0)\n \t\treturn;\n-\tif (parse_tree(tree) < 0)\n-\t\tdie(\"bad tree %s\", oid_to_hex(&obj->oid));\n \n \tinit_tree_desc(&desc, tree->buffer, tree->size);\n \twhile (tree_entry(&desc, &entry)) {\n-- \n2.16.2.582.ge2c16ac3c4\n\n"},{"id":"340563","messageId":"43e0daf5-e6d9-5a2c-ebc2-43df8fa94204@gmail.com","threadId":"47922","inReplyTo":"20180228063707.GA4409@sigill.intra.peff.net","subject":"Re: [PATCH] revision.c: reduce object database queries","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-02-28T13:34:23Z","receivedAt":"2018-02-28T13:34:32Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/28/2018 1:37 AM, Jeff King wrote:\n> On Tue, Feb 27, 2018 at 03:16:58PM -0800, Junio C Hamano wrote:\n>\n>>>> This code comes originally form 454fbbcde3 (git-rev-list: allow missing\n>>>> objects when the parent is marked UNINTERESTING, 2005-07-10). But later,\n>>>> in aeeae1b771 (revision traversal: allow UNINTERESTING objects to be\n>>>> missing, 2009-01-27), we marked dealt with calling parse_object() on the\n>>>> parents more directly.\n>>>>\n>>>> So what I wonder is whether this code is simply redundant and can go\n>>>> away entirely. That would save the has_object_file() call in all cases.\n>> Hmm, interesting. I forgot all what I did around this area, but you\n>> are right.\n> I'll leave it to Stolee whether he wants to dig into removing the\n> has_object_file() call. I think it would do the right thing, but the\n> most interesting bit would be how it impacts the timings.\n\nThis patch was so small that I could understand the full implication of \nmy change.\n\nI'm still very unfamiliar with the object walking machinery in \nrevision.c. There are a lot of inter-dependencies that are taking time \nfor me to understand and to feel confident that I won't cause a side \neffect in a special case. I do appreciate that Junio added a test in \naeeae1b771.\n\nI'll make a note to revisit this area after I have a better grasp of the \nobject walk code, but I will not try removing the has_object_file() call \nnow.\n\n>\n>>> There's a similar case for trees. ...\n>>> though technically the existing code allows _missing_ trees, but\n>>> not on corrupt ones.\n>> True, but the intention of these \"do not care too much about missing\n>> stuff while marking uninteresting\" effort is aligned better with\n>> ignoring corrupt ones, too, I would think, as \"missing\" in that\n>> sentence is in fact about \"not availble\", and stuff that exists in\n>> corrupt form is still not available anyway.  So I do not think it\n>> makes a bad change to start allowing corrupt ones.\n> Agreed. Here it is in patch form, though as we both said, it probably\n> doesn't matter that much in practice. So I'd be OK dropping it out of\n> a sense of conservatism.\n>\n> -- >8 --\n> Subject: [PATCH] mark_tree_contents_uninteresting: drop has_object check\n>\n> It's generally acceptable for UNINTERESTING objects in a\n> traversal to be unavailable (e.g., see aeeae1b771). When\n> marking trees UNINTERESTING, we access the object database\n> twice: once to check if the object is missing (and return\n> quietly if it is), and then again to actually parse it.\n>\n> We can instead just try to parse; if that fails, we can then\n> return quietly. That halves the effort we spend on locating\n> the object.\n>\n> Note that this isn't _exactly_ the same as the original\n> behavior, as the parse failure could be due to other\n> problems than a missing object: it could be corrupted, in\n> which case the original code would have died. But the new\n> behavior is arguably better, as it covers the object being\n> unavailable for any reason. We'll also still issue a warning\n> to stderr in such a case.\n>\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n>   revision.c | 5 +----\n>   1 file changed, 1 insertion(+), 4 deletions(-)\n>\n> diff --git a/revision.c b/revision.c\n> index 5ce9b93baa..221d62c52b 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -51,12 +51,9 @@ static void mark_tree_contents_uninteresting(struct tree *tree)\n>   {\n>   \tstruct tree_desc desc;\n>   \tstruct name_entry entry;\n> -\tstruct object *obj = &tree->object;\n>   \n> -\tif (!has_object_file(&obj->oid))\n> +\tif (parse_tree_gently(tree, 1) < 0)\n>   \t\treturn;\n> -\tif (parse_tree(tree) < 0)\n> -\t\tdie(\"bad tree %s\", oid_to_hex(&obj->oid));\n>   \n>   \tinit_tree_desc(&desc, tree->buffer, tree->size);\n>   \twhile (tree_entry(&desc, &entry)) {\n\n"}]}