Re: [PATCH] revision.c: reduce object database queries
On 2/24/2018 8:34 PM, Derrick Stolee wrote: In mark_parents_uninteresting(), we check for the existence of an object file to see if we should treat a commit as parsed. The result is to set the "parsed" bit on the commit. Modify the condition to only check has_object_file() if the result would change the parsed bit. When a local branch is different from its upstream ref, "git status" will compute ahead/behind counts. This uses paint_down_to_common() and hits mark_parents_uninteresting(). On a copy of the Linux repo with a local instance of "master" behind the remote branch "origin/master" by ~60,000 commits, we find the performance of "git status" went from 1.42 seconds to 1.32 seconds, for a relative difference of -7.0%. I do want to add that the exact same "git status" performance test with the commit-graph feature goes from 0.29 seconds to 0.21 seconds for a relative change of -27.5%. Thanks, -Stolee
Re: [PATCH] revision.c: reduce object database queries
On Sat, Feb 24, 2018 at 08:34:56PM -0500, Derrick Stolee wrote: > In mark_parents_uninteresting(), we check for the existence of an > object file to see if we should treat a commit as parsed. The result > is to set the "parsed" bit on the commit. > > Modify the condition to only check has_object_file() if the result > would change the parsed bit. > > When a local branch is different from its upstream ref, "git status" > will compute ahead/behind counts. This uses paint_down_to_common() > and hits mark_parents_uninteresting(). On a copy of the Linux repo > with a local instance of "master" behind the remote branch > "origin/master" by ~60,000 commits, we find the performance of > "git status" went from 1.42 seconds to 1.32 seconds, for a relative > difference of -7.0%. This looks like an obvious and easy optimization, and I'm OK with this patch. But looking at the existing code, it makes me wonder a few things: > diff --git a/revision.c b/revision.c > index 5ce9b93..bc7def5 100644 > --- a/revision.c > +++ b/revision.c > @@ -113,7 +113,8 @@ void mark_parents_uninteresting(struct commit *commit) >* it is popped next time around, we won't be trying >* to parse it and get an error. >*/ > - if (!has_object_file(&commit->object.oid)) > + if (!commit->object.parsed && > + !has_object_file(&commit->object.oid)) > commit->object.parsed = 1; We don't actually need the object contents at all right here. This is just faking the "parsed" flag for later so that calls to parse_object() don't barf. This code comes originally form 454fbbcde3 (git-rev-list: allow missing objects when the parent is marked UNINTERESTING, 2005-07-10). But later, in aeeae1b771 (revision traversal: allow UNINTERESTING objects to be missing, 2009-01-27), we marked dealt with calling parse_object() on the parents more directly. So what I wonder is whether this code is simply redundant and can go away entirely. That would save the has_object_file() call in all cases. We'd stop setting the fake commit->object.parsed flag, which in theory means we'd make repeated failed calls to parse_commit_gently() if we visited the same commit over and over. I wonder if add_parents_to_list() should skip already-UNINTERESTING parents, which would mean we only try to access each missing candidate once (OTOH missing ones are probably rare enough that it doesn't make much difference either way). Probably the fake commit->object.parsed flag isn't hurting anything in practice, but it seems pretty nasty to lie about having loaded the commit in the global store. E.g., imagine a follow-up traversal in the same process in which that commit _isn't_ UNINTERESTING, and we'd erroneously treat it as an available commit with no parents. -Peff
Re: [PATCH] revision.c: reduce object database queries
On Sun, Feb 25, 2018 at 08:30:48PM -0500, Jeff King wrote: > > diff --git a/revision.c b/revision.c > > index 5ce9b93..bc7def5 100644 > > --- a/revision.c > > +++ b/revision.c > > @@ -113,7 +113,8 @@ void mark_parents_uninteresting(struct commit *commit) > > * it is popped next time around, we won't be trying > > * to parse it and get an error. > > */ > > - if (!has_object_file(&commit->object.oid)) > > + if (!commit->object.parsed && > > + !has_object_file(&commit->object.oid)) > > commit->object.parsed = 1; > > We don't actually need the object contents at all right here. This is > just faking the "parsed" flag for later so that calls to parse_object() > don't barf. > > This code comes originally form 454fbbcde3 (git-rev-list: allow missing > objects when the parent is marked UNINTERESTING, 2005-07-10). But later, > in aeeae1b771 (revision traversal: allow UNINTERESTING objects to be > missing, 2009-01-27), we marked dealt with calling parse_object() on the > parents more directly. > > So what I wonder is whether this code is simply redundant and can go > away entirely. That would save the has_object_file() call in all cases. There's a similar case for trees. In mark_tree_contents_uninteresting() we do: if (!has_object_file(&obj->oid)) return; if (parse_tree(tree) < 0) die("bad tree %s", oid_to_hex(&obj->oid)); which seems wasteful. Probably this could be: if (parse_tree_gently(tree, 1) < 0) return; /* missing uninteresting trees ok */ though technically the existing code allows _missing_ trees, but not on corrupt ones. I guess this is perhaps less interesting, because we only mark trees directly fed from the pending array, not every tree of commits that we traverse. Though if you had a really gigantic tree, it might be measurable. -Peff
Re: [PATCH] revision.c: reduce object database queries
Jeff King writes: >> This code comes originally form 454fbbcde3 (git-rev-list: allow missing >> objects when the parent is marked UNINTERESTING, 2005-07-10). But later, >> in aeeae1b771 (revision traversal: allow UNINTERESTING objects to be >> missing, 2009-01-27), we marked dealt with calling parse_object() on the >> parents more directly. >> >> So what I wonder is whether this code is simply redundant and can go >> away entirely. That would save the has_object_file() call in all cases. Hmm, interesting. I forgot all what I did around this area, but you are right. > There's a similar case for trees. ... > though technically the existing code allows _missing_ trees, but > not on corrupt ones. True, but the intention of these "do not care too much about missing stuff while marking uninteresting" effort is aligned better with ignoring corrupt ones, too, I would think, as "missing" in that sentence is in fact about "not availble", and stuff that exists in corrupt form is still not available anyway. So I do not think it makes a bad change to start allowing corrupt ones. > I guess this is perhaps less interesting, because we only mark trees > directly fed from the pending array, not every tree of commits that we > traverse. Though if you had a really gigantic tree, it might be > measurable. I tend to agree that this is less interesting case than commits. A huge tree with millions of entries in a single level would spend quite a lot of cycle in slurping the tree data to in-core buffer, but we do not actually parse these million entries upon opening the tree, so it may not be too bad.
Re: [PATCH] revision.c: reduce object database queries
On Tue, Feb 27, 2018 at 03:16:58PM -0800, Junio C Hamano wrote: > >> This code comes originally form 454fbbcde3 (git-rev-list: allow missing > >> objects when the parent is marked UNINTERESTING, 2005-07-10). But later, > >> in aeeae1b771 (revision traversal: allow UNINTERESTING objects to be > >> missing, 2009-01-27), we marked dealt with calling parse_object() on the > >> parents more directly. > >> > >> So what I wonder is whether this code is simply redundant and can go > >> away entirely. That would save the has_object_file() call in all cases. > > Hmm, interesting. I forgot all what I did around this area, but you > are right. I'll leave it to Stolee whether he wants to dig into removing the has_object_file() call. I think it would do the right thing, but the most interesting bit would be how it impacts the timings. > > There's a similar case for trees. ... > > though technically the existing code allows _missing_ trees, but > > not on corrupt ones. > > True, but the intention of these "do not care too much about missing > stuff while marking uninteresting" effort is aligned better with > ignoring corrupt ones, too, I would think, as "missing" in that > sentence is in fact about "not availble", and stuff that exists in > corrupt form is still not available anyway. So I do not think it > makes a bad change to start allowing corrupt ones. Agreed. Here it is in patch form, though as we both said, it probably doesn't matter that much in practice. So I'd be OK dropping it out of a sense of conservatism. -- >8 -- Subject: [PATCH] mark_tree_contents_uninteresting: drop has_object check It's generally acceptable for UNINTERESTING objects in a traversal to be unavailable (e.g., see aeeae1b771). When marking trees UNINTERESTING, we access the object database twice: once to check if the object is missing (and return quietly if it is), and then again to actually parse it. We can instead just try to parse; if that fails, we can then return quietly. That halves the effort we spend on locating the object. Note that this isn't _exactly_ the same as the original behavior, as the parse failure could be due to other problems than a missing object: it could be corrupted, in which case the original code would have died. But the new behavior is arguably better, as it covers the object being unavailable for any reason. We'll also still issue a warning to stderr in such a case. Signed-off-by: Jeff King --- revision.c | 5 + 1 file changed, 1 insertion(+), 4 deletions(-) diff --git a/revision.c b/revision.c index 5ce9b93baa..221d62c52b 100644 --- a/revision.c +++ b/revision.c @@ -51,12 +51,9 @@ static void mark_tree_contents_uninteresting(struct tree *tree) { struct tree_desc desc; struct name_entry entry; - struct object *obj = &tree->object; - if (!has_object_file(&obj->oid)) + if (parse_tree_gently(tree, 1) < 0) return; - if (parse_tree(tree) < 0) - die("bad tree %s", oid_to_hex(&obj->oid)); init_tree_desc(&desc, tree->buffer, tree->size); while (tree_entry(&desc, &entry)) { -- 2.16.2.582.ge2c16ac3c4
Re: [PATCH] revision.c: reduce object database queries
On 2/28/2018 1:37 AM, Jeff King wrote: On Tue, Feb 27, 2018 at 03:16:58PM -0800, Junio C Hamano wrote: This code comes originally form 454fbbcde3 (git-rev-list: allow missing objects when the parent is marked UNINTERESTING, 2005-07-10). But later, in aeeae1b771 (revision traversal: allow UNINTERESTING objects to be missing, 2009-01-27), we marked dealt with calling parse_object() on the parents more directly. So what I wonder is whether this code is simply redundant and can go away entirely. That would save the has_object_file() call in all cases. Hmm, interesting. I forgot all what I did around this area, but you are right. I'll leave it to Stolee whether he wants to dig into removing the has_object_file() call. I think it would do the right thing, but the most interesting bit would be how it impacts the timings. This patch was so small that I could understand the full implication of my change. I'm still very unfamiliar with the object walking machinery in revision.c. There are a lot of inter-dependencies that are taking time for me to understand and to feel confident that I won't cause a side effect in a special case. I do appreciate that Junio added a test in aeeae1b771. I'll make a note to revisit this area after I have a better grasp of the object walk code, but I will not try removing the has_object_file() call now. There's a similar case for trees. ... though technically the existing code allows _missing_ trees, but not on corrupt ones. True, but the intention of these "do not care too much about missing stuff while marking uninteresting" effort is aligned better with ignoring corrupt ones, too, I would think, as "missing" in that sentence is in fact about "not availble", and stuff that exists in corrupt form is still not available anyway. So I do not think it makes a bad change to start allowing corrupt ones. Agreed. Here it is in patch form, though as we both said, it probably doesn't matter that much in practice. So I'd be OK dropping it out of a sense of conservatism. -- >8 -- Subject: [PATCH] mark_tree_contents_uninteresting: drop has_object check It's generally acceptable for UNINTERESTING objects in a traversal to be unavailable (e.g., see aeeae1b771). When marking trees UNINTERESTING, we access the object database twice: once to check if the object is missing (and return quietly if it is), and then again to actually parse it. We can instead just try to parse; if that fails, we can then return quietly. That halves the effort we spend on locating the object. Note that this isn't _exactly_ the same as the original behavior, as the parse failure could be due to other problems than a missing object: it could be corrupted, in which case the original code would have died. But the new behavior is arguably better, as it covers the object being unavailable for any reason. We'll also still issue a warning to stderr in such a case. Signed-off-by: Jeff King --- revision.c | 5 + 1 file changed, 1 insertion(+), 4 deletions(-) diff --git a/revision.c b/revision.c index 5ce9b93baa..221d62c52b 100644 --- a/revision.c +++ b/revision.c @@ -51,12 +51,9 @@ static void mark_tree_contents_uninteresting(struct tree *tree) { struct tree_desc desc; struct name_entry entry; - struct object *obj = &tree->object; - if (!has_object_file(&obj->oid)) + if (parse_tree_gently(tree, 1) < 0) return; - if (parse_tree(tree) < 0) - die("bad tree %s", oid_to_hex(&obj->oid)); init_tree_desc(&desc, tree->buffer, tree->size); while (tree_entry(&desc, &entry)) {