{"thread":{"id":"28885","subject":"Benchmarks regarding git's gc","startedAt":"2011-11-08T11:34:09Z","lastAt":"2011-11-09T12:34:58Z","messageCount":7,"participants":["Felipe Contreras","Nguyen Thai Ngoc Duy","Brandon Casey","Jeff King","Michael Haggerty","David Michael Barr"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"179133","messageId":"CAMP44s3E-YCMQQzJAU2wjjD-adpNy6bGb-=iUQ=p=bFTWxm+Ng@mail.gmail.com","threadId":"28885","inReplyTo":null,"subject":"Benchmarks regarding git's gc","fromName":"Felipe Contreras","fromEmail":"felipe.contreras@gmail.com","sentAt":"2011-11-08T11:34:09Z","receivedAt":"2011-11-08T11:34:09Z","isPatch":false,"sender":{"key":"felipe.contreras@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8358?v=4"},"body":"Has anybody seen these?\nhttp://draketo.de/proj/hg-vs-git-server/test-results.html#results\n\nSeems like a potential area of improvement.\n\nCheers.\n\n-- \nFelipe Contreras\n"},{"id":"179139","messageId":"CACsJy8DMAdjT8gsoSerkzNRvHgdcBWLaUd+-xHqXkV+hceo9rA@mail.gmail.com","threadId":"28885","inReplyTo":"CAMP44s3E-YCMQQzJAU2wjjD-adpNy6bGb-=iUQ=p=bFTWxm+Ng@mail.gmail.com","subject":"Re: Benchmarks regarding git's gc","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-11-08T14:37:29Z","receivedAt":"2011-11-08T14:37:29Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Nov 8, 2011 at 6:34 PM, Felipe Contreras\n wrote:\n> Has anybody seen these?\n> http://draketo.de/proj/hg-vs-git-server/test-results.html#results\n>\n> Seems like a potential area of improvement.\n\nThe proportion between time and commits may have something to do with\nreachability test, where we traverse all commits and trees (I think\ntwice in git-gc, one when it runs \"reflog expire\" and one \"prune\").\npackv4 is supposed to make tree traversing faster. Although it'd be\nbest if we could avoid this test.\n-- \nDuy\n"},{"id":"179144","messageId":"CAMP44s04B0vbecFb0JXmvnBX81A5q-m4ZAab8AxPpCjHpQvQKg@mail.gmail.com","threadId":"28885","inReplyTo":"CACsJy8DMAdjT8gsoSerkzNRvHgdcBWLaUd+-xHqXkV+hceo9rA@mail.gmail.com","subject":"Re: Benchmarks regarding git's gc","fromName":"Felipe Contreras","fromEmail":"felipe.contreras@gmail.com","sentAt":"2011-11-08T16:28:50Z","receivedAt":"2011-11-08T16:28:50Z","isPatch":false,"sender":{"key":"felipe.contreras@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8358?v=4"},"body":"On Tue, Nov 8, 2011 at 4:37 PM, Nguyen Thai Ngoc Duy wrote:\n> On Tue, Nov 8, 2011 at 6:34 PM, Felipe Contreras\n> wrote:\n>> Has anybody seen these?\n>> http://draketo.de/proj/hg-vs-git-server/test-results.html#results\n>>\n>> Seems like a potential area of improvement.\n>\n> The proportion between time and commits may have something to do with\n> reachability test, where we traverse all commits and trees (I think\n> twice in git-gc, one when it runs \"reflog expire\" and one \"prune\").\n> packv4 is supposed to make tree traversing faster. Although it'd be\n> best if we could avoid this test.\n\nIs there someone working on a way to avoid this test?\n\n-- \nFelipe Contreras\n"},{"id":"179145","messageId":"CA+sFfMdax6UYsi2ojGWQT_TdPSMPGMGRZA3jz+VaENmbs4buzQ@mail.gmail.com","threadId":"28885","inReplyTo":"CAMP44s3E-YCMQQzJAU2wjjD-adpNy6bGb-=iUQ=p=bFTWxm+Ng@mail.gmail.com","subject":"Re: Benchmarks regarding git's gc","fromName":"Brandon Casey","fromEmail":"drafnel@gmail.com","sentAt":"2011-11-08T16:40:15Z","receivedAt":"2011-11-08T16:40:15Z","isPatch":false,"sender":{"key":"drafnel@gmail.com","avatar":"https://avatars.githubusercontent.com/u/921167?v=4"},"body":"On Tue, Nov 8, 2011 at 5:34 AM, Felipe Contreras\n wrote:\n> Has anybody seen these?\n> http://draketo.de/proj/hg-vs-git-server/test-results.html#results\n>\n> Seems like a potential area of improvement.\n\nI think this is a case of designing the problem space so that your\nintended winner wins and your intended loser loses.\n\n'git gc' is designed so that it can be run out-of-band. It doesn't\nmake a lot of sense to design your application so that the end-user\nhas to wait for git-gc to run, and I don't think anyone ever would.\nBut that is similar to how mercurial works, and that is why the author\nof that page measured git's performance that way.\n\nOff the top of my head, it seems to me that running 'git gc --auto' in\na cron job with SCHED_BATCH scheduling and some simple locking may\nsatisfy his requirement of keeping the repository size bounded and\nensuring that the pack operation does not affect the operation of the\nweb app.\n\n-Brandon\n"},{"id":"179166","messageId":"20111108215812.GB18529@sigill.intra.peff.net","threadId":"28885","inReplyTo":"CA+sFfMdax6UYsi2ojGWQT_TdPSMPGMGRZA3jz+VaENmbs4buzQ@mail.gmail.com","subject":"Re: Benchmarks regarding git's gc","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-11-08T21:58:12Z","receivedAt":"2011-11-08T21:58:12Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Nov 08, 2011 at 10:40:15AM -0600, Brandon Casey wrote:\n\n> On Tue, Nov 8, 2011 at 5:34 AM, Felipe Contreras\n> wrote:\n> > Has anybody seen these?\n> > http://draketo.de/proj/hg-vs-git-server/test-results.html#results\n> >\n> > Seems like a potential area of improvement.\n> \n> I think this is a case of designing the problem space so that your\n> intended winner wins and your intended loser loses.\n\nSort of. It is a real problem space, and mercurial does have some\nadvantage in that area.\n\nHis problem definition is that of a git-backed server database that is\nunder constant load creating new commits. So imagine wikipedia backed by\ngit.\n\nMercurial's strategy (as I understand it) is to always calculate and\nstore deltas as new commits are created. Git's strategy is to store full\nobjects, and then worry about deltification later. So of course git is\ngoing to do more work, and especially more I/O.\n\nGit's strategy is fine for the workload for which it was designed:\npeople making commits in burst, and occasionally doing book-keeping to\nmake things smaller.\n\nBut for a constant-commit workflow, the burstiness is annoying, and the\namount of I/O can be cumbersome. We realized this long ago when\nimporting old histories into git. And that's why fast-import was born:\nit does at least a minimal level of delta and puts everything into a\nsingle packfile, instead of writing out loose objects.\n\nIf you were writing commits at some fast constant rate into your\nrepository, then you'd probably want to do the same thing. And it would\nbe fairly easy to do on top of git's object model. At best, it's just a\nspecialized commit command (like fast-import), and at worst it's\nprobably a more incremental object store.\n\nSo he may have a point that mercurial might perform better for some\nmetrics than git in the current state. But I think a lot of that is\nbecause nobody has bothered putting git into this situation and done the\ntweaks needed to make it fast. You can argue that git sucks because it\nneeds tweaking, of course, but if I were picking between the two systems\nto implement something like this, I'd consider picking git and doing the\ntweaks (of course, I'm far from unbiased).\n\n-Peff\n"},{"id":"179197","messageId":"4EBA0BD7.3050301@alum.mit.edu","threadId":"28885","inReplyTo":"CAMP44s3E-YCMQQzJAU2wjjD-adpNy6bGb-=iUQ=p=bFTWxm+Ng@mail.gmail.com","subject":"Re: Benchmarks regarding git's gc","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2011-11-09T05:12:55Z","receivedAt":"2011-11-09T05:12:55Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 11/08/2011 12:34 PM, Felipe Contreras wrote:\n> Has anybody seen these?\n> http://draketo.de/proj/hg-vs-git-server/test-results.html#results\n> \n> Seems like a potential area of improvement.\n\nThe fact that git requires periodic garbage collection is indeed\nannoying (even in interactive use) and even more annoying in the\nscenario discussed by the author of this article.\n\nWith respect to the article's claims about the overall efficiency of\nMercurial vs. git, I would like to point out that the author's use of a\ntest repository with a linear history avoids one of Mercurial's big\ndesign weaknesses. If the repository had had a branching history,\nMercurial's numbers would probably be significantly less flattering.\n\nMercurial's revlog repository format [1] (at least the last time I\nchecked) uses a single data file to hold the contents of all versions of\na single file in the working copy. It appends a delta to the end of the\nrevlog file for each revision, with periodic fulltexts. It is designed\nto make it possible to reconstruct any file revision via a single seek\nand a single read of at most twice the length of the file's fulltext\n(assuming that the index is already known). The avoidance of disk seeks\ngoes a long way to explaining Mercurial's competitive performance\ndespite the fact that it is written in Python.\n\nHowever, the deltas stored in revlog are not relative to a revision's\nparent(s), but rather relative to the previous revision in the revlog\nfile, which is typically the most recent revision committed *to any\nbranch*. Therefore, revlog is very good at storing a linear series of\ncommits, but is considerably less efficient at storing a history with\nlots of branches that were under development concurrently. The net\nresult is that the history of a branchy repository can take up much more\nspace than that of a linear repository.\n\nThere was a GSOC \"parentdelta\" project to allow deltas to be computed\nagainst parents [2], later replaced by a second \"generaldelta\" scheme\n[3], but AFAICT this is still experimental and they are struggling with\nits performance.\n\nThere is also a script in contrib that reorders the revisions in a\nrevlog file to put topological neighbors closer together [4]. This can\nshrink the size of the file dramatically. But of course this script is\nsomething like \"git gc\" in the sense that it would presumably need to be\nrun periodically, and each run would have to lock the repo for some time.\n\nAll this is not to detract from the fact that Mercurial, by not\nrequiring garbage collection, has a big advantage against git in certain\nscenarios.\n\nMichael\n\n[1]\nhttp://mercurial.selenic.com/wiki/FAQ#FAQ.2BAC8-TechnicalDetails.How_does_Mercurial_store_its_data.3F\n[2] http://mercurial.selenic.com/wiki/ParentDeltaPlan\n[3]\nhttp://mercurial.selenic.com/wiki/WhatsNew#Mercurial_1.9_.282011-07-01.29\n[4] http://selenic.com/hg/file/54c0517c0fe8/contrib/shrink-revlog.py\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"179204","messageId":"CAFfmPPNeriyNbnag9ekXW6YEVzordKNxUCjw837roub8hn+HGw@mail.gmail.com","threadId":"28885","inReplyTo":"20111108215812.GB18529@sigill.intra.peff.net","subject":"Re: Benchmarks regarding git's gc","fromName":"David Michael Barr","fromEmail":"davidbarr@google.com","sentAt":"2011-11-09T12:34:58Z","receivedAt":"2011-11-09T12:34:58Z","isPatch":false,"sender":{"key":"davidbarr@google.com","avatar":"https://avatars.githubusercontent.com/u/220594?v=4"},"body":"On Wed, Nov 9, 2011 at 8:58 AM, Jeff King wrote:\n> On Tue, Nov 08, 2011 at 10:40:15AM -0600, Brandon Casey wrote:\n>\n>> On Tue, Nov 8, 2011 at 5:34 AM, Felipe Contreras\n>> wrote:\n>> > Has anybody seen these?\n>> > http://draketo.de/proj/hg-vs-git-server/test-results.html#results\n>> >\n>> > Seems like a potential area of improvement.\n>>\n>> I think this is a case of designing the problem space so that your\n>> intended winner wins and your intended loser loses.\n>\n> Sort of. It is a real problem space, and mercurial does have some\n> advantage in that area.\n[...]\n> So he may have a point that mercurial might perform better for some\n> metrics than git in the current state. But I think a lot of that is\n> because nobody has bothered putting git into this situation and done the\n> tweaks needed to make it fast. You can argue that git sucks because it\n> needs tweaking, of course, but if I were picking between the two systems\n> to implement something like this, I'd consider picking git and doing the\n> tweaks (of course, I'm far from unbiased).\n\nIt is the case that the default behaviour of git gc --auto is far from optimal.\nI've been playing with ways to achieve both better asymptotic\nperformance and less jitter.\nOne part of that is choosing \"good\" packing parameters for a given repo.\nI did this in a partially automated fashion for WebKit but I think the\nprocess can be generalised.\nThe other issue is how often you repack ancient history, the potential\nwaste is obvious.\nTo this end I propose a repacking strategy in the spirit of merge-sort:\nIf you can maintain the constraint that the sizes of packs in a repo\nform a geometric sequence, my napkin says the amortised cost of gc is\nlog(n).\n\n--\nDavid Barr.\n"}]}