{"thread":{"id":"40957","subject":"Why does send-pack call pack-objects for all remote refs?","startedAt":"2015-12-07T21:02:22Z","lastAt":"2015-12-14T22:37:18Z","messageCount":10,"participants":["Daniel Koverman","Junio C Hamano","Jeff King","Nasser Grainawi","Jonathan Nieder"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"274142","messageId":"4766c8518c2a46afb88fc0a2dd9a1688@EXCHANGE1U.uunet.arlington.PredictiveTechnologies.com","threadId":"40957","inReplyTo":null,"subject":"Why does send-pack call pack-objects for all remote refs?","fromName":"Daniel Koverman","fromEmail":"dkoverman@predictivetechnologies.com","sentAt":"2015-12-07T21:02:22Z","receivedAt":"2015-12-07T21:02:22Z","isPatch":false,"sender":{"key":"dkoverman@predictivetechnologies.com","avatar":null},"body":"I have a repository which has ~2000 branches on the remote, and it takes ~8 seconds to push a change to one ref. The majority of this time is spent in pack-object. I wrote a hack so that only the ref being updated would be packed (the normal behavior is to pack for every ref on the remote).  The push time dropped to <1 second with (seemingly) no consequences. This raised a couple of questions:\n\n1) Are there consequences for not packing refs that are not being updated? Can all operations in send-pack which operate on other refs be skipped?\n2) Why isn't git more selective about what it packs? Is it simply a performance optimization not worth the implementation complexity?\n3) Is something about my repository strange? ex: 2000 is too many branches, packing for each ref takes me an unusually long time, etc.\n\nThanks in advance to anyone who takes the time to clarify this for me.\n\nDaniel\n"},{"id":"274150","messageId":"xmqqvb89lw5f.fsf@gitster.mtv.corp.google.com","threadId":"40957","inReplyTo":"4766c8518c2a46afb88fc0a2dd9a1688@EXCHANGE1U.uunet.arlington.PredictiveTechnologies.com","subject":"Re: Why does send-pack call pack-objects for all remote refs?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-12-07T22:41:00Z","receivedAt":"2015-12-07T22:41:00Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Daniel Koverman <dkoverman@predictiveTechnologies.com> writes:\n\n> I have a repository which has ~2000 branches on the remote, and it\n> takes ~8 seconds to push a change to one ref. The majority of this\n> time is spent in pack-object. I wrote a hack so that only the ref\n> being updated would be packed (the normal behavior is to pack for\n> every ref on the remote).\n\nI am having a hard time understanding what you are trying to say, as\nnobody's pack-objects \"packs for a ref\" or \"packs a ref\", so my\nresponse has to be based on my best guess---I think you are talking\nabout feeding the object names of the tips of all remote refs as\nthe bottoms of the revision range to pack-objects.\n\nWhen you are pushing your 'topic' branch to update the 'topic'\nbranch at the remote, it is true that we compute\n\n\tgit rev-list --objects $your_topic --not $all_of_the_remote_refs\n\nto produce a packfile.  And by tweaking this to\n\n\tgit rev-list --objects $your_topic --not $their_topic\n\nyou will cut down the processing time of 'rev-list', especially if\nyou have insane number of refs at the remote end.\n\nThere is a price you would pay for doing so, though.  An obvious one\nis what if the 'topic' branch does not exist yet at the remote.\nWithout the \"--not ...\" part, you would end up sending the entire\nhistory behind $your_topic, and the way you prevent that from\nhappening is to give what are known to exist at the remote end.\nEven when there already is 'topic' at the remote, the contents at\nthe paths that are different between your 'topic' and the 'topic' as\nexists at the remote may already exist on some other branches that\nare already at the remote (e.g. you may have merged some branches\nthat are common between your repository and the remote, and the only\nobject missing from the remote that your repository has to send may\nbe a merge commit and the top-level tree object), but limiting the\nbottoms of the revision range only to \"--not $their_topic\" would rob\nthis obvious optimization opportunity from you.\n\nThere has to be some way to limit the list of remote-refs that are\nused as bottoms of the revision range.  For example, if you know\nthat the remote has all the tags, and that everything in the v1.0\ntag is contained in the v2.0 tag, then a single \"--not v2.0\" should\ngive the same result as \"--not v1.0 v2.0\" that lists both.  But the\ncomputation that is needed to figure out which tags and branches are\nnot worth listing as bottoms would need to look at all of them at\nleast once anyway, so a naive implementation of such would end up\nspending the same cycles, I would suspect.\n\nAlso it was unclear if you are working with a shallow repository.\nThe performance trade-off made between the packsize and the cycles\nis somewhat different between a normal and a shallow repository,\ne.g. 2dacf26d (pack-objects: use --objects-edge-aggressive for\nshallow repos, 2014-12-24) might be a good starting point to think\nabout this issue.\n"},{"id":"274156","messageId":"20151207225714.GA3785@sigill.intra.peff.net","threadId":"40957","inReplyTo":"xmqqvb89lw5f.fsf@gitster.mtv.corp.google.com","subject":"Re: Why does send-pack call pack-objects for all remote refs?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-12-07T22:57:14Z","receivedAt":"2015-12-07T22:57:14Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Dec 07, 2015 at 02:41:00PM -0800, Junio C Hamano wrote:\n\n> Also it was unclear if you are working with a shallow repository.\n> The performance trade-off made between the packsize and the cycles\n> is somewhat different between a normal and a shallow repository,\n> e.g. 2dacf26d (pack-objects: use --objects-edge-aggressive for\n> shallow repos, 2014-12-24) might be a good starting point to think\n> about this issue.\n\nAlso note that for a while the \"aggressive\" form was used everywhere. I\nthink that started in fbd4a70 (list-objects: mark more commits as edges\nin mark_edges_uninteresting - 2013-08-16), and was fixed in 1684c1b\n(rev-list: add an option to mark fewer edges as uninteresting,\n2014-12-24).\n\nSo it was present from v1.8.4.2 up to v2.3.0.\n\n-Peff\n"},{"id":"274186","messageId":"8712f730fb4c414ebc2b1168ca7948b8@EXCHANGE1U.uunet.arlington.PredictiveTechnologies.com","threadId":"40957","inReplyTo":"20151207225714.GA3785@sigill.intra.peff.net","subject":"RE: Why does send-pack call pack-objects for all remote refs?","fromName":"Daniel Koverman","fromEmail":"dkoverman@predictivetechnologies.com","sentAt":"2015-12-08T17:34:43Z","receivedAt":"2015-12-08T17:34:43Z","isPatch":false,"sender":{"key":"dkoverman@predictivetechnologies.com","avatar":null},"body":"Your interpretation of my email was correct. As you picked up on, I\nhad a fundamental misunderstanding of what pack-objects was doing.\nThanks for the explanation, I have a much better idea of what is\ngoing on now.\n\nGiven my use pattern, it may be reasonable for me to patch in an\noption to compute\n\n    git rev-list --objects $my_topic --not $subset_of_remote_refs\n\ncapitalizing on my knowledge of this particular repository to come\nup with heuristics for picking a reasonable subset. This will\ncome with the risk of sometimes producing an unnecessarily large\n(potentially an obscenely large) packfile. You have thoroughly\nconvinced me that an option like that will not generalize and would\nbe unsuitable for main line git.\n\nIt is also good to know that 2000 remote refs is insane. The lower\nhanging fruit here sounds like trimming that to a reasonable\nnumber, so I'll try that approach first.\n\nThanks again, Junio and Peff.\n\nDaniel\n\n-----Original Message-----\nFrom: Jeff King [mailto:peff@peff.net] \nSent: Monday, December 07, 2015 5:57 PM\nTo: Daniel Koverman\nCc: Junio C Hamano; git@vger.kernel.org\nSubject: Re: Why does send-pack call pack-objects for all remote refs?\n\nOn Mon, Dec 07, 2015 at 02:41:00PM -0800, Junio C Hamano wrote:\n\n> Also it was unclear if you are working with a shallow repository.\n> The performance trade-off made between the packsize and the cycles\n> is somewhat different between a normal and a shallow repository,\n> e.g. 2dacf26d (pack-objects: use --objects-edge-aggressive for\n> shallow repos, 2014-12-24) might be a good starting point to think\n> about this issue.\n\nAlso note that for a while the \"aggressive\" form was used everywhere. I\nthink that started in fbd4a70 (list-objects: mark more commits as edges\nin mark_edges_uninteresting - 2013-08-16), and was fixed in 1684c1b\n(rev-list: add an option to mark fewer edges as uninteresting,\n2014-12-24).\n\nSo it was present from v1.8.4.2 up to v2.3.0.\n\n-Peff\n"},{"id":"274225","messageId":"20151210041941.GA4056@sigill.intra.peff.net","threadId":"40957","inReplyTo":"8712f730fb4c414ebc2b1168ca7948b8@EXCHANGE1U.uunet.arlington.PredictiveTechnologies.com","subject":"Re: Why does send-pack call pack-objects for all remote refs?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-12-10T04:19:42Z","receivedAt":"2015-12-10T04:19:42Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Dec 08, 2015 at 05:34:43PM +0000, Daniel Koverman wrote:\n\n> Your interpretation of my email was correct. As you picked up on, I\n> had a fundamental misunderstanding of what pack-objects was doing.\n> Thanks for the explanation, I have a much better idea of what is\n> going on now.\n> \n> Given my use pattern, it may be reasonable for me to patch in an\n> option to compute\n> \n>     git rev-list --objects $my_topic --not $subset_of_remote_refs\n\nYou might also try repacking with \"git repack -adb\", which will build\nreachability bitmaps. Pack-objects can use them to compute the set of\nrequired objects much faster.\n\n> It is also good to know that 2000 remote refs is insane. The lower\n> hanging fruit here sounds like trimming that to a reasonable\n> number, so I'll try that approach first.\n\nIt's definitely a lot, but it's not unheard of. The git project has over\n500 tags. That's not 2000, but you're within an order of magnitude.\n\nI have seen repositories with 20,000+ tags. I consider that a bit more\nridiculous, but it does work in practice.\n\n-Peff\n"},{"id":"274313","messageId":"EC1A4F48-729B-4DC5-ADB4-C0BEAE104908@codeaurora.org","threadId":"40957","inReplyTo":"20151210041941.GA4056@sigill.intra.peff.net","subject":"Re: Why does send-pack call pack-objects for all remote refs?","fromName":"Nasser Grainawi","fromEmail":"nasser@codeaurora.org","sentAt":"2015-12-12T04:15:17Z","receivedAt":"2015-12-12T04:15:17Z","isPatch":false,"sender":{"key":"nasser@codeaurora.org","avatar":"https://avatars.githubusercontent.com/u/757421?v=4"},"body":"\n> On Dec 9, 2015, at 9:19 PM, Jeff King <peff@peff.net> wrote:\n> \n> On Tue, Dec 08, 2015 at 05:34:43PM +0000, Daniel Koverman wrote:\n> \n>> It is also good to know that 2000 remote refs is insane. The lower\n>> hanging fruit here sounds like trimming that to a reasonable\n>> number, so I'll try that approach first.\n> \n> It's definitely a lot, but it's not unheard of. The git project has over\n> 500 tags. That's not 2000, but you're within an order of magnitude.\n> \n> I have seen repositories with 20,000+ tags. I consider that a bit more\n> ridiculous, but it does work in practice.\n> \n\nWe have one at $DAY_JOB with 400,000+ refs. It presents some issues, but\nMartin has raised those with the community and it works pretty well now.\n\nRef advertisement is still a pain...\n\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at  http://vger.kernel.org/majordomo-info.html\n\n-- \nQualcomm Innovation Center, Inc.\nThe Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum, \na Linux Foundation Collaborative Project\n"},{"id":"274371","messageId":"d0a39b03e49d41e685cf61398c0d1102@EXCHANGE2U.uunet.arlington.PredictiveTechnologies.com","threadId":"40957","inReplyTo":"20151210041941.GA4056@sigill.intra.peff.net","subject":"RE: Why does send-pack call pack-objects for all remote refs?","fromName":"Daniel Koverman","fromEmail":"dkoverman@predictivetechnologies.com","sentAt":"2015-12-14T13:47:39Z","receivedAt":"2015-12-14T13:47:39Z","isPatch":false,"sender":{"key":"dkoverman@predictivetechnologies.com","avatar":null},"body":"> You might also try repacking with \"git repack -adb\", which will\n> build reachability bitmaps. Pack-objects can use them to compute\n> the set of required objects much faster.\n\nRunning \"git repack -adb\" caused my push time to incease by about 5x.\nI made some fresh clones and tried other options with repack, and\nconsistently anything I tried with -b caused the push time to\nincrease about 5x.\n\nI don't know much about reachability bitmaps, but perhaps it is\nimportant to note that I timed the pushes after repacking on Git for\nWindows. My earlier timings were done on both Linux and Windows and I\ndid not see a significant difference.\n\n> It's definitely a lot, but it's not unheard of. The git project has\n> over 500 tags. That's not 2000, but you're within an order of\n> magnitude.\n>\n> I have seen repositories with 20,000+ tags. I consider that a bit\n> more ridiculous, but it does work in practice.\n\nThanks for the extra context. I'll keep that in mind while I decide\nhow to approach this.\n\nDaniel\n"},{"id":"274433","messageId":"20151214210429.GC14788@sigill.intra.peff.net","threadId":"40957","inReplyTo":"d0a39b03e49d41e685cf61398c0d1102@EXCHANGE2U.uunet.arlington.PredictiveTechnologies.com","subject":"Re: Why does send-pack call pack-objects for all remote refs?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-12-14T21:04:29Z","receivedAt":"2015-12-14T21:04:29Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Dec 14, 2015 at 01:47:39PM +0000, Daniel Koverman wrote:\n\n> > You might also try repacking with \"git repack -adb\", which will\n> > build reachability bitmaps. Pack-objects can use them to compute\n> > the set of required objects much faster.\n> \n> Running \"git repack -adb\" caused my push time to incease by about 5x.\n> I made some fresh clones and tried other options with repack, and\n> consistently anything I tried with -b caused the push time to\n> increase about 5x.\n> \n> I don't know much about reachability bitmaps, but perhaps it is\n> important to note that I timed the pushes after repacking on Git for\n> Windows. My earlier timings were done on both Linux and Windows and I\n> did not see a significant difference.\n\nHmm. I guess that makes sense. The bitmap we want is the set difference\nbetween the objects we are sending, and the tips the other side has. If\nwe have a bitmap at each ref tip, that's very fast. But if you have a\nvery large number of refs, we don't make one for each ref, and it has to\nfallback to walking to the nearest one (and it ends up worse than a\nregular walk, because it's filling in the bitmap for each tree, rather\nthan just doing the \"good enough\" commit walk that we usually do).\n\nI suspect there's room for improvement in the way we select commits to\nstore bitmaps for (so that the average walk is smaller). But it's rather\ntricky; there's not a single constant to change to make it work better.\n\nThanks for trying out my suggestion.\n\n-Peff\n"},{"id":"274446","messageId":"20151214223155.GA6594@google.com","threadId":"40957","inReplyTo":"20151214210429.GC14788@sigill.intra.peff.net","subject":"Re: Why does send-pack call pack-objects for all remote refs?","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2015-12-14T22:31:55Z","receivedAt":"2015-12-14T22:31:55Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Jeff King wrote:\n\n> Hmm. I guess that makes sense. The bitmap we want is the set difference\n> between the objects we are sending, and the tips the other side has. If\n> we have a bitmap at each ref tip, that's very fast. But if you have a\n> very large number of refs, we don't make one for each ref, and it has to\n> fallback to walking to the nearest one (and it ends up worse than a\n> regular walk, because it's filling in the bitmap for each tree, rather\n> than just doing the \"good enough\" commit walk that we usually do).\n>\n> I suspect there's room for improvement in the way we select commits to\n> store bitmaps for (so that the average walk is smaller). But it's rather\n> tricky; there's not a single constant to change to make it work better.\n\nGit gc and JGit GC differ here.  JGit partitions the commits being\npacked by branch and then runs a selection algorithm on each part.\nGit runs a selection once on a list of all commits.\n\nSome effects:\n- JGit selects more bitmaps, so the gc takes longer and the resulting\n  bitmap file is larger (bad)\n- JGit is more likely to have bitmaps for the commits involved in\n  pushes and fetches (good)\n\nThe commit selection code, for reference:\n\nhttps://eclipse.googlesource.com/jgit/jgit/+/86af34e1/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapPreparer.java#151\nhttps://kernel.googlesource.com/pub/scm/git/git/+/ed1c9977/pack-bitmap-write.c#383\n\nThoughts?\nJonathan\n"},{"id":"274448","messageId":"20151214223717.GA20167@sigill.intra.peff.net","threadId":"40957","inReplyTo":"20151214223155.GA6594@google.com","subject":"Re: Why does send-pack call pack-objects for all remote refs?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-12-14T22:37:18Z","receivedAt":"2015-12-14T22:37:18Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Dec 14, 2015 at 02:31:55PM -0800, Jonathan Nieder wrote:\n\n> > I suspect there's room for improvement in the way we select commits to\n> > store bitmaps for (so that the average walk is smaller). But it's rather\n> > tricky; there's not a single constant to change to make it work better.\n> \n> Git gc and JGit GC differ here.  JGit partitions the commits being\n> packed by branch and then runs a selection algorithm on each part.\n> Git runs a selection once on a list of all commits.\n> \n> Some effects:\n> - JGit selects more bitmaps, so the gc takes longer and the resulting\n>   bitmap file is larger (bad)\n> - JGit is more likely to have bitmaps for the commits involved in\n>   pushes and fetches (good)\n> \n> The commit selection code, for reference:\n> \n> https://eclipse.googlesource.com/jgit/jgit/+/86af34e1/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapPreparer.java#151\n> https://kernel.googlesource.com/pub/scm/git/git/+/ed1c9977/pack-bitmap-write.c#383\n> \n> Thoughts?\n\nMy thought is it would be great if somebody wanted to work on this. :)\n\nMy understanding is that JGit's approach has some problems, too. Terry's\nmessage doesn't seem to have made it to the list, but you can see in the\nquoted bits he mentions some OOM problems during the bitmap write:\n\n  http://article.gmane.org/gmane.comp.version-control.git/281476\n\nThat may not be a big deal to work around. I really just haven't looked\nat it at all. Vicent did the original bitmap selection code for C Git,\nand I don't think it has been touched since then.\n\n-Peff\n"}]}