{"thread":{"id":"12979","subject":"Achieving efficient storage of weirdly structured repos","startedAt":"2008-04-03T19:42:39Z","lastAt":"2008-04-07T00:36:19Z","messageCount":14,"participants":["Roman Shaposhnik","Linus Torvalds","Jakub Narebski","Nicolas Pitre","Pieter de Bie","Shawn O. Pearce","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"73623","messageId":"7BE3E865-C30D-49B8-A1D9-898109514990@sun.com","threadId":"12979","inReplyTo":null,"subject":"Achieving efficient storage of weirdly structured repos","fromName":"Roman Shaposhnik","fromEmail":"rvs@sun.com","sentAt":"2008-04-03T19:42:39Z","receivedAt":"2008-04-03T19:42:39Z","isPatch":false,"sender":{"key":"rvs@sun.com","avatar":null},"body":"Hi Guys!\n\nFirst of all, I must admit that I got seriously hooked up on Git when  \nI started to\nuse it internally for FFmpeg development and my life as far as non  \ncompany\nrelated projects are concerned hasn't been the same ever since. The way\nGit addresses issues like branches (both local and remote), merges and\ncontent tracking are, in my opinion, quite superior to the  \nalternative SCMs\nsuch as Mercurial. In fact, that's why when I saw my coworkers  \nstruggling\nwith exactly the same issues around NetBeans Mercurial repository my\nnatural instinct was to introduce them to Git and show them that life  \ndoesn't\nhave to be that complicated or troublesome.\n\nBut before I can do that, there's a little issue that I either need  \nto address or\nat least understand better. It seems that the storage requirements  \nfor the\nrepository that a friend of mine and I created from: http:// \nhg.netbeans.org/main/\ngot doubled under Git:\n     $  du -sh Mercurial- nb-main\n     491M   Mercurial- nb-main\n     $ du -sh Git-nb-main\n     1.1G     Git-nb-main\n\nThe repository was created using hg2git (the one based on git-fast- \nimport)\nand it was GC'ed and REPACK'ed just in case. I spent some time trying\nto understand the issue and here's some statistics on the kind of  \nobjects\nthat this repository consists of:\n     75053 commit\n   334572 blob\n   750003 tree\n\nThe last item (trees) also seem to take the most space and the most  \nreasonable\nexplanation that I can offer is that NetBeans repository has a really  \nweird\nstructure where they have approximately 700 (yes, seven hundred!) top- \nlevel\nsubdirectories there. They are clearly Submodules-shy, but that's  \nanother\nissue that I will need to address with them.\n\nSo based on my preliminary analysis the biggest culprit seems to be\nthat for every commit at least one pretty hefty tree object needs to  \nbe created\n(remember 700 top level subdirectories). These objects are all in 18-20K\nrange but they are almost identical to each other except for one or two\ntrees that they refer to.\n\nSo here's my question: is there anything in Git that I can use to  \naccommodate\na repository like http://hg.netbeans.org/main in an efficient manner?  \nAny\nkind of ideas (like particular command line options for repack, etc.)  \nwould be\ngreatly appreciated!\n\nThanks,\nRoman.\n"},{"id":"73629","messageId":"alpine.LFD.1.00.0804031402530.14670@woody.linux-foundation.org","threadId":"12979","inReplyTo":"7BE3E865-C30D-49B8-A1D9-898109514990@sun.com","subject":"Re: Achieving efficient storage of weirdly structured repos","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-04-03T21:11:04Z","receivedAt":"2008-04-03T21:11:04Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 3 Apr 2008, Roman Shaposhnik wrote:\n> \n> The repository was created using hg2git (the one based on git-fast-import)\n> and it was GC'ed and REPACK'ed just in case.\n\nBefore going any further - exactly _how_ was it repacked?\n\nIn particular, when using importers that do partial packing on their own \n(and any \"git-fastimport\" user is that by definition - and I think \nhg2git does that), at the end of it all you have to make sure to repack in \na way where the repacking will totally discard the import-time packfiles.\n\nIOW, that's one of the very few times you should use \"-f\" to git repack.\n\nIt's usually also a good place to make sure that since you ignore the old \npacking information, it's best to also make sure that the new packing info \nis good by using a bigger window (and perhaps a bigger depth). That makes \nthe packing much slower, of course, but this is meant to be a one-time \nevent.\n\nSo try something like\n\n\tgit repack -a -d -f --depth=100 --window=100\n\nif you have a good CPU and plenty of memory.\n\n> The last item (trees) also seem to take the most space and the most \n> reasonable explanation that I can offer is that NetBeans repository has \n> a really weird structure where they have approximately 700 (yes, seven \n> hundred!) top-level subdirectories there. They are clearly \n> Submodules-shy, but that's another issue that I will need to address \n> with them.\n\nTrees taking the biggest amount of space is not unheard of, and it may \nalso be that the name heuristics (for finding good packing partners) could \nbe failign, which would result in a much bigger pack than necessary. \n\nSo if you already did an aggressive repack like the above, I'd happily \ntake a look at whether maybe it's bad heuristics for finding tree objects \nto pair up for delta-compression. Do you have a place where you can put \nthat repo for people to clone and look at? \n\n\t\t\tLinus\n"},{"id":"73644","messageId":"m3tziita2y.fsf@localhost.localdomain","threadId":"12979","inReplyTo":"alpine.LFD.1.00.0804031402530.14670@woody.linux-foundation.org","subject":"Re: Achieving efficient storage of weirdly structured repos","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2008-04-04T06:21:06Z","receivedAt":"2008-04-04T06:21:06Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> On Thu, 3 Apr 2008, Roman Shaposhnik wrote:\n>> \n>> The last item (trees) also seem to take the most space and the most \n>> reasonable explanation that I can offer is that NetBeans repository has \n>> a really weird structure where they have approximately 700 (yes, seven \n>> hundred!) top-level subdirectories there. They are clearly \n>> Submodules-shy, but that's another issue that I will need to address \n>> with them.\n> \n> Trees taking the biggest amount of space is not unheard of, and it may \n> also be that the name heuristics (for finding good packing partners) could \n> be failign, which would result in a much bigger pack than necessary. \n> \n> So if you already did an aggressive repack like the above, I'd happily \n> take a look at whether maybe it's bad heuristics for finding tree objects \n> to pair up for delta-compression. Do you have a place where you can put \n> that repo for people to clone and look at? \n\nHmmm... I wonder if it would be the case that would speed-up\ndevelopment of pack v4.  If I remember correctly one of bigger changes\nwas the way trees were represented in pack; the biggest improvement\nwas for trees.\n\nOne of bigger hindrances, as I understand it, in developing pack v4\nwas the fact that it didn't offer that much of improvement in typical\ncases for the work needed... but perhaps \"your\" repository would be\ngood showcase for pack v4.\n\nJust my 2 eurocents...\n\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"73651","messageId":"alpine.LFD.1.00.0804040844470.2947@xanadu.home","threadId":"12979","inReplyTo":"m3tziita2y.fsf@localhost.localdomain","subject":"Re: Achieving efficient storage of weirdly structured repos","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-04-04T13:11:34Z","receivedAt":"2008-04-04T13:11:34Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 3 Apr 2008, Jakub Narebski wrote:\n\n> Linus Torvalds <torvalds@linux-foundation.org> writes:\n> \n> > On Thu, 3 Apr 2008, Roman Shaposhnik wrote:\n> >> \n> >> The last item (trees) also seem to take the most space and the most \n> >> reasonable explanation that I can offer is that NetBeans repository has \n> >> a really weird structure where they have approximately 700 (yes, seven \n> >> hundred!) top-level subdirectories there. They are clearly \n> >> Submodules-shy, but that's another issue that I will need to address \n> >> with them.\n> > \n> > Trees taking the biggest amount of space is not unheard of, and it may \n> > also be that the name heuristics (for finding good packing partners) could \n> > be failign, which would result in a much bigger pack than necessary. \n> > \n> > So if you already did an aggressive repack like the above, I'd happily \n> > take a look at whether maybe it's bad heuristics for finding tree objects \n> > to pair up for delta-compression. Do you have a place where you can put \n> > that repo for people to clone and look at? \n> \n> Hmmm... I wonder if it would be the case that would speed-up\n> development of pack v4.\n\nNot really.  Pack v4 won't magically shrink a repository to less than \nhalf the pack v3 size.\n\nI think we're simply facing the same situation as with the initial GCC \nrepository which shrank from 3GB down to 300MB or so due to misfitted \nrepacking parameters.\n\n> If I remember correctly one of bigger changes\n> was the way trees were represented in pack; the biggest improvement\n> was for trees.\n\nYes, but that wasn't really so much about size but rather access speed \nby not deflating them. The pack v4 tree representation would certainly \nhelp, of course, but I suspect that simply repacking with more \naggressive window/depth arguments would be even more effective in this \ncase.\n\n> One of bigger hindrances, as I understand it, in developing pack v4\n> was the fact that it didn't offer that much of improvement in typical\n> cases for the work needed... but perhaps \"your\" repository would be\n> good showcase for pack v4.\n\nThe biggest hindrance for pack v4 is actually the lack of a native \nruntime tree walking, and having both tree object formats properly and \noptimally abstracted has not been looked at yet.\n\nSpeed is the primary goal for pack v4.  The fact that it also provides a \n10% pack reduction is only consequential.  But without native tree \nwalking we must recreate the legacy tree format on the fly each time a \ntree object is loaded which dwarfs any improvements pack v4 is aiming \nfor (yes it is still a little bit faster than pack v3 nevertheless, but \nnot yet significantly enough to overcome the incompatibility costs).\n\n\nNicolas (who wishes he was still a student with plenty of hacking time)\n"},{"id":"73654","messageId":"DBD32AF9-AFF9-4DA2-9122-9997773C64ED@ai.rug.nl","threadId":"12979","inReplyTo":"alpine.LFD.1.00.0804040844470.2947@xanadu.home","subject":"Re: Achieving efficient storage of weirdly structured repos","fromName":"Pieter de Bie","fromEmail":"pdebie@ai.rug.nl","sentAt":"2008-04-04T14:16:25Z","receivedAt":"2008-04-04T14:16:25Z","isPatch":false,"sender":{"key":"pdebie@ai.rug.nl","avatar":null},"body":"\nOn 4 apr 2008, at 15:11, Nicolas Pitre wrote:\n> I think we're simply facing the same situation as with the initial GCC\n> repository which shrank from 3GB down to 300MB or so due to misfitted\n> repacking parameters.\n\nI'd say so too. I imported the first 14000 revisions of that hg  \nrepository and the resulting pack file was just 25 MB after repacking.\n\n- Pieter\n"},{"id":"73671","messageId":"1207351858.13123.52.camel@work.sfbay.sun.com","threadId":"12979","inReplyTo":"alpine.LFD.1.00.0804031402530.14670@woody.linux-foundation.org","subject":"Re: Achieving efficient storage of weirdly structured repos","fromName":"Roman Shaposhnik","fromEmail":"rvs@sun.com","sentAt":"2008-04-04T23:30:58Z","receivedAt":"2008-04-04T23:30:58Z","isPatch":false,"sender":{"key":"rvs@sun.com","avatar":null},"body":"Hi Linus!\n\nOn Thu, 2008-04-03 at 14:11 -0700, Linus Torvalds wrote:\n> \n> On Thu, 3 Apr 2008, Roman Shaposhnik wrote:\n> > \n> > The repository was created using hg2git (the one based on git-fast-import)\n> > and it was GC'ed and REPACK'ed just in case.\n> \n> Before going any further - exactly _how_ was it repacked?\n\nI believe it was the following two steps:\n   $ git gc --aggressive\n   $ git repack\n\n> In particular, when using importers that do partial packing on their own \n> (and any \"git-fastimport\" user is that by definition - and I think \n> hg2git does that), at the end of it all you have to make sure to repack in \n> a way where the repacking will totally discard the import-time packfiles.\n\nGood point. Speaking of which: do you have an FAQ for importers? The\nentries in the official FAQ (http://git.or.cz/gitwiki/GitFaq#head-929a8825d04dde226c2530f5337d3b3ed8dcc7ce)\nseem a bit stale for such an important issue. After all, importing from\nan existing SCM is what usually forms a first time impression of Git's\neffectiveness.\n\n> IOW, that's one of the very few times you should use \"-f\" to git repack.\n\nGot it!\n\n> It's usually also a good place to make sure that since you ignore the old \n> packing information, it's best to also make sure that the new packing info \n> is good by using a bigger window (and perhaps a bigger depth). That makes \n> the packing much slower, of course, but this is meant to be a one-time \n> event.\n> \n> So try something like\n> \n> \tgit repack -a -d -f --depth=100 --window=100\n> \n> if you have a good CPU and plenty of memory.\n\nThat turned out to be a perfect suggestion. Thank you. I'm now the\nhappiest camper ever. And I'm also also pretty dumbfounded ;-)\n\nHere's what happened. \n\nI started with a a repository filled with \"loose\" (one object per file)\nobjects (the reason I needed it was for the ease of sleuthing through\nindividual objects and it was created by git-unpack-objects from that\ninitial 1.1Gb pack). And I tried to pack it exactly like you\nsuggested:\n   $ git-pack-objects --depth=100 --window=100 --delta-base-offset --progress pack < objects\n   Generating pack...\n   Counting objects: 1096305\n   Done counting 1159628 objects.\n   Deltifying 1159628 objects...\n      100% (1159628/1159628) done\n   Writing 1159628 objects...\n   dd134c407324dc55b0cd2aa3a9e1b3420c2bba3f\n\n   Total 1159628 (delta 386980), reused 0 (delta 0)\n\nand it payed off reasonably well:\n    $ du -s NB-clone\n    670M NB-clone\n\nIt still was bigger than the Mercurial repository but at least it got\n2 times smaller than the original result of hg2git. Now, if it wasn't\nfor a friend of mine, I probably would've stopped there. But he\nshowed up and saved the day ;-) His comments made me try something\nthat I didn't consider to be of any use -- repacking a freshly packed\npack with the *same* --depth=100 --window=100:\n    $ git repack -a  -f --window=100 --depth=100 \n    Generating pack...\n    Counting objects: 1056829\n    Done counting 1159628 objects.\n    Deltifying 1159628 objects...\n       100% (1159628/1159628) done\n    Writing 1159628 objects...\n       100% (1159628/1159628) done\n    Total 1159628 (delta 614516), reused 0 (delta 0)\n    Pack pack-dd134c407324dc55b0cd2aa3a9e1b3420c2bba3f created.\nAnd then, a miracle occurred:\n     $ du -sh NB-small \n     268M NB-small\n\nNow, don't get me wrong: I'm as happy as a clam. The repository is now\n*smaller* than the Mercurial's and because the structure of the\ntree is so weird Git gets major points here. The only question that\nis still bothering me is: how did it happen? Why did repacking \na repository with exactly the same set of objects and the only\ndifference being where these objects resided (former case filesystem,\nthe later case an intermediate pack) made so huge a difference?\n\nPlease help!\n\n> > The last item (trees) also seem to take the most space and the most \n> > reasonable explanation that I can offer is that NetBeans repository has \n> > a really weird structure where they have approximately 700 (yes, seven \n> > hundred!) top-level subdirectories there. They are clearly \n> > Submodules-shy, but that's another issue that I will need to address \n> > with them.\n> \n> Trees taking the biggest amount of space is not unheard of, and it may \n> also be that the name heuristics (for finding good packing partners) could \n> be failign, which would result in a much bigger pack than necessary. \n\nIs there any documentation that describes the heuristics involved in\ncreating a pack?\n\n> So if you already did an aggressive repack like the above, I'd happily \n> take a look at whether maybe it's bad heuristics for finding tree objects \n> to pair up for delta-compression. Do you have a place where you can put \n> that repo for people to clone and look at?\n\nUnfortunately I don't. The only thing I can do is I can always create\na *.tar.bz2 and put and on  Sun's ftp server. Actually, that makes me\nwonder: is there any public Git hosting available such that publishing\na hefty repository for the forensic purposes only wouldn't violate their\nterms of use?\n\nThanks,\nRoman.\n\nP.S. Oh, and here's one extra tiny question that I also have: what\ndoes the output:\n   Total 1159628 (delta 614516), reused 0 (delta 0)\nreally mean?\n"},{"id":"73674","messageId":"alpine.LFD.1.00.0804041634180.14670@woody.linux-foundation.org","threadId":"12979","inReplyTo":"1207351858.13123.52.camel@work.sfbay.sun.com","subject":"Re: Achieving efficient storage of weirdly structured repos","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-04-04T23:57:34Z","receivedAt":"2008-04-04T23:57:34Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 4 Apr 2008, Roman Shaposhnik wrote:\n> \n> That turned out to be a perfect suggestion. Thank you. I'm now the\n> happiest camper ever. And I'm also also pretty dumbfounded ;-)\n\nOk, the dumbfounded we can help with.\n\n> Here's what happened. \n> \n> I started with a a repository filled with \"loose\" (one object per file)\n> objects (the reason I needed it was for the ease of sleuthing through\n> individual objects and it was created by git-unpack-objects from that\n> initial 1.1Gb pack). And I tried to pack it exactly like you\n> suggested:\n>    $ git-pack-objects --depth=100 --window=100 --delta-base-offset --progress pack < objects\n\nWell, that's not exactly like I suggested, that's a *really* old-fashioned \nway.\n\nBut the part you left off was what the \"objects\" file contained?\n\nIn particular, \"git pack-objects\" can take just a raw list of objects, and \nit will *work*, but without the naming information and without the \nordering information on the objects, the end result will generally suck.\n\nSo how did you generate the \"objects\" file? You can do it by just listing \nevery single loose object you have, and it will work, but the end result \nwon't be very pretty.\n\n>    Total 1159628 (delta 386980), reused 0 (delta 0)\n> \n> and it payed off reasonably well:\n>     $ du -s NB-clone\n>     670M NB-clone\n\nSo what git-repack-objects will do is that it will *try* to figure out a \ngood and likely pairing of objects, and it uses the type and the size of \nthe objectf rot it, but it obviously didn't find very good deltas. In \nfact, only about 35% of all objects are deltas at all!\n\nWhich is why I suspect that your object list was just the raw list of \nobjects.\n\n> His comments made me try something that I didn't consider to be of any \n> use -- repacking a freshly packed pack with the *same* --depth=100 \n> --window=100:\n>     $ git repack -a  -f --window=100 --depth=100 \n\nWell, \"git repack\" doesn't just list the objects and then repack them, it \nalso\n\n - lists them with the filename they were reachable from (if they are \n   trees or blobs)\n - sorts them topologically (ie most reachable objects first).\n\nAnd that first thing will generate a *much* better packing, because now \nthe packing algorithm can look at the filename, and generate a much better \nguess about which objects to try to delta against each others. And now you \nhave\n\n>     Total 1159628 (delta 614516), reused 0 (delta 0)\n\nIe you got a much better 60% delta ratio, and obviously a much smaller \npack. But it's not just smaller, because the resulting pack will also have \nthe objects in topological order, so that objects that are \"new\" \n(ie more closely reachable from the top-of-tree) will be at the front of \nthe pack, so you'll also generally have better IO patterns in the packfile \nitself.\n\n> Now, don't get me wrong: I'm as happy as a clam. The repository is now\n> *smaller* than the Mercurial's and because the structure of the\n> tree is so weird Git gets major points here. The only question that\n> is still bothering me is: how did it happen? Why did repacking \n> a repository with exactly the same set of objects and the only\n> difference being where these objects resided (former case filesystem,\n> the later case an intermediate pack) made so huge a difference?\n\nThat location thing really shouldn't have mattered (since you used \"-f\", \nwhich throws it away).  So I think it was all from how you generated the \nlist of objects. But since I don't know how you did that, I cannot \nguarantee anything.\n\n> Is there any documentation that describes the heuristics involved in\n> creating a pack?\n\nIt's been explained a few times on the mailing list, but I don't know if \nthere is some write-up.\n\nThe git pack format is a bit more relaxed than any other SCM format I know \nabout, since it literally is just a \"bunch of objects with deltas randomly \nbetween them\". So a pack can look just about any way it wants - there are \nno real ordering requirements (--delta-base-offset does require that the \ndelta follows the base, but even that is really just a trivial practical \n\"because otherwise you could never know what the offset in the pack-file \nwas\" issue rather than anything else).\n\nSo you can order the objects and make deltas just about any way you want. \nWhat \"git repack\" will do is to sort objects by <type, namehash, length>, \nand then walk the list with the window of the specified size to see the \nbest pairing it can do.\n\nThe \"namehash\" is just designed so that files that have the same name sort \ntogether (and it's also not a real \"hash\" - it's really a meaningless \nnumber, but one that is designed so that even if the names aren't exactly \nthe same, they sort closer together if they end in similar character \nsequences - so a file that moves from one directory to another but keeps \nthe same basename will sort source and destination together).\n\nSee \"type_size_sort()\" in builtin-pack-objects.c to see what's up.\n\n(The preferred_base thing is just to keep objects we actually want to \n*keep* in the pack separated from the objects we may be using for \nreferences - but that is only used for transferring objects over the wire, \nnever for standalone packs).\n\nOh. And now I notice that there is *some* documentation on this in \n\n\tDocumentation/technical/pack-heuristics.txt\n\nbut that's pretty old (not that I think it has really changed) and not \nvery deep. Just taken from some #irc discussion.\n\n> P.S. Oh, and here's one extra tiny question that I also have: what\n> does the output:\n>    Total 1159628 (delta 614516), reused 0 (delta 0)\n> really mean?\n\nIt just means that there were a million objects total, the pack was \ncreated with 614k of them as deltas against other objects, and none of \nthem were re-used from previous packs.\n\nYou'll see that when you do incremental repacks, 99% of all the objects \nand deltas get re-used from the old pack, which is how we can make \nrepacking fairly efficient. That's imporant because the native git \nprotocol format itself is just a pack-file (plus the handshake to figure \nout what both sides have, of course). So a \"git clone\" implies a repack.\n\n\t\tLinus\n"},{"id":"73684","messageId":"20080405032445.GS10274@spearce.org","threadId":"12979","inReplyTo":"alpine.LFD.1.00.0804040844470.2947@xanadu.home","subject":"Re: Achieving efficient storage of weirdly structured repos","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-04-05T03:24:45Z","receivedAt":"2008-04-05T03:24:45Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre <nico@cam.org> wrote:\n> On Thu, 3 Apr 2008, Jakub Narebski wrote:\n> \n> > One of bigger hindrances, as I understand it, in developing pack v4\n> > was the fact that it didn't offer that much of improvement in typical\n> > cases for the work needed... but perhaps \"your\" repository would be\n> > good showcase for pack v4.\n> \n> The biggest hindrance for pack v4 is actually the lack of a native \n> runtime tree walking, and having both tree object formats properly and \n> optimally abstracted has not been looked at yet.\n> \n> Speed is the primary goal for pack v4.  The fact that it also provides a \n> 10% pack reduction is only consequential.  But without native tree \n> walking we must recreate the legacy tree format on the fly each time a \n> tree object is loaded which dwarfs any improvements pack v4 is aiming \n> for (yes it is still a little bit faster than pack v3 nevertheless, but \n> not yet significantly enough to overcome the incompatibility costs).\n\nEven though we don't have native tree walking, I think the right\nway to do this is to put in pack v4 with \"canonical tree, canonical\ncommit\" mode, where it inflates its native tree/commit encoding\ninto the canonical forms, then come back later with native walking.\n\nCanonical mode is still faster than pack v2 inflate is for these\ntypes, so it does (slightly) boost rev-list performance.  It might\nchop a solid 30% off the CPU time jgit spends in its equivilant of\nrevision.c, and that's without teaching jgit to use the native pack\nv4 encoding directly.\n\nOnce we have it in we can experiment with the necessary abstractions\nto handle the two different available encodings, and allowing\nhigher level code to switch back and forth between them as objects\ncome from loose or pack v2, and from pack v4.  One of the things we\nwanted to do was boost path limiter performance by matching on tree\nname ids when walking a pack v4 native tree, but fall back to the\nstring based memcmp when walking a canonical tree.  That won't be\neasy to design without the two different encodings being available\nat the lower level in sha1_file.c.\n\nJust my rapidly declining .02 bush peso.\n\n> Nicolas (who wishes he was still a student with plenty of hacking time)\n\nDon't we all.  :-)\n\n-- \nShawn.\n"},{"id":"73720","messageId":"4A31E284-E7F1-4748-A2CB-D8682748D3D6@sun.com","threadId":"12979","inReplyTo":"alpine.LFD.1.00.0804041634180.14670@woody.linux-foundation.org","subject":"Re: Achieving efficient storage of weirdly structured repos","fromName":"Roman Shaposhnik","fromEmail":"rvs@sun.com","sentAt":"2008-04-06T00:13:30Z","receivedAt":"2008-04-06T00:13:30Z","isPatch":false,"sender":{"key":"rvs@sun.com","avatar":null},"body":"Hi Linus,\n\nOn Apr 4, 2008, at 4:57 PM, Linus Torvalds wrote:\n> On Fri, 4 Apr 2008, Roman Shaposhnik wrote:\n>>\n>> That turned out to be a perfect suggestion. Thank you. I'm now the\n>> happiest camper ever. And I'm also also pretty dumbfounded ;-)\n>\n> Ok, the dumbfounded we can help with.\n\nGreat!\n\n>> Here's what happened.\n>>\n>> I started with a a repository filled with \"loose\" (one object per  \n>> file)\n>> objects (the reason I needed it was for the ease of sleuthing through\n>> individual objects and it was created by git-unpack-objects from that\n>> initial 1.1Gb pack). And I tried to pack it exactly like you\n>> suggested:\n>>    $ git-pack-objects --depth=100 --window=100 --delta-base-offset  \n>> --progress pack < objects\n>\n> Well, that's not exactly like I suggested, that's a *really* old- \n> fashioned\n> way.\n\nIt sure is old-fashioned. My only excuse is that since git repack is  \na shell\nscript around git-pack-objects I've always felt comfortable just using\nthe lower level utility.\n\n> But the part you left off was what the \"objects\" file contained?\n\nIt was pretty much the result of (cd .git/objects ; find . -type f |  \ntr -d './')\nOmitting that was quite silly on my part, but I was really convinced\nthat because of the internal sorting the original ordering of objects\nwouldn't matter at all.\n\n> In particular, \"git pack-objects\" can take just a raw list of  \n> objects, and\n> it will *work*, but without the naming information and without the\n> ordering information on the objects, the end result will generally  \n> suck.\n>\n> So how did you generate the \"objects\" file? You can do it by just  \n> listing\n> every single loose object you have, and it will work, but the end  \n> result\n> won't be very pretty.\n\nSo it seems that my list of objects was different from what git-rev- \nlist/setup_revisions()\nwould have provided in two ways:\n     1. the order of objects was arbitrary\n     2. the naming of blobs and trees was missing\n#2 was, indeed, a huge oversight on my part. At the same time, I've  \nalways thought\nthat #1 shouldn't matter, because, as you pointed out, the objects get\nsorted by <type, namehash, length> anyway. However, it seems that  \nbecause\nof the lack of naming there was much less sorting done by  \ntype_size_sort()\nand the original order persevered (at least within type-size  \npartitions).\nIt did matter after all!\n\nNow, in my particular case, the ordering was braindead and it  \nresulted in\na highly visible inefficiency. On the other hand, it seems that creative\nordering could very well be used to exploit localities which go beyond\nhow default name hashing in builtin-pack-objects.c works.\n\nIn fact, it starts to look awfully like custom MPEG profiles where if  \nyou know\nyour footage you can achieve a much higher compression ratio\ncompared to what the default might give you. It also makes it very\nclear that Git's approach of doing away with per-file content tracking\nis quite superior to the in-file deltas. Cool!\n\nHere's my final question on that issue: wouldn't it be great to give  \nusers\na direct control over specifying the list of objects in exactly the  \norder\nthey would like them to be tried for deltifying? Something like -- \npreserve-order\noption available for git-pack-objects?\n\n>>     Total 1159628 (delta 614516), reused 0 (delta 0)\n>\n> Ie you got a much better 60% delta ratio, and obviously a much smaller\n> pack. But it's not just smaller, because the resulting pack will  \n> also have\n> the objects in topological order, so that objects that are \"new\"\n> (ie more closely reachable from the top-of-tree) will be at the  \n> front of\n> the pack, so you'll also generally have better IO patterns in the  \n> packfile\n> itself.\n\nGot it! This makes total sense.\n\n>> Is there any documentation that describes the heuristics involved in\n>> creating a pack?\n>\n> It's been explained a few times on the mailing list, but I don't  \n> know if\n> there is some write-up.\n>\n> The git pack format is a bit more relaxed than any other SCM format  \n> I know\n> about, since it literally is just a \"bunch of objects with deltas  \n> randomly\n> between them\". So a pack can look just about any way it wants -  \n> there are\n> no real ordering requirements (--delta-base-offset does require  \n> that the\n> delta follows the base, but even that is really just a trivial  \n> practical\n> \"because otherwise you could never know what the offset in the pack- \n> file\n> was\" issue rather than anything else).\n>\n> So you can order the objects and make deltas just about any way you  \n> want.\n> What \"git repack\" will do is to sort objects by <type, namehash,  \n> length>,\n> and then walk the list with the window of the specified size to see  \n> the\n> best pairing it can do.\n>\n> The \"namehash\" is just designed so that files that have the same  \n> name sort\n> together (and it's also not a real \"hash\" - it's really a meaningless\n> number, but one that is designed so that even if the names aren't  \n> exactly\n> the same, they sort closer together if they end in similar character\n> sequences - so a file that moves from one directory to another but  \n> keeps\n> the same basename will sort source and destination together).\n>\n> See \"type_size_sort()\" in builtin-pack-objects.c to see what's up.\n>\n> (The preferred_base thing is just to keep objects we actually want to\n> *keep* in the pack separated from the objects we may be using for\n> references - but that is only used for transferring objects over  \n> the wire,\n> never for standalone packs).\n>\n> Oh. And now I notice that there is *some* documentation on this in\n>\n> \tDocumentation/technical/pack-heuristics.txt\n>\n> but that's pretty old (not that I think it has really changed) and not\n> very deep. Just taken from some #irc discussion.\n>\n>> P.S. Oh, and here's one extra tiny question that I also have: what\n>> does the output:\n>>    Total 1159628 (delta 614516), reused 0 (delta 0)\n>> really mean?\n>\n> It just means that there were a million objects total, the pack was\n> created with 614k of them as deltas against other objects, and none of\n> them were re-used from previous packs.\n>\n> You'll see that when you do incremental repacks, 99% of all the  \n> objects\n> and deltas get re-used from the old pack, which is how we can make\n> repacking fairly efficient. That's imporant because the native git\n> protocol format itself is just a pack-file (plus the handshake to  \n> figure\n> out what both sides have, of course). So a \"git clone\" implies a  \n> repack.\n\nVery nice summary! Many, many thanks for providing it!\n\nThanks,\nRoman.\n"},{"id":"73721","messageId":"alpine.LFD.1.00.0804051729230.11277@woody.linux-foundation.org","threadId":"12979","inReplyTo":"4A31E284-E7F1-4748-A2CB-D8682748D3D6@sun.com","subject":"Re: Achieving efficient storage of weirdly structured repos","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-04-06T00:48:43Z","receivedAt":"2008-04-06T00:48:43Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 5 Apr 2008, Roman Shaposhnik wrote:\n> \n> It was pretty much the result of (cd .git/objects ; find . -type f | tr -d\n> './')\n\nOk, that explains it. And yes, it definitely works, but I think you now \nunderstand why it gave you that oddly pessimised pack-file.\n\nThat said, I think it's also a really good example of how the git \npack-files really are just a \"bag of objects\", and the fact that it worked \nbut was non-optimal is a very good way to show something very fundamental \nabout git.\n\n> So it seems that my list of objects was different from what\n> git-rev-list/setup_revisions()\n> would have provided in two ways:\n>    1. the order of objects was arbitrary\n>    2. the naming of blobs and trees was missing\n> #2 was, indeed, a huge oversight on my part. At the same time, I've always\n> thought\n> that #1 shouldn't matter, because, as you pointed out, the objects get\n> sorted by <type, namehash, length> anyway. However, it seems that because\n> of the lack of naming there was much less sorting done by type_size_sort()\n> and the original order persevered (at least within type-size partitions).\n> It did matter after all!\n\nWell, a pack actually as two *different* orderings, in that there's one \nordering that is used for laying out the result in the pack-file, and \nanother ordering that is used for actually finding the deltas with the \nsliding window.\n\nAnd the input order is actually used for the layout ordering.\n\nAnd both matter. The  <type, namehash, length> is the one that determines \nhow large the resulting pack is, but the layout order is what causes the \nIO patterns for most common uses, so if the pack-file is cold in the \ncache, it can matter quite a bit for performance.\n\nSo the layout order is the one you give as input to \"git pack-objects\". \nAnd if that input has no particular ordering, then the final layout will \nalso have no particular ordering and you get random IO patterns when \nloading from disk.\n\n> Now, in my particular case, the ordering was braindead and it resulted in\n> a highly visible inefficiency. On the other hand, it seems that creative\n> ordering could very well be used to exploit localities which go beyond\n> how default name hashing in builtin-pack-objects.c works.\n\nYes. We've changed some of the heuristics subtly over time (eg the whole \nname-hashing was a tweak that was added later), but you're absolutely \nright - it's an area where some *particular* usage model could come up \nwith a special ordering to optimize a some special load. The defaults are \nmeant to be \"good enough\", and there has been some thought put into them, \nbut yes, there's probably room for specialization there.\n\nIn particular, one thing I've wanted to do is to do some \"fingerprint \nhash\" and perhaps use that as a sorting guide for finding deltas even more \naggressively than we do now, but I've never really found the energy to try \nsomething like that out.\n\n> In fact, it starts to look awfully like custom MPEG profiles where if you know\n> your footage you can achieve a much higher compression ratio\n> compared to what the default might give you. It also makes it very\n> clear that Git's approach of doing away with per-file content tracking\n> is quite superior to the in-file deltas. Cool!\n\nWell, one thing that git doesn't do, but that I find intriguing is if it \ncould be possible to do deltas not even between different files, but even \n*across* files. \n\nOne thing that the git model sucks at is how it's not very good at \nhandling large objects. I've often wondered if I should have made \"object\" \nbe more fine-grained and tried to build up large files from multiple \nsmaller objects.\n\n[ That said, I think git does the right thing - for source code. The \n  blocking-up of files would cause a rather more complex model, and one of \n  the great things about git is how simple the basic model is. But the\n  large-file thing does mean that git potentially sucks really badly for \n  some other loads ]\n\n> Here's my final question on that issue: wouldn't it be great to give users\n> a direct control over specifying the list of objects in exactly the order\n> they would like them to be tried for deltifying? Something like\n> --preserve-order option available for git-pack-objects?\n\nSee above: there's actually two orders, so you'd need to specify *both* \norders some way, since the input order already has meaning (it's assumed \nto be the \"topological ordering\".\n\nYou *can* approximate what you descibe by playing games with the filenames \n(which you can give in the input too - they're just strings on the same \nline as the SHA1), and that would be a total hack to give that secondary \nordering. And yes, I agree that it might be cool to do this explicitly \nsome way. If only to give a way to test experimental versions of the type \nsorting.\n\n[ To see how the filename thing works, do\n\n\tgit rev-list --objects --all > object-list\n\tgit pack-objects ... < object-list\n\n  and you can look at the \"object-list\" file to see how it's not just the \n  list of SHA1, it now has the filename info in it too. Imagine changing \n  that filename to generate a \"custom\" pack order ]\n\n\t\t\t\tLinus\n"},{"id":"73744","messageId":"20080406161003.GA24358@coredump.intra.peff.net","threadId":"12979","inReplyTo":"alpine.LFD.1.00.0804051729230.11277@woody.linux-foundation.org","subject":"Re: Achieving efficient storage of weirdly structured repos","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-04-06T16:10:03Z","receivedAt":"2008-04-06T16:10:03Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Apr 05, 2008 at 05:48:43PM -0700, Linus Torvalds wrote:\n\n> One thing that the git model sucks at is how it's not very good at \n> handling large objects. I've often wondered if I should have made \"object\" \n> be more fine-grained and tried to build up large files from multiple \n> smaller objects.\n> \n> [ That said, I think git does the right thing - for source code. The \n>   blocking-up of files would cause a rather more complex model, and one of \n>   the great things about git is how simple the basic model is. But the\n>   large-file thing does mean that git potentially sucks really badly for \n>   some other loads ]\n\nI have considered something like this for one of my repos, which is full\nof images. The large image data very rarely changes, but the small EXIF\ntags do.\n\nMy thought was something like:\n\n  - add a new object type, multiblob; a multiblob contains zero or more\n    \"child\" sha1s, each of which is another multiblob or a blob. The\n    data in the multiblob is an in-order concatenation of its children.\n\n  - you would create multiblobs with a \"smart\" git-add that understands\n    the filetype and splits the file accordingly (in my case, probably a\n    chunk of headers and EXIF data, and then a chunk with the image\n    data).\n\n  - in most of git, whenever you need a blob, you just \"unwrap\" the\n    multiblob to get the original blob data\n\n  - because they're separate objects, pack-objects automagically does\n    the right thing\n\n  - a few places would benefit from handling multiblobs specially. In\n    particular:\n      - the diff machinery could do much more efficient comparisons for\n        some inexact renames. E.g., multiblob \"1234\\n5678\" and multiblob\n        \"abcd\\n5678\" could ignore the \"5678\" id.\n      - the diff machinery could show diffs that were more human\n        readable (e.g., even without understanding what the chunks of\n        the multiblob _mean_, it can still say \"most of this image\n        didn't change, but this textual part did\").\n\nOf course there are a few drawbacks:\n\n  - one of git's strengths is that content is the same no matter who\n    adds it or how. Now the same file has a different sha1 as a\n    multiblob versus a regular blob.\n\n  - it breaks the git model of \"we store state in the simplest way, and\n    figure everything out afterwards.\" IOW, you are stuck with whatever\n    crappy multiblob split you did when you added or updated the file.\n    The usual pattern in git is \"dumb add, smart view\". Now maybe it is\n    worth breaking this for two reasons:\n\n      - dumb add, smart view is often very resource intensive; we can\n        get smaller packs and faster rename detection out of this\n\n      - we might be losing information; in the case of renames, we can\n        justify not explicitly recording because we can figure out\n        later what actually happened. I don't know if there is a\n        multiblob split that would encapsulate useful user input.\n        My EXIF example doesn't; with a little more CPU time, you could\n        just do the automated split at diff or delta time.\n\nSo it's an approach that I think would work, but I'm not sure it's worth\nthe effort unless somebody comes up with a compelling reason that you\ncan't just split the blobs up after the fact (and maybe the right\napproach is that pack v5 can split blobs intelligently to get better\ndeltas, so they are still blobs, but we just store them differently).\n\n-Peff\n"},{"id":"73791","messageId":"alpine.LFD.1.00.0804062000240.2947@xanadu.home","threadId":"12979","inReplyTo":"20080406161003.GA24358@coredump.intra.peff.net","subject":"Re: Achieving efficient storage of weirdly structured repos","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-04-07T00:13:10Z","receivedAt":"2008-04-07T00:13:10Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 6 Apr 2008, Jeff King wrote:\n\n> My thought was something like:\n> \n>   - add a new object type, multiblob; a multiblob contains zero or more\n>     \"child\" sha1s, each of which is another multiblob or a blob. The\n>     data in the multiblob is an in-order concatenation of its children.\n> \n>   - you would create multiblobs with a \"smart\" git-add that understands\n>     the filetype and splits the file accordingly (in my case, probably a\n>     chunk of headers and EXIF data, and then a chunk with the image\n>     data).\n\nWell, in your example, the large image part should already be common to \nmany objects due to deltas if they're really the same: different objects \nwill only have different EXIF data plus a delta reference to the same \nbase image object. So in a way the split is already there.  Needs only \nthat some applications exploit this information at runtime.\n\n\nNicolas\n"},{"id":"73792","messageId":"20080407001833.GA16558@sigill.intra.peff.net","threadId":"12979","inReplyTo":"alpine.LFD.1.00.0804062000240.2947@xanadu.home","subject":"Re: Achieving efficient storage of weirdly structured repos","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-04-07T00:18:34Z","receivedAt":"2008-04-07T00:18:34Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Apr 06, 2008 at 08:13:10PM -0400, Nicolas Pitre wrote:\n\n> Well, in your example, the large image part should already be common to \n> many objects due to deltas if they're really the same: different objects \n> will only have different EXIF data plus a delta reference to the same \n> base image object. So in a way the split is already there.  Needs only \n> that some applications exploit this information at runtime.\n\nYes, the resulting packfiles find the deltas and are pretty efficient\n(although it is quite slow to pack).  However, the delta information is\nnot used at all for inexact rename detection. Are you proposing to make\nthat information available to the rename detector?\n\n-Peff\n"},{"id":"73793","messageId":"alpine.LFD.1.00.0804062028260.2947@xanadu.home","threadId":"12979","inReplyTo":"20080407001833.GA16558@sigill.intra.peff.net","subject":"Re: Achieving efficient storage of weirdly structured repos","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-04-07T00:36:19Z","receivedAt":"2008-04-07T00:36:19Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 6 Apr 2008, Jeff King wrote:\n\n> On Sun, Apr 06, 2008 at 08:13:10PM -0400, Nicolas Pitre wrote:\n> \n> > Well, in your example, the large image part should already be common to \n> > many objects due to deltas if they're really the same: different objects \n> > will only have different EXIF data plus a delta reference to the same \n> > base image object. So in a way the split is already there.  Needs only \n> > that some applications exploit this information at runtime.\n> \n> Yes, the resulting packfiles find the deltas and are pretty efficient\n> (although it is quite slow to pack).  However, the delta information is\n> not used at all for inexact rename detection. Are you proposing to make\n> that information available to the rename detector?\n\nIn practice I don't know how well that would work since the \ncurrent heuristic groups deltas and their \nbase according to the name under which those objects are known.  So it \nis possible that some inexact renames end up creating objects that \ncurrently never delta against each other even if that would be the right \nthing to do.\n\nBut in some cases, that might be beneficial to look at the delta object \nthemselves when diffing files as the delta might already contain the \ninformation telling the upper layer that file A and B are in fact 90% \nthe same and that they differ from offset X to Y only.\n\n\nNicolas\n"}]}