{"thread":{"id":"31720","subject":"upload-pack is slow with lots of refs","startedAt":"2012-10-03T12:36:00Z","lastAt":"2012-10-09T20:46:42Z","messageCount":24,"participants":["Ævar Arnfjörð Bjarmason","Nguyen Thai Ngoc Duy","Jeff King","Junio C Hamano","Shawn Pearce","Sascha Cunz","Johannes Sixt"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"200408","messageId":"CACBZZX70NTic2WtrXooTg+yBbiFFDAEX_Y-b=W=rAkcYKJ3T2g@mail.gmail.com","threadId":"31720","inReplyTo":null,"subject":"upload-pack is slow with lots of refs","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2012-10-03T12:36:00Z","receivedAt":"2012-10-03T12:36:00Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"I'm creating a system where a lot of remotes constantly fetch from a\ncentral repository for deployment purposes, but I've noticed that even\nwith a remote.$name.fetch configuration to only get certain refs a\n\"git fetch\" will still call git-upload pack which will provide a list\nof all references.\n\nThis is being done against a repository with tens of thousands of refs\n(it has a tag for each deployment), so it ends up burning a lot of CPU\ntime on the uploader/receiver side.\n\nHas there been any work on extending the protocol so that the client\ntells the server what refs it's interested in?\n\nI've been looking at turning this into a push mechanism instead of a\npoll mechanism, but I've also noted that even when you one tag you\nstill end up listing all refs on the remote side:\n\n    $ GIT_TRACE=1 git push origin my-new-tag -n\n    trace: built-in: git 'push' 'origin' 'my-new-tag' '-n'\n    trace: run_command: 'ssh' 'avar@git.example.com' 'git-receive-pack\n'\\''/gitroot/example.git'\\'''\n    nohup: redirecting stderr to stdout\n    To ssh://avar@git.example.com/gitroot/example.git\n     * [new tag]         my-new-tag -> my-new-tag\n\nWhich seems like a lot of superfluous work when it presumably only\nneeds to check if there's a remote \"my-new-tag\" tag which conflicts\nwith what you're pushing..\n"},{"id":"200411","messageId":"CACsJy8DgM7ncbT8seUMLoPj=j8hFHCP6SvsDHu4P-YN2xfiNHg@mail.gmail.com","threadId":"31720","inReplyTo":"CACBZZX70NTic2WtrXooTg+yBbiFFDAEX_Y-b=W=rAkcYKJ3T2g@mail.gmail.com","subject":"Re: upload-pack is slow with lots of refs","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-10-03T13:06:03Z","receivedAt":"2012-10-03T13:06:03Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Oct 3, 2012 at 7:36 PM, Ævar Arnfjörð Bjarmason\n<avarab@gmail.com> wrote:\n> I'm creating a system where a lot of remotes constantly fetch from a\n> central repository for deployment purposes, but I've noticed that even\n> with a remote.$name.fetch configuration to only get certain refs a\n> \"git fetch\" will still call git-upload pack which will provide a list\n> of all references.\n>\n> This is being done against a repository with tens of thousands of refs\n> (it has a tag for each deployment), so it ends up burning a lot of CPU\n> time on the uploader/receiver side.\n\nIf all refs are packed, will it still burn lots of CPU on server side?\n\n> Has there been any work on extending the protocol so that the client\n> tells the server what refs it's interested in?\n\nIt'll be a new protocol, not an extension for git protocol. Ref\nadvertising is step 1. Capababilities are advertised much later. The\nclient has to time to tell the server what protocol version it likes\nto use for step 1. (I looked at this protcol extension from a\ndifferent angle. I wanted to compress the ref list for git protocol.\nBut git over http compresses well so I don't care much.)\n\nOn that git-over-http, I don't know, maybe git client can send\nsomething as http headers, which are recognized by the server end, to\nnegotiate interested ref patterns?\n-- \nDuy\n"},{"id":"200438","messageId":"20121003180324.GB27446@sigill.intra.peff.net","threadId":"31720","inReplyTo":"CACBZZX70NTic2WtrXooTg+yBbiFFDAEX_Y-b=W=rAkcYKJ3T2g@mail.gmail.com","subject":"Re: upload-pack is slow with lots of refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-03T18:03:24Z","receivedAt":"2012-10-03T18:03:24Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 03, 2012 at 02:36:00PM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> I'm creating a system where a lot of remotes constantly fetch from a\n> central repository for deployment purposes, but I've noticed that even\n> with a remote.$name.fetch configuration to only get certain refs a\n> \"git fetch\" will still call git-upload pack which will provide a list\n> of all references.\n> \n> This is being done against a repository with tens of thousands of refs\n> (it has a tag for each deployment), so it ends up burning a lot of CPU\n> time on the uploader/receiver side.\n\nWhere is the CPU being burned? Are your refs packed (that's a huge\nsavings)? What are the refs like? Are they .have refs from an alternates\nrepository, or real refs? Are they pointing to commits or tag objects?\n\nWhat version of git are you using?  In the past year or so, I've made\nseveral tweaks to speed up large numbers of refs, including:\n\n  - cff38a5 (receive-pack: eliminate duplicate .have refs, v1.7.6); note\n    that this only helps if they are being pulled in by an alternates\n    repo. And even then, it only helps if they are mostly duplicates;\n    distinct ones are still O(n^2).\n\n  - 7db8d53 (fetch-pack: avoid quadratic behavior in remove_duplicates)\n    a0de288 (fetch-pack: avoid quadratic loop in filter_refs)\n    Both in v1.7.11. I think there is still a potential quadratic loop\n    in mark_complete()\n\n  - 90108a2 (upload-pack: avoid parsing tag destinations)\n    926f1dd (upload-pack: avoid parsing objects during ref advertisement)\n    Both in v1.7.10. Note that tag objects are more expensive to\n    advertise than commits, because we have to load and peel them.\n\nEven with those patches, though, I found that it was something like ~2s\nto advertise 100,000 refs.\n\n> Has there been any work on extending the protocol so that the client\n> tells the server what refs it's interested in?\n\nI don't think so. It would be hard to do in a backwards-compatible way,\nbecause the advertisement is the first thing the server says, before it\nhas negotiated any capabilities with the client at all.\n\n-Peff\n"},{"id":"200443","messageId":"7vobkj4cb4.fsf@alter.siamese.dyndns.org","threadId":"31720","inReplyTo":"20121003180324.GB27446@sigill.intra.peff.net","subject":"Re: upload-pack is slow with lots of refs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-10-03T18:53:35Z","receivedAt":"2012-10-03T18:53:35Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n>> Has there been any work on extending the protocol so that the client\n>> tells the server what refs it's interested in?\n>\n> I don't think so. It would be hard to do in a backwards-compatible way,\n> because the advertisement is the first thing the server says, before it\n> has negotiated any capabilities with the client at all.\n\nThat is being discussed but hasn't surfaced on the list.\n"},{"id":"200444","messageId":"20121003185542.GA3635@sigill.intra.peff.net","threadId":"31720","inReplyTo":"7vobkj4cb4.fsf@alter.siamese.dyndns.org","subject":"Re: upload-pack is slow with lots of refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-03T18:55:42Z","receivedAt":"2012-10-03T18:55:42Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 03, 2012 at 11:53:35AM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> >> Has there been any work on extending the protocol so that the client\n> >> tells the server what refs it's interested in?\n> >\n> > I don't think so. It would be hard to do in a backwards-compatible way,\n> > because the advertisement is the first thing the server says, before it\n> > has negotiated any capabilities with the client at all.\n> \n> That is being discussed but hasn't surfaced on the list.\n\nOut of curiosity, how are you thinking about triggering such a new\nbehavior in a backwards-compatible way? Invoke git-upload-pack2, and\nfall back to reconnecting to start git-upload-pack if it fails?\n\n-Peff\n"},{"id":"200452","messageId":"7vd30z4bej.fsf@alter.siamese.dyndns.org","threadId":"31720","inReplyTo":"CACBZZX70NTic2WtrXooTg+yBbiFFDAEX_Y-b=W=rAkcYKJ3T2g@mail.gmail.com","subject":"Re: upload-pack is slow with lots of refs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-10-03T19:13:08Z","receivedAt":"2012-10-03T19:13:08Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:\n\n> I'm creating a system where a lot of remotes constantly fetch from a\n> central repository for deployment purposes, but I've noticed that even\n> with a remote.$name.fetch configuration to only get certain refs a\n> \"git fetch\" will still call git-upload pack which will provide a list\n> of all references.\n\nIt has been observed that the sender has to advertise megabytes of\nrefs because it has to speak first before knowing what the receiver\nwants, even when the receiver is interested in getting updates from\nonly one of them, or worse yet, when the receiver is only trying to\npeek the ref it is interested has been updated.\n\nI do not think upload-pack that runs on the sender side with\nmillions refs, when asked for a single \"want\", feeds all the refs\nthat it has to the revision machinery, and if you observed it does,\nI cannot explain why it happens.\n"},{"id":"200454","messageId":"CAJo=hJtZ_8H6+kXPpZcRCbJi3LPuuF7M1U8YsjAp-iWvut9oMw@mail.gmail.com","threadId":"31720","inReplyTo":"20121003185542.GA3635@sigill.intra.peff.net","subject":"Re: upload-pack is slow with lots of refs","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-10-03T19:41:38Z","receivedAt":"2012-10-03T19:41:38Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Wed, Oct 3, 2012 at 11:55 AM, Jeff King <peff@peff.net> wrote:\n> On Wed, Oct 03, 2012 at 11:53:35AM -0700, Junio C Hamano wrote:\n>> Jeff King <peff@peff.net> writes:\n>>\n>> >> Has there been any work on extending the protocol so that the client\n>> >> tells the server what refs it's interested in?\n>> >\n>> > I don't think so. It would be hard to do in a backwards-compatible way,\n>> > because the advertisement is the first thing the server says, before it\n>> > has negotiated any capabilities with the client at all.\n>>\n>> That is being discussed but hasn't surfaced on the list.\n>\n> Out of curiosity, how are you thinking about triggering such a new\n> behavior in a backwards-compatible way? Invoke git-upload-pack2, and\n> fall back to reconnecting to start git-upload-pack if it fails?\n\nBasically, yes. New clients connect for git-upload-pack2. Over git://\nthe remote peer will just close the TCP socket with no messages. The\nclient can fallback to git-upload-pack and try again. Over SSH a\nsimilar thing will happen in the sense there is no data output from\nthe remote side, so the client can try again. This has the downside of\nauthentication twice over SSH, which may prompt for a password twice.\nBut the user can get out of this by setting remote.NAME.uploadpack =\ngit-upload-pack and thus force the Git client to use the current\nprotocol if they have a new client and must continue to work over SSH\nwith an old server, and don't use an ssh-agent.\n\nOver HTTP we can request ?service=git-upload-pack2 and retry just like\ngit:// would, or be a bit smarter and say\n?service=git-upload-pack&v=2, and determine the protocol support of\nthe remote peer based on the response we get. If we see an immediate\nadvertisement its still the \"v1\" protocol, if we get back the \"yes I\nspeak v2\" response like git:// would see, we can continue the\nconversation from there.\n"},{"id":"200449","messageId":"20121003201316.GA4484@sigill.intra.peff.net","threadId":"31720","inReplyTo":"CAJo=hJtZ_8H6+kXPpZcRCbJi3LPuuF7M1U8YsjAp-iWvut9oMw@mail.gmail.com","subject":"Re: upload-pack is slow with lots of refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-03T20:13:16Z","receivedAt":"2012-10-03T20:13:16Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 03, 2012 at 12:41:38PM -0700, Shawn O. Pearce wrote:\n\n> > Out of curiosity, how are you thinking about triggering such a new\n> > behavior in a backwards-compatible way? Invoke git-upload-pack2, and\n> > fall back to reconnecting to start git-upload-pack if it fails?\n> \n> Basically, yes. New clients connect for git-upload-pack2. Over git://\n> the remote peer will just close the TCP socket with no messages. The\n> client can fallback to git-upload-pack and try again. Over SSH a\n> similar thing will happen in the sense there is no data output from\n> the remote side, so the client can try again. This has the downside of\n> authentication twice over SSH, which may prompt for a password twice.\n> But the user can get out of this by setting remote.NAME.uploadpack =\n> git-upload-pack and thus force the Git client to use the current\n> protocol if they have a new client and must continue to work over SSH\n> with an old server, and don't use an ssh-agent.\n\nIt's a shame that we have to reestablish the TCP or ssh connection to do\nthe retry. The password thing is annoying, but also it just wastes a\nround-trip. It means we'd probably want to default the v2 probe to off\n(and let the user turn it on for a specific remote) until v2 is much\nmore common than v1. Otherwise everyone pays the price.\n\nIt may also be worth designing v2 to handle more graceful capability\nnegotiation so this doesn't come up again.\n\nAnother alternative would be to tweak git-daemon to allow more graceful\nfallback. That wouldn't help us now, but it would if we ever wanted a\nv3. For stock ssh, you could send:\n\n  sh -c 'git upload-pack2; test $? = 127 && git-upload-pack'\n\nwhich would work if you have an unrestricted shell on the other side.\nBut it would break for a restricted shell or other \"fake\" ssh\nenvironment. It's probably too ugly to have restricted shells recognize\nthat as a magic token (well, I could maybe even live with the ugliness,\nbut it is not strictly backwards compatible).\n\nI was hoping we could do something like \"git upload-pack --v2\", but I'm\npretty sure current git-daemon would reject that.\n\n> Over HTTP we can request ?service=git-upload-pack2 and retry just like\n> git:// would, or be a bit smarter and say\n> ?service=git-upload-pack&v=2, and determine the protocol support of\n> the remote peer based on the response we get. If we see an immediate\n> advertisement its still the \"v1\" protocol, if we get back the \"yes I\n> speak v2\" response like git:// would see, we can continue the\n> conversation from there.\n\nYeah, I would think \"&v=2\" would be better simply to avoid the\nround-trip if we fail. It should be safe to turn the new protocol on by\ndefault for http, then.\n\n-Peff\n"},{"id":"200459","messageId":"CACBZZX4Grya=FbL9XEh_EK6KVsFZYWCuHveV2QevcBwr+iYTMQ@mail.gmail.com","threadId":"31720","inReplyTo":"20121003180324.GB27446@sigill.intra.peff.net","subject":"Re: upload-pack is slow with lots of refs","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2012-10-03T20:16:56Z","receivedAt":"2012-10-03T20:16:56Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Wed, Oct 3, 2012 at 8:03 PM, Jeff King <peff@peff.net> wrote:\n> On Wed, Oct 03, 2012 at 02:36:00PM +0200, Ævar Arnfjörð Bjarmason wrote:\n>\n>> I'm creating a system where a lot of remotes constantly fetch from a\n>> central repository for deployment purposes, but I've noticed that even\n>> with a remote.$name.fetch configuration to only get certain refs a\n>> \"git fetch\" will still call git-upload pack which will provide a list\n>> of all references.\n>>\n>> This is being done against a repository with tens of thousands of refs\n>> (it has a tag for each deployment), so it ends up burning a lot of CPU\n>> time on the uploader/receiver side.\n>\n> Where is the CPU being burned? Are your refs packed (that's a huge\n> savings)? What are the refs like? Are they .have refs from an alternates\n> repository, or real refs? Are they pointing to commits or tag objects?\n>\n> What version of git are you using?  In the past year or so, I've made\n> several tweaks to speed up large numbers of refs, including:\n>\n>   - cff38a5 (receive-pack: eliminate duplicate .have refs, v1.7.6); note\n>     that this only helps if they are being pulled in by an alternates\n>     repo. And even then, it only helps if they are mostly duplicates;\n>     distinct ones are still O(n^2).\n>\n>   - 7db8d53 (fetch-pack: avoid quadratic behavior in remove_duplicates)\n>     a0de288 (fetch-pack: avoid quadratic loop in filter_refs)\n>     Both in v1.7.11. I think there is still a potential quadratic loop\n>     in mark_complete()\n>\n>   - 90108a2 (upload-pack: avoid parsing tag destinations)\n>     926f1dd (upload-pack: avoid parsing objects during ref advertisement)\n>     Both in v1.7.10. Note that tag objects are more expensive to\n>     advertise than commits, because we have to load and peel them.\n>\n> Even with those patches, though, I found that it was something like ~2s\n> to advertise 100,000 refs.\n\nI can't provide all the details now (not with access to that machine\nnow), but briefly:\n\n * The git client/server version is 1.7.8\n\n * The repository has around 50k refs, they're \"real\" refs, almost all\n   of them (say all but 0.5k-1k) are annotated tags, the rest are\n   branches.\n\n * >99% of them are packed, there's a weekly cronjob that packs them\n   all up, there were a few newly pushed branches and tags outside of\n   the\n\n * I tried \"echo -n | git upload-pack <repo>\" on both that 50k\n   repository and a repository with <100 refs, the former took around\n   ~1-2s to run on a 24 core box and the latter ~500ms.\n\n * When I ran git-upload-pack with GNU parallel I managed around 20/s\n   packs on the 24 core box on the 50k ref one, 40/s on the 100 ref\n   one.\n\n * A co-worker who was working on this today tried it on 1.7.12 and\n   claimed that it had the same performance characteristics.\n\n * I tried to profile it under gcc -pg && echo -n | ./git-upload-pack\n   <repo> but it doesn't produce a profile like that, presumably\n   because the process exits unsuccessfully.\n\n   Maybe someone here knows offhand what mock data I could feed\n   git-upload-pack to make it happy to just list the refs, or better\n   yet do a bit more work which it would do if it were actually doing\n   the fetch (I suppose I could just do a fetch, but I wanted to do\n   this from a locally compiled checkout).\n\n>> Has there been any work on extending the protocol so that the client\n>> tells the server what refs it's interested in?\n>\n> I don't think so. It would be hard to do in a backwards-compatible way,\n> because the advertisement is the first thing the server says, before it\n> has negotiated any capabilities with the client at all.\n\nI suppose at least for the ssh protocol we could just do:\n\n    ssh server \"(git upload-pack <repo> --refs=* || git upload-pack <repo>)\"\n\nAnd something similar with HTTP headers, but that of course leaves the\ngit:// protocol.\n"},{"id":"200461","messageId":"20121003212007.GC4484@sigill.intra.peff.net","threadId":"31720","inReplyTo":"CACBZZX4Grya=FbL9XEh_EK6KVsFZYWCuHveV2QevcBwr+iYTMQ@mail.gmail.com","subject":"Re: upload-pack is slow with lots of refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-03T21:20:07Z","receivedAt":"2012-10-03T21:20:07Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 03, 2012 at 10:16:56PM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> I can't provide all the details now (not with access to that machine\n> now), but briefly:\n> \n>  * The git client/server version is 1.7.8\n> \n>  * The repository has around 50k refs, they're \"real\" refs, almost all\n>    of them (say all but 0.5k-1k) are annotated tags, the rest are\n>    branches.\n\nI'd definitely try upgrading, then; I got measurable speedups from this\nexact case using the patches in v1.7.10.\n\n>  * >99% of them are packed, there's a weekly cronjob that packs them\n>    all up, there were a few newly pushed branches and tags outside of\n>    the\n\nA few strays shouldn't make a big difference. The killer is calling\nopen(2) 50,000 times, but having most of it packed should prevent that.\nI suspect Michael Haggerty's work on the ref cache may help, too\n(otherwise we have to try each packed ref in the filesystem to make sure\nnobody has written it since we packed).\n\n>  * I tried \"echo -n | git upload-pack <repo>\" on both that 50k\n>    repository and a repository with <100 refs, the former took around\n>    ~1-2s to run on a 24 core box and the latter ~500ms.\n\nMore cores won't help, of course, as dumping the refs is single-threaded.\n\nWith v1.7.12, my ~400K test repository takes about 0.8s to run (on my\n2-year-old 1.8 GHz i7, though it is probably turbo-boosting to 3 GHz).\nSo I'm surprised it is so slow.\n\nYour 100-ref case is slow, too. Upload-pack's initial advertisement on\nmy linux-2.6 repository (without about 900 refs) is more like 20ms. I'd\n\n>  * A co-worker who was working on this today tried it on 1.7.12 and\n>    claimed that it had the same performance characteristics.\n\nThat's surprising to me. Can you try to verify those numbers?\n\n>  * I tried to profile it under gcc -pg && echo -n | ./git-upload-pack\n>    <repo> but it doesn't produce a profile like that, presumably\n>    because the process exits unsuccessfully.\n\nIf it's a recent version of Linux, you'll get much nicer results with\nperf. Here's what my 400K-ref case looks like:\n\n  $ time echo 0000 | perf record git-upload-pack . >/dev/null\n  real    0m0.808s\n  user    0m0.660s\n  sys     0m0.136s\n\n  $ perf report | grep -v ^# | head\n  11.40%  git-upload-pack  libc-2.13.so        [.] vfprintf\n   9.70%  git-upload-pack  git-upload-pack     [.] find_pack_entry_one\n   7.64%  git-upload-pack  git-upload-pack     [.] check_refname_format\n   6.81%  git-upload-pack  libc-2.13.so        [.] __memcmp_sse4_1\n   5.79%  git-upload-pack  libc-2.13.so        [.] getenv\n   4.20%  git-upload-pack  libc-2.13.so        [.] __strlen_sse42\n   3.72%  git-upload-pack  git-upload-pack     [.] ref_entry_cmp_sslice\n   3.15%  git-upload-pack  git-upload-pack     [.] read_packed_refs\n   2.65%  git-upload-pack  git-upload-pack     [.] sha1_to_hex\n   2.44%  git-upload-pack  libc-2.13.so        [.] _IO_default_xsputn\n\nSo nothing too surprising, though there is some room for improvement\n(e.g., it looks like we are calling getenv in a tight loop, which could\nbe hoisted out to a single call).\n\nDo note that this version of git was compiled with -O3. Compiling with\n-O0 produces very different results (it's more like 1.3s, and the\nhotspots are check_refname_component and sha1_to_hex).\n\n>    Maybe someone here knows offhand what mock data I could feed\n>    git-upload-pack to make it happy to just list the refs, or better\n>    yet do a bit more work which it would do if it were actually doing\n>    the fetch (I suppose I could just do a fetch, but I wanted to do\n>    this from a locally compiled checkout).\n\nIf you feed \"0000\" as I did above, that is the flush signal for \"I have\nno more lines to send you\", which means that we are not actually\nfetching anything. I.e., this is the exact same conversation a no-op\n\"git fetch\" would produce.\n\n-Peff\n"},{"id":"200463","messageId":"CACBZZX6yMfeOx6x4iy8beq5niy9HvPq0c8ND5jZkoiJWAgVjfw@mail.gmail.com","threadId":"31720","inReplyTo":"20121003212007.GC4484@sigill.intra.peff.net","subject":"Re: upload-pack is slow with lots of refs","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2012-10-03T22:15:47Z","receivedAt":"2012-10-03T22:15:47Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Wed, Oct 3, 2012 at 11:20 PM, Jeff King <peff@peff.net> wrote:\n\nThanks for all that info, it's really useful.\n\n>>  * A co-worker who was working on this today tried it on 1.7.12 and\n>>    claimed that it had the same performance characteristics.\n>\n> That's surprising to me. Can you try to verify those numbers?\n\nI think he was wrong, I tested this on git.git by first creating a lot\nof tags:\n\n     parallel --eta \"git tag -a -m\"{}\" test-again-{}\" ::: $(git rev-list HEAD)\n\nThen doing:\n\n    git pack-refs --all\n    git repack -A -d\n\nAnd compiled with -g -O3 I get around 1.55 runs/s of git-upload-pack\non 1.7.8 and 2.59/s on the master branch.\n\n>>  * I tried to profile it under gcc -pg && echo -n | ./git-upload-pack\n>>    <repo> but it doesn't produce a profile like that, presumably\n>>    because the process exits unsuccessfully.\n>\n> If it's a recent version of Linux, you'll get much nicer results with\n> perf. Here's what my 400K-ref case looks like:\n>\n>   $ time echo 0000 | perf record git-upload-pack . >/dev/null\n>   real    0m0.808s\n>   user    0m0.660s\n>   sys     0m0.136s\n>\n>   $ perf report | grep -v ^# | head\n>   11.40%  git-upload-pack  libc-2.13.so        [.] vfprintf\n>    9.70%  git-upload-pack  git-upload-pack     [.] find_pack_entry_one\n>    7.64%  git-upload-pack  git-upload-pack     [.] check_refname_format\n>    6.81%  git-upload-pack  libc-2.13.so        [.] __memcmp_sse4_1\n>    5.79%  git-upload-pack  libc-2.13.so        [.] getenv\n>    4.20%  git-upload-pack  libc-2.13.so        [.] __strlen_sse42\n>    3.72%  git-upload-pack  git-upload-pack     [.] ref_entry_cmp_sslice\n>    3.15%  git-upload-pack  git-upload-pack     [.] read_packed_refs\n>    2.65%  git-upload-pack  git-upload-pack     [.] sha1_to_hex\n>    2.44%  git-upload-pack  libc-2.13.so        [.] _IO_default_xsputn\n\nFWIW here are my results on the above pathological git.git\n\n    $ uname -r; perf --version; echo 0000 | perf record\n./git-upload-pack .>/dev/null; perf report | grep -v ^# | head\n    3.2.0-2-amd64\n    perf version 3.2.17\n    [ perf record: Woken up 1 times to write data ]\n    [ perf record: Captured and wrote 0.026 MB perf.data (~1131 samples) ]\n        29.08%  git-upload-pack  libz.so.1.2.7       [.] inflate\n        17.99%  git-upload-pack  libz.so.1.2.7       [.] 0xaec1\n         6.21%  git-upload-pack  libc-2.13.so        [.] 0x117503\n         5.69%  git-upload-pack  libcrypto.so.1.0.0  [.] 0x82c3d\n         4.87%  git-upload-pack  git-upload-pack     [.] find_pack_entry_one\n         3.18%  git-upload-pack  ld-2.13.so          [.] 0x886e\n         2.96%  git-upload-pack  libc-2.13.so        [.] vfprintf\n         2.83%  git-upload-pack  git-upload-pack     [.] search_for_subdir\n         1.56%  git-upload-pack  [kernel.kallsyms]   [k] do_raw_spin_lock\n         1.36%  git-upload-pack  libc-2.13.so        [.] vsnprintf\n\nI wonder why your report doesn't note any time in libz. This is on\nDebian testing, maybe your OS uses different strip settings so it\ndoesn't show up?\n\n    $ ldd -r ./git-upload-pack\n            linux-vdso.so.1 =>  (0x00007fff621ff000)\n            libz.so.1 => /lib/x86_64-linux-gnu/libz.so.1 (0x00007f768feee000)\n            libcrypto.so.1.0.0 =>\n/usr/lib/x86_64-linux-gnu/libcrypto.so.1.0.0 (0x00007f768fb0a000)\n            libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0\n(0x00007f768f8ed000)\n            libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f768f566000)\n            libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x00007f768f362000)\n            /lib64/ld-linux-x86-64.so.2 (0x00007f7690117000\n"},{"id":"200483","messageId":"CACBZZX4Fb0OCkh5kwKvLC+_0xb7q-UB7LH2_WY=dFN5SYUeezQ@mail.gmail.com","threadId":"31720","inReplyTo":"20121003180324.GB27446@sigill.intra.peff.net","subject":"Re: upload-pack is slow with lots of refs","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2012-10-03T22:32:35Z","receivedAt":"2012-10-03T22:32:35Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Wed, Oct 3, 2012 at 8:03 PM, Jeff King <peff@peff.net> wrote:\n> What version of git are you using?  In the past year or so, I've made\n> several tweaks to speed up large numbers of refs, including:\n>\n>   - cff38a5 (receive-pack: eliminate duplicate .have refs, v1.7.6); note\n>     that this only helps if they are being pulled in by an alternates\n>     repo. And even then, it only helps if they are mostly duplicates;\n>     distinct ones are still O(n^2).\n>\n>   - 7db8d53 (fetch-pack: avoid quadratic behavior in remove_duplicates)\n>     a0de288 (fetch-pack: avoid quadratic loop in filter_refs)\n>     Both in v1.7.11. I think there is still a potential quadratic loop\n>     in mark_complete()\n>\n>   - 90108a2 (upload-pack: avoid parsing tag destinations)\n>     926f1dd (upload-pack: avoid parsing objects during ref advertisement)\n>     Both in v1.7.10. Note that tag objects are more expensive to\n>     advertise than commits, because we have to load and peel them.\n>\n> Even with those patches, though, I found that it was something like ~2s\n> to advertise 100,000 refs.\n\nFWIW I bisected between 1.7.9 and 1.7.10 and found that the point at\nwhich it went from 1.5/s to 2.5/s upload-pack runs on the pathological\ngit.git repository was none of those, but:\n\n    ccdc6037fe - parse_object: try internal cache before reading object db\n"},{"id":"200484","messageId":"20121003231529.GA11618@sigill.intra.peff.net","threadId":"31720","inReplyTo":"CACBZZX6yMfeOx6x4iy8beq5niy9HvPq0c8ND5jZkoiJWAgVjfw@mail.gmail.com","subject":"Re: upload-pack is slow with lots of refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-03T23:15:29Z","receivedAt":"2012-10-03T23:15:29Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 04, 2012 at 12:15:47AM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> I think he was wrong, I tested this on git.git by first creating a lot\n> of tags:\n> \n>      parallel --eta \"git tag -a -m\"{}\" test-again-{}\" ::: $(git rev-list HEAD)\n> \n> Then doing:\n> \n>     git pack-refs --all\n>     git repack -A -d\n> \n> And compiled with -g -O3 I get around 1.55 runs/s of git-upload-pack\n> on 1.7.8 and 2.59/s on the master branch.\n\nThanks for the update, that's more like what I expected.\n\n> FWIW here are my results on the above pathological git.git\n> \n>     $ uname -r; perf --version; echo 0000 | perf record\n> ./git-upload-pack .>/dev/null; perf report | grep -v ^# | head\n>     3.2.0-2-amd64\n>     perf version 3.2.17\n>     [ perf record: Woken up 1 times to write data ]\n>     [ perf record: Captured and wrote 0.026 MB perf.data (~1131 samples) ]\n>         29.08%  git-upload-pack  libz.so.1.2.7       [.] inflate\n>         17.99%  git-upload-pack  libz.so.1.2.7       [.] 0xaec1\n>          6.21%  git-upload-pack  libc-2.13.so        [.] 0x117503\n>          5.69%  git-upload-pack  libcrypto.so.1.0.0  [.] 0x82c3d\n>          4.87%  git-upload-pack  git-upload-pack     [.] find_pack_entry_one\n>          3.18%  git-upload-pack  ld-2.13.so          [.] 0x886e\n>          2.96%  git-upload-pack  libc-2.13.so        [.] vfprintf\n>          2.83%  git-upload-pack  git-upload-pack     [.] search_for_subdir\n>          1.56%  git-upload-pack  [kernel.kallsyms]   [k] do_raw_spin_lock\n>          1.36%  git-upload-pack  libc-2.13.so        [.] vsnprintf\n> \n> I wonder why your report doesn't note any time in libz. This is on\n> Debian testing, maybe your OS uses different strip settings so it\n> doesn't show up?\n\nMine was on Debian unstable. The difference is probably that I have 400K\nrefs, but only 12K unique ones (this is the master alternates repo\ncontaining every ref from every fork of rails/rails on GitHub). So I\nspend proportionally more time fiddling with refs and outputting than\nI do actually inflating tag objects.\n\nHmm. It seems like we should not need to open the tags at all. The main\nreason is to produce the \"peeled\" advertisement just after it. But for a\npacked ref with a modern version of git that supports the \"peeled\"\nextension, we should already have that information.\n\nThe hack-ish patch below tries to reuse that. The interface is terrible,\nand we should probably just pass the peel information via for_each_ref\n(peel_ref tries to do a similar thing, but it also has a bad interface;\nif we don't have the information already, it will redo the ref lookup.\nWe could probably get away with a peel_sha1 which uses the same\noptimization trick as peel_ref).\n\nWith this patch my 800ms upload-pack drops to 600ms. I suspect it will\nhave an even greater impact for you, since you are spending much more of\nyour time on object loading than I am.\n\nAnd note of course that while these micro-optimizations are neat, we're\nstill going to end up shipping quite a lot of data over the wire. Moving\nto a protocol where we are advertising fewer refs would solve a lot more\nproblems in the long run.\n\n---\ndiff --git a/refs.c b/refs.c\nindex 551a0f9..68eca3a 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -510,6 +510,14 @@ static struct ref_entry *current_ref;\n \n static struct ref_entry *current_ref;\n \n+/* XXX horrible interface due to implied argument. not for real use */\n+const unsigned char *peel_current_ref(void)\n+{\n+\tif (!current_ref || !(current_ref->flag & REF_KNOWS_PEELED))\n+\t\treturn NULL;\n+\treturn current_ref->u.value.peeled;\n+}\n+\n static int do_one_ref(const char *base, each_ref_fn fn, int trim,\n \t\t      int flags, void *cb_data, struct ref_entry *entry)\n {\ndiff --git a/refs.h b/refs.h\nindex 9d14558..88c5445 100644\n--- a/refs.h\n+++ b/refs.h\n@@ -14,6 +14,8 @@ struct ref_lock {\n #define REF_ISPACKED 0x02\n #define REF_ISBROKEN 0x04\n \n+const unsigned char *peel_current_ref(void);\n+\n /*\n  * Calls the specified function for each ref file until it returns\n  * nonzero, and returns the value.  Please note that it is not safe to\ndiff --git a/upload-pack.c b/upload-pack.c\nindex 8f4703b..cdf43b0 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -736,8 +736,9 @@ static int send_ref(const char *refname, const unsigned char *sha1, int flag, vo\n \t\t\" include-tag multi_ack_detailed\";\n \tstruct object *o = lookup_unknown_object(sha1);\n \tconst char *refname_nons = strip_namespace(refname);\n+\tconst unsigned char *peeled = peel_current_ref();\n \n-\tif (o->type == OBJ_NONE) {\n+\tif (!peeled && o->type == OBJ_NONE) {\n \t\to->type = sha1_object_info(sha1, NULL);\n \t\tif (o->type < 0)\n \t\t    die(\"git upload-pack: cannot find object %s:\", sha1_to_hex(sha1));\n@@ -756,11 +757,13 @@ static int send_ref(const char *refname, const unsigned char *sha1, int flag, vo\n \t\to->flags |= OUR_REF;\n \t\tnr_our_refs++;\n \t}\n-\tif (o->type == OBJ_TAG) {\n+\tif (!peeled && o->type == OBJ_TAG) {\n \t\to = deref_tag_noverify(o);\n \t\tif (o)\n-\t\t\tpacket_write(1, \"%s %s^{}\\n\", sha1_to_hex(o->sha1), refname_nons);\n+\t\t\tpeeled = o->sha1;\n \t}\n+\tif (peeled && !is_null_sha1(peeled))\n+\t\tpacket_write(1, \"%s %s^{}\\n\", sha1_to_hex(peeled), refname_nons);\n \treturn 0;\n }\n \n"},{"id":"200475","messageId":"20121003232115.GB11618@sigill.intra.peff.net","threadId":"31720","inReplyTo":"CACBZZX4Fb0OCkh5kwKvLC+_0xb7q-UB7LH2_WY=dFN5SYUeezQ@mail.gmail.com","subject":"Re: upload-pack is slow with lots of refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-03T23:21:15Z","receivedAt":"2012-10-03T23:21:15Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 04, 2012 at 12:32:35AM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> On Wed, Oct 3, 2012 at 8:03 PM, Jeff King <peff@peff.net> wrote:\n> > What version of git are you using?  In the past year or so, I've made\n> > several tweaks to speed up large numbers of refs, including:\n> >\n> >   - cff38a5 (receive-pack: eliminate duplicate .have refs, v1.7.6); note\n> >     that this only helps if they are being pulled in by an alternates\n> >     repo. And even then, it only helps if they are mostly duplicates;\n> >     distinct ones are still O(n^2).\n> >\n> >   - 7db8d53 (fetch-pack: avoid quadratic behavior in remove_duplicates)\n> >     a0de288 (fetch-pack: avoid quadratic loop in filter_refs)\n> >     Both in v1.7.11. I think there is still a potential quadratic loop\n> >     in mark_complete()\n> >\n> >   - 90108a2 (upload-pack: avoid parsing tag destinations)\n> >     926f1dd (upload-pack: avoid parsing objects during ref advertisement)\n> >     Both in v1.7.10. Note that tag objects are more expensive to\n> >     advertise than commits, because we have to load and peel them.\n> >\n> > Even with those patches, though, I found that it was something like ~2s\n> > to advertise 100,000 refs.\n> \n> FWIW I bisected between 1.7.9 and 1.7.10 and found that the point at\n> which it went from 1.5/s to 2.5/s upload-pack runs on the pathological\n> git.git repository was none of those, but:\n> \n>     ccdc6037fe - parse_object: try internal cache before reading object db\n\nAh, yeah, I forgot about that one. That implies that you have a lot of\nrefs pointing to the same objects (since the benefit of that commit is\nto avoid reading from disk when we have already seen it).\n\nOut of curiosity, what does your repo contain? I saw a lot of speedup\nwith that commit because my repos are big object stores, where we have\nthe same duplicated tag refs for every fork of the repo.\n\n-Peff\n"},{"id":"200485","messageId":"CACBZZX764OOH82CiLYPr+_qNU65U4Zxuod_7G5ef8yAtHApXog@mail.gmail.com","threadId":"31720","inReplyTo":"20121003232115.GB11618@sigill.intra.peff.net","subject":"Re: upload-pack is slow with lots of refs","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2012-10-03T23:47:00Z","receivedAt":"2012-10-03T23:47:00Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Thu, Oct 4, 2012 at 1:21 AM, Jeff King <peff@peff.net> wrote:\n> On Thu, Oct 04, 2012 at 12:32:35AM +0200, Ævar Arnfjörð Bjarmason wrote:\n>\n>> On Wed, Oct 3, 2012 at 8:03 PM, Jeff King <peff@peff.net> wrote:\n>> > What version of git are you using?  In the past year or so, I've made\n>> > several tweaks to speed up large numbers of refs, including:\n>> >\n>> >   - cff38a5 (receive-pack: eliminate duplicate .have refs, v1.7.6); note\n>> >     that this only helps if they are being pulled in by an alternates\n>> >     repo. And even then, it only helps if they are mostly duplicates;\n>> >     distinct ones are still O(n^2).\n>> >\n>> >   - 7db8d53 (fetch-pack: avoid quadratic behavior in remove_duplicates)\n>> >     a0de288 (fetch-pack: avoid quadratic loop in filter_refs)\n>> >     Both in v1.7.11. I think there is still a potential quadratic loop\n>> >     in mark_complete()\n>> >\n>> >   - 90108a2 (upload-pack: avoid parsing tag destinations)\n>> >     926f1dd (upload-pack: avoid parsing objects during ref advertisement)\n>> >     Both in v1.7.10. Note that tag objects are more expensive to\n>> >     advertise than commits, because we have to load and peel them.\n>> >\n>> > Even with those patches, though, I found that it was something like ~2s\n>> > to advertise 100,000 refs.\n>>\n>> FWIW I bisected between 1.7.9 and 1.7.10 and found that the point at\n>> which it went from 1.5/s to 2.5/s upload-pack runs on the pathological\n>> git.git repository was none of those, but:\n>>\n>>     ccdc6037fe - parse_object: try internal cache before reading object db\n>\n> Ah, yeah, I forgot about that one. That implies that you have a lot of\n> refs pointing to the same objects (since the benefit of that commit is\n> to avoid reading from disk when we have already seen it).\n>\n> Out of curiosity, what does your repo contain? I saw a lot of speedup\n> with that commit because my repos are big object stores, where we have\n> the same duplicated tag refs for every fork of the repo.\n\nThings are much faster with your monkeypatch, got up to around 10\nruns/s.\n\nThe repository mainly contains a lot of git-deploy[1] generated tags\nwhich are added for every rollout to several subsystems.\n\nOf the ~50k references in the repo 75% point to a commit that no other\nreference points to. Around 98% of the references are annotated tags,\nthe rest are branches.\n\n1. https://github.com/git-deploy/git-deploy\n"},{"id":"200480","messageId":"CACBZZX5Sm++Wjyoue-qk7TjwxUM3QihXfWGtEHhOq=VtkgvNbQ@mail.gmail.com","threadId":"31720","inReplyTo":"20121003231529.GA11618@sigill.intra.peff.net","subject":"Re: upload-pack is slow with lots of refs","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2012-10-03T23:54:47Z","receivedAt":"2012-10-03T23:54:47Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Thu, Oct 4, 2012 at 1:15 AM, Jeff King <peff@peff.net> wrote:\n> On Thu, Oct 04, 2012 at 12:15:47AM +0200, Ævar Arnfjörð Bjarmason wrote:\n>\n>> I think he was wrong, I tested this on git.git by first creating a lot\n>> of tags:\n>>\n>>      parallel --eta \"git tag -a -m\"{}\" test-again-{}\" ::: $(git rev-list HEAD)\n>>\n>> Then doing:\n>>\n>>     git pack-refs --all\n>>     git repack -A -d\n>>\n>> And compiled with -g -O3 I get around 1.55 runs/s of git-upload-pack\n>> on 1.7.8 and 2.59/s on the master branch.\n>\n> Thanks for the update, that's more like what I expected.\n>\n>> FWIW here are my results on the above pathological git.git\n>>\n>>     $ uname -r; perf --version; echo 0000 | perf record\n>> ./git-upload-pack .>/dev/null; perf report | grep -v ^# | head\n>>     3.2.0-2-amd64\n>>     perf version 3.2.17\n>>     [ perf record: Woken up 1 times to write data ]\n>>     [ perf record: Captured and wrote 0.026 MB perf.data (~1131 samples) ]\n>>         29.08%  git-upload-pack  libz.so.1.2.7       [.] inflate\n>>         17.99%  git-upload-pack  libz.so.1.2.7       [.] 0xaec1\n>>          6.21%  git-upload-pack  libc-2.13.so        [.] 0x117503\n>>          5.69%  git-upload-pack  libcrypto.so.1.0.0  [.] 0x82c3d\n>>          4.87%  git-upload-pack  git-upload-pack     [.] find_pack_entry_one\n>>          3.18%  git-upload-pack  ld-2.13.so          [.] 0x886e\n>>          2.96%  git-upload-pack  libc-2.13.so        [.] vfprintf\n>>          2.83%  git-upload-pack  git-upload-pack     [.] search_for_subdir\n>>          1.56%  git-upload-pack  [kernel.kallsyms]   [k] do_raw_spin_lock\n>>          1.36%  git-upload-pack  libc-2.13.so        [.] vsnprintf\n>>\n>> I wonder why your report doesn't note any time in libz. This is on\n>> Debian testing, maybe your OS uses different strip settings so it\n>> doesn't show up?\n>\n> Mine was on Debian unstable. The difference is probably that I have 400K\n> refs, but only 12K unique ones (this is the master alternates repo\n> containing every ref from every fork of rails/rails on GitHub). So I\n> spend proportionally more time fiddling with refs and outputting than\n> I do actually inflating tag objects.\n\nAn updated profile with your patch:\n\n    $ uname -r; perf --version; echo 0000 | perf record\n./git-upload-pack .>/dev/null; perf report | grep -v ^# | head\n    3.2.0-2-amd64\n    perf version 3.2.17\n    [ perf record: Woken up 1 times to write data ]\n    [ perf record: Captured and wrote 0.015 MB perf.data (~662 samples) ]\n        14.45%  git-upload-pack  libc-2.13.so        [.] 0x78140\n        12.13%  git-upload-pack  [kernel.kallsyms]   [k] walk_component\n        11.01%  git-upload-pack  libc-2.13.so        [.] _IO_getline_info\n        10.74%  git-upload-pack  git-upload-pack     [.] find_pack_entry_one\n         8.96%  git-upload-pack  [kernel.kallsyms]   [k] __mmdrop\n         8.64%  git-upload-pack  git-upload-pack     [.] sha1_to_hex\n         6.73%  git-upload-pack  libc-2.13.so        [.] vfprintf\n         4.07%  git-upload-pack  libc-2.13.so        [.] strchrnul\n         4.00%  git-upload-pack  libc-2.13.so        [.] getenv\n         3.37%  git-upload-pack  git-upload-pack     [.] packet_write\n\n> Hmm. It seems like we should not need to open the tags at all. The main\n> reason is to produce the \"peeled\" advertisement just after it. But for a\n> packed ref with a modern version of git that supports the \"peeled\"\n> extension, we should already have that information.\n\nB.t.w. do you plan to submit this as a non-hack, I'd like to have it\nin git.git, so if you're not going to I could pick it up and clean it\nup a bit. But I think it would be better coming from you.\n"},{"id":"200539","messageId":"7939878.c2fCDAx1ds@blacky","threadId":"31720","inReplyTo":"20121003201316.GA4484@sigill.intra.peff.net","subject":"Re: upload-pack is slow with lots of refs","fromName":"Sascha Cunz","fromEmail":"sascha-ml@babbelbox.org","sentAt":"2012-10-04T21:52:13Z","receivedAt":"2012-10-04T21:52:13Z","isPatch":false,"sender":{"key":"sascha-ml@babbelbox.org","avatar":null},"body":"Am Mittwoch, 3. Oktober 2012, 16:13:16 schrieb Jeff King:\n> On Wed, Oct 03, 2012 at 12:41:38PM -0700, Shawn O. Pearce wrote:\n> > > Out of curiosity, how are you thinking about triggering such a new\n> > > behavior in a backwards-compatible way? Invoke git-upload-pack2, and\n> > > fall back to reconnecting to start git-upload-pack if it fails?\n> > \n> > Basically, yes. New clients connect for git-upload-pack2. Over git://\n> > the remote peer will just close the TCP socket with no messages. The\n> > client can fallback to git-upload-pack and try again. Over SSH a\n> > similar thing will happen in the sense there is no data output from\n> > the remote side, so the client can try again. This has the downside of\n> > authentication twice over SSH, which may prompt for a password twice.\n> > But the user can get out of this by setting remote.NAME.uploadpack =\n> > git-upload-pack and thus force the Git client to use the current\n> > protocol if they have a new client and must continue to work over SSH\n> > with an old server, and don't use an ssh-agent.\n> \n> It's a shame that we have to reestablish the TCP or ssh connection to do\n> the retry. The password thing is annoying, but also it just wastes a\n> round-trip. It means we'd probably want to default the v2 probe to off\n> (and let the user turn it on for a specific remote) until v2 is much\n> more common than v1. Otherwise everyone pays the price.\n\nWould it be possible to use this workflow:\n\n- Every client connects per default to v1\n\n- If server is capable of v2, it sends a flag along with the usual response\n  (A v1 server will obviously not send that flag)\n\n- If client is also capable of v2 and gets the flag, it enables v2 for\n  just that remote (probably unless the user said, \"i never want to\")\n\n- Next time the client connects to that remote it will use v2.\n\nI'm not sure, if this is possible, since I think to remember that I have read \nin the Documentation folder something along the line: Capabilities announced \nfrom the server mean \"I want you to use exactly these flags\".\n\nSascha\n"},{"id":"200576","messageId":"20121005002048.GA17586@sigill.intra.peff.net","threadId":"31720","inReplyTo":"7939878.c2fCDAx1ds@blacky","subject":"Re: upload-pack is slow with lots of refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-05T00:20:48Z","receivedAt":"2012-10-05T00:20:48Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 04, 2012 at 11:52:13PM +0200, Sascha Cunz wrote:\n\n> Would it be possible to use this workflow:\n> \n> - Every client connects per default to v1\n> \n> - If server is capable of v2, it sends a flag along with the usual response\n>   (A v1 server will obviously not send that flag)\n\nThat is more or less the strategy we use for existing extensions (your\n\"flag\" is a space-separated list of capability strings). But in this\ncase, the idea would be to change what the \"usual response\" is. Since a\nv1 client would be expecting the response, we must send it, but at that\npoint it is too late to make the change. So we need to see some flag\nfrom the client before the server says anything.\n\nAnd the problem is that the client sending that flag will break v1\nservers, and the client would need to waste time doing a retry when\nconnecting to the (initially more common) v1 servers.\n\n> - If client is also capable of v2 and gets the flag, it enables v2 for\n>   just that remote (probably unless the user said, \"i never want to\")\n> \n> - Next time the client connects to that remote it will use v2.\n\nSo yeah, that would work to help with the wasted time. We'd have\ngit-upload-pack2 to do the v2 protocol, but the v1 git-upload-pack for\nthe server would say \"by the way, next time you connect, try v2 first\".\nSo the client would have to store a version number for each remote.\nWhich is not too onerous.\n\nAnother way to think of it is phasing it in like this:\n\n  1. Add v2 support to client and server. Initially, clients try only\n     v1.\n\n  2. Add a remote.*.preferProtocol config option, defaulting to v1. This\n     lets people turn on v2 for remotes they know support it. If v2\n     fails, still fall back to v1.\n\n  3. Add a server upload-pack capability that says \"by the way, try v2\n     next time\".  Have the client set the preferProtocol config option\n     for a remote if we see that capability.\n\n  4. Wait a while until v2 is very popular.\n\n  5. Switch the default for preferProtocol to v2 (but still fall back to\n     v1).\n\nSo always fall back and remain compatible, and let the config option\njust be an optimization to avoid extra failed requests.\n\n> I'm not sure, if this is possible, since I think to remember that I have read \n> in the Documentation folder something along the line: Capabilities announced \n> from the server mean \"I want you to use exactly these flags\".\n\nNo, the server capability says \"I can do this\", and the client should\nrespond with \"I want you to do this\". Because the server might be\ntalking to an older client that does not know what \"this\" is, it must\nhandle the case that the capability does not come back.\n\n-Peff\n"},{"id":"200591","messageId":"506E7D01.8080509@viscovery.net","threadId":"31720","inReplyTo":"CAJo=hJtZ_8H6+kXPpZcRCbJi3LPuuF7M1U8YsjAp-iWvut9oMw@mail.gmail.com","subject":"Re: upload-pack is slow with lots of refs","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2012-10-05T06:24:01Z","receivedAt":"2012-10-05T06:24:01Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 10/3/2012 21:41, schrieb Shawn Pearce:\n> On Wed, Oct 3, 2012 at 11:55 AM, Jeff King <peff@peff.net> wrote:\n>> On Wed, Oct 03, 2012 at 11:53:35AM -0700, Junio C Hamano wrote:\n>>> Jeff King <peff@peff.net> writes:\n>>>\n>>>>> Has there been any work on extending the protocol so that the client\n>>>>> tells the server what refs it's interested in?\n>>>>\n>>>> I don't think so. It would be hard to do in a backwards-compatible way,\n>>>> because the advertisement is the first thing the server says, before it\n>>>> has negotiated any capabilities with the client at all.\n>>>\n>>> That is being discussed but hasn't surfaced on the list.\n>>\n>> Out of curiosity, how are you thinking about triggering such a new\n>> behavior in a backwards-compatible way? Invoke git-upload-pack2, and\n>> fall back to reconnecting to start git-upload-pack if it fails?\n> \n> Basically, yes. New clients connect for git-upload-pack2. Over git://\n> the remote peer will just close the TCP socket with no messages. The\n> client can fallback to git-upload-pack and try again. Over SSH a\n> similar thing will happen in the sense there is no data output from\n> the remote side, so the client can try again.\n\nThese connections are bidirectional. Upload-pack can just start\nadvertising refs in the \"v1\" way and announce a \"v2\" capability and listen\nfor response in parallel. A v2 capable client can start sending \"wants\" or\nsome other signal as soon as it sees the \"v2\" capability. Upload-pack,\nwhich was listening for responses in parallel, can interrupt its\nadvertisements and continue with v2 protocol from here.\n\nThis sounds so simple (not the implementation, of course) - I must be\nmissing something.\n\n-- Hannes\n"},{"id":"200631","messageId":"CAJo=hJsYVdWeG0ZyqexEXNfOq_k1XDR_gGP+fy_z==LvdnWJTQ@mail.gmail.com","threadId":"31720","inReplyTo":"506E7D01.8080509@viscovery.net","subject":"Re: upload-pack is slow with lots of refs","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-10-05T16:57:41Z","receivedAt":"2012-10-05T16:57:41Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Thu, Oct 4, 2012 at 11:24 PM, Johannes Sixt <j.sixt@viscovery.net> wrote:\n> Am 10/3/2012 21:41, schrieb Shawn Pearce:\n>> On Wed, Oct 3, 2012 at 11:55 AM, Jeff King <peff@peff.net> wrote:\n>>> On Wed, Oct 03, 2012 at 11:53:35AM -0700, Junio C Hamano wrote:\n>>>> Jeff King <peff@peff.net> writes:\n>>>>\n>>>>>> Has there been any work on extending the protocol so that the client\n>>>>>> tells the server what refs it's interested in?\n>>>>>\n>>>>> I don't think so. It would be hard to do in a backwards-compatible way,\n>>>>> because the advertisement is the first thing the server says, before it\n>>>>> has negotiated any capabilities with the client at all.\n>>>>\n>>>> That is being discussed but hasn't surfaced on the list.\n>>>\n>>> Out of curiosity, how are you thinking about triggering such a new\n>>> behavior in a backwards-compatible way? Invoke git-upload-pack2, and\n>>> fall back to reconnecting to start git-upload-pack if it fails?\n>>\n>> Basically, yes. New clients connect for git-upload-pack2. Over git://\n>> the remote peer will just close the TCP socket with no messages. The\n>> client can fallback to git-upload-pack and try again. Over SSH a\n>> similar thing will happen in the sense there is no data output from\n>> the remote side, so the client can try again.\n>\n> These connections are bidirectional.\n\nSmart HTTP is not bidirectional.\n\n> Upload-pack can just start\n> advertising refs in the \"v1\" way and announce a \"v2\" capability and listen\n> for response in parallel. A v2 capable client can start sending \"wants\" or\n> some other signal as soon as it sees the \"v2\" capability. Upload-pack,\n> which was listening for responses in parallel, can interrupt its\n> advertisements and continue with v2 protocol from here.\n>\n> This sounds so simple (not the implementation, of course) - I must be\n> missing something.\n\nSmart HTTP is not bidirectional. The client can't cut off the server.\nIts also more complex to code the server to listen for a stop command\nfrom the client at the same time the server is blasting out useless\nreferences to the client.\n"},{"id":"200748","messageId":"5072EBD1.40500@kdbg.org","threadId":"31720","inReplyTo":"CAJo=hJsYVdWeG0ZyqexEXNfOq_k1XDR_gGP+fy_z==LvdnWJTQ@mail.gmail.com","subject":"Re: upload-pack is slow with lots of refs","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2012-10-08T15:05:53Z","receivedAt":"2012-10-08T15:05:53Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 05.10.2012 18:57, schrieb Shawn Pearce:\n> On Thu, Oct 4, 2012 at 11:24 PM, Johannes Sixt <j.sixt@viscovery.net> wrote:\n>> Upload-pack can just start\n>> advertising refs in the \"v1\" way and announce a \"v2\" capability and listen\n>> for response in parallel. A v2 capable client can start sending \"wants\" or\n>> some other signal as soon as it sees the \"v2\" capability. Upload-pack,\n>> which was listening for responses in parallel, can interrupt its\n>> advertisements and continue with v2 protocol from here.\n>>\n>> This sounds so simple (not the implementation, of course) - I must be\n>> missing something.\n> \n> Smart HTTP is not bidirectional. The client can't cut off the server.\n\nSmart HTTP does not need it: you already posted a better solution (I'm\nrefering to \"&v=2\").\n\n> Its also more complex to code the server to listen for a stop command\n> from the client at the same time the server is blasting out useless\n> references to the client.\n\nAt least the server side does not seem to be that complex. See below.\nOf course, the server blasted out some refs, but I'm confident that in\npractice the client will be able to signal v2 capability after a few packets\nof advertisements. You can switch on TCP_NODELAY for the first line with\nthe capabilities to ensure it goes out on the wire ASAP.\n\ndiff --git a/upload-pack.c b/upload-pack.c\nindex 2e90ccb..c29ae04 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -720,11 +720,20 @@ static void receive_needs(void)\n \tfree(shallows.objects);\n }\n \n+static int client_spoke(void)\n+{\n+\tstruct pollfd pfd;\n+\tpfd.fd = 0;\n+\tpfd.events = POLLIN;\n+\treturn poll(&pfd, 1, 0) > 0 &&\n+\t\t(pfd.revents & (POLLIN|POLLHUP));\n+}\n+\n static int send_ref(const char *refname, const unsigned char *sha1, int flag, void *cb_data)\n {\n \tstatic const char *capabilities = \"multi_ack thin-pack side-band\"\n \t\t\" side-band-64k ofs-delta shallow no-progress\"\n-\t\t\" include-tag multi_ack_detailed\";\n+\t\t\" include-tag multi_ack_detailed version2\";\n \tstruct object *o = lookup_unknown_object(sha1);\n \tconst char *refname_nons = strip_namespace(refname);\n \n@@ -752,7 +761,8 @@ static int send_ref(const char *refname, const unsigned char *sha1, int flag, vo\n \t\tif (o)\n \t\t\tpacket_write(1, \"%s %s^{}\\n\", sha1_to_hex(o->sha1), refname_nons);\n \t}\n-\treturn 0;\n+\n+\treturn client_spoke();\n }\n \n static int mark_our_ref(const char *refname, const unsigned char *sha1, int flag, void *cb_data)\n@@ -771,8 +781,14 @@ static void upload_pack(void)\n {\n \tif (advertise_refs || !stateless_rpc) {\n \t\treset_timeout();\n-\t\thead_ref_namespaced(send_ref, NULL);\n-\t\tfor_each_namespaced_ref(send_ref, NULL);\n+\t\tif (head_ref_namespaced(send_ref, NULL) ||\n+\t\t    for_each_namespaced_ref(send_ref, NULL)) {\n+\t\t\t/*\n+\t\t\t * TODO: continue with protocol version 2\n+\t\t\t * optimization: do not send refs\n+\t\t\t * that were already sent\n+\t\t\t */\n+\t\t}\n \t\tpacket_flush(1);\n \t} else {\n \t\thead_ref_namespaced(mark_our_ref, NULL);\n"},{"id":"200818","messageId":"CAJo=hJsJgqZqPxucRcSgYSa0N3pcw5seT9vcu2BE8WwfJVrvKQ@mail.gmail.com","threadId":"31720","inReplyTo":"5072EBD1.40500@kdbg.org","subject":"Re: upload-pack is slow with lots of refs","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-10-09T06:46:05Z","receivedAt":"2012-10-09T06:46:05Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Oct 8, 2012 at 8:05 AM, Johannes Sixt <j6t@kdbg.org> wrote:\n> Am 05.10.2012 18:57, schrieb Shawn Pearce:\n>> On Thu, Oct 4, 2012 at 11:24 PM, Johannes Sixt <j.sixt@viscovery.net> wrote:\n>>> Upload-pack can just start\n>>> advertising refs in the \"v1\" way and announce a \"v2\" capability and listen\n>>> for response in parallel. A v2 capable client can start sending \"wants\" or\n>>> some other signal as soon as it sees the \"v2\" capability. Upload-pack,\n>>> which was listening for responses in parallel, can interrupt its\n>>> advertisements and continue with v2 protocol from here.\n>>>\n>>> This sounds so simple (not the implementation, of course) - I must be\n>>> missing something.\n>>\n>> Smart HTTP is not bidirectional. The client can't cut off the server.\n>\n> Smart HTTP does not need it: you already posted a better solution (I'm\n> refering to \"&v=2\").\n\nYes but then it diverges even further from the native bidirectional protocol.\n\n>> Its also more complex to code the server to listen for a stop command\n>> from the client at the same time the server is blasting out useless\n>> references to the client.\n>\n> At least the server side does not seem to be that complex. See below.\n> Of course, the server blasted out some refs, but I'm confident that in\n> practice the client will be able to signal v2 capability after a few packets\n> of advertisements. You can switch on TCP_NODELAY for the first line with\n> the capabilities to ensure it goes out on the wire ASAP.\n...\n> +static int client_spoke(void)\n> +{\n> +       struct pollfd pfd;\n> +       pfd.fd = 0;\n> +       pfd.events = POLLIN;\n> +       return poll(&pfd, 1, 0) > 0 &&\n> +               (pfd.revents & (POLLIN|POLLHUP));\n\nExcept doing this in Java is harder on an arbitrary InputStream type.\nI guess we really only care about basic TCP, in which case we can use\nNIO to implement an emulation of poll, and SSH, where MINA SSHD\nprobably doesn't provide a way to see if the client has given us data\nwithout blocking. That makes supporting v2 really hard in e.g. Gerrit\nCode Review. You could argue that its improper to attempt to implement\na network protocol in a language whose standard libraries have gone\nout of their way to prevent you from polling to see if data is\nimmediately available, but I prefer to ignore such arguments.\n\nAs it turns out we don't really have this problem with git://. Clients\ncan bury a v2 request in the extended headers where the host line\nappears today. Its a bit tricky because of that \\0 bug causing\ninfinite looping, but IIRC using \\0\\0 is safe even against ancient\nservers. So git:// and http:// both have a way where the client can\nask for v2 support before the server speaks, and have it transparently\nbe ignored by ancient servers.\n\n\nThe only place we have a problem is SSH. That exec of the remote\nbinary is just super-strict. Its good to be paranoid, but its also\nlocked out any chance we have at doing the upgrade over SSH without\nhaving to run two SSH commands in the worst case. I guess the best\napproach is to try the v1 protocol by default, have the remote\nadvertise it supports v2, and remember this on a per-host basis in\n~/.gitconfig for future requests. Users could always force a specific\npreference with remote.NAME.uploadpack variable or --uploadpack\ncommand line flag.\n"},{"id":"200856","messageId":"5074894D.90307@kdbg.org","threadId":"31720","inReplyTo":"CAJo=hJsJgqZqPxucRcSgYSa0N3pcw5seT9vcu2BE8WwfJVrvKQ@mail.gmail.com","subject":"Re: upload-pack is slow with lots of refs","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2012-10-09T20:30:05Z","receivedAt":"2012-10-09T20:30:05Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 09.10.2012 08:46, schrieb Shawn Pearce:\n> On Mon, Oct 8, 2012 at 8:05 AM, Johannes Sixt <j6t@kdbg.org> wrote:\n>> Am 05.10.2012 18:57, schrieb Shawn Pearce:\n>>> Smart HTTP is not bidirectional. The client can't cut off the server.\n>>\n>> Smart HTTP does not need it: you already posted a better solution (I'm\n>> refering to \"&v=2\").\n> \n> Yes but then it diverges even further from the native bidirectional protocol.\n\nI won't argue here because I know next to nothing about Smart HTTP. But\nit sounds like you either have compatibility, but a diverging protocol\nor at least implementation, or no compatibility.\n\n>> +static int client_spoke(void)\n>> +{\n>> +       struct pollfd pfd;\n>> +       pfd.fd = 0;\n>> +       pfd.events = POLLIN;\n>> +       return poll(&pfd, 1, 0) > 0 &&\n>> +               (pfd.revents & (POLLIN|POLLHUP));\n> \n> Except doing this in Java is harder on an arbitrary InputStream type.\n> I guess we really only care about basic TCP, in which case we can use\n> NIO to implement an emulation of poll, and SSH, where MINA SSHD\n> probably doesn't provide a way to see if the client has given us data\n> without blocking. That makes supporting v2 really hard in e.g. Gerrit\n> Code Review. You could argue that its improper to attempt to implement\n> a network protocol in a language whose standard libraries have gone\n> out of their way to prevent you from polling to see if data is\n> immediately available, but I prefer to ignore such arguments.\n\nCan't you read the inbound stream in a second thread while the first\nthread writes the advertisements to the outbound stream? Then you don't\neven need to poll; you can just read the 4-byte length header, stash it\naway and set a flag. The implementation of client_spoke() would only\namount to check that flag.\n\n> As it turns out we don't really have this problem with git://. Clients\n> can bury a v2 request in the extended headers where the host line\n> appears today.\n\nI tried, but it seems that todays git-daemons are too strict and accept\nonly \\0host=foo\\0, nothing else :-(\n\n-- Hannes\n"},{"id":"200858","messageId":"50748D32.8020907@kdbg.org","threadId":"31720","inReplyTo":"5074894D.90307@kdbg.org","subject":"Re: upload-pack is slow with lots of refs","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2012-10-09T20:46:42Z","receivedAt":"2012-10-09T20:46:42Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 09.10.2012 22:30, schrieb Johannes Sixt:\n> Am 09.10.2012 08:46, schrieb Shawn Pearce:\n>> As it turns out we don't really have this problem with git://. Clients\n>> can bury a v2 request in the extended headers where the host line\n>> appears today.\n> \n> I tried, but it seems that todays git-daemons are too strict and accept\n> only \\0host=foo\\0, nothing else :-(\n\nI take that back: Modern git-daemons accept \"\\0host=foo\\0\\0version=2\\0\",\nas you said.\n\nIt looks like SSH is the only stubborn protocol.\n\n-- Hannes\n"}]}