{"thread":{"id":"31014","subject":"[PATCH] revision: avoid work after --max-count is reached","startedAt":"2012-07-13T07:50:23Z","lastAt":"2012-07-14T08:10:33Z","messageCount":6,"participants":["Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"194996","messageId":"20120713075023.GA31618@sigill.intra.peff.net","threadId":"31014","inReplyTo":null,"subject":"[PATCH] revision: avoid work after --max-count is reached","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-07-13T07:50:23Z","receivedAt":"2012-07-13T07:50:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"During a revision traversal in which --max-count has been\nspecified, we decrement a counter for each revision returned\nby get_revision. When it hits 0, we typically return NULL\n(the exception being if we still have boundary commits to\nshow).\n\nHowever, before we check the counter, we call get_revision_1\nto get the next commit. This might involve looking at a\nlarge number of commits if we have restricted the traversal\n(e.g., we might traverse until we find the next commit whose\ndiff actually matches a pathspec).\n\nThere's no need to make this get_revision_1 call when our\ncounter runs out. If we are not in --boundary mode, we will\njust throw away the result and immediately return NULL. If\nwe are in --boundary mode, then we will still throw away the\nresult, and then start showing the boundary commits.\nHowever, as git_revision_1 does not impact the boundary\nlist, it should not have an impact.\n\nIn most cases, avoiding this work will not be especially\nnoticeable. However, in some cases, it can make a big\ndifference:\n\n  [before]\n  $ time git rev-list -1 origin Documentation/RelNotes/1.7.11.2.txt\n  8d141a1d562abb31f27f599dbf6e10a6c06ed73e\n\n  real    0m0.301s\n  user    0m0.280s\n  sys     0m0.016s\n\n  [after]\n  $ time git rev-list -1 origin Documentation/RelNotes/1.7.11.2.txt\n  8d141a1d562abb31f27f599dbf6e10a6c06ed73e\n\n  real    0m0.010s\n  user    0m0.008s\n  sys     0m0.000s\n\nNote that the output is produced almost instantaneously in\nthe first case, and then git uselessly spends a long time\nlooking for the next commit to touch that file (but there\nisn't one, and we traverse all the way down to the roots).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nI'd really like more sets of eyes to make sure this won't\ncause a weird regression. Calling get_revision_1 does tweak\nthe flags on objects as it traverses, so I'm worried about\nsome other code relying on this side effect of get_revision\nin some way. That does seem a bit crazy to me, though.\n\n revision.c | 39 +++++++++++++++++++--------------------\n 1 file changed, 19 insertions(+), 20 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 5b81a92..7e39655 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2361,29 +2361,28 @@ static struct commit *get_revision_internal(struct rev_info *revs)\n \t}\n \n \t/*\n-\t * Now pick up what they want to give us\n+\t * If our max_count counter has reached zero, then we are done. We\n+\t * don't simply return NULL because we still might need to show\n+\t * boundary commits. But we want to avoid calling get_revision_1, which\n+\t * might do a considerable amount of work finding the next commit only\n+\t * for us to throw it away.\n+\t *\n+\t * If it is non-zero, then either we don't have a max_count at all\n+\t * (-1), or it is still counting, in which case we decrement.\n \t */\n-\tc = get_revision_1(revs);\n-\tif (c) {\n-\t\twhile (0 < revs->skip_count) {\n-\t\t\trevs->skip_count--;\n-\t\t\tc = get_revision_1(revs);\n-\t\t\tif (!c)\n-\t\t\t\tbreak;\n+\tif (revs->max_count) {\n+\t\tc = get_revision_1(revs);\n+\t\tif (c) {\n+\t\t\twhile (0 < revs->skip_count) {\n+\t\t\t\trevs->skip_count--;\n+\t\t\t\tc = get_revision_1(revs);\n+\t\t\t\tif (!c)\n+\t\t\t\t\tbreak;\n+\t\t\t}\n \t\t}\n-\t}\n \n-\t/*\n-\t * Check the max_count.\n-\t */\n-\tswitch (revs->max_count) {\n-\tcase -1:\n-\t\tbreak;\n-\tcase 0:\n-\t\tc = NULL;\n-\t\tbreak;\n-\tdefault:\n-\t\trevs->max_count--;\n+\t\tif (revs->max_count > 0)\n+\t\t\trevs->max_count--;\n \t}\n \n \tif (c)\n-- \n1.7.11.35.gbaf554e.dirty\n"},{"id":"194997","messageId":"20120713075326.GA32206@sigill.intra.peff.net","threadId":"31014","inReplyTo":"20120713075023.GA31618@sigill.intra.peff.net","subject":"Re: [PATCH] revision: avoid work after --max-count is reached","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-07-13T07:53:26Z","receivedAt":"2012-07-13T07:53:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jul 13, 2012 at 03:50:23AM -0400, Jeff King wrote:\n\n>  revision.c | 39 +++++++++++++++++++--------------------\n>  1 file changed, 19 insertions(+), 20 deletions(-)\n\nBTW, the patch is slightly hard to read because of the re-indentation.\nHere it is with \"-w -U5\":\n\ndiff --git a/revision.c b/revision.c\nindex 5b81a92..7e39655 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2359,32 +2359,31 @@ static struct commit *get_revision_internal(struct rev_info *revs)\n \t\t\tc->object.flags |= SHOWN;\n \t\treturn c;\n \t}\n \n \t/*\n-\t * Now pick up what they want to give us\n+\t * If our max_count counter has reached zero, then we are done. We\n+\t * don't simply return NULL because we still might need to show\n+\t * boundary commits. But we want to avoid calling get_revision_1, which\n+\t * might do a considerable amount of work finding the next commit only\n+\t * for us to throw it away.\n+\t *\n+\t * If it is non-zero, then either we don't have a max_count at all\n+\t * (-1), or it is still counting, in which case we decrement.\n \t */\n+\tif (revs->max_count) {\n \t\tc = get_revision_1(revs);\n \t\tif (c) {\n \t\t\twhile (0 < revs->skip_count) {\n \t\t\t\trevs->skip_count--;\n \t\t\t\tc = get_revision_1(revs);\n \t\t\t\tif (!c)\n \t\t\t\t\tbreak;\n \t\t\t}\n \t\t}\n \n-\t/*\n-\t * Check the max_count.\n-\t */\n-\tswitch (revs->max_count) {\n-\tcase -1:\n-\t\tbreak;\n-\tcase 0:\n-\t\tc = NULL;\n-\t\tbreak;\n-\tdefault:\n+\t\tif (revs->max_count > 0)\n \t\t\trevs->max_count--;\n \t}\n \n \tif (c)\n \t\tc->object.flags |= SHOWN;\n-- \n1.7.11.35.gbaf554e.dirty\n"},{"id":"195027","messageId":"7v7gu78izl.fsf@alter.siamese.dyndns.org","threadId":"31014","inReplyTo":"20120713075023.GA31618@sigill.intra.peff.net","subject":"Re: [PATCH] revision: avoid work after --max-count is reached","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-07-13T21:10:54Z","receivedAt":"2012-07-13T21:10:54Z","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> There's no need to make this get_revision_1 call when our\n> counter runs out. If we are not in --boundary mode, we will\n> just throw away the result and immediately return NULL. If\n> we are in --boundary mode, then we will still throw away the\n> result, and then start showing the boundary commits.\n>\n> However, as git_revision_1 does not impact the boundary\n> list, it should not have an impact.\n\nWe used to reset 'c' to NULL (\"throw away the result\"), run\ncreate_boundary_commit_list(), and ask ourselves to pop the boundary\nit computed.\n\nNow we don't call get_revision_1() and leave 'c' to NULL as\ninitialized (\"avoid work\"), and do the same.\n\nThe state create_boundary_commit_list() sees would slightly be\ndifferent, as we used to dig one level deeper, smudging more commits\nwith bits, but the only bits that may be smudged by this digging\nthat may matter in create_commit_list() is CHILD_SHOWN and SHOWN,\nbut by definition the commits around the commit the extra call to\nget_revision_1() would have returned are marked with neither during\nthat extra call, so I think this conversion does not affect the\nboundary list.\n\nSo I think I like this change.  If anything, it makes the loop\nstructure simpler and a bit easier to understand.\n"},{"id":"195028","messageId":"20120713212050.GB10767@sigill.intra.peff.net","threadId":"31014","inReplyTo":"7v7gu78izl.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] revision: avoid work after --max-count is reached","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-07-13T21:20:50Z","receivedAt":"2012-07-13T21:20:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jul 13, 2012 at 02:10:54PM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > There's no need to make this get_revision_1 call when our\n> > counter runs out. If we are not in --boundary mode, we will\n> > just throw away the result and immediately return NULL. If\n> > we are in --boundary mode, then we will still throw away the\n> > result, and then start showing the boundary commits.\n> >\n> > However, as git_revision_1 does not impact the boundary\n> > list, it should not have an impact.\n> \n> We used to reset 'c' to NULL (\"throw away the result\"), run\n> create_boundary_commit_list(), and ask ourselves to pop the boundary\n> it computed.\n> \n> Now we don't call get_revision_1() and leave 'c' to NULL as\n> initialized (\"avoid work\"), and do the same.\n\nRight.\n\n> The state create_boundary_commit_list() sees would slightly be\n> different, as we used to dig one level deeper, smudging more commits\n> with bits, but the only bits that may be smudged by this digging\n> that may matter in create_commit_list() is CHILD_SHOWN and SHOWN,\n> but by definition the commits around the commit the extra call to\n> get_revision_1() would have returned are marked with neither during\n> that extra call, so I think this conversion does not affect the\n> boundary list.\n\nYeah, this was my analysis, too. Though reading get_revision-1, it seems\nlike we can actually set SHOWN, but I wasn't able to trigger any change\nof behavior in practice. I think it is because we must set both SHOWN\nand BOUNDARY to have an effect, and we do not do so.\n\nSo the only questionable thing would be: are there commits with BOUNDARY\nset but not SHOWN that could be affected by calling get_revision_1? For\nthat matter, if such a commit existed, would the current behavior even\nbe correct? We would not have actually shown the commit, so if such a\ncase did exist, I wonder if we would be fixing a bug.\n\n-Peff\n"},{"id":"195029","messageId":"7vwr2771k0.fsf@alter.siamese.dyndns.org","threadId":"31014","inReplyTo":"20120713212050.GB10767@sigill.intra.peff.net","subject":"Re: [PATCH] revision: avoid work after --max-count is reached","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-07-13T22:12:47Z","receivedAt":"2012-07-13T22:12:47Z","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> Yeah, this was my analysis, too. Though reading get_revision-1, it seems\n> like we can actually set SHOWN, but I wasn't able to trigger any change\n> of behavior in practice. I think it is because we must set both SHOWN\n> and BOUNDARY to have an effect, and we do not do so.\n\nIn principle, SHOWN is only given when get_revision_internal gives\nthe commit back to be shown, and the parents of the returned commit\nare painted CHILD_SHOWN.  This should be the only place to paint\ncommit as CHILD_SHOWN.\n\nA handful of places set the bit to commits that would be shown if\nsome options that further limit what is shown by topological\nproperty (e.g. --left-only, --cherry-pick), which may cause that a\nparent of a commit that was omitted due to these conditions may\nlater be marked incorrectly as a boundary inside\ncreate_boundary_commit_list().\n\nBOUNDARY is only given in create_boundary_commit_list() using\nCHILD_SHOWN and SHOWN, and that should happen only once when\nget_revision_1() runs out of the commits.\n\nBy the way, cherry_pick_list() pays attention to BOUNDARY, but I\nthink it is written overly defensively to protect itself from future\ncallsites.  With the current code structure, it is only called from\nlimit_list() and get_revision_*() functions are never called until\nlimit_list() returns (and again create_boundary_commit_list() that\nis called from get_revision_internal() is the only place that sets\nBOUNDARY, so the commits cherry_pick_list() sees would never have\nthat bit set.\n\n> So the only questionable thing would be: are there commits with BOUNDARY\n> set but not SHOWN that could be affected by calling get_revision_1? For\n> that matter, if such a commit existed, would the current behavior even\n> be correct? We would not have actually shown the commit, so if such a\n> case did exist, I wonder if we would be fixing a bug.\n"},{"id":"195039","messageId":"20120714081033.GA32547@sigill.intra.peff.net","threadId":"31014","inReplyTo":"7vwr2771k0.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] revision: avoid work after --max-count is reached","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-07-14T08:10:33Z","receivedAt":"2012-07-14T08:10:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jul 13, 2012 at 03:12:47PM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > Yeah, this was my analysis, too. Though reading get_revision-1, it seems\n> > like we can actually set SHOWN, but I wasn't able to trigger any change\n> > of behavior in practice. I think it is because we must set both SHOWN\n> > and BOUNDARY to have an effect, and we do not do so.\n> \n> In principle, SHOWN is only given when get_revision_internal gives\n> the commit back to be shown, and the parents of the returned commit\n> are painted CHILD_SHOWN.  This should be the only place to paint\n> commit as CHILD_SHOWN.\n> \n> A handful of places set the bit to commits that would be shown if\n> some options that further limit what is shown by topological\n> property (e.g. --left-only, --cherry-pick), which may cause that a\n> parent of a commit that was omitted due to these conditions may\n> later be marked incorrectly as a boundary inside\n> create_boundary_commit_list().\n\nI think what confused me is that I thought I saw get_revision_1 setting\nSHOWN in the reflog case. But of course it is _clearing_ the flag, since\nthe reflog walker may show the commit multiple times. And no other code\npaths in get_revision_1 set it (nor should they, since as you say, it is\nabout us actually handing back the commit to be shown).\n\n> BOUNDARY is only given in create_boundary_commit_list() using\n> CHILD_SHOWN and SHOWN, and that should happen only once when\n> get_revision_1() runs out of the commits.\n\nYeah, agreed.\n\n> By the way, cherry_pick_list() pays attention to BOUNDARY, but I\n> think it is written overly defensively to protect itself from future\n> callsites.  With the current code structure, it is only called from\n> limit_list() and get_revision_*() functions are never called until\n> limit_list() returns (and again create_boundary_commit_list() that\n> is called from get_revision_internal() is the only place that sets\n> BOUNDARY, so the commits cherry_pick_list() sees would never have\n> that bit set.\n\nI think we wouldn't be impacting it even so, because the commits that\nmake it to create_boundary_commit_list (and therefore get marked with\nBOUNDARY) should be identical. We only put items into the\nboundary_commits list when we are about to return them from\nget_revision_internal, and with my patch that will not change (because\nprior to my patch, we would have thrown away the commit after checking\nmax_count anyway).\n\nSo I think after looking again that this change is the right\nthing to do, and there shouldn't be any side effects. Thanks for the\ncareful review.\n\n-Peff\n"}]}