{"thread":{"id":"5419","subject":"Packfile can't be mapped","startedAt":"2006-08-28T01:04:01Z","lastAt":"2006-08-29T05:33:12Z","messageCount":16,"participants":["Jon Smirl","Shawn Pearce","Nicolas Pitre","Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"26022","messageId":"9e4733910608271804j762960a8ud83654c78ebe009a@mail.gmail.com","threadId":"5419","inReplyTo":null,"subject":"Packfile can't be mapped","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-28T01:04:01Z","receivedAt":"2006-08-28T01:04:01Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"git-repack can't handle my 1.75GB pack file. I am running x86 with 3GB\naddress space.\n\n-rw-rw-r-- 1 jonsmirl jonsmirl 47221712 Aug 27 20:29 testme.idx\n-rw-rw-r-- 1 jonsmirl jonsmirl 1754317619 Aug 27 20:29 testme.pack\n\n[jonsmirl@jonsmirl t1]$ git-repack -a -f --window=50 --depth=5000\nGenerating pack...\nDone counting 1963325 objects.\nfatal: packfile .git/objects/pack/testme.pack cannot be mapped.\n[jonsmirl@jonsmirl t1]$\n\nIt is built from Mozilla CVS but it is an intermediate stage of our\nwork. The fast-import tool isn't diffing directory tree which makes\nthe pack much bigger than it needs to be. Shawn is working on the\npacking code.\n\n---------------------------------------------------\nAlloc'd objects: 1968000 ( 1892000 overflow )\nTotal objects: 1967527 ( 41856 duplicates)\n blobs : 633842 ( 0 duplicates)\n trees : 1131208 ( 41856 duplicates)\n commits: 200921 ( 0 duplicates)\n tags : 1556 ( 0 duplicates)\nTotal branches: 1600 ( 7985 loads )\n marks: 1048576 ( 200921 unique )\n atoms: 56803\nMemory total: 66908 KiB\n pools: 5408 KiB\n objects: 61500 KiB\nPack remaps: 9501\n---------------------------------------------------\nPack size: 1713200 KiB\nIndex size: 46114 KiB\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26023","messageId":"20060828024720.GD24204@spearce.org","threadId":"5419","inReplyTo":"9e4733910608271804j762960a8ud83654c78ebe009a@mail.gmail.com","subject":"Re: Packfile can't be mapped","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-28T02:47:20Z","receivedAt":"2006-08-28T02:47:20Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jon Smirl wrote:\n> git-repack can't handle my 1.75GB pack file. I am running x86 with 3GB\n> address space.\n> \n> -rw-rw-r-- 1 jonsmirl jonsmirl 47221712 Aug 27 20:29 testme.idx\n> -rw-rw-r-- 1 jonsmirl jonsmirl 1754317619 Aug 27 20:29 testme.pack\n> \n> [jonsmirl@jonsmirl t1]$ git-repack -a -f --window=50 --depth=5000\n> Generating pack...\n> Done counting 1963325 objects.\n> fatal: packfile .git/objects/pack/testme.pack cannot be mapped.\n> [jonsmirl@jonsmirl t1]$\n> \n> It is built from Mozilla CVS but it is an intermediate stage of our\n> work. The fast-import tool isn't diffing directory tree which makes\n> the pack much bigger than it needs to be. Shawn is working on the\n> packing code.\n\nI'm going to try to get tree deltas written to the pack sometime this\nweek. That should compact this intermediate pack down to something\nthat git-pack-objects would be able to successfully mmap into a\n32 bit address space. A complete repack with no delta reuse will\nhopefully generate a pack closer to 400 MB in size. But I know\nJon would like to get that pack even smaller. :)\n\nI should point out that the input stream to fast-import was 20 GB\n(completely decompressed revisions from RCS) plus all commit data.\nThe original CVS ,v files are around 3 GB. An archive .tar.gz'ing\nthe ,v files is around 550 MB. Going to only 1.7 GB without tree\nor commit deltas is certainly pretty good. :)\n\n> ---------------------------------------------------\n> Alloc'd objects: 1968000 ( 1892000 overflow )\n> Total objects: 1967527 ( 41856 duplicates)\n> blobs : 633842 ( 0 duplicates)\n> trees : 1131208 ( 41856 duplicates)\n> commits: 200921 ( 0 duplicates)\n> tags : 1556 ( 0 duplicates)\n> Total branches: 1600 ( 7985 loads )\n> marks: 1048576 ( 200921 unique )\n> atoms: 56803\n> Memory total: 66908 KiB\n> pools: 5408 KiB\n> objects: 61500 KiB\n> Pack remaps: 9501\n> ---------------------------------------------------\n> Pack size: 1713200 KiB\n> Index size: 46114 KiB\n\nAll of that says that aside from the 1.7 GB output file fast-import\nran extremely well. About 1.9 million objects were written into\nthe output pack file, with 41k duplicate trees (duplicate blobs\nwere removed by cvs2svn prior to fast-import so they don't appear).\n200k commits were created across 1600 branches. And we did it in\nonly 67 MB of memory.\n\nWe also had ~8000 LRU cache misses related to our branch data;\nthis just means that cvs2svn likes to frequently jump around\nbetween branches rather than import an entire branch at a time.\nBoosting the size of the LRU cache (at the expense of needing more\nmemory) should reduce those cache misses as well as 'Pack remaps'.\n\nI'd also like to clean up that pack remapping code and move it\ninto sha1_file.c. Its an implementation of partial pack mapping\nand it is apparently working quite well for us in fast-import.\nIt may help GIT deal with very large packs (e.g. 1.7 GB) on smaller\naddress space systems (e.g. 32 bit).\n\n\nWe're not confident that this import is completely valid yet.\nWe have a few translation issues we're still working on. But now\nthat we have a complete pack going from start to finish we can start\nto focus on those issues. Especially since this entire process\n(,v to .pack) is less than half a day to run.\n\n-- \nShawn.\n"},{"id":"26025","messageId":"Pine.LNX.4.64.0608280014190.3683@localhost.localdomain","threadId":"5419","inReplyTo":"20060828024720.GD24204@spearce.org","subject":"Re: Packfile can't be mapped","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-28T04:27:02Z","receivedAt":"2006-08-28T04:27:02Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 27 Aug 2006, Shawn Pearce wrote:\n\n> I'm going to try to get tree deltas written to the pack sometime this\n> week. That should compact this intermediate pack down to something\n> that git-pack-objects would be able to successfully mmap into a\n> 32 bit address space. A complete repack with no delta reuse will\n> hopefully generate a pack closer to 400 MB in size. But I know\n> Jon would like to get that pack even smaller. :)\n\nOne thing to consider in your code (if you didn't implement that \nalready) is to _not_ attempt any delta on any object whose size is \nsmaller than 50 bytes, and then limit the maximum delta size to \nobject_size/2 - 20 (use that for the last argument to diff-delta() and \nstore the undeltified object when diff-delta returns NULL). This way \nyou'll avoid creating delta objects that are most likely to end up being \n_larger_ than the undeltified object.\n\n> I should point out that the input stream to fast-import was 20 GB\n> (completely decompressed revisions from RCS) plus all commit data.\n> The original CVS ,v files are around 3 GB. An archive .tar.gz'ing\n> the ,v files is around 550 MB. Going to only 1.7 GB without tree\n> or commit deltas is certainly pretty good. :)\n\nGood job indeed. Oh and you probably should not bother trying to \ndeltify commit objects at all since that would be a waste of time.\n\n\nNicolas\n"},{"id":"26027","messageId":"Pine.LNX.4.64.0608272133390.27779@g5.osdl.org","threadId":"5419","inReplyTo":"Pine.LNX.4.64.0608280014190.3683@localhost.localdomain","subject":"Re: Packfile can't be mapped","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-08-28T04:36:27Z","receivedAt":"2006-08-28T04:36:27Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 28 Aug 2006, Nicolas Pitre wrote:\n> \n> Good job indeed. Oh and you probably should not bother trying to \n> deltify commit objects at all since that would be a waste of time.\n\nIt might not necessarily always be a waste of time. Especially if you have \nmultiple branches tracking a \"maintenance\" branch, you often end up having \nthe same commit message repeated several times in \"unrelated\" commits \n(they're really the same commit, applied to another branch).\n\nAlso, I could imagine that some automated system generates very verbose \n(and possibly very regular) commit messages, so under certain \ncircumstances it may well make sense to see if the commits migth delta \nagainst each other.\n\nBut I'll agree that in normal use it's not likely to be a huge saving, \nthough. It's probably not worth doing for the fast importer unless it just \nhappens to fall out of the code very easily.\n\n\t\tLinus\n"},{"id":"26029","messageId":"20060828053301.GA25285@spearce.org","threadId":"5419","inReplyTo":"Pine.LNX.4.64.0608280014190.3683@localhost.localdomain","subject":"Re: Packfile can't be mapped","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-28T05:33:01Z","receivedAt":"2006-08-28T05:33:01Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> On Sun, 27 Aug 2006, Shawn Pearce wrote:\n> \n> > I'm going to try to get tree deltas written to the pack sometime this\n> > week. That should compact this intermediate pack down to something\n> > that git-pack-objects would be able to successfully mmap into a\n> > 32 bit address space. A complete repack with no delta reuse will\n> > hopefully generate a pack closer to 400 MB in size. But I know\n> > Jon would like to get that pack even smaller. :)\n> \n> One thing to consider in your code (if you didn't implement that \n> already) is to _not_ attempt any delta on any object whose size is \n> smaller than 50 bytes, and then limit the maximum delta size to \n> object_size/2 - 20 (use that for the last argument to diff-delta() and \n> store the undeltified object when diff-delta returns NULL). This way \n> you'll avoid creating delta objects that are most likely to end up being \n> _larger_ than the undeltified object.\n\nI haven't tried this. Should be trivial to implement. Thanks for\nthe suggestion.\n\n> > I should point out that the input stream to fast-import was 20 GB\n> > (completely decompressed revisions from RCS) plus all commit data.\n> > The original CVS ,v files are around 3 GB. An archive .tar.gz'ing\n> > the ,v files is around 550 MB. Going to only 1.7 GB without tree\n> > or commit deltas is certainly pretty good. :)\n> \n> Good job indeed. Oh and you probably should not bother trying to \n> deltify commit objects at all since that would be a waste of time.\n\nI wasn't going to bother even trying to delta the commits. In this\nimport the 200k commits isn't a very large percentage of the data.\nAs I'm sure you are well aware its pretty much a waste time to try\nwith the commits, especially with an \"intermediate\" pack such as\nthis one.\n\n-- \nShawn.\n"},{"id":"26032","messageId":"20060828060029.GB25285@spearce.org","threadId":"5419","inReplyTo":"Pine.LNX.4.64.0608272133390.27779@g5.osdl.org","subject":"Re: Packfile can't be mapped","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-28T06:00:29Z","receivedAt":"2006-08-28T06:00:29Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Linus Torvalds wrote:\n> \n> On Mon, 28 Aug 2006, Nicolas Pitre wrote:\n> > \n> > Good job indeed. Oh and you probably should not bother trying to \n> > deltify commit objects at all since that would be a waste of time.\n> \n> It might not necessarily always be a waste of time. Especially if you have \n> multiple branches tracking a \"maintenance\" branch, you often end up having \n> the same commit message repeated several times in \"unrelated\" commits \n> (they're really the same commit, applied to another branch).\n> \n> Also, I could imagine that some automated system generates very verbose \n> (and possibly very regular) commit messages, so under certain \n> circumstances it may well make sense to see if the commits migth delta \n> against each other.\n> \n> But I'll agree that in normal use it's not likely to be a huge saving, \n> though. It's probably not worth doing for the fast importer unless it just \n> happens to fall out of the code very easily.\n\nDoes git-pack-objects attempt to delta commits against each other?\n\n\nI've been thinking about applying a pack-local but zlib-stream\nglobal dictionary. If we added three global dicationaries to the\nfront of the pack file, one for commits, one for trees and one\nfor blobs, and use those as the global dictionaries for the zlib\nstreams stored within that pack we could probably get a good space\nsavings for trees and commits.\n\nI'd suspect that for many projects the commit global dictionary\nwould contain the common required strings such as:\n\n 'tree ', 'parent ', 'committer ', 'author ', 'Signed-off-by: '\n\nplus the top author/committer name/email combination strings.\nFor GIT I'd expect 'Junio C Hamano ' to be way up\nthere in terms of frequency within commit objects. Finding the most\ncommon authors and committer strings would be trivial, as would\nfinding the most common 'footer' strings such as 'Signed-off-by: '\nand 'Acked-by: '.\n\nI think the same is true of trees, with '10644 ', '10755 ', '40000 '\nbeing way up there, but also file names that commonly appear within\ntrees, e.g. \"Makefile.in\\0\".\n\nBlobs would be more difficult to generate a reasonable global\ndictionary for. But for some projects a crude estimated dictionary\ncan shave off at least 4% of pack size (true in both GIT and Mozilla\nsources it seems).\n\n\nOf course the major problem with pack-local, stream global\ndictionaries is it voids the ability to reuse that zlib'd content\nfrom that pack in another pack without wholesale copying the\ndictionary as well. This is an issue for servers which want to\ncopy out the pack entry without recompressing it but also want the\nstorage savings from the global dictionaries.\n\nBut then again, if we just delta against a commit which uses the\nsame author and committer, or against the same tree but different\nversion then there should be a lot of delta copying from the base...\nwhich easily allows entry reuse and should provide similiar space\nsavings, providing the delta depth is deep enough (or the delta graph\nis wide enough) to minimize the number of base objects containing\nrepeated occurrances of the common strings.\n\n-- \nShawn.\n"},{"id":"26045","messageId":"9e4733910608280715s52ae1d48n8886f24034cf44a5@mail.gmail.com","threadId":"5419","inReplyTo":"20060828060029.GB25285@spearce.org","subject":"Re: Packfile can't be mapped","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-28T14:15:57Z","receivedAt":"2006-08-28T14:15:57Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/28/06, Shawn Pearce wrote:\n> Of course the major problem with pack-local, stream global\n> dictionaries is it voids the ability to reuse that zlib'd content\n> from that pack in another pack without wholesale copying the\n> dictionary as well. This is an issue for servers which want to\n> copy out the pack entry without recompressing it but also want the\n> storage savings from the global dictionaries.\n\nIf you copy an entire pack with a dictionary embedded in it everything\nis fine. But if you pull objects out of the pack for transmission it\nlooks like they will need to be unpacked and repacked without the\ndictionary. My plan was to only use dictionaries in archival packs\nthat would be used in a read only manner and copied around whole.\n\nSo there would need to something like an archive flag on git-repack\nwhich would spend extra CPU time trying to make the pack as small as\npossible. Normal use of git-repack wouldn't touch packs marked with\nthe archive flag since they were already in optimal form.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26046","messageId":"Pine.LNX.4.64.0608281026110.3683@localhost.localdomain","threadId":"5419","inReplyTo":"20060828060029.GB25285@spearce.org","subject":"Re: Packfile can't be mapped","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-28T14:40:49Z","receivedAt":"2006-08-28T14:40:49Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 28 Aug 2006, Shawn Pearce wrote:\n\n> Linus Torvalds wrote:\n> > \n> > On Mon, 28 Aug 2006, Nicolas Pitre wrote:\n> > > \n> > > Good job indeed. Oh and you probably should not bother trying to \n> > > deltify commit objects at all since that would be a waste of time.\n> > \n> > It might not necessarily always be a waste of time. Especially if you have \n> > multiple branches tracking a \"maintenance\" branch, you often end up having \n> > the same commit message repeated several times in \"unrelated\" commits \n> > (they're really the same commit, applied to another branch).\n> > \n> > Also, I could imagine that some automated system generates very verbose \n> > (and possibly very regular) commit messages, so under certain \n> > circumstances it may well make sense to see if the commits migth delta \n> > against each other.\n> > \n> > But I'll agree that in normal use it's not likely to be a huge saving, \n> > though. It's probably not worth doing for the fast importer unless it just \n> > happens to fall out of the code very easily.\n> \n> Does git-pack-objects attempt to delta commits against each other?\n\nYes it does. But simply because it requires no special case in the code \nfor that and it can afford spending more time trying to tighten a pack \ngiven that it wastes a lot of cycles with delta windows already. In the \ncontext of an intermediate pack from fast-import I doubt it is worth it \nsince the extra time spent on that won't give you a significant size \nreduction.\n\n> I've been thinking about applying a pack-local but zlib-stream\n> global dictionary. If we added three global dicationaries to the\n> front of the pack file, one for commits, one for trees and one\n> for blobs, and use those as the global dictionaries for the zlib\n> streams stored within that pack we could probably get a good space\n> savings for trees and commits.\n> \n> I'd suspect that for many projects the commit global dictionary\n> would contain the common required strings such as:\n> \n> 'tree ', 'parent ', 'committer ', 'author ', 'Signed-off-by: '\n> \n> plus the top author/committer name/email combination strings.\n> For GIT I'd expect 'Junio C Hamano ' to be way up\n> there in terms of frequency within commit objects. Finding the most\n> common authors and committer strings would be trivial, as would\n> finding the most common 'footer' strings such as 'Signed-off-by: '\n> and 'Acked-by: '.\n> \n> I think the same is true of trees, with '10644 ', '10755 ', '40000 '\n> being way up there, but also file names that commonly appear within\n> trees, e.g. \"Makefile.in\\0\".\n\nIndeed.\n\n> Blobs would be more difficult to generate a reasonable global\n> dictionary for. But for some projects a crude estimated dictionary\n> can shave off at least 4% of pack size (true in both GIT and Mozilla\n> sources it seems).\n> \n> \n> Of course the major problem with pack-local, stream global\n> dictionaries is it voids the ability to reuse that zlib'd content\n> from that pack in another pack without wholesale copying the\n> dictionary as well. This is an issue for servers which want to\n> copy out the pack entry without recompressing it but also want the\n> storage savings from the global dictionaries.\n\nWhy would copying the dictionary as well be a problem? How large might \nit be? Can it be stored deflated itself?\n\n> But then again, if we just delta against a commit which uses the\n> same author and committer, or against the same tree but different\n> version then there should be a lot of delta copying from the base...\n> which easily allows entry reuse and should provide similiar space\n> savings, providing the delta depth is deep enough (or the delta graph\n> is wide enough) to minimize the number of base objects containing\n> repeated occurrances of the common strings.\n\nThis is already attempted by pack-objects and used when it provides a \ngain. It is just much less likely to happen than with trees or blobs.\n\n\nNicolas\n"},{"id":"26047","messageId":"Pine.LNX.4.64.0608281045590.3683@localhost.localdomain","threadId":"5419","inReplyTo":"Pine.LNX.4.64.0608272133390.27779@g5.osdl.org","subject":"Re: Packfile can't be mapped","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-28T14:48:52Z","receivedAt":"2006-08-28T14:48:52Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 27 Aug 2006, Linus Torvalds wrote:\n\n> \n> \n> On Mon, 28 Aug 2006, Nicolas Pitre wrote:\n> > \n> > Good job indeed. Oh and you probably should not bother trying to \n> > deltify commit objects at all since that would be a waste of time.\n> \n> It might not necessarily always be a waste of time.\n[...]\n> It's probably not worth doing for the fast importer unless it just \n> happens to fall out of the code very easily.\n\n... which is what my comment was all about.\n\n\nNicolas\n"},{"id":"26049","messageId":"9e4733910608280844q41ea1a61r33c3eadc3e942604@mail.gmail.com","threadId":"5419","inReplyTo":"Pine.LNX.4.64.0608281026110.3683@localhost.localdomain","subject":"Re: Packfile can't be mapped","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-28T15:44:37Z","receivedAt":"2006-08-28T15:44:37Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/28/06, Nicolas Pitre wrote:\n> > Of course the major problem with pack-local, stream global\n> > dictionaries is it voids the ability to reuse that zlib'd content\n> > from that pack in another pack without wholesale copying the\n> > dictionary as well. This is an issue for servers which want to\n> > copy out the pack entry without recompressing it but also want the\n> > storage savings from the global dictionaries.\n>\n> Why would copying the dictionary as well be a problem? How large might\n> it be? Can it be stored deflated itself?\n\nThe dictionaries are only 4KB. But they have to match up with the\nobjects compressed using them. If you bring an object straight down\nout of a dictionary based pack and make it standalone you won't be\nable to read it. You need the dictionary to decode it. What if the\nlocal and remote packs have been packed using two different\ndictionaries? You can't directly move objects between them.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26051","messageId":"20060828164222.GA22451@spearce.org","threadId":"5419","inReplyTo":"Pine.LNX.4.64.0608280014190.3683@localhost.localdomain","subject":"Re: Packfile can't be mapped","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-28T16:42:22Z","receivedAt":"2006-08-28T16:42:22Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> On Sun, 27 Aug 2006, Shawn Pearce wrote:\n> \n> > I'm going to try to get tree deltas written to the pack sometime this\n> > week. That should compact this intermediate pack down to something\n> > that git-pack-objects would be able to successfully mmap into a\n> > 32 bit address space. A complete repack with no delta reuse will\n> > hopefully generate a pack closer to 400 MB in size. But I know\n> > Jon would like to get that pack even smaller. :)\n> \n> One thing to consider in your code (if you didn't implement that \n> already) is to _not_ attempt any delta on any object whose size is \n> smaller than 50 bytes, and then limit the maximum delta size to \n> object_size/2 - 20 (use that for the last argument to diff-delta() and \n> store the undeltified object when diff-delta returns NULL). This way \n> you'll avoid creating delta objects that are most likely to end up being \n> _larger_ than the undeltified object.\n\nSo I added Nico's suggestions to fast-import and ran it on a small\nsubset of the Mozilla repository (3424 blobs):\n\n naive always delta: 6652 KiB\n Nico's suggestion: 6842 KiB\n\nSo Nico's suggestion of limiting delta size to (orig_len/2)-20 or\nnot using deltas on blobs < 50 bytes actually added 190 KB to the\noutput pack. Since this sample is probably fairly representative\nof the rest of the repository's blobs I'm thinking we may see a 2.8%\nincrease in size over the current 930 MB blob pack. That's another\n26 MB in our intermediate pack. I don't think this suggestion is\nreally worth including in fast-import right now...\n\n-- \nShawn.\n"},{"id":"26052","messageId":"Pine.LNX.4.64.0608281236130.3683@localhost.localdomain","threadId":"5419","inReplyTo":"9e4733910608280844q41ea1a61r33c3eadc3e942604@mail.gmail.com","subject":"Re: Packfile can't be mapped","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-28T16:43:26Z","receivedAt":"2006-08-28T16:43:26Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 28 Aug 2006, Jon Smirl wrote:\n\n> On 8/28/06, Nicolas Pitre wrote:\n> > > Of course the major problem with pack-local, stream global\n> > > dictionaries is it voids the ability to reuse that zlib'd content\n> > > from that pack in another pack without wholesale copying the\n> > > dictionary as well. This is an issue for servers which want to\n> > > copy out the pack entry without recompressing it but also want the\n> > > storage savings from the global dictionaries.\n> >\n> > Why would copying the dictionary as well be a problem? How large might\n> > it be? Can it be stored deflated itself?\n> \n> The dictionaries are only 4KB. But they have to match up with the\n> objects compressed using them. If you bring an object straight down\n> out of a dictionary based pack and make it standalone you won't be\n> able to read it. You need the dictionary to decode it. What if the\n> local and remote packs have been packed using two different\n> dictionaries? You can't directly move objects between them.\n\nI guess we'll be able to reuse the same dictionary when objects are all \nfrom the same pack.\n\nIf not then they could be recompressed which is costly but never as much \nas delta matching initially was when it was always done.\n\nAnyway let's look at the size saving first. The implied costs could \nthen be evaluated and weighted accordingly.\n\n\nNicolas\n"},{"id":"26053","messageId":"20060828164855.GB22451@spearce.org","threadId":"5419","inReplyTo":"Pine.LNX.4.64.0608281026110.3683@localhost.localdomain","subject":"Re: Packfile can't be mapped","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-28T16:48:55Z","receivedAt":"2006-08-28T16:48:55Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> On Mon, 28 Aug 2006, Shawn Pearce wrote:\n> > Of course the major problem with pack-local, stream global\n> > dictionaries is it voids the ability to reuse that zlib'd content\n> > from that pack in another pack without wholesale copying the\n> > dictionary as well. This is an issue for servers which want to\n> > copy out the pack entry without recompressing it but also want the\n> > storage savings from the global dictionaries.\n> \n> Why would copying the dictionary as well be a problem? How large might \n> it be? Can it be stored deflated itself?\n\nLargest size is like 200 bytes smaller than the window size. Times 3\nas we would want to store 3 dictionaries, though maybe only 2 if the\nblob dictionary proves to be worse than not having one at all for a\ngiven project. Since its just a binary buffer holding bytes which\nfrequently appear in our compressed objects its easily deflatable;\nespecially when you consider its primarily storing US-ASCII text.\n\nI was definately planning on the dictionary being deflated in the\npack.\n\nWe could alawys use the SHA1 of a dictionary to signal to the client\nwhat dictionary was in use. If the dictionary itself was treated\nlike any other SHA1 object then we might be able to transfer the\nserver's current dictionaries to the client along with everything\nelse in the same pack if the client doesn't have the necessary\ndictionary yet.\n\n-- \nShawn.\n"},{"id":"26054","messageId":"Pine.LNX.4.64.0608281244380.3683@localhost.localdomain","threadId":"5419","inReplyTo":"20060828164222.GA22451@spearce.org","subject":"Re: Packfile can't be mapped","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-28T17:19:31Z","receivedAt":"2006-08-28T17:19:31Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 28 Aug 2006, Shawn Pearce wrote:\n\n> Nicolas Pitre wrote:\n> > On Sun, 27 Aug 2006, Shawn Pearce wrote:\n> > \n> > > I'm going to try to get tree deltas written to the pack sometime this\n> > > week. That should compact this intermediate pack down to something\n> > > that git-pack-objects would be able to successfully mmap into a\n> > > 32 bit address space. A complete repack with no delta reuse will\n> > > hopefully generate a pack closer to 400 MB in size. But I know\n> > > Jon would like to get that pack even smaller. :)\n> > \n> > One thing to consider in your code (if you didn't implement that \n> > already) is to _not_ attempt any delta on any object whose size is \n> > smaller than 50 bytes, and then limit the maximum delta size to \n> > object_size/2 - 20 (use that for the last argument to diff-delta() and \n> > store the undeltified object when diff-delta returns NULL). This way \n> > you'll avoid creating delta objects that are most likely to end up being \n> > _larger_ than the undeltified object.\n> \n> So I added Nico's suggestions to fast-import and ran it on a small\n> subset of the Mozilla repository (3424 blobs):\n> \n> naive always delta: 6652 KiB\n> Nico's suggestion: 6842 KiB\n\nHmmm...\n\n> So Nico's suggestion of limiting delta size to (orig_len/2)-20 or\n> not using deltas on blobs < 50 bytes actually added 190 KB to the\n> output pack. Since this sample is probably fairly representative\n> of the rest of the repository's blobs I'm thinking we may see a 2.8%\n> increase in size over the current 930 MB blob pack. That's another\n> 26 MB in our intermediate pack. I don't think this suggestion is\n> really worth including in fast-import right now...\n\nThe above is based on the assumption that undeltified blobs usually \ndeflates to 50% the undeflated size or more, and that pure object data \ndeflates better than delta data. Then there is the 20 byte base object \nreference overhead for any deltas. The 20 bytes is a hard fact. The \n50% factor is a wild guess. What I forgot to consider in the above \nformula is the fact that delta data gets deflated as well so the /2 \ndivisor is probably a bit too much (you could try orig_len*2/3 - 20, or \norig-len - 20, and adjust the initial treshold so the limit value \ndoesn't go negative).\n\nIf you are IO bound (I recall Jon mentioning something to that effect) \nthen you could probably use some CPU cycles to always deflate the \nobject, deflate the resulting delta, and pick the smallest between the \ntwo (don't forget the additional 20 bytes in the delta case). Maybe the \nincreased CPU usage won't justify this solution though.\n\n\nNicolas\n"},{"id":"26074","messageId":"20060829045239.GB24479@spearce.org","threadId":"5419","inReplyTo":"20060828024720.GD24204@spearce.org","subject":"Re: Packfile can't be mapped","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-29T04:52:39Z","receivedAt":"2006-08-29T04:52:39Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Shawn Pearce wrote:\n> I'm going to try to get tree deltas written to the pack sometime this\n> week.\n\nI was able to implement and with Jon Smirl's help debug the tree\ndelta code in fast-import.\n \nEarlier this evening Jon sent me the following:\n> git-fast-import statistics:\n> ---------------------------------------------------------------------\n> Alloc'd objects: 1980000 ( 0 overflow )\n> Total objects: 1967527 ( 41856 duplicates )\n> blobs : 633842 ( 0 duplicates 576219 deltas)\n> trees : 1131208 ( 41856 duplicates 1019741 deltas)\n> commits: 200921 ( 0 duplicates 0 deltas)\n> tags : 1556 ( 0 duplicates 0 deltas)\n> Total branches: 1600 ( 2228 loads )\n> marks: 1048576 ( 200921 unique )\n> atoms: 56803\n> Memory total: 75213 KiB\n> pools: 13338 KiB\n> objects: 61875 KiB\n> Pack remaps: 658\n> Pack size: 895983 KiB\n> Index size: 46114 KiB\n> ---------------------------------------------------------------------\n\nCompared to our last attempt:\n> > Pack size: 1713200 KiB\n> > Index size: 46114 KiB\n\nThis tree delta version came out pretty good. The pack with tree\ndeltas is 874 MiB. Quite a reduction in size. fast-import takes\nabout 20 minutes to convert its 20 GiB input file into this 874 MiB\npack. Producing the 20 GiB input file from the 3 GiB CVS ,v\nfiles takes about 4 hours with Jon's modified cvs2svn.\n\nJon has started a `git-repack -a -f` with aggressive depth and\nwindow sizes. He estimated it may need another 2.5 hours to process.\nHopefully I'll hear more details tomorrow.\n\n-- \nShawn.\n"},{"id":"26075","messageId":"20060829053312.GB24594@spearce.org","threadId":"5419","inReplyTo":"20060829045239.GB24479@spearce.org","subject":"Re: Packfile can't be mapped","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-29T05:33:12Z","receivedAt":"2006-08-29T05:33:12Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Shawn Pearce wrote:\n> This tree delta version came out pretty good. The pack with tree\n> deltas is 874 MiB. Quite a reduction in size. fast-import takes\n> about 20 minutes to convert its 20 GiB input file into this 874 MiB\n> pack. Producing the 20 GiB input file from the 3 GiB CVS ,v\n> files takes about 4 hours with Jon's modified cvs2svn.\n> \n> Jon has started a `git-repack -a -f` with aggressive depth and\n> window sizes. He estimated it may need another 2.5 hours to process.\n> Hopefully I'll hear more details tomorrow.\n\nI just heard from Jon:\n> git-repack -a -f --window=50 --depth=5000\n> 100% CPU for 60 minutes\n> 1.2GB resident memory\n> Final pack size is 451,203,363 bytes.\n\nSo with very agressive delta depth and window sizes git-repack took\na while to run but came very close to the best packed size from\nprevious Mozilla CVS import attempts. I think we'd still like to\nmake the final historical pack smaller than that.\n\n-- \nShawn.\n"}]}