{"thread":{"id":"38730","subject":"Why is \"git fetch --prune\" so much slower than \"git remote prune\"?","startedAt":"2015-03-06T16:48:39Z","lastAt":"2015-03-20T07:04:42Z","messageCount":8,"participants":["Ævar Arnfjörð Bjarmason","Jeff King","Michael Haggerty","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"257176","messageId":"CACBZZX5n5tTCSa-_A5gQzbzboF_v8a3_oVUjdjyFtKHHe8h-NA@mail.gmail.com","threadId":"38730","inReplyTo":null,"subject":"Why is \"git fetch --prune\" so much slower than \"git remote prune\"?","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2015-03-06T16:48:39Z","receivedAt":"2015-03-06T16:48:39Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"The --prune option to fetch added in v1.6.5-8-gf360d84 seems to be\naround 20-30x slower than the equivalent operation with git remote\nprune. I'm wondering if I'm missing something and fetch does something\nmore, but it doesn't seem so.\n\nTo test this clone git.git, create 1000 branches it in, create two\nlocal clones of that clone and then delete the 1000 branches in the\noriginal. I have a script to do this at\nhttps://gist.github.com/avar/497c8c8fbd641fb756ef\n\nThen in each of the clones:\n\n    $ git branch -a|wc -l; time (~/g/git/git-fetch --prune origin\n>/dev/null 2>&1); git branch -a | wc -l\n1003\n    real    0m3.337s\n    user    0m2.996s\n    sys     0m0.336s\n    3\n\n    $ git branch -a|wc -l; time (~/g/git/git-remote prune origin\n>/dev/null 2>&1); git branch -a | wc -l\n    1003\n    real    0m0.067s\n    user    0m0.020s\n    sys     0m0.040s\n    3\n\nBoth of these ends up doing a \"git fetch\", so it's not that. I'm quite\nrusty in C profiling but here's a gprof of the git-fetch command:\n\n$ gprof ~/g/git/git-fetch|head -n 20\nFlat profile:\n\nEach sample counts as 0.01 seconds.\n  %   cumulative   self              self     total\n time   seconds   seconds    calls   s/call   s/call  name\n 26.42      0.33     0.33  1584583     0.00     0.00  strbuf_getwholeline\n 14.63      0.51     0.18 90601347     0.00     0.00  strbuf_grow\n 13.82      0.68     0.17  1045676     0.00     0.00  find_pack_entry_one\n  8.13      0.78     0.10  1050062     0.00     0.00  check_refname_format\n  6.50      0.86     0.08  1584675     0.00     0.00  get_sha1_hex\n  5.69      0.93     0.07  2100529     0.00     0.00  starts_with\n  3.25      0.97     0.04  1044043     0.00     0.00  refname_is_safe\n  3.25      1.01     0.04     8007     0.00     0.00  get_packed_ref_cache\n  2.44      1.04     0.03  2605595     0.00     0.00  search_ref_dir\n  2.44      1.07     0.03  1040500     0.00     0.00  peel_entry\n  1.63      1.09     0.02  2632661     0.00     0.00  get_ref_dir\n  1.63      1.11     0.02  1044043     0.00     0.00  create_ref_entry\n  1.63      1.13     0.02     8024     0.00     0.00  do_for_each_entry_in_dir\n  0.81      1.14     0.01  2155105     0.00     0.00  memory_limit_check\n  0.81      1.15     0.01  1580503     0.00     0.00  sha1_to_hex\n\nAnd of the git-remote command:\n\n$ gprof ~/g/git/git-remote|head -n 20\nFlat profile:\n\nEach sample counts as 0.01 seconds.\n no time accumulated\n\n  %   cumulative   self              self     total\n time   seconds   seconds    calls  Ts/call  Ts/call  name\n  0.00      0.00     0.00   197475     0.00     0.00  strbuf_grow\n  0.00      0.00     0.00    24214     0.00     0.00  sort_ref_dir\n  0.00      0.00     0.00    24190     0.00     0.00  search_ref_dir\n  0.00      0.00     0.00    21661     0.00     0.00  memory_limit_check\n  0.00      0.00     0.00    20236     0.00     0.00  get_ref_dir\n  0.00      0.00     0.00     9187     0.00     0.00  xrealloc\n  0.00      0.00     0.00     7048     0.00     0.00  strbuf_add\n  0.00      0.00     0.00     6348     0.00     0.00  do_xmalloc\n  0.00      0.00     0.00     6126     0.00     0.00  xcalloc\n  0.00      0.00     0.00     6056     0.00     0.00  cleanup_path\n  0.00      0.00     0.00     6050     0.00     0.00  get_git_dir\n  0.00      0.00     0.00     6050     0.00     0.00  vsnpath\n  0.00      0.00     0.00     5554     0.00     0.00  config_file_fgetc\n\nAside from the slowness of git-fetch it seems git-remote can be sped\nup quite a bit by more aggressively allocating a larger string buffer\nfrom the get-go.\n"},{"id":"257206","messageId":"20150306225917.GA1589@peff.net","threadId":"38730","inReplyTo":"CACBZZX5n5tTCSa-_A5gQzbzboF_v8a3_oVUjdjyFtKHHe8h-NA@mail.gmail.com","subject":"Re: Why is \"git fetch --prune\" so much slower than \"git remote prune\"?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-03-06T22:59:17Z","receivedAt":"2015-03-06T22:59:17Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 06, 2015 at 05:48:39PM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> The --prune option to fetch added in v1.6.5-8-gf360d84 seems to be\n> around 20-30x slower than the equivalent operation with git remote\n> prune. I'm wondering if I'm missing something and fetch does something\n> more, but it doesn't seem so.\n\n\"git fetch --prune\" is \"do a normal fetch, and also prune anything\nnecessary\". \"git remote prune\" is \"ls-remote the other side and see if\nthere is anything we can prune; do not touch anything else\".\n\nIf your fetch is a noop (i.e., the other side has not advanced any\nbranches), the outcome is the same. But perhaps fetch is doing more\nwork to find out that it is a noop.\n\nOne way to measure that would be to see how expensive a noop \"git fetch\"\nis (if it's expensive, then there is room to improve there. If not, then\nit is the pruning itself that is expensive).\n\nBut just guessing (I do not have time to dig in deeper right now), and\nseeing this:\n\n> $ gprof ~/g/git/git-fetch|head -n 20\n> Flat profile:\n> \n> Each sample counts as 0.01 seconds.\n>   %   cumulative   self              self     total\n>  time   seconds   seconds    calls   s/call   s/call  name\n>  26.42      0.33     0.33  1584583     0.00     0.00  strbuf_getwholeline\n>  14.63      0.51     0.18 90601347     0.00     0.00  strbuf_grow\n>  13.82      0.68     0.17  1045676     0.00     0.00  find_pack_entry_one\n>   8.13      0.78     0.10  1050062     0.00     0.00  check_refname_format\n>   6.50      0.86     0.08  1584675     0.00     0.00  get_sha1_hex\n>   5.69      0.93     0.07  2100529     0.00     0.00  starts_with\n>   3.25      0.97     0.04  1044043     0.00     0.00  refname_is_safe\n>   3.25      1.01     0.04     8007     0.00     0.00  get_packed_ref_cache\n>   2.44      1.04     0.03  2605595     0.00     0.00  search_ref_dir\n>   2.44      1.07     0.03  1040500     0.00     0.00  peel_entry\n>   1.63      1.09     0.02  2632661     0.00     0.00  get_ref_dir\n>   1.63      1.11     0.02  1044043     0.00     0.00  create_ref_entry\n>   1.63      1.13     0.02     8024     0.00     0.00  do_for_each_entry_in_dir\n>   0.81      1.14     0.01  2155105     0.00     0.00  memory_limit_check\n>   0.81      1.15     0.01  1580503     0.00     0.00  sha1_to_hex\n\nWe spend a lot of time checking refs here. Probably this comes from\nwriting the `packed-refs` file out 1000 times in your example, because\nfetch handles each ref individually. Whereas since c9e768b (remote:\nrepack packed-refs once when deleting multiple refs, 2014-05-23),\ngit-remote does it in one pass.\n\nNow that we have ref_transaction_*, I think if git-fetch fed all of the\ndeletes (along with the updates) into a single transaction, we would get\nthe same optimization for free. Maybe that is even part of some of the\npending ref_transaction work from Stefan or Michael (both cc'd). I\nhaven't kept up very well with what is cooking in pu.\n\n-Peff\n"},{"id":"258028","messageId":"550AE1E4.7020407@alum.mit.edu","threadId":"38730","inReplyTo":"20150306225917.GA1589@peff.net","subject":"Re: Why is \"git fetch --prune\" so much slower than \"git remote prune\"?","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2015-03-19T14:49:08Z","receivedAt":"2015-03-19T14:49:08Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 03/06/2015 11:59 PM, Jeff King wrote:\n> On Fri, Mar 06, 2015 at 05:48:39PM +0100, Ævar Arnfjörð Bjarmason wrote:\n> \n>> The --prune option to fetch added in v1.6.5-8-gf360d84 seems to be\n>> around 20-30x slower than the equivalent operation with git remote\n>> prune. I'm wondering if I'm missing something and fetch does something\n>> more, but it doesn't seem so.\n> \n> [...]\n> We spend a lot of time checking refs here. Probably this comes from\n> writing the `packed-refs` file out 1000 times in your example, because\n> fetch handles each ref individually. Whereas since c9e768b (remote:\n> repack packed-refs once when deleting multiple refs, 2014-05-23),\n> git-remote does it in one pass.\n> \n> Now that we have ref_transaction_*, I think if git-fetch fed all of the\n> deletes (along with the updates) into a single transaction, we would get\n> the same optimization for free. Maybe that is even part of some of the\n> pending ref_transaction work from Stefan or Michael (both cc'd). I\n> haven't kept up very well with what is cooking in pu.\n\nI am looking into this now.\n\nFor pruning, we can't use a ref_transaction as it is currently\nimplemented because it would fail if any of the reference deletions\nfailed. But in this case I think if any deletions fail, we would prefer\nto emit a warning but keep going.\n\nI'm trying to decide whether to have a separate function in the refs API\nto \"delete as many of the following refs as possible\", or whether to add\na flag to ref_transaction_update() that says \"try this update, but don't\nfail the transaction if it fails\". The latter would probably be more\nwork because we would need to invent a way to return multiple error\nmessages from a single transaction.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\n"},{"id":"258034","messageId":"20150319171416.GB6386@peff.net","threadId":"38730","inReplyTo":"550AE1E4.7020407@alum.mit.edu","subject":"Re: Why is \"git fetch --prune\" so much slower than \"git remote prune\"?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-03-19T17:14:16Z","receivedAt":"2015-03-19T17:14:16Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Mar 19, 2015 at 03:49:08PM +0100, Michael Haggerty wrote:\n\n> For pruning, we can't use a ref_transaction as it is currently\n> implemented because it would fail if any of the reference deletions\n> failed. But in this case I think if any deletions fail, we would prefer\n> to emit a warning but keep going.\n>\n> I'm trying to decide whether to have a separate function in the refs API\n> to \"delete as many of the following refs as possible\", or whether to add\n> a flag to ref_transaction_update() that says \"try this update, but don't\n> fail the transaction if it fails\". The latter would probably be more\n> work because we would need to invent a way to return multiple error\n> messages from a single transaction.\n\nHmm, yeah. That is sort of antithetical to the original purpose of ref\ntransactions (which was atomicity). Given the way it is implemented now,\nI don't think it would be too big a deal to keep a per-ref status (one\nper \"struct ref_upate\").  But I would worry in the long run that it\nmakes things much harder on proposed ref backends, which otherwise can\nconsider a transaction an atomic unit.\n\nOTOH, I do not think there is an abstracted way to do this _without_\nthe ref backend knowing about it. You cannot just do a series of\ntransactions; that defeats the purpose. It is a bit of a layering\nviolation that builtin/remote.c (which does this optimization already)\ncalls repack_without_refs directly.\n\n-Peff\n"},{"id":"258042","messageId":"xmqqpp84iye2.fsf@gitster.dls.corp.google.com","threadId":"38730","inReplyTo":"550AE1E4.7020407@alum.mit.edu","subject":"Re: Why is \"git fetch --prune\" so much slower than \"git remote prune\"?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-03-19T19:24:21Z","receivedAt":"2015-03-19T19:24:21Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n>> Now that we have ref_transaction_*, I think if git-fetch fed all of the\n>> deletes (along with the updates) into a single transaction, we would get\n>> the same optimization for free. Maybe that is even part of some of the\n>> pending ref_transaction work from Stefan or Michael (both cc'd). I\n>> haven't kept up very well with what is cooking in pu.\n>\n> I am looking into this now.\n>\n> For pruning, we can't use a ref_transaction as it is currently\n> implemented because it would fail if any of the reference deletions\n> failed. But in this case I think if any deletions fail, we would prefer\n> to emit a warning but keep going.\n\nI am not quite sure what you mean here.  I agree with you if you\nmeant \"we shouldn't fail the fetch only because 'fetch --prune'\nfailed to remove only one of the remote-tracking refs that are no\nlonger there\" but that can easily be solved by the pruning phase\ninto a separate transaction.  If you meant \"we would rather remove\norigin/{a,b} non-atomically when we noticed that origin/{a,b,c} are\nall gone than leaving all three intact only because we failed to\nremove origin/c for whatever reason\", my knee-jerk reaction is \"does\nit make practical difference to the end user between these two?\"\n\nWhat are the plausible cause of failing to prune unused\nremote-tracking refs?\n"},{"id":"258060","messageId":"20150319212640.GB8363@peff.net","threadId":"38730","inReplyTo":"xmqqpp84iye2.fsf@gitster.dls.corp.google.com","subject":"Re: Why is \"git fetch --prune\" so much slower than \"git remote prune\"?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-03-19T21:26:40Z","receivedAt":"2015-03-19T21:26:40Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Mar 19, 2015 at 12:24:21PM -0700, Junio C Hamano wrote:\n\n> > For pruning, we can't use a ref_transaction as it is currently\n> > implemented because it would fail if any of the reference deletions\n> > failed. But in this case I think if any deletions fail, we would prefer\n> > to emit a warning but keep going.\n> \n> I am not quite sure what you mean here.  I agree with you if you\n> meant \"we shouldn't fail the fetch only because 'fetch --prune'\n> failed to remove only one of the remote-tracking refs that are no\n> longer there\" but that can easily be solved by the pruning phase\n> into a separate transaction.  If you meant \"we would rather remove\n> origin/{a,b} non-atomically when we noticed that origin/{a,b,c} are\n> all gone than leaving all three intact only because we failed to\n> remove origin/c for whatever reason\", my knee-jerk reaction is \"does\n> it make practical difference to the end user between these two?\"\n> \n> What are the plausible cause of failing to prune unused\n> remote-tracking refs?\n\nI had assumed earlier that Michael meant to use a single ref_transaction\nfor all updates. Thinking on it more, that is probably a bad idea, as it\nmakes fetch atomic in a user-visible way, whereas currently the updates\nare always per-ref (i.e., some may fail, but we let others succeed). I\ndon't know if people actually care or not (certainly the exit code of\nfetch represents all of the refs, so it is not like you could say \"eh,\ngit-fetch return 1, but it probably got the ref I wanted\" without\nparsing the human-readable output).\n\nIf it is just a single atomic commit for all of the deletions, I agree\nit is less of a big deal. They are unlikely to fail, and when they do,\nyou are not blocking the new refs from coming in.\n\nI think the ref_transaction does have some smarts to handle a case where\nwe are updating \"refs/foo/bar\" while \"refs/foo\" exists but is deleted in\nthe transaction. We switched to pruning before updating in\n10a6cc8 (fetch --prune: Run prune before fetching, 2014-01-02), so it is\na non-issue, but what is there now is technically racy[1], and it would\nhave been nice to let the ref-storage code handle it. I guess we still\ncan if we introduce a \"git fetch --atomic\" option.\n\n-Peff\n\n[1] http://article.gmane.org/gmane.comp.version-control.git/239519\n"},{"id":"258085","messageId":"550BA76C.80501@alum.mit.edu","threadId":"38730","inReplyTo":"xmqqpp84iye2.fsf@gitster.dls.corp.google.com","subject":"Re: Why is \"git fetch --prune\" so much slower than \"git remote prune\"?","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2015-03-20T04:51:56Z","receivedAt":"2015-03-20T04:51:56Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 03/19/2015 08:24 PM, Junio C Hamano wrote:\n> Michael Haggerty <mhagger@alum.mit.edu> writes:\n> \n>>> Now that we have ref_transaction_*, I think if git-fetch fed all of the\n>>> deletes (along with the updates) into a single transaction, we would get\n>>> the same optimization for free. Maybe that is even part of some of the\n>>> pending ref_transaction work from Stefan or Michael (both cc'd). I\n>>> haven't kept up very well with what is cooking in pu.\n>>\n>> I am looking into this now.\n>>\n>> For pruning, we can't use a ref_transaction as it is currently\n>> implemented because it would fail if any of the reference deletions\n>> failed. But in this case I think if any deletions fail, we would prefer\n>> to emit a warning but keep going.\n> \n> I am not quite sure what you mean here.  I agree with you if you\n> meant \"we shouldn't fail the fetch only because 'fetch --prune'\n> failed to remove only one of the remote-tracking refs that are no\n> longer there\" but that can easily be solved by the pruning phase\n> into a separate transaction.  If you meant \"we would rather remove\n> origin/{a,b} non-atomically when we noticed that origin/{a,b,c} are\n> all gone than leaving all three intact only because we failed to\n> remove origin/c for whatever reason\", my knee-jerk reaction is \"does\n> it make practical difference to the end user between these two?\"\n> \n> What are the plausible cause of failing to prune unused\n> remote-tracking refs?\n\nI wasn't proposing to combine the updates with the prunes in a single\ntransaction. (Though now that I think about it, when \"fetch --atomic\" is\nspecified it wouldn't be so crazy. It would also have the virtue of\nallowing the reference transaction code to deal with any D/F conflicts\nbetween references being added and references being deleted.)\n\nWhat I meant is the second thing you mentioned, namely that currently we\nprune each reference on a \"best-effort\" basis and wouldn't skip *all*\nprunes just because one failed.\n\nBut you raise an interesting question: what could cause a failure to\nprune an unused remote-tracking ref (i.e. if all pruning is done in a\nsingle transaction)?\n\n* I think the most likely reason for a failure would be a lock conflict\nwith another process. We don't retry lock attempts [1], so this would\ncause the whole transaction to fail. This could happen, for example, if\nthe user launches two \"fetch --prune\" operations at the same time, or\nruns \"pack-refs\" while fetching [2].\n\n* It is *not* a failure if another process deletes or updates the\nreference before we get to it, because we don't provide an \"old\" value\nof the reference for a pre-check.\n\n* I haven't verified this, but I can imagine it could fail if another\nprocess deletes the reference (say refs/remotes/origin/foo/bar) and adds\nanother reference that would D/F conflict with it (say\nrefs/remotes/origin/foo) while we are working, because our attempt to\ncreate refs/remotes/origin/foo/bar.lock would fail.\n\n* A repository problem, like for example wrong file permissions\nsomewhere in the loose refs directory, could prevent us from being able\nto create the lockfile or delete the loose reference file.\n\nThe lock conflict scenario is the only one that really worries me.\n\nBut I don't think it is *so* hard to keep the current \"best-effort\"\nbehavior. I am working on a function delete_refs() for the reference API\nthat deletes a bunch of references on a \"best effort\" basis, reporting\nper-reference errors for any deletions that fail. Longer term, we could\nadd something like a REFS_NON_ATOMIC flag to the\nrefs_transaction_update() functions, which allows the rest of the\ntransaction to proceed even if that particular update fails.\n\nMichael\n\n[1] I hope to submit a patch to make it possible to retry lock\nacquisition with a specified timeout. This should help in scenarios like\nthis.\n\n[2] Maybe a careful analysis or a slight change to our locking protocol\ncould prove that the only lock acquisition that can fail is the one on\npacked-refs, which would cause all of the deletes to fail anyway. In\nthat case per-reference failures would cease to be a worry.\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\n"},{"id":"258088","messageId":"xmqq7fucgned.fsf@gitster.dls.corp.google.com","threadId":"38730","inReplyTo":"550BA76C.80501@alum.mit.edu","subject":"Re: Why is \"git fetch --prune\" so much slower than \"git remote prune\"?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-03-20T07:04:42Z","receivedAt":"2015-03-20T07:04:42Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> The lock conflict scenario is the only one that really worries me.\n\nActually, I'd feel worried if this were on the receive-pack side, as\nit is entirely valid that two or more people make uncoordinated push\ninto a single meeting point, but much less for something like\n\"fetch\".  I do not see a valid reason why somebody cannot avoid\nfetching into the same repository in a racy way.\n\n> But I don't think it is *so* hard to keep the current \"best-effort\"\n> behavior.\n\nI agree that transaction is a wrong way to look at this.  I view \"We\nknow packed refs is a lot more efficient if written once\" as in the\nsame category as \"We know we will register many new objects with\nthis operation, so instead of creating them into separate loose\nobject files, declare that the object store is 'plugged' and send\nthem into a single new packfile\" (aka \"bulk checkin\").  Both are\nuninterested in all-or-none execution, but merely want to declare a\nboundary between a group of operations to help Git optimize them.\n\n> I am working on a function delete_refs() for the reference API\n> that deletes a bunch of references on a \"best effort\" basis, reporting\n> per-reference errors for any deletions that fail.\n\nI think it would make sense, but I suspect you would want to make it\nclear that the function is best-effort-bulk somewhere in its name\n(e.g. delete-refs-if-able or something) and make it not to\nautomatically fail the surrounding transaction if any.  That way\nan application could do things like this:\n\n    transaction-begin;\n      create-ref;\n      update-ref;\n      ...\n      delete-refs-if-able;\n      if trying to be as atomic as possible\n      then\n\tif previous delete-refs-if-able found undeletable refs\n        then\n          transaction-abort;\n\tfi\n      fi\n    transaction-commit;\n\nOf course, supplying delete-refs that is not best-effort separately\nwould make it even easier to code the above (the last if/then/fi will\nbecome unnecessary).\n"}]}