{"thread":{"id":"42921","subject":"[PATCH 0/2] speed up \"Counting objects\" when there are many packs","startedAt":"2016-07-25T18:49:45Z","lastAt":"2016-07-27T22:04:49Z","messageCount":13,"participants":["Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"292117","messageId":"20160725184938.GA12871@sigill.intra.peff.net","threadId":"42921","inReplyTo":null,"subject":"[PATCH 0/2] speed up \"Counting objects\" when there are many packs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-25T18:49:38Z","receivedAt":"2016-07-25T18:49:45Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We sometimes see cases at GitHub where repository maintenance has fallen\nbehind, and you get a large number of packs. The solution is to repack,\nbut that process is itself made a lot slower by the number of packs.\n\nWe've experimented a bit with fast \"just cat all the packfiles together\"\ntype approaches, but they have some downsides, so I have nothing to show\nthere yet.\n\nHowever, there are a few easy optimizations we can do to cut out some\nunnecessary computation in common cases (e.g., when you have no .keep\nfiles and when you have no upstream alternates storage). Both of these\npatches have been in production at GitHub for about 6 months.\n\n [1/2]: pack-objects: break out of want_object loop early\n [2/2]: pack-objects: compute local/ignore_pack_keep early\n\n-Peff\n"},{"id":"292118","messageId":"20160725185010.GA12974@sigill.intra.peff.net","threadId":"42921","inReplyTo":"20160725184938.GA12871@sigill.intra.peff.net","subject":"[PATCH 1/2] pack-objects: break out of want_object loop early","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-25T18:50:10Z","receivedAt":"2016-07-25T18:50:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When pack-objects collects the list of objects to pack\n(either from stdin, or via its internal rev-list), it\nfilters each one through want_object_in_pack().\n\nThis function loops through each existing packfile, looking\nfor the object. When we find it, we mark the pack/offset\ncombo for later use. However, we can't just return \"yes, we\nwant it\" at that point. If --honor-pack-keep is in effect,\nwe must keep looking to find it in _all_ packs, to make sure\nnone of them has a .keep. Likewise, if --local is in effect,\nwe must make sure it is not present in any local pack.\n\nAs a result, the sum effort of these calls is effectively\nO(nr_objects * nr_packs). In an ordinary repository, we have\nonly a handful of packs, and this doesn't make a big\ndifference. But in pathological cases, it can slow the\ncounting phase to a crawl.\n\nThis patch notices the case that we have neither \"--local\"\nnor \"--honor-pack-keep\" in effect and breaks out of the loop\nearly, after finding the first instance. Note that our worst\ncase is still \"objects * packs\" (i.e., we might find each\nobject in the last pack we look in), but in practice we will\noften break out early. On an \"average\" repo, my git.git with\n8 packs, this shows a modest 2% (a few dozen milliseconds)\nimprovement in the counting-objects phase of \"git\npack-objects --all \n---\n builtin/pack-objects.c | 2 ++\n 1 file changed, 2 insertions(+)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex a2f8cfd..55ef5a8 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -981,6 +981,8 @@ static int want_object_in_pack(const unsigned char *sha1,\n \t\t\t\treturn 0;\n \t\t\tif (ignore_packed_keep && p->pack_local && p->pack_keep)\n \t\t\t\treturn 0;\n+\t\t\tif (!ignore_packed_keep && !local)\n+\t\t\t\tbreak;\n \t\t}\n \t}\n \n-- \n2.9.2.512.g8a06708\n\n"},{"id":"292119","messageId":"20160725185031.GB12974@sigill.intra.peff.net","threadId":"42921","inReplyTo":"20160725184938.GA12871@sigill.intra.peff.net","subject":"[PATCH 2/2] pack-objects: compute local/ignore_pack_keep early","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-25T18:50:31Z","receivedAt":"2016-07-25T18:50:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"In want_object_in_pack(), we can exit early from our loop if\nneither \"local\" nor \"ignore_pack_keep\" are set. If they are,\nhowever, we must examine each pack to see if it has the\nobject and is non-local or has a \".keep\".\n\nIt's quite common for there to be no non-local or .keep\npacks at all, in which case we know ahead of time that\nlooking further will be pointless. We can pre-compute this\nby simply iterating over the list of packs ahead of time,\nand dropping the flags if there are no packs that could\nmatch.\n\nAnother similar strategy would be to modify the loop in\nwant_object_in_pack() to notice that we have already found\nthe object once, and that we are looping only to check for\n\"local\" and \"keep\" attributes. If a pack has neither of\nthose, we can skip the call to find_pack_entry_one(), which\nis the expensive part of the loop.\n\nThis has two advantages:\n\n - it isn't all-or-nothing; we still get some improvement\n when there's a small number of kept or non-local packs,\n and a large number of non-kept local packs\n\n - it eliminates any possible race where we add new\n non-local or kept packs after our initial scan. In\n practice, I don't think this race matters; we already\n cache the packed_git information, so somebody who adds a\n new pack or .keep file after we've started will not be\n noticed at all, unless we happen to need to call\n reprepare_packed_git() because a lookup fails.\n\n In other words, we're already racy, and the race is not\n a big deal (losing the race means we might include an\n object in the pack that would not otherwise be, which is\n an acceptable outcome).\n\nHowever, it also has a disadvantage: we still loop over the\nrest of the packs for each object to check their flags. This\nis much less expensive than doing the object lookup, but\nstill not free. So if we wanted to implement that strategy\nto cover the non-all-or-nothing cases, we could do so in\naddition to this one (so you get the most speedup in the\nall-or-nothing case, and the best we can do in the other\ncases). But given that the all-or-nothing case is likely the\nmost common, it is probably not worth the trouble, and we\ncan revisit this later if evidence points otherwise.\n\nSigned-off-by: Jeff King \n---\n builtin/pack-objects.c | 25 ++++++++++++++++++++++++-\n 1 file changed, 24 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 55ef5a8..c5e343c 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -46,6 +46,7 @@ static int keep_unreachable, unpack_unreachable, include_tag;\n static unsigned long unpack_unreachable_expiration;\n static int pack_loose_unreachable;\n static int local;\n+static int have_non_local_packs;\n static int incremental;\n static int ignore_packed_keep;\n static int allow_ofs_delta;\n@@ -981,7 +982,7 @@ static int want_object_in_pack(const unsigned char *sha1,\n \t\t\t\treturn 0;\n \t\t\tif (ignore_packed_keep && p->pack_local && p->pack_keep)\n \t\t\t\treturn 0;\n-\t\t\tif (!ignore_packed_keep && !local)\n+\t\t\tif (!ignore_packed_keep && (!local || !have_non_local_packs))\n \t\t\t\tbreak;\n \t\t}\n \t}\n@@ -2785,6 +2786,28 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\tprogress = 2;\n \n \tprepare_packed_git();\n+\tif (ignore_packed_keep) {\n+\t\tstruct packed_git *p;\n+\t\tfor (p = packed_git; p; p = p->next)\n+\t\t\tif (p->pack_local && p->pack_keep)\n+\t\t\t\tbreak;\n+\t\tif (!p) /* no keep-able packs found */\n+\t\t\tignore_packed_keep = 0;\n+\t}\n+\tif (local) {\n+\t\t/*\n+\t\t * unlike ignore_packed_keep above, we do not want to\n+\t\t * unset \"local\" based on looking at packs, as it\n+\t\t * also covers non-local objects\n+\t\t */\n+\t\tstruct packed_git *p;\n+\t\tfor (p = packed_git; p; p = p->next) {\n+\t\t\tif (!p->pack_local) {\n+\t\t\t\thave_non_local_packs = 1;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\t}\n \n \tif (progress)\n \t\tprogress_state = start_progress(_(\"Counting objects\"), 0);\n-- \n2.9.2.512.g8a06708\n"},{"id":"292131","messageId":"xmqqeg6h5w60.fsf@gitster.mtv.corp.google.com","threadId":"42921","inReplyTo":"20160725185010.GA12974@sigill.intra.peff.net","subject":"Re: [PATCH 1/2] pack-objects: break out of want_object loop early","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-25T19:56:23Z","receivedAt":"2016-07-25T19:56:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> When pack-objects collects the list of objects to pack\n> (either from stdin, or via its internal rev-list), it\n> filters each one through want_object_in_pack().\n>\n> This function loops through each existing packfile, looking\n> for the object. When we find it, we mark the pack/offset\n> combo for later use. However, we can't just return \"yes, we\n> want it\" at that point. If --honor-pack-keep is in effect,\n> we must keep looking to find it in _all_ packs, to make sure\n> none of them has a .keep. Likewise, if --local is in effect,\n> we must make sure it is not present in any local pack.\n\ns/any local pack/any non-local pack/, no?\n\n> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n> index a2f8cfd..55ef5a8 100644\n> --- a/builtin/pack-objects.c\n> +++ b/builtin/pack-objects.c\n> @@ -981,6 +981,8 @@ static int want_object_in_pack(const unsigned char *sha1,\n> \t\t\t\treturn 0;\n> \t\t\tif (ignore_packed_keep && p->pack_local && p->pack_keep)\n> \t\t\t\treturn 0;\n> +\t\t\tif (!ignore_packed_keep && !local)\n> +\t\t\t\tbreak;\n> \t\t}\n> \t}\n\nOK, so in this loop, we may return \"false\" (meaning, we do not want\nto pack the object) if \"local\" (do not pack objects that appear in\nnon-local packs) or \"ignore_packed_keep\" (do not pack objects that\nappear in locally kept packs) are in effect, but if neither of the\noptions is set, we know that one of the preconditions (\"local\" or\n\"ignore_packed_keep\") for these two \"reject by returning false\" if\nstatements would never trigger for any pack on packed_git list, so\nit is safe to break out and return the one that we have found.\n\nIf that is what is going on, I would have expected to see this early\nbreak before these \"we found that this is available in borrowed pack\nand we are only packing local\" and \"we ignore objects in locally\nkept packs\" checks return false.\n\nOr am I not following the logic in the loop correctly?\n"},{"id":"292147","messageId":"xmqqbn1l4c87.fsf@gitster.mtv.corp.google.com","threadId":"42921","inReplyTo":"20160725214113.GA13589@sigill.intra.peff.net","subject":"Re: [PATCH 1/2] pack-objects: break out of want_object loop early","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-25T21:52:24Z","receivedAt":"2016-07-25T21:52:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> if (!*found_pack) {\n> ... first find! fill in found pack, etc ...\n> }\n> if (exclude)\n> \treturn 1;\n> if (incremental)\n> \treturn 0;\n> if (!ignore_packed_keep && !local)\n> \tbreak; /* effectively return 1, but I think the break is more clear */\n> if (local && !p->pack_local)\n> \treturn 0;\n> if (ignore_packed_keep && p->pack_local && p->pack_keep)\n> \treturn 0;\n>\n> which just bumps it up. I don't think there is a way to make it more\n> elegant, e.g., by only checking ignore_packed_keep once, because we have\n> to distinguish between each condition being set independently, or the\n> case where neither is set.\n>\n> So I stuck the new check at the end, because to me logically it was \"can\n> we break out of the loop instead of looking at p->next\". But I agree it\n> would be equivalent to place it before the related checks, and I don't\n> mind doing that if you think it's more readable.\n\nI do not mind too much about having to check two bools twice. But\ngiven that the reason why I was confused was because I didn't see\nwhy we need to pass the two \"return 0\" conditions at least once\nbefore we decide that we do not need the \"return 0\" thing at all,\nand started constructing a case where this might break by writing\n\"Suppose you have two packs, one remote and one local in packed_git\nlist in this order, and ...\" before I realized that the new \"early\nbreak\" can be hoisted up like the above, I definitely feel that \"we\nfound one, and we aren't conditionally pretending that this thing\ndoes not need to be packed at all, so return early and say we want\nto pack it\" is easier to understand before the two existing \"if\"\nstatements.\n\nThanks.\n"},{"id":"292153","messageId":"20160725214113.GA13589@sigill.intra.peff.net","threadId":"42921","inReplyTo":"xmqqeg6h5w60.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 1/2] pack-objects: break out of want_object loop early","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-25T21:41:13Z","receivedAt":"2016-07-25T22:10:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 25, 2016 at 12:56:23PM -0700, Junio C Hamano wrote:\n\n> > This function loops through each existing packfile, looking\n> > for the object. When we find it, we mark the pack/offset\n> > combo for later use. However, we can't just return \"yes, we\n> > want it\" at that point. If --honor-pack-keep is in effect,\n> > we must keep looking to find it in _all_ packs, to make sure\n> > none of them has a .keep. Likewise, if --local is in effect,\n> > we must make sure it is not present in any local pack.\n> \n> s/any local pack/any non-local pack/, no?\n\nOops, yeah.\n\n> > diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n> > index a2f8cfd..55ef5a8 100644\n> > --- a/builtin/pack-objects.c\n> > +++ b/builtin/pack-objects.c\n> > @@ -981,6 +981,8 @@ static int want_object_in_pack(const unsigned char *sha1,\n> > \t\t\t\treturn 0;\n> > \t\t\tif (ignore_packed_keep && p->pack_local && p->pack_keep)\n> > \t\t\t\treturn 0;\n> > +\t\t\tif (!ignore_packed_keep && !local)\n> > +\t\t\t\tbreak;\n> > \t\t}\n> > \t}\n> \n> OK, so in this loop, we may return \"false\" (meaning, we do not want\n> to pack the object) if \"local\" (do not pack objects that appear in\n> non-local packs) or \"ignore_packed_keep\" (do not pack objects that\n> appear in locally kept packs) are in effect, but if neither of the\n> options is set, we know that one of the preconditions (\"local\" or\n> \"ignore_packed_keep\") for these two \"reject by returning false\" if\n> statements would never trigger for any pack on packed_git list, so\n> it is safe to break out and return the one that we have found.\n\nCorrect.\n\n> If that is what is going on, I would have expected to see this early\n> break before these \"we found that this is available in borrowed pack\n> and we are only packing local\" and \"we ignore objects in locally\n> kept packs\" checks return false.\n> \n> Or am I not following the logic in the loop correctly?\n\nYeah, I think that would work. It has to come after \"did we find this in\nthe pack\", obviously. And it has to come after the other unrelated\nchecks (\"are we just finding it to exclude?\" and \"are we\nincremental?\"). But you could do:\n\n if (!*found_pack) {\n ... first find! fill in found pack, etc ...\n }\n if (exclude)\n\treturn 1;\n if (incremental)\n\treturn 0;\n if (!ignore_packed_keep && !local)\n\tbreak; /* effectively return 1, but I think the break is more clear */\n if (local && !p->pack_local)\n\treturn 0;\n if (ignore_packed_keep && p->pack_local && p->pack_keep)\n\treturn 0;\n\nwhich just bumps it up. I don't think there is a way to make it more\nelegant, e.g., by only checking ignore_packed_keep once, because we have\nto distinguish between each condition being set independently, or the\ncase where neither is set.\n\nSo I stuck the new check at the end, because to me logically it was \"can\nwe break out of the loop instead of looking at p->next\". But I agree it\nwould be equivalent to place it before the related checks, and I don't\nmind doing that if you think it's more readable.\n\n-Peff\n"},{"id":"292155","messageId":"20160725221411.GA14131@sigill.intra.peff.net","threadId":"42921","inReplyTo":"xmqqbn1l4c87.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 1/2] pack-objects: break out of want_object loop early","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-25T22:14:11Z","receivedAt":"2016-07-25T22:14:22Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 25, 2016 at 02:52:24PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > if (!*found_pack) {\n> > ... first find! fill in found pack, etc ...\n> > }\n> > if (exclude)\n> > \treturn 1;\n> > if (incremental)\n> > \treturn 0;\n> > if (!ignore_packed_keep && !local)\n> > \tbreak; /* effectively return 1, but I think the break is more clear */\n> > if (local && !p->pack_local)\n> > \treturn 0;\n> > if (ignore_packed_keep && p->pack_local && p->pack_keep)\n> > \treturn 0;\n> >\n> > which just bumps it up. I don't think there is a way to make it more\n> > elegant, e.g., by only checking ignore_packed_keep once, because we have\n> > to distinguish between each condition being set independently, or the\n> > case where neither is set.\n> >\n> > So I stuck the new check at the end, because to me logically it was \"can\n> > we break out of the loop instead of looking at p->next\". But I agree it\n> > would be equivalent to place it before the related checks, and I don't\n> > mind doing that if you think it's more readable.\n> \n> I do not mind too much about having to check two bools twice. But\n> given that the reason why I was confused was because I didn't see\n> why we need to pass the two \"return 0\" conditions at least once\n> before we decide that we do not need the \"return 0\" thing at all,\n> and started constructing a case where this might break by writing\n> \"Suppose you have two packs, one remote and one local in packed_git\n> list in this order, and ...\" before I realized that the new \"early\n> break\" can be hoisted up like the above, I definitely feel that \"we\n> found one, and we aren't conditionally pretending that this thing\n> does not need to be packed at all, so return early and say we want\n> to pack it\" is easier to understand before the two existing \"if\"\n> statements.\n\nAh, right. Now you had me second-guessing for a moment that there might\nbe a bad case in hoisting it up where we would want to return 0 but\nwould break out early to the \"return 1\".\n\nBut it cannot be the case, because the break is mutually exclusive with\nthe two conditions.\n\n-Peff\n"},{"id":"292259","messageId":"xmqqshuwyw14.fsf@gitster.mtv.corp.google.com","threadId":"42921","inReplyTo":"20160725221411.GA14131@sigill.intra.peff.net","subject":"Re: [PATCH 1/2] pack-objects: break out of want_object loop early","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-26T20:38:47Z","receivedAt":"2016-07-26T20:40:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n>> I do not mind too much about having to check two bools twice. But\n>> given that the reason why I was confused was because I didn't see\n>> why we need to pass the two \"return 0\" conditions at least once\n>> before we decide that we do not need the \"return 0\" thing at all,\n>> and started constructing a case where this might break by writing\n>> \"Suppose you have two packs, one remote and one local in packed_git\n>> list in this order, and ...\" before I realized that the new \"early\n>> break\" can be hoisted up like the above, I definitely feel that \"we\n>> found one, and we aren't conditionally pretending that this thing\n>> does not need to be packed at all, so return early and say we want\n>> to pack it\" is easier to understand before the two existing \"if\"\n>> statements.\n>\n> Ah, right. Now you had me second-guessing for a moment that there might\n> be a bad case in hoisting it up where we would want to return 0 but\n> would break out early to the \"return 1\".\n>\n> But it cannot be the case, because the break is mutually exclusive with\n> the two conditions.\n\nHere is what I amended looks like (with s/local/non-local/ in the\nlog message).\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex a2f8cfd..a46bf5b 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -977,6 +977,21 @@ static int want_object_in_pack(const unsigned char *sha1,\n \t\t\t\treturn 1;\n \t\t\tif (incremental)\n \t\t\t\treturn 0;\n+\n+\t\t\t/*\n+\t\t\t * When asked to do --local (do not include an\n+\t\t\t * object that appears in a pack we borrow\n+\t\t\t * from elsewhere) or --honor-pack-keep (do not\n+\t\t\t * include an object that appears in a pack marked\n+\t\t\t * with .keep), we need to make sure no copy of this\n+\t\t\t * object come from in _any_ pack that causes us to\n+\t\t\t * omit it, and need to complete this loop. When\n+\t\t\t * neither option is in effect, we know the object\n+\t\t\t * we just found is going to be packed, so break\n+\t\t\t * out of the loop to return 1 now.\n+\t\t\t */\n+\t\t\tif (!ignore_packed_keep && !local)\n+\t\t\t\tbreak;\n \t\t\tif (local && !p->pack_local)\n \t\t\t\treturn 0;\n \t\t\tif (ignore_packed_keep && p->pack_local && p->pack_keep)\n"},{"id":"292268","messageId":"20160726204851.GA22353@sigill.intra.peff.net","threadId":"42921","inReplyTo":"xmqqshuwyw14.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 1/2] pack-objects: break out of want_object loop early","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-26T20:48:51Z","receivedAt":"2016-07-26T20:48:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 26, 2016 at 01:38:47PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> >> I do not mind too much about having to check two bools twice. But\n> >> given that the reason why I was confused was because I didn't see\n> >> why we need to pass the two \"return 0\" conditions at least once\n> >> before we decide that we do not need the \"return 0\" thing at all,\n> >> and started constructing a case where this might break by writing\n> >> \"Suppose you have two packs, one remote and one local in packed_git\n> >> list in this order, and ...\" before I realized that the new \"early\n> >> break\" can be hoisted up like the above, I definitely feel that \"we\n> >> found one, and we aren't conditionally pretending that this thing\n> >> does not need to be packed at all, so return early and say we want\n> >> to pack it\" is easier to understand before the two existing \"if\"\n> >> statements.\n> >\n> > Ah, right. Now you had me second-guessing for a moment that there might\n> > be a bad case in hoisting it up where we would want to return 0 but\n> > would break out early to the \"return 1\".\n> >\n> > But it cannot be the case, because the break is mutually exclusive with\n> > the two conditions.\n> \n> Here is what I amended looks like (with s/local/non-local/ in the\n> log message).\n\nThanks, I was actually just preparing a very similar patch (to move the\ncondition and to add a comment, since clearly it is tricky).\n\nI got side-tracked by adding a t/perf test to show off the improvement.\nIt's rather tricky to get right and takes a long time to run. I _think_\nI have it now, but am waiting for results. :)\n\n> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n> index a2f8cfd..a46bf5b 100644\n> --- a/builtin/pack-objects.c\n> +++ b/builtin/pack-objects.c\n> @@ -977,6 +977,21 @@ static int want_object_in_pack(const unsigned char *sha1,\n> \t\t\t\treturn 1;\n> \t\t\tif (incremental)\n> \t\t\t\treturn 0;\n> +\n> +\t\t\t/*\n> +\t\t\t * When asked to do --local (do not include an\n> +\t\t\t * object that appears in a pack we borrow\n> +\t\t\t * from elsewhere) or --honor-pack-keep (do not\n> +\t\t\t * include an object that appears in a pack marked\n> +\t\t\t * with .keep), we need to make sure no copy of this\n> +\t\t\t * object come from in _any_ pack that causes us to\n> +\t\t\t * omit it, and need to complete this loop. When\n> +\t\t\t * neither option is in effect, we know the object\n> +\t\t\t * we just found is going to be packed, so break\n> +\t\t\t * out of the loop to return 1 now.\n> +\t\t\t */\n> +\t\t\tif (!ignore_packed_keep && !local)\n> +\t\t\t\tbreak;\n\nThis looks great. Given the explanation in the comment, it might be more\nclear to switch the break to \"return 1\", but I could go either way.\n\n-Peff\n"},{"id":"292284","messageId":"xmqqr3agxep7.fsf@gitster.mtv.corp.google.com","threadId":"42921","inReplyTo":"20160726204851.GA22353@sigill.intra.peff.net","subject":"Re: [PATCH 1/2] pack-objects: break out of want_object loop early","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-26T21:38:28Z","receivedAt":"2016-07-26T21:40:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I got side-tracked by adding a t/perf test to show off the improvement.\n> It's rather tricky to get right and takes a long time to run. I _think_\n> I have it now, but am waiting for results. :)\n\nWell, then I'd stop here and wait for the reroll to requeue.\n\nThanks.\n\n"},{"id":"292372","messageId":"20160727211338.GA20608@sigill.intra.peff.net","threadId":"42921","inReplyTo":"xmqqr3agxep7.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 1/2] pack-objects: break out of want_object loop early","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-27T21:13:38Z","receivedAt":"2016-07-27T21:13:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 26, 2016 at 02:38:28PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > I got side-tracked by adding a t/perf test to show off the improvement.\n> > It's rather tricky to get right and takes a long time to run. I _think_\n> > I have it now, but am waiting for results. :)\n> \n> Well, then I'd stop here and wait for the reroll to requeue.\n\nSo I hoped to follow up with my little perf-testing patch last night,\nbut the rabbit hole goes deeper. :)\n\nIt turns out that I could not replicate my earlier results using a perf\nscript like the one below. The problem is that it heavily depends on the\nordering of your packs. The early-break does not do any good if you\nmostly end up finding your objects in the final pack in the list. And\nthat is the exact situation my perf script creates: imagine you had a\nbig repository, then 1000 pushes came in, and then you tried to run \"git\nrepack\". We sort reverse-chronologically, so the big pack is at the end,\nand most lookups have to go through the entire pack list to get there.\n\nIn the normal object-lookup paths, we cache the last_found_pack and\ncheck it first, but this loop has no equivalent (and until now it\nwouldn't have helped much, because we generally had to walk the whole\nlist anyway).\n\nI knew this was a potential issue and even had experimented this back\nwhen the original patches were written, but in my experiments then it\ndidn't help much. That makes sense, though; any case that _was_ improved\nby the first two patches would not benefit from reordering the pack\nlookups, because that meant it was finding the objects early in the\nsearch (or else the first two patches would have helped not at all).\n\nAnd I think the particular case I was experimenting on back then was not\na normal \"oops, we had some pushes and forgot to run gc\". It was more\nbizarre, and had several packs that had most of the objects duplicated.\n\nSo I think this is an area worth looking into; a series of small\nincremental packs on top of a large one is what I would expect to be\nthe most common case, and the first two patches don't handle it well.\n\nI tried a hacky version of the last_found_pack trick, and it does cut\nthe counting phase in half for my perf test. But no patch yet. One is\njust that doing it cleanly is a little tricky. But two is that I've\nwondered if we can do even better with a most-recently-used cache\ninstead of the last_pack_found hack. So I'm trying to implement and\nmeasure that (both for this loop, and to see if it does better in\nfind_pack_entry).\n\nPerf script below is just for a sneak peek at what I'm trying to\nmeasure.\n\n-Peff\n\n-- >8 --\n#!/bin/sh\n\ntest_description='performance with large numbers of packs'\n. ./perf-lib.sh\n\ntest_perf_large_repo\n\n# Pretend we just have a single branch and no reflogs, and that everything is\n# in objects/pack; that makes our fake pack-building in the next step much\n# simpler.\ntest_expect_success 'simplify reachability' '\n\ttip=$(git rev-parse --verify HEAD) &&\n\tgit for-each-ref --format=\"option no-deref%0adelete %(refname)\" |\n\tgit update-ref --stdin &&\n\trm -rf .git/logs &&\n\tgit update-ref refs/heads/master $tip &&\n\tgit symbolic-ref HEAD refs/heads/master &&\n\tgit repack -ad\n'\n\n# A real many-pack situation would probably come from having a lot of pushes\n# over time. We don't know how big each push would be, but we can fake it by\n# just walking the first-parent chain and having each commit be its own \"push\".\n# This isn't _entirely_ accurate, as real pushes would have some duplicate\n# objects due to thin-pack fixing, but it's a reasonable approximation.\n#\n# And then all of the rest of the objects can go in a single packfile that\n# represents the state before any of those pushes (actually, we'll generate\n# that first because in such a setup it would be the oldest pack, and we sort\n# the packs by reverse mtime inside git).\n#\n# We prepare this in a staging area, because we need to install our baseline\n# set of packs for each iteration of the perf test (which unfortunately counts\n# against their times, but is a limitation of the perf framework).\ntest_expect_success 'create a large number of packs' '\n\tmkdir staging &&\n\n\tpushes() {\n\t\tgit rev-list --first-parent -1000 HEAD\n\t} &&\n\tpack() {\n\t\tgit pack-objects --revs --delta-base-offset staging/pack\n\t} &&\n\n\tbottom=$(pushes | tail -n 1) &&\n\techo \"$bottom^\" | pack &&\n\n\tpushes |\n\twhile read rev\n\tdo\n\t\tprintf \"%s\\n^%s^\" $rev $rev | pack ||\n\t\t\treturn 1\n\tdone &&\n\n\tsetup_many_packs () {\n\t\trm -f .git/objects/pack/* &&\n\t\tcp staging/* .git/objects/pack/\n\t} &&\n\tsetup_many_packs\n'\n\ntest_perf 'rev-list' '\n\tgit rev-list --objects --all\n'\n\ntest_perf 'full repack' '\n\tsetup_many_packs &&\n\tgit repack -ad\n'\n\ntest_done\n"},{"id":"292373","messageId":"CAPc5daWjNBazzVrH3jdgur2wC19upjM9A_pWp-u=tPUM_qaK0Q@mail.gmail.com","threadId":"42921","inReplyTo":"20160727211338.GA20608@sigill.intra.peff.net","subject":"Re: [PATCH 1/2] pack-objects: break out of want_object loop early","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-27T21:28:32Z","receivedAt":"2016-07-27T21:29:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"On Wed, Jul 27, 2016 at 2:13 PM, Jeff King wrote:\n> ... But two is that I've\n> wondered if we can do even better with a most-recently-used cache\n> instead of the last_pack_found hack. So I'm trying to implement and\n> measure that (both for this loop, and to see if it does better in\n> find_pack_entry).\n\nIt is always delightful to hear a well constructed description of a\nthought process. Thanks.\n\nOne thing that made me wonder was what would happen to the\nlast_found that is static to has_sha1_pack_kept_or_nonlocal()\nfunciton, when we invalidate the packed_git list, but within the\ncontext of pack-objects it is not likely?\n"},{"id":"292376","messageId":"20160727220437.GA2792@sigill.intra.peff.net","threadId":"42921","inReplyTo":"CAPc5daWjNBazzVrH3jdgur2wC19upjM9A_pWp-u=tPUM_qaK0Q@mail.gmail.com","subject":"Re: [PATCH 1/2] pack-objects: break out of want_object loop early","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-27T22:04:38Z","receivedAt":"2016-07-27T22:04:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 27, 2016 at 02:28:32PM -0700, Junio C Hamano wrote:\n\n> On Wed, Jul 27, 2016 at 2:13 PM, Jeff King wrote:\n> > ... But two is that I've\n> > wondered if we can do even better with a most-recently-used cache\n> > instead of the last_pack_found hack. So I'm trying to implement and\n> > measure that (both for this loop, and to see if it does better in\n> > find_pack_entry).\n> \n> It is always delightful to hear a well constructed description of a\n> thought process. Thanks.\n> \n> One thing that made me wonder was what would happen to the\n> last_found that is static to has_sha1_pack_kept_or_nonlocal()\n> funciton, when we invalidate the packed_git list, but within the\n> context of pack-objects it is not likely?\n\nI wondered that, too, and that's part of what I'm working on. :)\n\nWe leave the old packed_git structs in place when we re-read the pack\ndirectory. That works because either we have them already opened (so\neven though they're gone, we can still access them, and that's why we\n_must_ keep the structs in place), or we will call is_pack_valid() and\nnotice that it went away (and quietly skip to checking the next pack).\n\nThere is one place where we do free the packed_git, but I actually think\nwe can stop doing so. Here's what I'm planning as part of my series:\n\n\n-- >8 --\nSubject: [PATCH] sha1_file: drop free_pack_by_name\n\nThe point of this function is to drop an entry from the\n\"packed_git\" cache that points to a file we might be\noverwriting, because our contents may not be the same (and\nhence the only caller was pack-objects as it moved a\ntemporary packfile into place).\n\nIn older versions of git, this could happen because the\nnames of packfiles were derived from the set of objects they\ncontained, not the actual bits on disk. But since 1190a1a\n(pack-objects: name pack files after trailer hash,\n2013-12-05), the name reflects the actual bits on disk, and\nany two packfiles with the same name can be used\ninterchangeably.\n\nDropping this function not only saves a few lines of code,\nit makes the lifetime of \"struct packed_git\" much easier to\nreason about: namely, we now do not ever free these structs.\n\nSigned-off-by: Jeff King \n---\nI won't be surprised if this fixes some obscure bug, because there may\nbe parts of the code that store a pointer to our packed_git that could\nbe invalidated (I'm certain the bitmap code does). But perhaps it\ndoesn't matter because it's rare for this function to trigger at all.\n\n cache.h | 1 -\n pack-write.c | 1 -\n sha1_file.c | 30 ------------------------------\n 3 files changed, 32 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 3855ddf..57ef726 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1416,7 +1416,6 @@ extern unsigned char *use_pack(struct packed_git *, struct pack_window **, off_t\n extern void close_pack_windows(struct packed_git *);\n extern void close_all_packs(void);\n extern void unuse_pack(struct pack_window **);\n-extern void free_pack_by_name(const char *);\n extern void clear_delta_base_cache(void);\n extern struct packed_git *add_packed_git(const char *path, size_t path_len, int local);\n \ndiff --git a/pack-write.c b/pack-write.c\nindex 33293ce..ea0b788 100644\n--- a/pack-write.c\n+++ b/pack-write.c\n@@ -354,7 +354,6 @@ void finish_tmp_packfile(struct strbuf *name_buffer,\n \t\tdie_errno(\"unable to make temporary index file readable\");\n \n \tstrbuf_addf(name_buffer, \"%s.pack\", sha1_to_hex(sha1));\n-\tfree_pack_by_name(name_buffer->buf);\n \n \tif (rename(pack_tmp_name, name_buffer->buf))\n \t\tdie_errno(\"unable to rename temporary pack file\");\ndiff --git a/sha1_file.c b/sha1_file.c\nindex d5e1121..e045d2f 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -891,36 +891,6 @@ void close_pack_index(struct packed_git *p)\n \t}\n }\n \n-/*\n- * This is used by git-repack in case a newly created pack happens to\n- * contain the same set of objects as an existing one. In that case\n- * the resulting file might be different even if its name would be the\n- * same. It is best to close any reference to the old pack before it is\n- * replaced on disk. Of course no index pointers or windows for given pack\n- * must subsist at this point. If ever objects from this pack are requested\n- * again, the new version of the pack will be reinitialized through\n- * reprepare_packed_git().\n- */\n-void free_pack_by_name(const char *pack_name)\n-{\n-\tstruct packed_git *p, **pp = &packed_git;\n-\n-\twhile (*pp) {\n-\t\tp = *pp;\n-\t\tif (strcmp(pack_name, p->pack_name) == 0) {\n-\t\t\tclear_delta_base_cache();\n-\t\t\tclose_pack(p);\n-\t\t\tfree(p->bad_object_sha1);\n-\t\t\t*pp = p->next;\n-\t\t\tif (last_found_pack == p)\n-\t\t\t\tlast_found_pack = NULL;\n-\t\t\tfree(p);\n-\t\t\treturn;\n-\t\t}\n-\t\tpp = &p->next;\n-\t}\n-}\n-\n static unsigned int get_max_fd_limit(void)\n {\n #ifdef RLIMIT_NOFILE\n-- \n2.9.2.607.g98dce7b\n\n"}]}