{"thread":{"id":"5297","subject":"Huge win, compressing a window of delta runs as a unit","startedAt":"2006-08-16T17:20:30Z","lastAt":"2006-08-21T18:01:55Z","messageCount":36,"participants":["Jon Smirl","Shawn Pearce","Johannes Schindelin","Nicolas Pitre","Linus Torvalds","Jakub Narebski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"25419","messageId":"9e4733910608161020s6855140bs68aaab6e1bbd3bad@mail.gmail.com","threadId":"5297","inReplyTo":null,"subject":"Huge win, compressing a window of delta runs as a unit","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-16T17:20:30Z","receivedAt":"2006-08-16T17:20:30Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"Shawn put together a new version of his import utility that packs all\nof the deltas from a run into a single blob instead of one blob per\ndelta. The idea is to put 10 or more deltas into each delta entry\ninstead of one. The index format would map the 10 sha1's to a single\npacked delta entry which would be expanded when needed. Note that you\nprobably needed multiple entries out of the delta pack to generate the\nrevision you were looking for so this is no real loss on extraction.\n\nI ran it overnight on mozcvs. If his delta pack code is correct this\nis a huge win.\n\nOne entry per delta - 845,42,0150\nPacked deltas - 295,018,474\n65% smaller\n\nThe effect of packing the deltas is to totally eliminate many of the\nredundant zlib dictionaries.\n\nThis is without using a zlib dictionary which gains another 4% form a\n4KB dictionary.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25445","messageId":"20060817040719.GC18500@spearce.org","threadId":"5297","inReplyTo":"9e4733910608161020s6855140bs68aaab6e1bbd3bad@mail.gmail.com","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-17T04:07:19Z","receivedAt":"2006-08-17T04:07:19Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jon Smirl wrote:\n> Shawn put together a new version of his import utility that packs all\n> of the deltas from a run into a single blob instead of one blob per\n> delta. The idea is to put 10 or more deltas into each delta entry\n> instead of one. The index format would map the 10 sha1's to a single\n> packed delta entry which would be expanded when needed. Note that you\n> probably needed multiple entries out of the delta pack to generate the\n> revision you were looking for so this is no real loss on extraction.\n> \n> I ran it overnight on mozcvs. If his delta pack code is correct this\n> is a huge win.\n> \n> One entry per delta - 845,42,0150\n> Packed deltas - 295,018,474\n> 65% smaller\n> \n> The effect of packing the deltas is to totally eliminate many of the\n> redundant zlib dictionaries.\n\nI'm going to try to integrate this into core GIT this weekend.\nMy current idea is to make use of the OBJ_EXT type flag to add\nan extended header field behind the length which describes the\n\"chunk\" as being a delta chain compressed in one zlib stream.\nI'm not overly concerned about saving lots of space in the header\nhere as it looks like we're winning a huge amount of pack space,\nso the extended header will probably itself be a couple of bytes.\nThis keeps the shorter reserved types free for other great ideas. :)\n\nMy primary goal of integrating it into core GIT is to take\nadvantage of verify-pack to check the file fast-import is producing.\nPlus having support for it in sha1_file.c will make it easier to\nperformance test the common access routines that need to be fast,\nlike commit and tree walking.\n\nMy secondary goal is to get a patchset which other folks can try\non their own workloads to see if its as effective as what Jon is\nseeing on the Mozilla archive.\n\n\nUnfortunately I can't think of a way to make this type of pack\nreadable by older software. So this could be creating a pretty\nbig change in the pack format, relatively speaking. :)\n\n-- \nShawn.\n"},{"id":"25453","messageId":"Pine.LNX.4.63.0608170943470.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5297","inReplyTo":"20060817040719.GC18500@spearce.org","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-17T07:56:17Z","receivedAt":"2006-08-17T07:56:17Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 17 Aug 2006, Shawn Pearce wrote:\n\n> Jon Smirl wrote:\n> > \n> > One entry per delta - 845,42,0150\n> > Packed deltas - 295,018,474\n> > 65% smaller\n\nImpressed.\n\n> Unfortunately I can't think of a way to make this type of pack\n> readable by older software. So this could be creating a pretty\n> big change in the pack format, relatively speaking. :)\n\nNot necessarily: the format could stay the same, where multiple object \nnames point to the same entry.\n\nIt should not be a problem, as long as this change is kept local: the same \ngit tools which created this kind of pack have to read it.\n\nHowever, I see some real problems when a public repository has a pack like \nthis: if the client is older, the server has to do some real work, \nespecially in the case of a fresh clone. It gets even worse with a public \nHTTP repo.\n\nThe obvious short-time solution would be to make this opt-in, and use it \nonly on private repositories.\n\nThen, one could think about how to handle the delta-chains in the pack \nprotocol (it should be easy, since you just have to store one object \ninstead of a few), and make this a \"supports\" option.\n\nCiao,\nDscho\n"},{"id":"25454","messageId":"Pine.LNX.4.63.0608171003020.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5297","inReplyTo":"Pine.LNX.4.63.0608170943470.28360@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-17T08:07:24Z","receivedAt":"2006-08-17T08:07:24Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 17 Aug 2006, Johannes Schindelin wrote:\n\n> However, I see some real problems when a public repository has a pack like \n> this: if the client is older, the server has to do some real work, \n> especially in the case of a fresh clone. It gets even worse with a public \n> HTTP repo.\n> \n> The obvious short-time solution would be to make this opt-in, and use it \n> only on private repositories.\n> \n> Then, one could think about how to handle the delta-chains in the pack \n> protocol (it should be easy, since you just have to store one object \n> instead of a few), and make this a \"supports\" option.\n\nOh, and I completely forgot: IIUC you have to unpack the (possibly big) \ndelta-chain until you have the delta you really want, right? So, you might \nwant to have a clever mechanism to keep the delta-chains short for recent \nobjects (i.e. objects you are likely to need more often).\n\nAt least, the delta-chains should be limited by size (_not_ by number of \ndeltas: you can have huge deltas, and if you have to unpack 5 huge deltas \nbefore getting to the huge delta you really need, it takes really long).\n\nCiao,\nDscho\n"},{"id":"25483","messageId":"9e4733910608170736y4863e0ebr55c6c822ae548cca@mail.gmail.com","threadId":"5297","inReplyTo":"Pine.LNX.4.63.0608171003020.28360@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-17T14:36:29Z","receivedAt":"2006-08-17T14:36:29Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/17/06, Johannes Schindelin wrote:\n> At least, the delta-chains should be limited by size (_not_ by number of\n> deltas: you can have huge deltas, and if you have to unpack 5 huge deltas\n> before getting to the huge delta you really need, it takes really long).\n\nThis is not an obvious conclusion. Reducing our pack from 845MB to\n292MB eliminates a huge amount of IO. All of the work I am doing with\nthis pack has been totally IO bound. The CPU time to get from one\ndelta to another is minor compared to the IO time increase if you\nbreak the chains up. Each time you break the chain you have to store a\nfull copy of the file, the IO increase from doing this out weighs the\nCPU time reduction.\n\nI would use a two pack model. One pack holds the 292MB archive and the\nsecond pack is made from recent changes. They can both be the same\nformat since the chains in the second pack won't be very long. We\nmight want to put a flag into an archive pack that tells git-repack\nnot to touch it by default.\n\nAs for public servers there is an immediate win in shifting to the new\npack format. Three hour downloads vs one hour, plus the bandwidth\nbills. Are the tools smart enough to say this is a newer pack format,\nupgrade? It takes far less than two hours to upgrade your git install.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25486","messageId":"Pine.LNX.4.63.0608171738490.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5297","inReplyTo":"9e4733910608170736y4863e0ebr55c6c822ae548cca@mail.gmail.com","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-17T15:45:12Z","receivedAt":"2006-08-17T15:45:12Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 17 Aug 2006, Jon Smirl wrote:\n\n> On 8/17/06, Johannes Schindelin wrote:\n> > At least, the delta-chains should be limited by size (_not_ by number of\n> > deltas: you can have huge deltas, and if you have to unpack 5 huge deltas\n> > before getting to the huge delta you really need, it takes really long).\n> \n> This is not an obvious conclusion.\n\nThe big win is bought by having _one_ zlib stream for multiple deltas, \nright?\n\nSo, everytime you want to access the _last_ delta in the chain, you unpack \n_all_ of them. This quite obvious conclusion is obviously your reason to \npropose two packs, one for the archive of \"old\" objects, and one for the \n\"new\" objects.\n\n> As for public servers there is an immediate win in shifting to the new\n> pack format. Three hour downloads vs one hour, plus the bandwidth\n> bills. Are the tools smart enough to say this is a newer pack format,\n> upgrade? It takes far less than two hours to upgrade your git install.\n\nHave you thought about a non-upgraded client? The server has to repack in \nthat case, and if the client wants a clone, you might not even have the \ntime to kiss your server good-bye before it goes belly up.\n\nThere is an obvious choice here as to how fast people would upgrade their \nservers.\n\nCiao,\nDscho\n"},{"id":"25487","messageId":"Pine.LNX.4.64.0608171220260.11359@localhost.localdomain","threadId":"5297","inReplyTo":"Pine.LNX.4.63.0608171738490.28360@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-17T16:33:21Z","receivedAt":"2006-08-17T16:33:21Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 17 Aug 2006, Johannes Schindelin wrote:\n\n> Hi,\n> \n> On Thu, 17 Aug 2006, Jon Smirl wrote:\n> \n> > On 8/17/06, Johannes Schindelin wrote:\n> > > At least, the delta-chains should be limited by size (_not_ by number of\n> > > deltas: you can have huge deltas, and if you have to unpack 5 huge deltas\n> > > before getting to the huge delta you really need, it takes really long).\n> > \n> > This is not an obvious conclusion.\n> \n> The big win is bought by having _one_ zlib stream for multiple deltas, \n> right?\n> \n> So, everytime you want to access the _last_ delta in the chain, you unpack \n> _all_ of them.\n\nThis is the case whether deltas are separately deflated or not.\n\n> This quite obvious conclusion is obviously your reason to \n> propose two packs, one for the archive of \"old\" objects, and one for the \n> \"new\" objects.\n\nOld objects are usually further down the delta chain and also stored \nfurther from the beginning of the pack. Hence \"new\" objects could still \nhave quick access since even if a delta chain is all in the same zlib \nstream, it is likely that inflating the whole of the zlib stream to get \n\"new\" objects won't be necessary, just like it is done now where only \nthe needed deltas are inflated.\n\n> > As for public servers there is an immediate win in shifting to the new\n> > pack format. Three hour downloads vs one hour, plus the bandwidth\n> > bills. Are the tools smart enough to say this is a newer pack format,\n> > upgrade? It takes far less than two hours to upgrade your git install.\n> \n> Have you thought about a non-upgraded client? The server has to repack in \n> that case, and if the client wants a clone, you might not even have the \n> time to kiss your server good-bye before it goes belly up.\n\nNah. The only overhead for a server to feed an \"old\" pack format from a \n\"new\" pack file is to inflate and deflate some data. That is not _that_ \ncostly.\n\n\nNicolas\n"},{"id":"25488","messageId":"Pine.LNX.4.63.0608171900130.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5297","inReplyTo":"Pine.LNX.4.64.0608171220260.11359@localhost.localdomain","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-17T17:05:46Z","receivedAt":"2006-08-17T17:05:46Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 17 Aug 2006, Nicolas Pitre wrote:\n\n> On Thu, 17 Aug 2006, Johannes Schindelin wrote:\n> \n> > On Thu, 17 Aug 2006, Jon Smirl wrote:\n> > \n> > > On 8/17/06, Johannes Schindelin wrote:\n> > > > At least, the delta-chains should be limited by size (_not_ by number of\n> > > > deltas: you can have huge deltas, and if you have to unpack 5 huge deltas\n> > > > before getting to the huge delta you really need, it takes really long).\n> > > \n> > > This is not an obvious conclusion.\n> > \n> > The big win is bought by having _one_ zlib stream for multiple deltas, \n> > right?\n> > \n> > So, everytime you want to access the _last_ delta in the chain, you unpack \n> > _all_ of them.\n> \n> This is the case whether deltas are separately deflated or not.\n\nOh, now I get it! The delta chain is comprised of exactly those deltas \nwhich are needed to reconstruct a certain object from another object which \nwas stored undeltified in the pack.\n\nNow it makes sense to me that they could be bundled before being deflated. \nIn the pack-index, the objects of that delta-chain could just point to \nthe delta-chain object. Which has a mini-index in its extended header.\n\nOr did I misunderstand again?\n\nCiao,\nDscho\n"},{"id":"25489","messageId":"9e4733910608171017k628ef754s4fcd075d60aaf062@mail.gmail.com","threadId":"5297","inReplyTo":"Pine.LNX.4.63.0608171738490.28360@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-17T17:17:33Z","receivedAt":"2006-08-17T17:17:33Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/17/06, Johannes Schindelin wrote:\n> Hi,\n>\n> On Thu, 17 Aug 2006, Jon Smirl wrote:\n>\n> > On 8/17/06, Johannes Schindelin wrote:\n> > > At least, the delta-chains should be limited by size (_not_ by number of\n> > > deltas: you can have huge deltas, and if you have to unpack 5 huge deltas\n> > > before getting to the huge delta you really need, it takes really long).\n> >\n> > This is not an obvious conclusion.\n>\n> The big win is bought by having _one_ zlib stream for multiple deltas,\n> right?\n>\n> So, everytime you want to access the _last_ delta in the chain, you unpack\n> _all_ of them. This quite obvious conclusion is obviously your reason to\n> propose two packs, one for the archive of \"old\" objects, and one for the\n> \"new\" objects.\n\nDo some measurements, the IO vs CPU time trade off is way in favor of\neliminating the IO. It really doesn't take very much CPU to unpack the\ndelta chain.\n\nThe two pack proprosal was not about reducing the delta chain length;\nthey are reverse deltas, the newest version is always at the front.\nTwo packs are used to avoid repacking the 280MB pack when you do a\nrepack command. It takes 2-3 hours to repack 280MB. Even if if you\njust copy the old pack to the new it take 30 minutes to do all of the\nIO.\n\n> > As for public servers there is an immediate win in shifting to the new\n> > pack format. Three hour downloads vs one hour, plus the bandwidth\n> > bills. Are the tools smart enough to say this is a newer pack format,\n> > upgrade? It takes far less than two hours to upgrade your git install.\n>\n> Have you thought about a non-upgraded client? The server has to repack in\n> that case, and if the client wants a clone, you might not even have the\n> time to kiss your server good-bye before it goes belly up.\n\nIs there a pack format version number built into the server procotol?\nIf not there needs to be one. When there is a mismatch with the server\npack version the client should simply display an error requesting an\nupgrade of the client software.\n\nGit should be designed for forward evolution, not infinite backward\ncompatibility. It is easy to upgrade your client to support the new\nprotocol. The protocol just needs to ensure that the client reliably\ngets an error about the need to upgrade.\n\nForward evolution implies that a client is able to work with older\nservers, but not the inverse, that new servers have to work with old\nclients.\n\n> There is an obvious choice here as to how fast people would upgrade their\n> servers.\n>\n> Ciao,\n> Dscho\n>\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25490","messageId":"Pine.LNX.4.64.0608171233370.11359@localhost.localdomain","threadId":"5297","inReplyTo":"20060817040719.GC18500@spearce.org","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-17T17:22:02Z","receivedAt":"2006-08-17T17:22:02Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 17 Aug 2006, Shawn Pearce wrote:\n\n> I'm going to try to integrate this into core GIT this weekend.\n> My current idea is to make use of the OBJ_EXT type flag to add\n> an extended header field behind the length which describes the\n> \"chunk\" as being a delta chain compressed in one zlib stream.\n> I'm not overly concerned about saving lots of space in the header\n> here as it looks like we're winning a huge amount of pack space,\n> so the extended header will probably itself be a couple of bytes.\n> This keeps the shorter reserved types free for other great ideas. :)\n\nWe're streaving for optimal data storage here so don't be afraid to use \none of the available types for an \"object stream\" object. Because when \nyou think of it, the deflating of multiple objects into a single zlib \nstream can be applied to all object types not only deltas. If ever \ndeflating many blobs into one zlib stream is dimmed worth it then the \nencoding will already be ready for it. Also you can leverage existing \ncode to write headers, etc.\n\nI'd suggest you use OBJ_GROUP = 0 as a new primary object type. Then \nthe \"size\" field in the header could then become the number of objects \nthat are included in the group. Most of the time that will fit in the \nlow 4 bits of the first header byte, but if there is more than 15 \ngrouped objects then more bits can be used on the following byte. \nAnyway so far all the code to generate and parse that is already there. \nIf ever there is a need for more extensions that could be prefixed with \na pure zero byte (an object group with a zero object count which is \ndistinguishable from a real group).\n\nThen, having the number of grouped objects, you just have to list the \nusual headers for those objects, which are their type and inflated size \njust like regular object headers, including the base sha1 for deltas. \nAgain you already have code to produce and parse those.\n\nAnd finally just append the objects payload in a single deflated stream.\n\nThis way the reading of an object from a group can be optimized if the \nobject data is located at the beginning of the stream such that you only \nneed to inflate the amount of bytes leading to the desired data \n(possibly caching those for further delta replaying), inflate \nthe needed data for the desired object and then ignoring the remaining \nof the stream.\n\n\nNicolas\n"},{"id":"25491","messageId":"9e4733910608171022w25886d13ka40e5752fec4680b@mail.gmail.com","threadId":"5297","inReplyTo":"Pine.LNX.4.64.0608171220260.11359@localhost.localdomain","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-17T17:22:15Z","receivedAt":"2006-08-17T17:22:15Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/17/06, Nicolas Pitre wrote:\n> Nah. The only overhead for a server to feed an \"old\" pack format from a\n> \"new\" pack file is to inflate and deflate some data. That is not _that_\n> costly.\n\nIt is costly because the Mozilla pack is going to inflate from 295MB\nto 845MB. It will take you much longer to download an extra 500MB than\nupgrading your client would take.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25492","messageId":"Pine.LNX.4.64.0608171323330.11359@localhost.localdomain","threadId":"5297","inReplyTo":"9e4733910608171017k628ef754s4fcd075d60aaf062@mail.gmail.com","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-17T17:32:26Z","receivedAt":"2006-08-17T17:32:26Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 17 Aug 2006, Jon Smirl wrote:\n\n> Is there a pack format version number built into the server procotol?\n> If not there needs to be one. When there is a mismatch with the server\n> pack version the client should simply display an error requesting an\n> upgrade of the client software.\n\nThere is a pack version number. Reception of an unknown pack already \nproduces an error:\n\n if (!pack_version_ok(hdr->hdr_version))\n die(\"unknown pack file version %d\", ntohl(hdr->hdr_version));\n\nThat will occur really early in a pull or clone when using the native \nprotocol.\n\n> Git should be designed for forward evolution, not infinite backward\n> compatibility. It is easy to upgrade your client to support the new\n> protocol. The protocol just needs to ensure that the client reliably\n> gets an error about the need to upgrade.\n> \n> Forward evolution implies that a client is able to work with older\n> servers, but not the inverse, that new servers have to work with old\n> clients.\n\nAnd still, if we really wanted, the server could have the ability to \nstream an old pack format by simply inflating the grouped objects and \ndeflating them individually all on the fly, which is not necessarily \nthat costly. But it might still be a good idea to simply have the \nability to generate both formats and make the grouped deltas the default \nonly after a while.\n\n\nNicolas\n"},{"id":"25494","messageId":"9e4733910608171103j545a7fd5x2b61b97376de04be@mail.gmail.com","threadId":"5297","inReplyTo":"Pine.LNX.4.64.0608171233370.11359@localhost.localdomain","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-17T18:03:05Z","receivedAt":"2006-08-17T18:03:05Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/17/06, Nicolas Pitre wrote:\n> We're streaving for optimal data storage here so don't be afraid to use\n> one of the available types for an \"object stream\" object. Because when\n> you think of it, the deflating of multiple objects into a single zlib\n> stream can be applied to all object types not only deltas. If ever\n> deflating many blobs into one zlib stream is dimmed worth it then the\n> encoding will already be ready for it. Also you can leverage existing\n> code to write headers, etc.\n\nHere are two more case that need to be accounted for in the packs.\n\n1) If you zip something and it gets bigger. We need an entry that just\nstores the object without it being zipped. Zipping jpegs or mpegs will\nlikely make them significantly bigger. Or does zlib like already\ndetect this case and do a null compression?\n\n2) If you delta something and the delta is bigger than the object\nbeing deltaed. The delta code should detect this and store the full\nobject instead of the delta. Again jpegs and mpegs will trigger this.\nYou may even want to say that the delta has to be smaller than 80% of\nthe full object.\n\nShawn is planning on looking into true dictionary based compression.\nThat will generate even more types inside of a pack. If dictionary\ncompression works out full text search can be added with a little more\noverhead. True dictionary based compression has the potential to go\neven smaller than the current 280MB. The optimal way to do this is for\neach pack to contain it's own dictionary.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25495","messageId":"9e4733910608171106l74ee4d39x6e34900877c24bb0@mail.gmail.com","threadId":"5297","inReplyTo":"Pine.LNX.4.64.0608171323330.11359@localhost.localdomain","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-17T18:06:25Z","receivedAt":"2006-08-17T18:06:25Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/17/06, Nicolas Pitre wrote:\n> On Thu, 17 Aug 2006, Jon Smirl wrote:\n>\n> > Is there a pack format version number built into the server procotol?\n> > If not there needs to be one. When there is a mismatch with the server\n> > pack version the client should simply display an error requesting an\n> > upgrade of the client software.\n>\n> There is a pack version number. Reception of an unknown pack already\n> produces an error:\n>\n> if (!pack_version_ok(hdr->hdr_version))\n> die(\"unknown pack file version %d\", ntohl(hdr->hdr_version));\n>\n> That will occur really early in a pull or clone when using the native\n> protocol.\n\nCan this be fixed so that if the pack protocol coming from the server\nis greater than the one handled by the client. they client gets a nice\nhint about upgrading?\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25496","messageId":"Pine.LNX.4.64.0608171413160.11359@localhost.localdomain","threadId":"5297","inReplyTo":"9e4733910608171022w25886d13ka40e5752fec4680b@mail.gmail.com","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-17T18:15:53Z","receivedAt":"2006-08-17T18:15:53Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 17 Aug 2006, Jon Smirl wrote:\n\n> On 8/17/06, Nicolas Pitre wrote:\n> > Nah. The only overhead for a server to feed an \"old\" pack format from a\n> > \"new\" pack file is to inflate and deflate some data. That is not _that_\n> > costly.\n> \n> It is costly because the Mozilla pack is going to inflate from 295MB\n> to 845MB. It will take you much longer to download an extra 500MB than\n> upgrading your client would take.\n\nI didn't say it isn't costly. I said that it isn't _that_ costly to the \npoint of bringing down a server.\n\n\nNicolas\n"},{"id":"25497","messageId":"Pine.LNX.4.64.0608171416030.11359@localhost.localdomain","threadId":"5297","inReplyTo":"9e4733910608171103j545a7fd5x2b61b97376de04be@mail.gmail.com","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-17T18:24:54Z","receivedAt":"2006-08-17T18:24:54Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 17 Aug 2006, Jon Smirl wrote:\n\n> On 8/17/06, Nicolas Pitre wrote:\n> > We're streaving for optimal data storage here so don't be afraid to use\n> > one of the available types for an \"object stream\" object. Because when\n> > you think of it, the deflating of multiple objects into a single zlib\n> > stream can be applied to all object types not only deltas. If ever\n> > deflating many blobs into one zlib stream is dimmed worth it then the\n> > encoding will already be ready for it. Also you can leverage existing\n> > code to write headers, etc.\n> \n> Here are two more case that need to be accounted for in the packs.\n> \n> 1) If you zip something and it gets bigger. We need an entry that just\n> stores the object without it being zipped. Zipping jpegs or mpegs will\n> likely make them significantly bigger. Or does zlib like already\n> detect this case and do a null compression?\n\nzlib appears to do the right thing here.\n\n> 2) If you delta something and the delta is bigger than the object\n> being deltaed. The delta code should detect this and store the full\n> object instead of the delta. Again jpegs and mpegs will trigger this.\n> You may even want to say that the delta has to be smaller than 80% of\n> the full object.\n\nI'd invite you to read te try_delta() code in \n[builtin-]builtin-pack-objects.c. You might find that we're already way \nmore agressive than that with rather simple heuristics that have been \ntweaked and tuned for over a year now. The commit logs for that file \n(before the rename to builtin-pack-objects.c) is also quite \nenlightening.\n\n\nNicolas\n"},{"id":"25512","messageId":"Pine.LNX.4.64.0608172323520.11359@localhost.localdomain","threadId":"5297","inReplyTo":"9e4733910608161020s6855140bs68aaab6e1bbd3bad@mail.gmail.com","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-18T04:03:37Z","receivedAt":"2006-08-18T04:03:37Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 16 Aug 2006, Jon Smirl wrote:\n\n> Shawn put together a new version of his import utility that packs all\n> of the deltas from a run into a single blob instead of one blob per\n> delta. The idea is to put 10 or more deltas into each delta entry\n> instead of one. The index format would map the 10 sha1's to a single\n> packed delta entry which would be expanded when needed. Note that you\n> probably needed multiple entries out of the delta pack to generate the\n> revision you were looking for so this is no real loss on extraction.\n> \n> I ran it overnight on mozcvs. If his delta pack code is correct this\n> is a huge win.\n> \n> One entry per delta - 845,42,0150\n> Packed deltas - 295,018,474\n> 65% smaller\n\nWell, I have to state that I don't believe those results to be right.\n\nNot that I question the results you obtained, but rather that Shawn's \npack generation is most probably broken.\n\nSince I was highly suspicious looking at the above size difference (it \nis just too good to be true), I did a quick hack to pack-objects.c to \nproduce packs with all deltas depending on the same root object into the \nsame zlib stream. In effect I implemented exactly what Shawn pretends \nto have done but directly in pack-objects.c so git-repack could be used \nwith existing repositories like the linux kernel in order to validate \nthe concept.\n\nResults:\n\nOne entry per delta - 122,103,455 \nPacked (or grouped) deltas : 108,479,014\n\nOnly 11% smaller.\n\nI was really enthousiastic at first when I saw the result you obtained, \nbut I no longer believe it can be right. \n\nFurthermore, such a pack organization has many disadvantages: it \nprevents trivial delta data reuse for incremental push/pull operations \nwhich is a huge performance penalty (bad for servers), as well as making \nrandom object extraction from such a pack somewhat more complex. Those \ndisadvantages greatly outweight the 11% size saving IMHO.\n\nA better way to get such a size saving is to increase the window and \ndepth parameters. For example, a window of 20 and depth of 20 can \nusually provide a pack size saving greater than 11% with none of the \ndisadvantages mentioned above.\n\nI therefore don't think this idea should be pursued any further.\n\nFor completeness you can find my changes to pack-objects below. Beware \nthat this produces packs that cannot be read back so backup your \nrepository first before playing with this.\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 448461b..bfae892 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -227,7 +227,7 @@ static int encode_header(enum object_typ\n \tint n = 1;\n \tunsigned char c;\n \n-\tif (type < OBJ_COMMIT || type > OBJ_DELTA)\n+\tif (type < 0 || type > OBJ_DELTA)\n \t\tdie(\"bad type %d\", type);\n \n \tc = (type << 4) | (size & 15);\n@@ -332,6 +332,8 @@ static unsigned long write_object(struct\n \treturn hdrlen + datalen;\n }\n \n+#if 0\n+\n static unsigned long write_one(struct sha1file *f,\n \t\t\t struct object_entry *e,\n \t\t\t unsigned long offset)\n@@ -349,6 +351,107 @@ static unsigned long write_one(struct sh\n \treturn offset;\n }\n \n+#else\n+\n+static unsigned count_delta_childs(struct object_entry *e, unsigned long o)\n+{\n+\tunsigned count = 0;\n+\tstruct object_entry *child = e->delta_child;\n+\twhile (child) {\n+\t\tcount += 1 + count_delta_childs(child, o);\n+\t\tif (child->offset)\n+\t\t\tdie(\"object already seen???\");\n+\t\tchild->offset = o;\n+\t\tchild = child->delta_sibling;\n+\t}\n+\treturn count;\n+}\n+\n+static unsigned long write_delta_headers(struct sha1file *f, struct object_entry *e, unsigned long *size)\n+{\n+\tunsigned long offset = 0;\n+\tstruct object_entry *child = e->delta_child;\n+\twhile (child) {\n+\t\tunsigned char header[10];\n+\t\tunsigned hdrlen;\n+\t\thdrlen = encode_header(OBJ_DELTA, child->delta_size, header);\n+\t\t*size += child->delta_size;\n+\t\tsha1write(f, header, hdrlen);\n+\t\tsha1write(f, child->delta, 20);\n+\t\toffset += hdrlen + 20;\n+\t\toffset += write_delta_headers(f, child, size);\n+\t\tchild = child->delta_sibling;\n+\t}\n+\treturn offset;\n+}\n+\n+static void * concat_delta_data(struct object_entry *e, void *buf)\n+{\n+\tstruct object_entry *child = e->delta_child;\n+\twhile (child) {\n+\t\tchar type[10];\n+\t\tunsigned long size;\n+\t\tvoid *data = read_sha1_file(child->sha1, type, &size);\n+\t\tif (!data)\n+\t\t\tdie(\"unable to read %s\", sha1_to_hex(child->sha1));\n+\t\tdata = delta_against(data, size, child);\n+\t\tmemcpy(buf, data, child->delta_size);\n+\t\tbuf += child->delta_size;\n+\t\tfree(data);\n+\t\twritten++;\n+\t\twritten_delta++;\n+\t\tbuf = concat_delta_data(child, buf);\n+\t\tchild = child->delta_sibling;\n+\t}\n+\treturn buf;\n+}\n+\n+static unsigned long write_one(struct sha1file *f,\n+\t\t\t struct object_entry *e,\n+\t\t\t unsigned long offset)\n+{\n+\tunsigned char header[10];\n+\tunsigned count, hdrlen;\n+\tunsigned long size;\n+\tvoid *buf, *p;\n+\n+\tif (e->offset)\n+\t\t/* offset starts from header size and cannot be zero\n+\t\t * if it is written already.\n+\t\t */\n+\t\treturn offset;\n+\tif (!e->delta) {\n+\t\te->offset = offset;\n+\t\treturn offset + write_object(f, e);\n+\t}\n+\n+\t/* find delta root object */\n+\twhile (e->delta)\n+\t\te = e->delta;\n+\n+\t/* count how many deltas depend on it */\n+\tcount = count_delta_childs(e, offset);\n+\n+\t/* write header for object group */\n+\thdrlen = encode_header(0, count, header);\n+\tsha1write(f, header, hdrlen);\n+\toffset += hdrlen;\n+\n+\t/* write each object's header and find total data size */\n+\tsize = 0;\n+\toffset += write_delta_headers(f, e, &size);\n+\n+\t/* write concatenated object data buffer */\n+\tbuf = xmalloc(size);\n+\tp = concat_delta_data(e, buf);\t\n+\toffset += sha1write_compressed(f, buf, p-buf);\n+\tfree(buf);\n+\n+\treturn offset;\n+}\n+\n+#endif\n+\n static void write_pack_file(void)\n {\n \tint i;\n\n\nNicolas\n"},{"id":"25552","messageId":"9e4733910608180553r34fa7b25he0bf910ef804630f@mail.gmail.com","threadId":"5297","inReplyTo":"Pine.LNX.4.64.0608172323520.11359@localhost.localdomain","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-18T12:53:10Z","receivedAt":"2006-08-18T12:53:10Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"I attached Shawn's code. He is gone until Monday and can't defend it.\n\nDo note that I am running this on the Mozilla CVS which is over 10\nyears old. Some of the files have over 2,000 deltas. I average 10\ndeltas per file but the distribution is not at all even. Many files\nget checked-in and never changed, for example 1000's of images.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n\n\n/*\nFormat of STDIN stream:\n\n stream ::= cmd*;\n\n cmd ::= new_blob\n | new_branch\n | new_commit\n | new_tag\n ;\n\n new_blob ::= 'blob' lf\n\tmark?\n file_content;\n file_content ::= data;\n\n new_branch ::= 'branch' sp ref_str lf\n ('from' sp (ref_str | hexsha1 | sha1exp_str | idnum) lf)?\n lf;\n\n new_commit ::= 'commit' sp ref_str lf\n\tmark?\n\t('author' sp name '<' email '>' ts tz lf)?\n\t'committer' sp name '<' email '>' ts tz lf\n\tcommit_msg\n file_change*\n lf;\n commit_msg ::= data;\n\n file_change ::= 'M' sp mode sp (hexsha1 | idnum) sp path_str lf\n | 'D' sp path_str lf\n ;\n mode ::= '644' | '755';\n\n new_tag ::= 'tag' sp tag_str lf\n 'from' sp (ref_str | hexsha1 | sha1exp_str | idnum) lf\n\t'tagger' sp name '<' email '>' ts tz lf\n tag_msg;\n tag_msg ::= data;\n\n # note: the first idnum in a stream should be 1 and subsequent\n # idnums should not have gaps between values as this will cause\n # the stream parser to reserve space for the gapped values. An\n\t # idnum can be updated in the future to a new object by issuing\n # a new mark directive with the old idnum.\n\t #\n mark ::= 'mark' sp idnum lf;\n\n # note: declen indicates the length of binary_data in bytes.\n # declen does not include the lf preceeding or trailing the\n # binary data.\n #\n data ::= 'data' sp declen lf\n binary_data\n\tlf;\n\n # note: quoted strings are C-style quoting supporting \\c for\n # common escapes of 'c' (e..g \\n, \\t, \\\\, \\\") or \\nnn where nnn\n\t # is the signed byte value in octal. Note that the only\n # characters which must actually be escaped to protect the\n # stream formatting is: \\, \" and LF. Otherwise these values\n\t # are UTF8.\n #\n ref_str ::= ref | '\"' quoted(ref) '\"' ;\n sha1exp_str ::= sha1exp | '\"' quoted(sha1exp) '\"' ;\n tag_str ::= tag | '\"' quoted(tag) '\"' ;\n path_str ::= path | '\"' quoted(path) '\"' ;\n\n declen ::= # unsigned 32 bit value, ascii base10 notation;\n binary_data ::= # file content, not interpreted;\n\n sp ::= # ASCII space character;\n lf ::= # ASCII newline (LF) character;\n\n # note: a colon (':') must precede the numerical value assigned to\n\t # an idnum. This is to distinguish it from a ref or tag name as\n # GIT does not permit ':' in ref or tag strings.\n\t #\n idnum ::= ':' declen;\n path ::= # GIT style file path, e.g. \"a/b/c\";\n ref ::= # GIT ref name, e.g. \"refs/heads/MOZ_GECKO_EXPERIMENT\";\n tag ::= # GIT tag name, e.g. \"FIREFOX_1_5\";\n sha1exp ::= # Any valid GIT SHA1 expression;\n hexsha1 ::= # SHA1 in hexadecimal format;\n\n # note: name and email are UTF8 strings, however name must not\n\t # contain '<' or lf and email must not contain any of the\n # following: '<', '>', lf.\n\t #\n name ::= # valid GIT author/committer name;\n email ::= # valid GIT author/committer email;\n ts ::= # time since the epoch in seconds, ascii base10 notation;\n tz ::= # GIT style timezone;\n*/\n\n#include \"builtin.h\"\n#include \"cache.h\"\n#include \"object.h\"\n#include \"blob.h\"\n#include \"tree.h\"\n#include \"delta.h\"\n#include \"pack.h\"\n#include \"refs.h\"\n#include \"csum-file.h\"\n#include \"strbuf.h\"\n#include \"quote.h\"\n\nstruct object_entry\n{\n\tstruct object_entry *next;\n\tenum object_type type;\n\tunsigned long offset;\n\tunsigned char sha1[20];\n};\n\nstruct object_entry_pool\n{\n\tstruct object_entry_pool *next_pool;\n\tstruct object_entry *next_free;\n\tstruct object_entry *end;\n\tstruct object_entry entries[FLEX_ARRAY]; /* more */\n};\n\nstruct last_object\n{\n\tvoid *data;\n\tunsigned int len;\n\tunsigned int depth;\n\tunsigned char sha1[20];\n};\n\nstruct mem_pool\n{\n\tstruct mem_pool *next_pool;\n\tchar *next_free;\n\tchar *end;\n\tchar space[FLEX_ARRAY]; /* more */\n};\n\nstruct atom_str\n{\n\tstruct atom_str *next_atom;\n\tint str_len;\n\tchar str_dat[FLEX_ARRAY]; /* more */\n};\n\nstruct tree_content;\nstruct tree_entry\n{\n\tstruct tree_content *tree;\n\tstruct atom_str* name;\n\tunsigned int mode;\n\tunsigned char sha1[20];\n};\n\nstruct tree_content\n{\n\tunsigned int entry_capacity; /* must match avail_tree_content */\n\tunsigned int entry_count;\n\tstruct tree_entry *entries[FLEX_ARRAY]; /* more */\n};\n\nstruct avail_tree_content\n{\n\tunsigned int entry_capacity; /* must match tree_content */\n\tstruct avail_tree_content *next_avail;\n};\n\nstruct branch\n{\n\tstruct branch *table_next_branch;\n\tstruct branch *active_next_branch;\n\tconst char *name;\n\tunsigned long last_commit;\n\tstruct tree_entry branch_tree;\n\tunsigned char sha1[20];\n};\n\n\n/* Stats and misc. counters */\nstatic int max_depth = 10;\nstatic unsigned long alloc_count;\nstatic unsigned long branch_count;\nstatic unsigned long object_count;\nstatic unsigned long duplicate_count;\nstatic unsigned long object_count_by_type[9];\nstatic unsigned long duplicate_count_by_type[9];\nstatic unsigned long stream_cnt;\n\n/* Memory pools */\nstatic size_t mem_pool_alloc = 2*1024*1024 - sizeof(struct mem_pool);\nstatic size_t total_allocd;\nstatic struct mem_pool *mem_pool;\n\n/* Atom management */\nstatic unsigned int atom_table_sz = 4451;\nstatic unsigned int atom_cnt;\nstatic struct atom_str **atom_table;\n\n/* The .pack file being generated */\nstatic int pack_fd;\nstatic unsigned long pack_offset;\nstatic unsigned char pack_sha1[20];\nstatic z_stream zs;\nstatic int zs_live;\nstatic void* zs_out;\nstatic unsigned long zs_outlen;\n\n/* Table of objects we've written. */\nstatic unsigned int object_entry_alloc = 1000;\nstatic struct object_entry_pool *blocks;\nstatic struct object_entry *object_table[1 << 16];\n\n/* Our last blob */\nstatic struct last_object last_blob;\n\n/* Tree management */\nstatic unsigned int tree_entry_alloc = 1000;\nstatic void *avail_tree_entry;\nstatic unsigned int avail_tree_table_sz = 100;\nstatic struct avail_tree_content **avail_tree_table;\n\n/* Branch data */\nstatic unsigned int max_active_branches = 5;\nstatic unsigned int cur_active_branches;\nstatic unsigned int branch_table_sz = 1039;\nstatic struct branch **branch_table;\nstatic struct branch *active_branches;\n\n/* Input stream parsing */\nstatic struct strbuf command_buf;\nstatic unsigned long command_mark;\n\n\nstatic void alloc_objects(int cnt)\n{\n\tstruct object_entry_pool *b;\n\n\tb = xmalloc(sizeof(struct object_entry_pool)\n\t\t+ cnt * sizeof(struct object_entry));\n\tb->next_pool = blocks;\n\tb->next_free = b->entries;\n\tb->end = b->entries + cnt;\n\tblocks = b;\n\talloc_count += cnt;\n}\n\nstatic struct object_entry* new_object(unsigned char *sha1)\n{\n\tstruct object_entry *e;\n\n\tif (blocks->next_free == blocks->end)\n\t\talloc_objects(object_entry_alloc);\n\n\te = blocks->next_free++;\n\tmemcpy(e->sha1, sha1, sizeof(e->sha1));\n\treturn e;\n}\n\nstatic struct object_entry* find_object(unsigned char *sha1)\n{\n\tunsigned int h = sha1[0] << 8 | sha1[1];\n\tstruct object_entry *e;\n\tfor (e = object_table[h]; e; e = e->next)\n\t\tif (!memcmp(sha1, e->sha1, sizeof(e->sha1)))\n\t\t\treturn e;\n\treturn NULL;\n}\n\nstatic struct object_entry* insert_object(unsigned char *sha1)\n{\n\tunsigned int h = sha1[0] << 8 | sha1[1];\n\tstruct object_entry *e = object_table[h];\n\tstruct object_entry *p = NULL;\n\n\twhile (e) {\n\t\tif (!memcmp(sha1, e->sha1, sizeof(e->sha1)))\n\t\t\treturn e;\n\t\tp = e;\n\t\te = e->next;\n\t}\n\n\te = new_object(sha1);\n\te->next = NULL;\n\te->offset = 0;\n\tif (p)\n\t\tp->next = e;\n\telse\n\t\tobject_table[h] = e;\n\treturn e;\n}\n\nstatic unsigned int hc_str(const char *s, size_t len)\n{\n\tunsigned int r = 0;\n\twhile (len-- > 0)\n\t\tr = r * 31 + *s++;\n\treturn r;\n}\n\nstatic void* pool_alloc(size_t len)\n{\n\tstruct mem_pool *p;\n\tvoid *r;\n\n\tfor (p = mem_pool; p; p = p->next_pool)\n\t\tif ((p->end - p->next_free >= len))\n\t\t\tbreak;\n\n\tif (!p) {\n\t\tif (len >= (mem_pool_alloc/2)) {\n\t\t\ttotal_allocd += len;\n\t\t\treturn xmalloc(len);\n\t\t}\n\t\ttotal_allocd += sizeof(struct mem_pool) + mem_pool_alloc;\n\t\tp = xmalloc(sizeof(struct mem_pool) + mem_pool_alloc);\n\t\tp->next_pool = mem_pool;\n\t\tp->next_free = p->space;\n\t\tp->end = p->next_free + mem_pool_alloc;\n\t\tmem_pool = p;\n\t}\n\n\tr = p->next_free;\n\tp->next_free += len;\n\treturn r;\n}\n\nstatic void* pool_calloc(size_t count, size_t size)\n{\n\tsize_t len = count * size;\n\tvoid *r = pool_alloc(len);\n\tmemset(r, 0, len);\n\treturn r;\n}\n\nstatic char* pool_strdup(const char *s)\n{\n\tchar *r = pool_alloc(strlen(s) + 1);\n\tstrcpy(r, s);\n\treturn r;\n}\n\nstatic struct atom_str* to_atom(const char *s, size_t len)\n{\n\tunsigned int hc = hc_str(s, len) % atom_table_sz;\n\tstruct atom_str *c;\n\t\n\tfor (c = atom_table[hc]; c; c = c->next_atom)\n\t\tif (c->str_len == len && !strncmp(s, c->str_dat, len))\n\t\t\treturn c;\n\n\tc = pool_alloc(sizeof(struct atom_str) + len + 1);\n\tc->str_len = len;\n\tstrncpy(c->str_dat, s, len);\n\tc->str_dat[len] = 0;\n\tc->next_atom = atom_table[hc];\n\tatom_table[hc] = c;\n\tatom_cnt++;\n\treturn c;\n}\n\nstatic struct branch* lookup_branch(const char *name)\n{\n\tunsigned int hc = hc_str(name, strlen(name)) % branch_table_sz;\n\tstruct branch *b;\n\n\tfor (b = branch_table[hc]; b; b = b->table_next_branch)\n\t\tif (!strcmp(name, b->name))\n\t\t\treturn b;\n\treturn NULL;\n}\n\nstatic struct branch* new_branch(const char *name)\n{\n\tunsigned int hc = hc_str(name, strlen(name)) % branch_table_sz;\n\tstruct branch* b = lookup_branch(name);\n\n\tif (b)\n\t\tdie(\"Invalid attempt to create duplicate branch: %s\", name);\n\tif (check_ref_format(name))\n\t\tdie(\"Branch name doesn't conform to GIT standards: %s\", name);\n\n\tb = pool_calloc(1, sizeof(struct branch));\n\tb->name = pool_strdup(name);\n\tb->table_next_branch = branch_table[hc];\n\tbranch_table[hc] = b;\n\tbranch_count++;\n\treturn b;\n}\n\nstatic unsigned int hc_entries(unsigned int cnt)\n{\n\tcnt = cnt & 7 ? (cnt / 8) + 1 : cnt / 8;\n\treturn cnt < avail_tree_table_sz ? cnt : avail_tree_table_sz - 1;\n}\n\nstatic struct tree_content* new_tree_content(unsigned int cnt)\n{\n\tstruct avail_tree_content *f, *l = NULL;\n\tstruct tree_content *t;\n\tunsigned int hc = hc_entries(cnt);\n\n\tfor (f = avail_tree_table[hc]; f; l = f, f = f->next_avail)\n\t\tif (f->entry_capacity >= cnt)\n\t\t\tbreak;\n\n\tif (f) {\n\t\tif (l)\n\t\t\tl->next_avail = f->next_avail;\n\t\telse\n\t\t\tavail_tree_table[hc] = f->next_avail;\n\t} else {\n\t\tcnt = cnt & 7 ? ((cnt / 8) + 1) * 8 : cnt;\n\t\tf = pool_alloc(sizeof(*t) + sizeof(t->entries[0]) * cnt);\n\t\tf->entry_capacity = cnt;\n\t}\n\n\tt = (struct tree_content*)f;\n\tt->entry_count = 0;\n\treturn t;\n}\n\nstatic void release_tree_entry(struct tree_entry *e);\nstatic void release_tree_content(struct tree_content *t)\n{\n\tstruct avail_tree_content *f = (struct avail_tree_content*)t;\n\tunsigned int hc = hc_entries(f->entry_capacity);\n\tunsigned int i;\n\tfor (i = 0; i < t->entry_count; i++)\n\t\trelease_tree_entry(t->entries[i]);\n\tf->next_avail = avail_tree_table[hc];\n\tavail_tree_table[hc] = f;\n}\n\nstatic struct tree_content* grow_tree_content(\n\tstruct tree_content *t,\n\tint amt)\n{\n\tstruct tree_content *r = new_tree_content(t->entry_count + amt);\n\tr->entry_count = t->entry_count;\n\tmemcpy(r->entries,t->entries,t->entry_count*sizeof(t->entries[0]));\n\trelease_tree_content(t);\n\treturn r;\n}\n\nstatic struct tree_entry* new_tree_entry()\n{\n\tstruct tree_entry *e;\n\n\tif (!avail_tree_entry) {\n\t\tunsigned int n = tree_entry_alloc;\n\t\tavail_tree_entry = e = xmalloc(n * sizeof(struct tree_entry));\n\t\twhile (n--) {\n\t\t\t*((void**)e) = e + 1;\n\t\t\te++;\n\t\t}\n\t}\n\n\te = avail_tree_entry;\n\tavail_tree_entry = *((void**)e);\n\treturn e;\n}\n\nstatic void release_tree_entry(struct tree_entry *e)\n{\n\tif (e->tree)\n\t\trelease_tree_content(e->tree);\n\t*((void**)e) = avail_tree_entry;\n\tavail_tree_entry = e;\n}\n\nstatic void yread(int fd, void *buffer, size_t length)\n{\n\tssize_t ret = 0;\n\twhile (ret < length) {\n\t\tssize_t size = xread(fd, (char *) buffer + ret, length - ret);\n\t\tif (!size)\n\t\t\tdie(\"Read from descriptor %i: end of stream\", fd);\n\t\tif (size < 0)\n\t\t\tdie(\"Read from descriptor %i: %s\", fd, strerror(errno));\n\t\tret += size;\n\t}\n}\n\nstatic void ywrite(int fd, void *buffer, size_t length)\n{\n\tssize_t ret = 0;\n\twhile (ret < length) {\n\t\tssize_t size = xwrite(fd, (char *) buffer + ret, length - ret);\n\t\tif (!size)\n\t\t\tdie(\"Write to descriptor %i: end of file\", fd);\n\t\tif (size < 0)\n\t\t\tdie(\"Write to descriptor %i: %s\", fd, strerror(errno));\n\t\tret += size;\n\t}\n}\n\nstatic size_t encode_header(\n\tenum object_type type,\n\tsize_t size,\n\tunsigned char *hdr)\n{\n\tint n = 1;\n\tunsigned char c;\n\n\tif (type < OBJ_COMMIT || type > OBJ_DELTA)\n\t\tdie(\"bad type %d\", type);\n\n\tc = (type << 4) | (size & 15);\n\tsize >>= 4;\n\twhile (size) {\n\t\t*hdr++ = c | 0x80;\n\t\tc = size & 0x7f;\n\t\tsize >>= 7;\n\t\tn++;\n\t}\n\t*hdr = c;\n\treturn n;\n}\n\nstatic void zs_finish()\n{\n\tif (zs_live) {\n\t\twhile (deflate(&zs, Z_FINISH) == Z_OK) {\n\t\t\tif (zs.total_out) {\n\t\t\t\tywrite(pack_fd, zs_out, zs.total_out);\n\t\t\t\tpack_offset += zs.total_out;\n\t\t\t\tzs.next_out = zs_out;\n\t\t\t\tzs.avail_out = zs_outlen;\n\t\t\t\tzs.total_out = 0;\n\t\t\t}\n\t\t}\n\t\tdeflateEnd(&zs);\n\t\tfree(zs_out);\n\t\tstream_cnt++;\n\t}\n}\n\nstatic int store_object(\n\tenum object_type type,\n\tvoid *dat,\n\tsize_t datlen,\n\tstruct last_object *last,\n\tunsigned char *sha1out)\n{\n\tvoid *delta;\n\tstruct object_entry *e;\n\tunsigned char hdr[96];\n\tunsigned char sha1[20];\n\tunsigned long hdrlen, deltalen;\n\tSHA_CTX c;\n\n\thdrlen = sprintf((char*)hdr,\"%s %lu\",type_names[type],datlen) + 1;\n\tSHA1_Init(&c);\n\tSHA1_Update(&c, hdr, hdrlen);\n\tSHA1_Update(&c, dat, datlen);\n\tSHA1_Final(sha1, &c);\n\tif (sha1out)\n\t\tmemcpy(sha1out, sha1, sizeof(sha1));\n\n\te = insert_object(sha1);\n\tif (e->offset) {\n\t\tduplicate_count++;\n\t\tduplicate_count_by_type[type]++;\n\t\treturn 1;\n\t}\n\te->type = type;\n\te->offset = pack_offset;\n\tobject_count++;\n\tobject_count_by_type[type]++;\n\n\tif (last && last->data && last->depth < max_depth)\n\t\tdelta = diff_delta(last->data, last->len,\n\t\t\tdat, datlen,\n\t\t\t&deltalen, 0);\n\telse {\n\t\tzs_finish();\n\t\tdelta = 0;\n\t\tmemset(&zs, 0, sizeof(zs));\n\t\tdeflateInit(&zs, zlib_compression_level);\n\t\tzs_live = 1;\n\t\tzs_outlen = 1024*1024;\n\t\tzs_out = xmalloc(zs_outlen);\n\t\tzs.next_out = zs_out;\n\t\tzs.avail_out = zs_outlen;\n\t}\n\n\tif (delta) {\n\t\tlast->depth++;\n\t\tzs.next_in = delta;\n\t\tzs.avail_in = deltalen;\n\t\thdrlen = encode_header(OBJ_DELTA, deltalen, hdr);\n\t\tywrite(pack_fd, hdr, hdrlen);\n\t\tywrite(pack_fd, last->sha1, sizeof(sha1));\n\t\tpack_offset += hdrlen + sizeof(sha1);\n\t} else {\n\t\tif (last)\n\t\t\tlast->depth = 0;\n\t\tzs.next_in = dat;\n\t\tzs.avail_in = datlen;\n\t\thdrlen = encode_header(type, datlen, hdr);\n\t\tywrite(pack_fd, hdr, hdrlen);\n\t\tpack_offset += hdrlen;\n\t}\n\n\twhile (deflate(&zs, Z_NO_FLUSH) == Z_OK) {\n\t\tif (zs.total_out) {\n\t\t\tywrite(pack_fd, zs_out, zs.total_out);\n\t\t\tpack_offset += zs.total_out;\n\t\t\tzs.next_out = zs_out;\n\t\t\tzs.avail_out = zs_outlen;\n\t\t\tzs.total_out = 0;\n\t\t}\n\t}\n\n\tif (delta)\n\t\tfree(delta);\n\tif (last) {\n\t\tif (last->data)\n\t\t\tfree(last->data);\n\t\tlast->data = dat;\n\t\tlast->len = datlen;\n\t\tmemcpy(last->sha1, sha1, sizeof(sha1));\n\t}\n\treturn 0;\n}\n\nstatic const char *get_mode(const char *str, unsigned int *modep)\n{\n\tunsigned char c;\n\tunsigned int mode = 0;\n\n\twhile ((c = *str++) != ' ') {\n\t\tif (c < '0' || c > '7')\n\t\t\treturn NULL;\n\t\tmode = (mode << 3) + (c - '0');\n\t}\n\t*modep = mode;\n\treturn str;\n}\n\nstatic void load_tree(struct tree_entry *root)\n{\n\tstruct object_entry *myoe;\n\tstruct tree_content *t;\n\tunsigned long size;\n\tchar *buf;\n\tconst char *c;\n\tchar type[20];\n\n\troot->tree = t = new_tree_content(8);\n\tif (!memcmp(root->sha1, null_sha1, 20))\n\t\treturn;\n\n\tmyoe = find_object(root->sha1);\n\tif (myoe) {\n\t\tdie(\"FIXME\");\n\t} else {\n\t\tbuf = read_sha1_file(root->sha1, type, &size);\n\t\tif (!buf || strcmp(type, tree_type))\n\t\t\tdie(\"Can't load existing tree %s\", sha1_to_hex(root->sha1));\n\t}\n\n\tc = buf;\n\twhile (c != (buf + size)) {\n\t\tstruct tree_entry *e = new_tree_entry();\n\n\t\tif (t->entry_count == t->entry_capacity)\n\t\t\troot->tree = t = grow_tree_content(t, 8);\n\t\tt->entries[t->entry_count++] = e;\n\n\t\te->tree = NULL;\n\t\tc = get_mode(c, &e->mode);\n\t\tif (!c)\n\t\t\tdie(\"Corrupt mode in %s\", sha1_to_hex(root->sha1));\n\t\te->name = to_atom(c, strlen(c));\n\t\tc += e->name->str_len + 1;\n\t\tmemcpy(e->sha1, c, sizeof(e->sha1));\n\t\tc += 20;\n\t}\n\tfree(buf);\n}\n\nstatic int tecmp (const void *_a, const void *_b)\n{\n\tstruct tree_entry *a = *((struct tree_entry**)_a);\n\tstruct tree_entry *b = *((struct tree_entry**)_b);\n\treturn base_name_compare(\n\t\ta->name->str_dat, a->name->str_len, a->mode,\n\t\tb->name->str_dat, b->name->str_len, b->mode);\n}\n\nstatic void store_tree(struct tree_entry *root)\n{\n\tstruct tree_content *t = root->tree;\n\tunsigned int i;\n\tsize_t maxlen;\n\tchar *buf, *c;\n\n\tif (memcmp(root->sha1, null_sha1, 20))\n\t\treturn;\n\n\tmaxlen = 0;\n\tfor (i = 0; i < t->entry_count; i++) {\n\t\tmaxlen += t->entries[i]->name->str_len + 34;\n\t\tif (t->entries[i]->tree)\n\t\t\tstore_tree(t->entries[i]);\n\t}\n\n\tqsort(t->entries, t->entry_count, sizeof(t->entries[0]), tecmp);\n\tbuf = c = xmalloc(maxlen);\n\tfor (i = 0; i < t->entry_count; i++) {\n\t\tstruct tree_entry *e = t->entries[i];\n\t\tc += sprintf(c, \"%o\", e->mode);\n\t\t*c++ = ' ';\n\t\tstrcpy(c, e->name->str_dat);\n\t\tc += e->name->str_len + 1;\n\t\tmemcpy(c, e->sha1, 20);\n\t\tc += 20;\n\t}\n\tstore_object(OBJ_TREE, buf, c - buf, NULL, root->sha1);\n\tfree(buf);\n}\n\nstatic int tree_content_set(\n\tstruct tree_entry *root,\n\tconst char *p,\n\tconst unsigned char *sha1,\n\tconst unsigned int mode)\n{\n\tstruct tree_content *t = root->tree;\n\tconst char *slash1;\n\tunsigned int i, n;\n\tstruct tree_entry *e;\n\n\tslash1 = strchr(p, '/');\n\tif (slash1)\n\t\tn = slash1 - p;\n\telse\n\t\tn = strlen(p);\n\n\tfor (i = 0; i < t->entry_count; i++) {\n\t\te = t->entries[i];\n\t\tif (e->name->str_len == n && !strncmp(p, e->name->str_dat, n)) {\n\t\t\tif (!slash1) {\n\t\t\t\tif (e->mode == mode && !memcmp(e->sha1, sha1, 20))\n\t\t\t\t\treturn 0;\n\t\t\t\te->mode = mode;\n\t\t\t\tmemcpy(e->sha1, sha1, 20);\n\t\t\t\tif (e->tree) {\n\t\t\t\t\trelease_tree_content(e->tree);\n\t\t\t\t\te->tree = NULL;\n\t\t\t\t}\n\t\t\t\tmemcpy(root->sha1, null_sha1, 20);\n\t\t\t\treturn 1;\n\t\t\t}\n\t\t\tif (!S_ISDIR(e->mode)) {\n\t\t\t\te->tree = new_tree_content(8);\n\t\t\t\te->mode = S_IFDIR;\n\t\t\t}\n\t\t\tif (!e->tree)\n\t\t\t\tload_tree(e);\n\t\t\tif (tree_content_set(e, slash1 + 1, sha1, mode)) {\n\t\t\t\tmemcpy(root->sha1, null_sha1, 20);\n\t\t\t\treturn 1;\n\t\t\t}\n\t\t\treturn 0;\n\t\t}\n\t}\n\n\tif (t->entry_count == t->entry_capacity)\n\t\troot->tree = t = grow_tree_content(t, 8);\n\te = new_tree_entry();\n\te->name = to_atom(p, n);\n\tt->entries[t->entry_count++] = e;\n\tif (slash1) {\n\t\te->tree = new_tree_content(8);\n\t\te->mode = S_IFDIR;\n\t\ttree_content_set(e, slash1 + 1, sha1, mode);\n\t} else {\n\t\te->tree = NULL;\n\t\te->mode = mode;\n\t\tmemcpy(e->sha1, sha1, 20);\n\t}\n\tmemcpy(root->sha1, null_sha1, 20);\n\treturn 1;\n}\n\nstatic int tree_content_remove(struct tree_entry *root, const char *p)\n{\n\tstruct tree_content *t = root->tree;\n\tconst char *slash1;\n\tunsigned int i, n;\n\tstruct tree_entry *e;\n\n\tslash1 = strchr(p, '/');\n\tif (slash1)\n\t\tn = slash1 - p;\n\telse\n\t\tn = strlen(p);\n\n\tfor (i = 0; i < t->entry_count; i++) {\n\t\te = t->entries[i];\n\t\tif (e->name->str_len == n && !strncmp(p, e->name->str_dat, n)) {\n\t\t\tif (!slash1 || !S_ISDIR(e->mode))\n\t\t\t\tgoto del_entry;\n\t\t\tif (!e->tree)\n\t\t\t\tload_tree(e);\n\t\t\tif (tree_content_remove(e, slash1 + 1)) {\n\t\t\t\tif (!e->tree->entry_count)\n\t\t\t\t\tgoto del_entry;\n\t\t\t\tmemcpy(root->sha1, null_sha1, 20);\n\t\t\t\treturn 1;\n\t\t\t}\n\t\t\treturn 0;\n\t\t}\n\t}\n\treturn 0;\n\ndel_entry:\n\tfor (i++; i < t->entry_count; i++)\n\t\tt->entries[i-1] = t->entries[i];\n\tt->entry_count--;\n\trelease_tree_entry(e);\n\tmemcpy(root->sha1, null_sha1, 20);\n\treturn 1;\n}\n\nstatic void init_pack_header()\n{\n\tconst char* magic = \"PACK\";\n\tunsigned long version = 3;\n\tunsigned long zero = 0;\n\n\tversion = htonl(version);\n\tywrite(pack_fd, (char*)magic, 4);\n\tywrite(pack_fd, &version, 4);\n\tywrite(pack_fd, &zero, 4);\n\tpack_offset = 4 * 3;\n}\n\nstatic void fixup_header_footer()\n{\n\tSHA_CTX c;\n\tchar hdr[8];\n\tunsigned long cnt;\n\tchar *buf;\n\tsize_t n;\n\n\tzs_finish();\n\tif (lseek(pack_fd, 0, SEEK_SET) != 0)\n\t\tdie(\"Failed seeking to start: %s\", strerror(errno));\n\n\tSHA1_Init(&c);\n\tyread(pack_fd, hdr, 8);\n\tSHA1_Update(&c, hdr, 8);\n\n\tcnt = htonl(object_count);\n\tSHA1_Update(&c, &cnt, 4);\n\tywrite(pack_fd, &cnt, 4);\n\n\tbuf = xmalloc(128 * 1024);\n\tfor (;;) {\n\t\tn = xread(pack_fd, buf, 128 * 1024);\n\t\tif (n <= 0)\n\t\t\tbreak;\n\t\tSHA1_Update(&c, buf, n);\n\t}\n\tfree(buf);\n\n\tSHA1_Final(pack_sha1, &c);\n\tywrite(pack_fd, pack_sha1, sizeof(pack_sha1));\n}\n\nstatic int oecmp (const void *_a, const void *_b)\n{\n\tstruct object_entry *a = *((struct object_entry**)_a);\n\tstruct object_entry *b = *((struct object_entry**)_b);\n\treturn memcmp(a->sha1, b->sha1, sizeof(a->sha1));\n}\n\nstatic void write_index(const char *idx_name)\n{\n\tstruct sha1file *f;\n\tstruct object_entry **idx, **c, **last;\n\tstruct object_entry *e;\n\tstruct object_entry_pool *o;\n\tunsigned int array[256];\n\tint i;\n\n\t/* Build the sorted table of object IDs. */\n\tidx = xmalloc(object_count * sizeof(struct object_entry*));\n\tc = idx;\n\tfor (o = blocks; o; o = o->next_pool)\n\t\tfor (e = o->entries; e != o->next_free; e++)\n\t\t\t*c++ = e;\n\tlast = idx + object_count;\n\tqsort(idx, object_count, sizeof(struct object_entry*), oecmp);\n\n\t/* Generate the fan-out array. */\n\tc = idx;\n\tfor (i = 0; i < 256; i++) {\n\t\tstruct object_entry **next = c;;\n\t\twhile (next < last) {\n\t\t\tif ((*next)->sha1[0] != i)\n\t\t\t\tbreak;\n\t\t\tnext++;\n\t\t}\n\t\tarray[i] = htonl(next - idx);\n\t\tc = next;\n\t}\n\n\tf = sha1create(\"%s\", idx_name);\n\tsha1write(f, array, 256 * sizeof(int));\n\tfor (c = idx; c != last; c++) {\n\t\tunsigned int offset = htonl((*c)->offset);\n\t\tsha1write(f, &offset, 4);\n\t\tsha1write(f, (*c)->sha1, sizeof((*c)->sha1));\n\t}\n\tsha1write(f, pack_sha1, sizeof(pack_sha1));\n\tsha1close(f, NULL, 1);\n\tfree(idx);\n}\n\nstatic void dump_branches()\n{\n\tstatic const char *msg = \"fast-import\";\n\tunsigned int i;\n\tstruct branch *b;\n\tstruct ref_lock *lock;\n\n\tfor (i = 0; i < branch_table_sz; i++) {\n\t\tfor (b = branch_table[i]; b; b = b->table_next_branch) {\n\t\t\tlock = lock_any_ref_for_update(b->name, NULL, 0);\n\t\t\tif (!lock || write_ref_sha1(lock, b->sha1, msg) < 0)\n\t\t\t\tdie(\"Can't write %s\", b->name);\n\t\t}\n\t}\n}\n\nstatic void read_next_command()\n{\n\tread_line(&command_buf, stdin, '\\n');\n}\n\nstatic void cmd_mark()\n{\n\tif (!strncmp(\"mark :\", command_buf.buf, 6)) {\n\t\tcommand_mark = strtoul(command_buf.buf + 6, NULL, 10);\n\t\tread_next_command();\n\t}\n\telse\n\t\tcommand_mark = 0;\n}\n\nstatic void* cmd_data (size_t *size)\n{\n\tsize_t n = 0;\n\tvoid *buffer;\n\tsize_t length;\n\n\tif (strncmp(\"data \", command_buf.buf, 5))\n\t\tdie(\"Expected 'data n' command, found: %s\", command_buf.buf);\n\n\tlength = strtoul(command_buf.buf + 5, NULL, 10);\n\tbuffer = xmalloc(length);\n\n\twhile (n < length) {\n\t\tsize_t s = fread((char*)buffer + n, 1, length - n, stdin);\n\t\tif (!s && feof(stdin))\n\t\t\tdie(\"EOF in data (%lu bytes remaining)\", length - n);\n\t\tn += s;\n\t}\n\n\tif (fgetc(stdin) != '\\n')\n\t\tdie(\"An lf did not trail the binary data as expected.\");\n\n\t*size = length;\n\treturn buffer;\n}\n\nstatic void cmd_new_blob()\n{\n\tsize_t datlen;\n\tvoid *dat;\n\tunsigned char sha1[20];\n\n\tread_next_command();\n\tcmd_mark();\n\tdat = cmd_data(&datlen);\n\n\tif (store_object(OBJ_BLOB, dat, datlen, &last_blob, sha1)) \n\t\tfree(dat);\n}\n\nstatic void unload_one_branch()\n{\n\twhile (cur_active_branches >= max_active_branches) {\n\t\tunsigned long min_commit = ULONG_MAX;\n\t\tstruct branch *e, *l = NULL, *p = NULL;\n\n\t\tfor (e = active_branches; e; e = e->active_next_branch) {\n\t\t\tif (e->last_commit < min_commit) {\n\t\t\t\tp = l;\n\t\t\t\tmin_commit = e->last_commit;\n\t\t\t}\n\t\t\tl = e;\n\t\t}\n\n\t\tif (p) {\n\t\t\te = p->active_next_branch;\n\t\t\tp->active_next_branch = e->active_next_branch;\n\t\t} else {\n\t\t\te = active_branches;\n\t\t\tactive_branches = e->active_next_branch;\n\t\t}\n\t\te->active_next_branch = NULL;\n\t\tif (e->branch_tree.tree) {\n\t\t\trelease_tree_content(e->branch_tree.tree);\n\t\t\te->branch_tree.tree = NULL;\n\t\t}\n\t\tcur_active_branches--;\n\t}\n}\n\nstatic void load_branch(struct branch *b)\n{\n\tload_tree(&b->branch_tree);\n\tb->active_next_branch = active_branches;\n\tactive_branches = b;\n\tcur_active_branches++;\n}\n\nstatic void file_change_m(struct branch *b)\n{\n\tconst char *p = command_buf.buf + 2;\n\tchar *p_uq;\n\tconst char *endp;\n\tstruct object_entry *oe;\n\tunsigned char sha1[20];\n\tunsigned int mode;\n\tchar type[20];\n\n\tp = get_mode(p, &mode);\n\tif (!p)\n\t\tdie(\"Corrupt mode: %s\", command_buf.buf);\n\tswitch (mode) {\n\tcase S_IFREG | 0644:\n\tcase S_IFREG | 0755:\n\tcase 0644:\n\tcase 0755:\n\t\t/* ok */\n\t\tbreak;\n\tdefault:\n\t\tdie(\"Corrupt mode: %s\", command_buf.buf);\n\t}\n\n\tif (get_sha1_hex(p, sha1))\n\t\tdie(\"Invalid SHA1: %s\", command_buf.buf);\n\tp += 40;\n\tif (*p++ != ' ')\n\t\tdie(\"Missing space after SHA1: %s\", command_buf.buf);\n\n\tp_uq = unquote_c_style(p, &endp);\n\tif (p_uq) {\n\t\tif (*endp)\n\t\t\tdie(\"Garbage after path in: %s\", command_buf.buf);\n\t\tp = p_uq;\n\t}\n\n\toe = find_object(sha1);\n\tif (oe) {\n\t\tif (oe->type != OBJ_BLOB)\n\t\t\tdie(\"Not a blob (actually a %s): %s\",\n\t\t\t\tcommand_buf.buf, type_names[oe->type]);\n\t} else {\n\t\tif (sha1_object_info(sha1, type, NULL))\n\t\t\tdie(\"Blob not found: %s\", command_buf.buf);\n\t\tif (strcmp(blob_type, type))\n\t\t\tdie(\"Not a blob (actually a %s): %s\",\n\t\t\t\tcommand_buf.buf, type);\n\t}\n\n\ttree_content_set(&b->branch_tree, p, sha1, S_IFREG | mode);\n\n\tif (p_uq)\n\t\tfree(p_uq);\n}\n\nstatic void file_change_d(struct branch *b)\n{\n\tconst char *p = command_buf.buf + 2;\n\tchar *p_uq;\n\tconst char *endp;\n\n\tp_uq = unquote_c_style(p, &endp);\n\tif (p_uq) {\n\t\tif (*endp)\n\t\t\tdie(\"Garbage after path in: %s\", command_buf.buf);\n\t\tp = p_uq;\n\t}\n\ttree_content_remove(&b->branch_tree, p);\n\tif (p_uq)\n\t\tfree(p_uq);\n}\n\nstatic void cmd_new_commit()\n{\n\tstruct branch *b;\n\tvoid *msg;\n\tsize_t msglen;\n\tchar *str_uq;\n\tconst char *endp;\n\tchar *sp;\n\tchar *author = NULL;\n\tchar *committer = NULL;\n\tchar *body;\n\n\t/* Obtain the branch name from the rest of our command */\n\tsp = strchr(command_buf.buf, ' ') + 1;\n\tstr_uq = unquote_c_style(sp, &endp);\n\tif (str_uq) {\n\t\tif (*endp)\n\t\t\tdie(\"Garbage after ref in: %s\", command_buf.buf);\n\t\tsp = str_uq;\n\t}\n\tb = lookup_branch(sp);\n\tif (!b)\n\t\tdie(\"Branch not declared: %s\", sp);\n\tif (str_uq)\n\t\tfree(str_uq);\n\n\tread_next_command();\n\tcmd_mark();\n\tif (!strncmp(\"author \", command_buf.buf, 7)) {\n\t\tauthor = strdup(command_buf.buf);\n\t\tread_next_command();\n\t}\n\tif (!strncmp(\"committer \", command_buf.buf, 10)) {\n\t\tcommitter = strdup(command_buf.buf);\n\t\tread_next_command();\n\t}\n\tif (!committer)\n\t\tdie(\"Expected committer but didn't get one\");\n\tmsg = cmd_data(&msglen);\n\n\t/* ensure the branch is active/loaded */\n\tif (!b->branch_tree.tree) {\n\t\tunload_one_branch();\n\t\tload_branch(b);\n\t}\n\n\t/* file_change* */\n\tfor (;;) {\n\t\tread_next_command();\n\t\tif (1 == command_buf.len)\n\t\t\tbreak;\n\t\telse if (!strncmp(\"M \", command_buf.buf, 2))\n\t\t\tfile_change_m(b);\n\t\telse if (!strncmp(\"D \", command_buf.buf, 2))\n\t\t\tfile_change_d(b);\n\t\telse\n\t\t\tdie(\"Unsupported file_change: %s\", command_buf.buf);\n\t}\n\n\t/* build the tree and the commit */\n\tstore_tree(&b->branch_tree);\n\tbody = xmalloc(97 + msglen\n\t\t+ (author\n\t\t\t? strlen(author) + strlen(committer)\n\t\t\t: 2 * strlen(committer)));\n\tsp = body;\n\tsp += sprintf(sp, \"tree %s\\n\", sha1_to_hex(b->branch_tree.sha1));\n\tif (memcmp(b->sha1, null_sha1, 20))\n\t\tsp += sprintf(sp, \"parent %s\\n\", sha1_to_hex(b->sha1));\n\tif (author)\n\t\tsp += sprintf(sp, \"%s\\n\", author);\n\telse\n\t\tsp += sprintf(sp, \"author %s\\n\", committer + 10);\n\tsp += sprintf(sp, \"%s\\n\\n\", committer);\n\tmemcpy(sp, msg, msglen);\n\tsp += msglen;\n\tif (author)\n\t\tfree(author);\n\tfree(committer);\n\tfree(msg);\n\n\tstore_object(OBJ_COMMIT, body, sp - body, NULL, b->sha1);\n\tfree(body);\n\tb->last_commit = object_count_by_type[OBJ_COMMIT];\n}\n\nstatic void cmd_new_branch()\n{\n\tstruct branch *b;\n\tchar *str_uq;\n\tconst char *endp;\n\tchar *sp;\n\n\t/* Obtain the new branch name from the rest of our command */\n\tsp = strchr(command_buf.buf, ' ') + 1;\n\tstr_uq = unquote_c_style(sp, &endp);\n\tif (str_uq) {\n\t\tif (*endp)\n\t\t\tdie(\"Garbage after ref in: %s\", command_buf.buf);\n\t\tsp = str_uq;\n\t}\n\tb = new_branch(sp);\n\tif (str_uq)\n\t\tfree(str_uq);\n\tread_next_command();\n\n\t/* from ... */\n\tif (!strncmp(\"from \", command_buf.buf, 5)) {\n\t\tconst char *from;\n\t\tstruct branch *s;\n\n\t\tfrom = strchr(command_buf.buf, ' ') + 1;\n\t\tstr_uq = unquote_c_style(from, &endp);\n\t\tif (str_uq) {\n\t\t\tif (*endp)\n\t\t\t\tdie(\"Garbage after string in: %s\", command_buf.buf);\n\t\t\tfrom = str_uq;\n\t\t}\n\n\t\ts = lookup_branch(from);\n\t\tif (b == s)\n\t\t\tdie(\"Can't create a branch from itself: %s\", b->name);\n\t\telse if (s) {\n\t\t\tmemcpy(b->sha1, s->sha1, 20);\n\t\t\tmemcpy(b->branch_tree.sha1, s->branch_tree.sha1, 20);\n\t\t} else if (!get_sha1(from, b->sha1)) {\n\t\t\tif (!memcmp(b->sha1, null_sha1, 20))\n\t\t\t\tmemcpy(b->branch_tree.sha1, null_sha1, 20);\n\t\t\telse {\n\t\t\t\tunsigned long size;\n\t\t\t\tchar *buf;\n\n\t\t\t\tbuf = read_object_with_reference(b->sha1,\n\t\t\t\t\ttype_names[OBJ_COMMIT], &size, b->sha1);\n\t\t\t\tif (!buf || size < 46)\n\t\t\t\t\tdie(\"Not a valid commit: %s\", from);\n\t\t\t\tif (memcmp(\"tree \", buf, 5)\n\t\t\t\t\t|| get_sha1_hex(buf + 5, b->branch_tree.sha1))\n\t\t\t\t\tdie(\"The commit %s is corrupt\", sha1_to_hex(b->sha1));\n\t\t\t\tfree(buf);\n\t\t\t}\n\t\t} else\n\t\t\tdie(\"Invalid ref name or SHA1 expression: %s\", from);\n\n\t\tif (str_uq)\n\t\t\tfree(str_uq);\n\t\tread_next_command();\n\t} else {\n\t\tmemcpy(b->sha1, null_sha1, 20);\n\t\tmemcpy(b->branch_tree.sha1, null_sha1, 20);\n\t}\n\n\tif (command_buf.eof || command_buf.len > 1)\n\t\tdie(\"An lf did not terminate the branch command as expected.\");\n}\n\nint main(int argc, const char **argv)\n{\n\tconst char *base_name = argv[1];\n\tint est_obj_cnt = atoi(argv[2]);\n\tchar *pack_name;\n\tchar *idx_name;\n\tstruct stat sb;\n\n\tsetup_ident();\n\tgit_config(git_default_config);\n\n\tpack_name = xmalloc(strlen(base_name) + 6);\n\tsprintf(pack_name, \"%s.pack\", base_name);\n\tidx_name = xmalloc(strlen(base_name) + 5);\n\tsprintf(idx_name, \"%s.idx\", base_name);\n\n\tpack_fd = open(pack_name, O_RDWR|O_CREAT|O_EXCL, 0666);\n\tif (pack_fd < 0)\n\t\tdie(\"Can't create %s: %s\", pack_name, strerror(errno));\n\n\tinit_pack_header();\n\talloc_objects(est_obj_cnt);\n\tstrbuf_init(&command_buf);\n\n\tatom_table = xcalloc(atom_table_sz, sizeof(struct atom_str*));\n\tbranch_table = xcalloc(branch_table_sz, sizeof(struct branch*));\n\tavail_tree_table = xcalloc(avail_tree_table_sz, sizeof(struct avail_tree_content*));\n\n\tfor (;;) {\n\t\tread_next_command();\n\t\tif (command_buf.eof)\n\t\t\tbreak;\n\t\telse if (!strcmp(\"blob\", command_buf.buf))\n\t\t\tcmd_new_blob();\n\t\telse if (!strncmp(\"branch \", command_buf.buf, 7))\n\t\t\tcmd_new_branch();\n\t\telse if (!strncmp(\"commit \", command_buf.buf, 7))\n\t\t\tcmd_new_commit();\n\t\telse\n\t\t\tdie(\"Unsupported command: %s\", command_buf.buf);\n\t}\n\n\tfixup_header_footer();\n\tclose(pack_fd);\n\twrite_index(idx_name);\n\tdump_branches();\n\n\tfprintf(stderr, \"%s statistics:\\n\", argv[0]);\n\tfprintf(stderr, \"---------------------------------------------------\\n\");\n\tfprintf(stderr, \"Alloc'd objects: %10lu (%10lu overflow )\\n\", alloc_count, alloc_count - est_obj_cnt);\n\tfprintf(stderr, \"Total objects: %10lu (%10lu duplicates)\\n\", object_count, duplicate_count);\n\tfprintf(stderr, \" blobs : %10lu (%10lu duplicates)\\n\", object_count_by_type[OBJ_BLOB], duplicate_count_by_type[OBJ_BLOB]);\n\tfprintf(stderr, \" trees : %10lu (%10lu duplicates)\\n\", object_count_by_type[OBJ_TREE], duplicate_count_by_type[OBJ_TREE]);\n\tfprintf(stderr, \" commits: %10lu (%10lu duplicates)\\n\", object_count_by_type[OBJ_COMMIT], duplicate_count_by_type[OBJ_COMMIT]);\n\tfprintf(stderr, \" tags : %10lu (%10lu duplicates)\\n\", object_count_by_type[OBJ_TAG], duplicate_count_by_type[OBJ_TAG]);\n\tfprintf(stderr, \"Total streams: %10u\\n\", stream_cnt);\n\tfprintf(stderr, \"Total branches: %10lu\\n\", branch_count);\n\tfprintf(stderr, \"Total atoms: %10u\\n\", atom_cnt);\n\tfprintf(stderr, \"Memory total: %10lu KiB\\n\", (total_allocd + alloc_count*sizeof(struct object_entry))/1024);\n\tfprintf(stderr, \" pools: %10lu KiB\\n\", total_allocd/1024);\n\tfprintf(stderr, \" objects: %10lu KiB\\n\", (alloc_count*sizeof(struct object_entry))/1024);\n\tfprintf(stderr, \"---------------------------------------------------\\n\");\n\n\tstat(pack_name, &sb);\n\tfprintf(stderr, \"Pack size: %10lu KiB\\n\", (unsigned long)(sb.st_size/1024));\n\tstat(idx_name, &sb);\n\tfprintf(stderr, \"Index size: %10lu KiB\\n\", (unsigned long)(sb.st_size/1024));\n\n\tfprintf(stderr, \"\\n\");\n\n\treturn 0;\n}\n\n"},{"id":"25553","messageId":"9e4733910608180615q4895334bw57c55e59a4ac5482@mail.gmail.com","threadId":"5297","inReplyTo":"Pine.LNX.4.64.0608172323520.11359@localhost.localdomain","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-18T13:15:10Z","receivedAt":"2006-08-18T13:15:10Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/18/06, Nicolas Pitre wrote:\n> A better way to get such a size saving is to increase the window and\n> depth parameters. For example, a window of 20 and depth of 20 can\n> usually provide a pack size saving greater than 11% with none of the\n> disadvantages mentioned above.\n\nOur window size is effectively infinite. I am handing him all of the\nrevisions from a single file in optimal order. This includes branches.\nHe takes these revisions, runs xdiff on them, and then puts the entire\nresult into a single zlib blob.\n\nI suspect the size reduction is directly proportional to the age of\nthe repository. The kernel repository only has three years worth of\ndata in it. Linus has the full history in another repository that is\nnot in general distribution. We can get it from him when he gets back\nfrom vacation.\n\nIf the repository doesn't contain long delta chains the optimization\ndoesn't help that much. On the other hand it doesn't hurt either since\nthe chains weren't long. My repository is four times as old as the\nkernel one and I am getting 4x the benefit.\n\nThis is a good format for archival data that is infrequency accessed.\nThat is why I proposed a two pack system. One pack would contain the\narchival data and be highly optimized for size and the second pack\nwould contain recent changes and be optimized for speed. The size\noptimization is important for controlling bandwidth costs.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25556","messageId":"Pine.LNX.4.63.0608181536250.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5297","inReplyTo":"9e4733910608180615q4895334bw57c55e59a4ac5482@mail.gmail.com","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-18T13:36:59Z","receivedAt":"2006-08-18T13:36:59Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 18 Aug 2006, Jon Smirl wrote:\n\n> I suspect the size reduction is directly proportional to the age of\n> the repository. The kernel repository only has three years worth of\n> data in it. Linus has the full history in another repository that is\n> not in general distribution. We can get it from him when he gets back\n> from vacation.\n\nMaybe you mean\n\nhttp://www.kernel.org/git/gitweb.cgi?p=linux/kernel/git/tglx/history.git\n\nCiao,\nDscho\n"},{"id":"25558","messageId":"9e4733910608180650j4542ab09q7daf4250825d3333@mail.gmail.com","threadId":"5297","inReplyTo":"Pine.LNX.4.63.0608181536250.28360@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-18T13:50:30Z","receivedAt":"2006-08-18T13:50:30Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/18/06, Johannes Schindelin wrote:\n> Hi,\n>\n> On Fri, 18 Aug 2006, Jon Smirl wrote:\n>\n> > I suspect the size reduction is directly proportional to the age of\n> > the repository. The kernel repository only has three years worth of\n> > data in it. Linus has the full history in another repository that is\n> > not in general distribution. We can get it from him when he gets back\n> > from vacation.\n>\n> Maybe you mean\n>\n> http://www.kernel.org/git/gitweb.cgi?p=linux/kernel/git/tglx/history.git\n\nThat one only goes to 2002, the full one goes back to around 1990.\n\n>\n> Ciao,\n> Dscho\n>\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25567","messageId":"Pine.LNX.4.64.0608181057440.11359@localhost.localdomain","threadId":"5297","inReplyTo":"9e4733910608180615q4895334bw57c55e59a4ac5482@mail.gmail.com","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-18T16:25:57Z","receivedAt":"2006-08-18T16:25:57Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 18 Aug 2006, Jon Smirl wrote:\n\n> On 8/18/06, Nicolas Pitre wrote:\n> > A better way to get such a size saving is to increase the window and\n> > depth parameters. For example, a window of 20 and depth of 20 can\n> > usually provide a pack size saving greater than 11% with none of the\n> > disadvantages mentioned above.\n> \n> Our window size is effectively infinite. I am handing him all of the\n> revisions from a single file in optimal order. This includes branches.\n\nIn GIT packing terms this is infinite delta _depth_ not _window_.\n\n> He takes these revisions, runs xdiff on them, and then puts the entire\n> result into a single zlib blob.\n\nThis is not a good idea to have infinite delta depth. The time to \nbrowse the repository history then becomes exponential with the number \nof revisions making the value of such a repository a bit questionnable \n(you could as well only preserve the last 2 years of history instead \nsince further than that with infinite delta depth is likely to be too \nslow and painful to use).\n\nBut just for comparison I did a repack -a -f on the kernel repository \nwith --window=50 --depth=5000 which should be a good approximation of \nthe best possible delta matchingwith infinite depth.\n\nDefault delta params (window=10 depth=10) : 122103455 \nAgressive deltas (window=50 depth=5000) : 105870516\nReduction : 13%\n\nOK let's try it with delta chains in the same zlib stream using the \npatch I posted yesterday (with a minor tweak allowing the usage of -f \nwith git-repack).\n\nAgressive and grouped deltas (window=50 depth=5000 : 99860685\n\nThis is a mere 5.7% reduction over the non grouped deltas, less than the \n11% reduction I obtained yesterday when the delta depth is kept \nreasonably short.\n\nThe increased delta depth is likely to make a large difference on old \nrepos with long history, maybe more so and with much less \ncomplexity than the delta grouping.\n\n> I suspect the size reduction is directly proportional to the age of\n> the repository. The kernel repository only has three years worth of\n> data in it. Linus has the full history in another repository that is\n> not in general distribution. We can get it from him when he gets back\n> from vacation.\n> \n> If the repository doesn't contain long delta chains the optimization\n> doesn't help that much. On the other hand it doesn't hurt either since\n> the chains weren't long. My repository is four times as old as the\n> kernel one and I am getting 4x the benefit.\n\nNo that cannot be right.\n\nLet's assume every whole objects are 10 in size and every deltas are 1. \nYou therefore can have 1 base object and 10 delta objects, effectively \nstoring 11 objects for a size of 20. You therefore have a 1.8 vs 10 \nsize ratio.\n\nIf the delta depth is 100 then you potentially have 1 base object and \n100 deltas for a size ratio of 1.1 vs 10.\n\nIf the delta depth is 1000 the ratiobecomes 1.01 vs 10.\n\nThe size saving is therefore _not_ proportional with the age of the \nrepository. It rather tend to be asymptotic with the delta ratio (but \nimpose an exponential runtime cost when fetching objects out of it).\n\nThe fact that your 4x old repository has \na 4x size saving \ncan be due only to packing malfunction I would say.\n\n\nNicolas\n"},{"id":"25568","messageId":"Pine.LNX.4.64.0608181226460.11359@localhost.localdomain","threadId":"5297","inReplyTo":"9e4733910608180553r34fa7b25he0bf910ef804630f@mail.gmail.com","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-18T16:30:41Z","receivedAt":"2006-08-18T16:30:41Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 18 Aug 2006, Jon Smirl wrote:\n\n> I attached Shawn's code. He is gone until Monday and can't defend it.\n\nI will have a look at it next week as I'll be gone for the weekend as \nwell.\n\n> Do note that I am running this on the Mozilla CVS which is over 10\n> years old. Some of the files have over 2,000 deltas. I average 10\n> deltas per file but the distribution is not at all even. Many files\n> get checked-in and never changed, for example 1000's of images.\n\nThis is IMHO more evidence that something is wrong with the results \nyou obtained.\n\n\nNicolas\n"},{"id":"25571","messageId":"9e4733910608180956n64e3362fm5c72d652e6b6243a@mail.gmail.com","threadId":"5297","inReplyTo":"Pine.LNX.4.64.0608181226460.11359@localhost.localdomain","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-18T16:56:21Z","receivedAt":"2006-08-18T16:56:21Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/18/06, Nicolas Pitre wrote:\n> On Fri, 18 Aug 2006, Jon Smirl wrote:\n>\n> > I attached Shawn's code. He is gone until Monday and can't defend it.\n>\n> I will have a look at it next week as I'll be gone for the weekend as\n> well.\n\nI looked at it some and couldn't see anything obviously wrong with it,\nbut it wasn't a detailed inspection.\n\nAs comparison, I just tar/zipped the Mozilla CVS repo and it is 541MB.\nThe 295MB git pack number does not have commits and trees in it, it is\nrevisions only.\n\nIt is not impossible that when the trees and commits are added to the\n295MB number that it won't end up being near the 541MB number. We\nalready know xdiff is better at generating diffs than CVS diff. And I\nstill have to add 250K log entries and trees. Those are going to add\nat least 100MB.\n\nI will get back to work on the import code over the weekend. One of my\n2 year olds gave me a cold so I have been useless the last couple of\ndays.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25624","messageId":"Pine.LNX.4.64.0608191218470.11811@g5.osdl.org","threadId":"5297","inReplyTo":"9e4733910608180650j4542ab09q7daf4250825d3333@mail.gmail.com","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-08-19T19:25:08Z","receivedAt":"2006-08-19T19:25:08Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 18 Aug 2006, Jon Smirl wrote:\n\n> On 8/18/06, Johannes Schindelin wrote:\n> > Hi,\n> > \n> > On Fri, 18 Aug 2006, Jon Smirl wrote:\n> > \n> > > I suspect the size reduction is directly proportional to the age of\n> > > the repository. The kernel repository only has three years worth of\n> > > data in it. Linus has the full history in another repository that is\n> > > not in general distribution. We can get it from him when he gets back\n> > > from vacation.\n> > \n> > Maybe you mean\n> > \n> > http://www.kernel.org/git/gitweb.cgi?p=linux/kernel/git/tglx/history.git\n> \n> That one only goes to 2002, the full one goes back to around 1990.\n\nI don't actually have such a \"full\" history. It would be wonderful if \nsomebody took the time to try to piece such a thing together (and git \nactually makes that a _lot_ easier than some other SCM's, because you can \njust import random versions in any order, and then re-stich just the \ncommit history when you add a new thing in the middle, without generating \nany new trees or deltas or anything strange at all).\n\nBut it's a lot of work. I tried to do a \"Linux-Historic\" archive about a \nyear ago (and imported some of the old kernels I had), but I gave up, just \nbecause it was such a pain to try to do a good job and try to find old \nrelease notes etc to import into the changelogs etc. \n\nOh, well.\n\nSo the only \"old\" history I have is indeed that BK conversion by Thomas \nGleixner. Any pre-BK stuff only exists as patches and tar-balls on various \nftp sites (and I don't have any magic repository of my own, so everybody \nelse can do exactly as well as I could, with possibly the exception that I \nmight remember some random details about some old release history - but \nconsidering my memory, that's pretty unlikely too. Google is your friend)\n\n\t\t\tLinus\n"},{"id":"25669","messageId":"Pine.LNX.4.64.0608202257020.3682@localhost.localdomain","threadId":"5297","inReplyTo":"9e4733910608180956n64e3362fm5c72d652e6b6243a@mail.gmail.com","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-21T03:45:42Z","receivedAt":"2006-08-21T03:45:42Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 18 Aug 2006, Jon Smirl wrote:\n\n> On 8/18/06, Nicolas Pitre wrote:\n> > On Fri, 18 Aug 2006, Jon Smirl wrote:\n> >\n> > > I attached Shawn's code. He is gone until Monday and can't defend it.\n> >\n> > I will have a look at it next week as I'll be gone for the weekend as\n> > well.\n> \n> I looked at it some and couldn't see anything obviously wrong with it,\n> but it wasn't a detailed inspection.\n\nI looked at it too and the code looks OK.\n\nThis doesn't mean there is no problem at a higher level though. The \ndeltification process is extremely crude and I think this is the cause \nof the original pack size.\n\nFor example, last April we discovered that a small change in the \nheuristics to determine base delta objects in git-pack-objects could \ncreate a pack size regression up to 4x the size of the same pack created \nbefore such change.\n\nIt is also possible to have a denser delta stream but once deflated it \nis larger than a less dense delta to start with.\n\nJust to say that many tweaks and heuristics have been implemented and \nstudied in git-pack-objects for over a year now in order to get the \nreally small packs we have today. And a really subtle and \ninocent-looking change can break it size wize.\n\nSo what I think is happening with the fastimport code is that the delta \nselection is not really good. It is certainly much better than no delta \nat all but still not optimal which smells deja vu to me. Then by \ndeflating them all together the redundent information that the bad delta \nset still carries along is eliminated -- thanks to zlib sort of \nmitigating the real issue.\n\nBut... as my recent experiments show, the grouping of related deltas \ninto a single zlib stream doesn't produce significant improvements when \nimplemented directly into git-pack-objects. Certainly not worth the \ninconvenients and costs it brings along. I even think that if you used \ngit-repack -a -f on the pack produced by the import process, with only \ndelta deflated individually just like it did originally, then the \nrepacked pack would _also_ shrink significantly. Most probably around \n4x just like you observed with the grouping of deltas in the same zlib \nstream.\n\nNot only would git-repack make it much smaller, but it also provicdes a \nmuch better layout where all objects for recent commits are all stored \ntogether at the beginning of the pack. The fastimport code is instead \nstoring them scattered all over the pack for every commit by making all \nrevisions of each file next to each other which will cause horrible \naccess patterns and really bad IO.\n\nSo I think that trying to make fastimport too clever is wrong. It \nshould instead focus on creating an initial pack as fast as possible and \nthen rely on a final git-repack pass to produce the shrinked pack. I \nreally doubt the import code could ever make a better job than \ngit-pack-objects does.\n\nIf I can make a suggestion, you should forget about this multiple deltas \nin one zlib stream for now and focus on making the import process work \nall the way to tree and commit objects instead. Then, only then, if \ngit-repack -a -f doesn't produce satisfactory pack size we could look at \nbetter pack encoding. And so far the grouping of related deltas in one \nzlib stream is _not_ a better encoding given the rather small \nimprovement over unmodified git-pack-objects vs the inconvenients and \ncost it brings with it.\n\n> As comparison, I just tar/zipped the Mozilla CVS repo and it is 541MB.\n> The 295MB git pack number does not have commits and trees in it, it is\n> revisions only.\n\nRunning git-repack -a -f from a recent GIT on the Mozilla repo converted \nthrough cvsps and friends produces a pack smaller than 500MB. I even \nbrought it down to 430MB by using non default delta window and depth.\n\n\nNicolas\n"},{"id":"25673","messageId":"20060821064659.GB24054@spearce.org","threadId":"5297","inReplyTo":"Pine.LNX.4.64.0608202257020.3682@localhost.localdomain","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-21T06:46:59Z","receivedAt":"2006-08-21T06:46:59Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> I looked at it too and the code looks OK.\n\nBased on the stats Jon provided me it appeared as though the code\nskipped about 9% of the objects, and at the time I thought I new\nwhy but looking at it again right now I'm not sure why. :-)\n\nAssuming the objects were roughly the same size (probably a bad\nassumption, but lets use it anyway) we're talking about approx. 9%\nincrease, bringing the size to around 360 MB.\n\nSince that is still only blobs and lacks trees&commits, and you were\nable to get a pack from the earlier import attempts down to 430 MB\n(including trees&commits) everything you pointed out with regards\nto delta base selection not being optimal is probably the major\nculprit here.\n \n> So I think that trying to make fastimport too clever is wrong. It \n> should instead focus on creating an initial pack as fast as possible and \n> then rely on a final git-repack pass to produce the shrinked pack. I \n> really doubt the import code could ever make a better job than \n> git-pack-objects does.\n\nI'm mixed on that.\n\nMy goal with fast-import was to construct a pack as cheaply as\npossible in such a way that IO is relatively minimized during\npack construction and later during an initial repacking, as well\nas to avoid all fork'ing costs associated with many update-index\nand repack calls.\n\nfast-import is assuming the front end driving it is being somewhat\nnice by feeding revisions in newest-oldest order, one file at a time.\nIf this assumption is false it will produce a pack but one that is\nso large the IO to repack it will be horrible (but probably would\nstill be better than if these were all loose objects).\n\nfast-import is also assuming that pack construction speed and memory\nusage required to build that pack are more important than subsequent\nreads of the resulting pack.\n\nWhy?\n\nBecause I fully expected the pack to undergo a `git-repack -a -d -f`\nwith a rather large delta depth before it really got used by\nclients which cared about performance or disk space. :-)\n\nWhether or not git-repack can handle such a large pack is another\nstory. Apparently it can already take a ~600 MB pack and do\nsomething useful to it in a reasonable time span so I'm putting\nany limits that might be in there off for now.\n\n\nBut the more I work with Jon on this Mozilla import process the more\nI'm realizing that:\n\n - fast-import.c's other name is \"GIT in 1325 lines of C code, all\n of which more or less already exists elsewhere in a form that\n wasn't useful in this context without refactoring it in major\n ways so I got lazy and rewrote it in another equally useless way\";\n\n - the strategy of how I'm slamming a very large number of objects\n into a pack may be useful in situations other than a foreign\n SCM import process. I can see someone wanting to create a\n large commit with a lot of modified objects. Doing this with\n update-index and write-tree into loose objects would be far\n slower than just generating a new pack if the number of objects\n you are writing exceeds about 100 on Windows or ~1k on UNIX;\n\n - Jon has lots of CPU time to spare and possibly even some memory.\n fast-import is barely using CPU and barely uses memory (its quite\n lightweight!) but its definately producing a suboptimal pack\n as a result. Just doing slightly better delta selection before\n committing an object to the output pack may prevent the need to\n use -f during git-repack and produce something almost as optimal.\n\nRight now fast-import is only lacking the following major features,\nat which point it *should* be able to process the entire Mozilla\nrepository, assuming Jon can get his symbol closing problem in\ncvs2svn solved:\n\n - reload a branch which has been swapped out (requires reading\n the pack that is currently being constructed back into memory,\n which since its not really a valid pack yet and lacks an index\n reusing the code in sha1_file.c is slightly interesting);\n\n - generate a tag object into the pack;\n\n - track association ID numbers to SHA1 IDs (needed to properly\n create a branch from a prior commit or a tag from a prior commit\n as the prior commit's SHA ID isn't known to the front end);\n\nWorking on the multiple objects in one zlib stream code over the\nweekend also showed me how to use sha1_file.c to perform the first\nof the three (I think) and the remaining two are trivial. So my\nweekend wasn't a total loss. :-)\n\nI plan on getting that code finished up in the next day or so and\nget a new draft of it off to Jon. Maybe by then he'll also have\nsomething coming out of cvs2svn's pass 9.\n\n> > As comparison, I just tar/zipped the Mozilla CVS repo and it is 541MB.\n> > The 295MB git pack number does not have commits and trees in it, it is\n> > revisions only.\n> \n> Running git-repack -a -f from a recent GIT on the Mozilla repo converted \n> through cvsps and friends produces a pack smaller than 500MB. I even \n> brought it down to 430MB by using non default delta window and depth.\n\nI'd still like to find a way to beat that 430 MB current\nbest-yet-still-valid size. :-)\n\nI think we'll get there. Shaving off 4-5% with a pack specific\ndictionary may be worthwhile on such large packs, especially ones\nthat are considered \"historical\" and probably will never get repacked\nagain. Folding objects into a single zlib stream may also be worth\nit, but for now I'm going to wait and see what mileage we can get\nfrom the existing repack code and the existing pack file format.\n\n-- \nShawn.\n"},{"id":"25674","messageId":"20060821070609.GC24054@spearce.org","threadId":"5297","inReplyTo":"Pine.LNX.4.64.0608181057440.11359@localhost.localdomain","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-21T07:06:09Z","receivedAt":"2006-08-21T07:06:09Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> On Fri, 18 Aug 2006, Jon Smirl wrote:\n> \n> > On 8/18/06, Nicolas Pitre wrote:\n> > > A better way to get such a size saving is to increase the window and\n> > > depth parameters. For example, a window of 20 and depth of 20 can\n> > > usually provide a pack size saving greater than 11% with none of the\n> > > disadvantages mentioned above.\n> > \n> > Our window size is effectively infinite. I am handing him all of the\n> > revisions from a single file in optimal order. This includes branches.\n> \n> In GIT packing terms this is infinite delta _depth_ not _window_.\n\nWe're not using infinite anything.\n\nfast-import is basically doing window=1 and depth=10.\n\nWe only examine the last blob to see if we can get a delta against\nit. If we do we write that delta out; otherwise we reset our delta\nchain and write the complete object. We also reset our chain after\nwriting out 10 deltas, each of which used the immediately prior\nobject as its base.\n\nSince I just found out that in some cases the Mozilla repository has\n1000s of revisions per file[*1*] and in others only 1 revision per\nfile we probably should be adjusting this depth to have a maximum\nof 500 while also having the frontend send us a \"I'm switching\nfiles now\" marker so we know to not even bother trying to delta\nthe new blob against the last blob as they are likely to not\ndelta well[*2*].\n \n> Default delta params (window=10 depth=10) : 122103455 \n> Agressive deltas (window=50 depth=5000) : 105870516\n> Agressive and grouped deltas (window=50 depth=5000 : 99860685\n\nAlthough complex the aggressive and grouped deltas appears to\nhave saved you 18.2% on this repository. That's not something\nto ignore. A reasonably optimal local pack dictionary could save\nat least 4%[*3*]. Whacking 22% off a 400 MB pack is saving 88 MB.\nTransferring that over the network on an initial clone is like\ndownloading all of Eclipse. Or an uncompressed kernel tarball...\n\n\n[*1*] Jon noted this in another email in this thread but I'm too\n lazy to lookup the hyperlink right now.\n\n[*2*] Granted in some cases they may delta very well against each\n other but I think the probablity of that occuring is low\n\t enough that its not worth worrying about in fast-import.c;\n\t we can let repack's strategy deal with it instead.\n\n[*3*] I wrote a brain-dead simple local dictionary selecter in Perl.\n Its horribly far from being ideal. But it is consistently\n saving us 4% on the GIT and the Mozilla repository and its\n\t pretty darn fast. Shockingly the C keywords didn't gain\n\t us very much here; its project specific text that's the\n\t real win.\n\n\t Looking at chunks which are frequently copied in deltas\n\t from base objects and breaking those chunks up into\n\t smaller common chunks, then loading those most frequent\n\t common chunks into the pack dictionary would most likely\n\t produce far better results.\n\n-- \nShawn.\n"},{"id":"25686","messageId":"ecc1ks$t3p$1@sea.gmane.org","threadId":"5297","inReplyTo":"20060821064659.GB24054@spearce.org","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-08-21T10:24:44Z","receivedAt":"2006-08-21T10:24:44Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Shawn Pearce wrote:\n\n>  - the strategy of how I'm slamming a very large number of objects\n>    into a pack may be useful in situations other than a foreign\n>    SCM import process.  I can see someone wanting to create a\n>    large commit with a lot of modified objects.  Doing this with\n>    update-index and write-tree into loose objects would be far\n>    slower than just generating a new pack if the number of objects\n>    you are writing exceeds about 100 on Windows or ~1k on UNIX;\n\nLike e.g. initial import of large project, or incorporating some subproject\ninto a projects (e.g. gitk and gitweb in git)?\n\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"25687","messageId":"9e4733910608210707v67659a1co7b73e409e0d20132@mail.gmail.com","threadId":"5297","inReplyTo":"20060821070609.GC24054@spearce.org","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-21T14:07:36Z","receivedAt":"2006-08-21T14:07:36Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"Mozilla CVS files have between 1 and 1700 deltas. The average is ten,\nbut the deviation is high. I believe less than 10 files have over 1000\ndeltas, they are all in the root directory and related to the build\nprocess. Many files have no deltas, or because of CVS artifacts all of\nthe revisions are identical.\n\nI am still IO bound. Random access IO is the problem, not stream IO. I\nhave to open and read 110,000 (5GB total) files. It takes about 2hrs\nto do all of the IO. I'm not CPU bound yet but as we make things more\nefficient, I am getting closer to being CPU bound.\n\nForking is not an option. It can takes days to fork 1M copies of an\napp. I have used oprofile on parsecvs. It spends 60% of the time in\nthe kernel processing fork calls. Parsecvs runs for 6hrs on mozcvs and\ndies without finishing.\n\nI am back to working on the branch code. I'm over the cold I got from\nmy 2 yr old. It is slow going now. I am in the phase where the import\nprocess runs without error 5-10 minutes and then dies from some\nunusual branch case. I fix it up and try again. I am slowly\nidentifying and removing all the code in cvs2svn that puts the\nbranches and symbols into their own subdirectories.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25691","messageId":"Pine.LNX.4.64.0608211036150.3851@localhost.localdomain","threadId":"5297","inReplyTo":"20060821070609.GC24054@spearce.org","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-21T15:46:42Z","receivedAt":"2006-08-21T15:46:42Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 21 Aug 2006, Shawn Pearce wrote:\n\n> Nicolas Pitre wrote:\n> > On Fri, 18 Aug 2006, Jon Smirl wrote:\n> > \n> > > On 8/18/06, Nicolas Pitre wrote:\n> > > > A better way to get such a size saving is to increase the window and\n> > > > depth parameters. For example, a window of 20 and depth of 20 can\n> > > > usually provide a pack size saving greater than 11% with none of the\n> > > > disadvantages mentioned above.\n> > > \n> > > Our window size is effectively infinite. I am handing him all of the\n> > > revisions from a single file in optimal order. This includes branches.\n> > \n> > In GIT packing terms this is infinite delta _depth_ not _window_.\n> \n> We're not using infinite anything.\n> \n> fast-import is basically doing window=1 and depth=10.\n\nYes, that is what I figured out looking at the code.\n\n> We only examine the last blob to see if we can get a delta against\n> it. If we do we write that delta out; otherwise we reset our delta\n> chain and write the complete object. We also reset our chain after\n> writing out 10 deltas, each of which used the immediately prior\n> object as its base.\n\nI think this is a perfectly sensible thing to do for the initial import \npass. This will get the data in GIT format quickly and save disk space \nover no deltas at all. No need to seek for optimal packing at that \npoint but only lay things out for a faster git-repack pass to complete \nthe import.\n\nAlso, like I said before, you cannot get a nice object layout from your \nimport process since all revisions of each file end up next to each \nother while in practice what you want is all objects for each _commit_ \nto be next to each other. Otherwise checking out a commit will seek all \nover the pack like mad. A final repack using git-repack will create \nthat nice object layout for you and that is something you cannot do \non the fly.\n\nThe git-pack-objects code is also where all the accumulated knowledge \nfor best delta packing heuristics has been created over the last year. \nIt would be counter productive to cut yourself from its value. If \nanything more clever can be done with packing it probably should be done \nthere.\n\nFinally, I don't see how you could create nice deltas for tree objects \non the fly like you do with blobs without making your code significantly \nmore complex and use more memory due to the recursive nature of \ndirectory information. This is no a problem for git-pack-objects since \ntree objects are no different from blob objects when deltifying them.\n\nAgain this is why I think you should focus on the quickest generation of \na reasonable intermediate pack and let git-repack make it optimal.\n\n> Since I just found out that in some cases the Mozilla repository has\n> 1000s of revisions per file[*1*] and in others only 1 revision per\n> file we probably should be adjusting this depth to have a maximum\n> of 500 while also having the frontend send us a \"I'm switching\n> files now\" marker so we know to not even bother trying to delta\n> the new blob against the last blob as they are likely to not\n> delta well[*2*].\n\nNo please don't do that. A deep delta chain won't produce a dramatic \nsize difference but it _will_ make it really costly to read objects back \nfrom the pack later on. For example it might make the next git-repack \nmany times longer but the size saving will not be more than 20%. If you \nagree with me that a final git-repack is the best thing to do then the \nintermediate pack doesn't have to be that small.\n\n> Although complex the aggressive and grouped deltas appears to\n> have saved you 18.2% on this repository. That's not something\n> to ignore.\n\nBut the aggressive delta alone saved 13% already. The remaining saving \nis questionable since, like I said, it prevents the delta data reuse \noptimization which is so nice in order to reduce the load on servers to \nnearly zero.\n\n> A reasonably optimal local pack dictionary could save\n> at least 4%[*3*]. Whacking 22% off a 400 MB pack is saving 88 MB.\n\nThis is still speculations though. The separate dictionary is certainly \na good idea to try out and it is way more flexible than the grouped \ndeltas. But I doubt the combined concepts will all add up size \nsavings linearly.\n\n> Transferring that over the network on an initial clone is like\n> downloading all of Eclipse. Or an uncompressed kernel tarball...\n\n... something that most people can afford these days. Plus, not using \ngrouped objects would make future shallow clones much less costly on the \nserver as well, while this is something that most people will be most \ninterested in with such large repos and which has much higher bandwidth \nsaver value.\n\n\nOf course this is a trade-off. Tighter packs are likely to be more \ncostly to use. So far we've contained that cost to the _initial_ \ngeneration of the pack (using -a -f with git-repack) while subsequent \nrepacking for network transfer were basically free on CPU. The grouped \nobject concept saves around 7 to 11% on pack size in my tests, but it \nimpose a non negligible cost on any further repacking as well as an \nadditional cost on the fetching of objects out of the pack.\n\n> [*3*] I wrote a brain-dead simple local dictionary selecter in Perl.\n> Its horribly far from being ideal. But it is consistently\n> saving us 4% on the GIT and the Mozilla repository and its\n> \t pretty darn fast. Shockingly the C keywords didn't gain\n> \t us very much here; its project specific text that's the\n> \t real win.\n> \n> \t Looking at chunks which are frequently copied in deltas\n> \t from base objects and breaking those chunks up into\n> \t smaller common chunks, then loading those most frequent\n> \t common chunks into the pack dictionary would most likely\n> \t produce far better results.\n\nI think such a global dictionary per pack is something that could be \nreally nice. Again it limits the cost to the initial repack process \nwhile having no cost impact neither on the delta reuse optimization nor \non the object checkout which is not the case for object grouping. \nCertainly worth experimenting ... but independently from any import \nprocess I think.\n\n\nNicolas\n"},{"id":"25695","messageId":"9e4733910608210914s1157f47eta821584928ce4dd5@mail.gmail.com","threadId":"5297","inReplyTo":"Pine.LNX.4.64.0608211036150.3851@localhost.localdomain","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-21T16:14:44Z","receivedAt":"2006-08-21T16:14:44Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"How about making the length of delta chains an exponential function of\nthe number of revs? In Mozilla configure.in has 1,700 revs and it is a\n250K file. If you store a full copy every 10 revs that is 43MB\n(prezip) of data that almost no one is going to look at. The chains\nlengths should reflect the relative probability that someone is going\nto ask to see the revs. That is not at all a uniform function.\n\nPersonally I am still in favor of a two pack system. One archival pack\nstores everything in a single chain and size, not speed, is it's most\nimportant attribute. It is marked readonly and only functions as an\narchive; git-repack never touches it. It might even use a more compact\ncompression algorithm.\n\nThe second pack is for storing more recent revisions. The archival\npack would be constructed such that none of the files needed for the\nhead revisions of any branch are in it. They would all be in the\nsecond pack.\n\nAfter time the second pack may grow large and another archival pack\ncan be created. The first one would still be maintained in it's\nreadonly form. git could be optimized to always search for objects in\nnon-archival packs before even opening the index of an archival one.\n\nThis may be a path to partial repositories. Instead of downloading the\nreal archival pack I could download just an index for it. The index\nentries would be marked to indicate that these objects are valid but\nnot-present.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25696","messageId":"9e4733910608210923qba3ca96n40c4c392fc65baa8@mail.gmail.com","threadId":"5297","inReplyTo":"20060821064659.GB24054@spearce.org","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-21T16:23:19Z","receivedAt":"2006-08-21T16:23:19Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/21/06, Shawn Pearce wrote:\n> Based on the stats Jon provided me it appeared as though the code\n> skipped about 9% of the objects, and at the time I thought I new\n> why but looking at it again right now I'm not sure why. :-)\n\n9% of the objects may be duplicates because of branching. I have no\nway of detecting them since I am not maintaining a map of sha1s\nencountered. The way CVS branching works some revisions are built\nusing forward diffs and some reverse, I can't tell when they will end\nup with the same result.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25698","messageId":"Pine.LNX.4.64.0608211309270.3851@localhost.localdomain","threadId":"5297","inReplyTo":"9e4733910608210914s1157f47eta821584928ce4dd5@mail.gmail.com","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-21T17:48:59Z","receivedAt":"2006-08-21T17:48:59Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 21 Aug 2006, Jon Smirl wrote:\n\n> How about making the length of delta chains an exponential function of\n> the number of revs? In Mozilla configure.in has 1,700 revs and it is a\n> 250K file. If you store a full copy every 10 revs that is 43MB\n> (prezip) of data that almost no one is going to look at.\n> The chains\n> lengths should reflect the relative probability that someone is going\n> to ask to see the revs. That is not at all a uniform function.\n\n1) You can do that already with stock git-repack.\n\n2) The current git-pack-objects code can and does produce a delta \"tree\" \n off of a single base object. It doesn't have to be a linear list.\n\nTherefore, even if the default depth is 10, you may as well have many \ndeltas pointing to the _same_ base object effectively making the \ncompression ratio much larger than 1/10.\n\nIf for example each object has 2 delta childs, and each of those deltas \nalso have 2 delta childs, you could have up to 39366 delta objects \nattached to a _single_ undeltified base object.\n\nAnd of course the git-pack-objects code doesn't limit the number of \ndelta childs in any way so this could theoritically be infinite even \nthough the max depth is 10. OK the delta matching window limits that \nsomehow but nothing prevents you from repacking with a larger window \nsince that parameter has no penalty on the reading of objects out of the \npack.\n\n> Personally I am still in favor of a two pack system. One archival pack\n> stores everything in a single chain and size, not speed, is it's most\n> important attribute. It is marked readonly and only functions as an\n> archive; git-repack never touches it. It might even use a more compact\n> compression algorithm.\n> \n> The second pack is for storing more recent revisions. The archival\n> pack would be constructed such that none of the files needed for the\n> head revisions of any branch are in it. They would all be in the\n> second pack.\n\nPersonally I'm still against that. All arguments put forward for a \ndifferent or multiple packing system are based on unproven assumptions \nso far and none of those arguments actually present significant \nadvantages over the current system. For example, I was really intriged \nby the potential of object grouping into a single zlib stream at first, \nbut it turns out not to be so great after actual testing.\n\nI still think that a global zlib dictionary is a good idea. Not because \nit looks like it'll make packs enormously smaller, but rather because it \nimpose no performance regression over the current system. And I \nstrongly believe that you have to have a really strong case for \npromoting a solution that carries performance regression, something like \nover 25% smaller packs for example. But so far it didn't happen.\n\n> This may be a path to partial repositories. Instead of downloading the\n> real archival pack I could download just an index for it. The index\n> entries would be marked to indicate that these objects are valid but\n> not-present.\n\nAn index without the actual objects is simply useless. You could do \nwithout the index entirely in that case anyway since the mere presence \nof an entry in the index doesn't give you anything really useful.\n\n\nNicolas\n"},{"id":"25699","messageId":"Pine.LNX.4.64.0608211350430.3851@localhost.localdomain","threadId":"5297","inReplyTo":"Pine.LNX.4.64.0608211309270.3851@localhost.localdomain","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-21T17:55:04Z","receivedAt":"2006-08-21T17:55:04Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 21 Aug 2006, Nicolas Pitre wrote:\n\n> If for example each object has 2 delta childs, and each of those deltas \n> also have 2 delta childs, you could have up to 39366 delta objects \n> attached to a _single_ undeltified base object.\n\nSorry I've got the math wrong. That is 3582 deltas, given a \nconservative number of delta childs = 2.\n\n\nNicolas\n"},{"id":"25700","messageId":"Pine.LNX.4.64.0608211358390.3851@localhost.localdomain","threadId":"5297","inReplyTo":"Pine.LNX.4.64.0608211350430.3851@localhost.localdomain","subject":"Re: Huge win, compressing a window of delta runs as a unit","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-21T18:01:55Z","receivedAt":"2006-08-21T18:01:55Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 21 Aug 2006, Nicolas Pitre wrote:\n\n> On Mon, 21 Aug 2006, Nicolas Pitre wrote:\n> \n> > If for example each object has 2 delta childs, and each of those deltas \n> > also have 2 delta childs, you could have up to 39366 delta objects \n> > attached to a _single_ undeltified base object.\n> \n> Sorry I've got the math wrong. That is 3582 deltas, given a \n> conservative number of delta childs = 2.\n\nOK I just can't count. That is 2046.\n\nBut since I made a fool of myself already, why not try with 3 delta \nchilds for a delta depth of 10 just for fun, now that I should have it \nright. The answer is 88572.\n\nAnyway I hope you've got my point now. ;-)\n\n\nNicolas\n"}]}