{"thread":{"id":"5501","subject":"A look at some alternative PACK file encodings","startedAt":"2006-09-06T21:47:32Z","lastAt":"2006-09-07T18:50:37Z","messageCount":24,"participants":["A Large Angry SCM","Jon Smirl","Linus Torvalds","David Lang","Nicolas Pitre","Junio C Hamano","Shawn Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"26449","messageId":"44FF41F4.1090906@gmail.com","threadId":"5501","inReplyTo":null,"subject":"A look at some alternative PACK file encodings","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2006-09-06T21:47:32Z","receivedAt":"2006-09-06T21:47:32Z","isPatch":false,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Since I'm currently between jobs and extra time on my hands until I find\na new one, I've been experimenting with some alternative encodings for\nPACK file contents.\n\nThe tables below show packing statistics for a number of actual pack\nfiles using difference pack file encodings. All of the encodings use\nobject names to find the base object of a DELTA object.\n\nEncodings:\n\tPack_2 - Pack version 2 (Git current), 32 bit\n\tPack_3 - Pack version 3 (Git future), 32 bit\n\tGitzilla_1 - Experimental >32 bit, described below\n\tGitzilla_2 - Experimental >32 bit, described below\n\nGitzilla_1: Per object header consisting of 2 fields: the Git object\ntype of the object with a flag indicating if it's delta encoded, big\nendian base 128 encoding of the object length. If the object is not\ndelta encoded, the object header is followed by the deflated object\ncontents. If the object is delta encoded, the object header is followed\nby the 20 byte ID of the base object, and the deflated edit list (see\nbelow). This encoding allows for the possibility of using some of the\nbits in the object type field to select one of up to 15 dictionaries.\n\nGitzilla_2: Per object header consisting of a single field combining the\nobject type and length; similar to that used in current packs but big\nendian encoded. The type could be encoded either as object type with\ndelta flag (no room for additional object types), or the same as what\nversion 2 packs (room for additional object types but need to walk the\ndelta chain to determine type of delta encode objects). If the object is\ndelta encoded, the object header is followed by the 20 byte ID of the\nbase object, and the deflated edit list (see below).\n\nNotice that the length encoded in the per object header for delta encode\nobjects is that of the decoded object, not the length of the inflated\nedit list.\n\nThe edit lists used in the Gitzilla encodings consist of a sequence of\none or more hunks. Each hunk specifies either a part of the base object\nto copy to the current position of the result object, or a length of\n(immediate) data to copy to the current position of the result object.\n\nEach hunk type is encode as 2 fields: the first is big endian base 128\nencoded length of data to copy with bit 6 of the first byte indicating\nwhere to copy from. The second field is the big endian base 128 encoded\noffset in the base object of the copy source, or the (immediate) data to\ncopy.\n\n\n\nObservations:\n\nMost of the savings are from not including the base and result object\nlengths in the deflated edit lists.\n\nOther minor savings from joining adjacent edit hunks of the same type,\nwhere possible.\n\nThe endian of the base 128 encoding is big because it requires less work\nto _decode_ than little.\n\nTREE objects do not delta or deflate well.\n\nDictionaries will need to be tailored to different object types, and\npossibly to other object subsets.\n\nThe ability to get the type and length of a delta'd object without\nneeding to walk the delta chain is a good thing.\n\nThe use of _relative_ offsets to specify base objects would save a lot\nof space.\n\n\n\nThe data:\n\nAll of the PACK files except bd5109... were rsync'd from the Git project\non kernel.org, at some point. PACK bd5109... is a mash-up of Linus'\nkernel and sparse projects, Thomas' kernel history, the stable 2.6.x.y\nkernel projects, Git, and gitk; all from kernel.org.\n\nThe columns are:\n encoding name\n pack file size\n size of pack file non-object overhead\n sum of packed object sizes\n byte difference in sum of packed object sizes and that of\n version 2 packs\n average byte difference per object\n average byte difference per DELTA'd object\n\n\n\npack-1abe018fa97f8a257a4f3a072000abf99eaa925e.pack\n\nBLOB : 237\nCOMMIT: 504\nDELTA : 1108\nTAG : 6\nTREE : 64\n====== ==========\nTotal : 1919\n\nGitzilla_1: 1202917 32 1202885 -6797 -3.5419 -6.1345\nGitzilla_2: 1202011 32 1201979 -7703 -4.0141 -6.9522\nPack_2 : 1209714 32 1209682 0 0.0000 0.0000\nPack_3 : 1209686 32 1209654 -28 -0.0146 -0.0253\n\n\npack-3a080dc749b452cc847d19d91981ddfcff629750.pack\n\nBLOB : 1020\nCOMMIT: 5300\nDELTA : 15013\nTAG : 80\nTREE : 564\n====== ==========\nTotal : 21977\n\nGitzilla_1: 6748060 32 6748028 -95768 -4.3576 -6.3790\nGitzilla_2: 6737992 32 6737960 -105836 -4.8158 -7.0496\nPack_2 : 6843828 32 6843796 0 0.0000 0.0000\nPack_3 : 6843747 32 6843715 -81 -0.0037 -0.0054\n\n\npack-3e6247e4edf3c006a037041eef28bbca8051b006.pack\n\nBLOB : 1062\nCOMMIT: 5545\nDELTA : 15565\nTAG : 81\nTREE : 703\n====== ==========\nTotal : 22956\n\nGitzilla_1: 6724940 32 6724908 -97643 -4.2535 -6.2732\nGitzilla_2: 6714303 32 6714271 -108280 -4.7168 -6.9566\nPack_2 : 6822583 32 6822551 0 0.0000 0.0000\nPack_3 : 6822458 32 6822426 -125 -0.0054 -0.0080\n\n\npack-6bdf691abdae3590f6a807d15ebe8ed523ef1e12.pack\n\nBLOB : 33\nCOMMIT: 36\nDELTA : 64\nTAG : 0\nTREE : 4\n====== ==========\nTotal : 137\n\nGitzilla_1: 136041 32 136009 -273 -1.9927 -4.2656\nGitzilla_2: 135991 32 135959 -323 -2.3577 -5.0469\nPack_2 : 136314 32 136282 0 0.0000 0.0000\nPack_3 : 136314 32 136282 0 0.0000 0.0000\n\n\npack-740c99c0be6734adbd130737dec2608dc4682761.pack\n\nBLOB : 181\nCOMMIT: 173\nDELTA : 383\nTAG : 5\nTREE : 24\n====== ==========\nTotal : 766\n\nGitzilla_1: 586580 32 586548 -1799 -2.3486 -4.6971\nGitzilla_2: 586264 32 586232 -2115 -2.7611 -5.5222\nPack_2 : 588379 32 588347 0 0.0000 0.0000\nPack_3 : 588370 32 588338 -9 -0.0117 -0.0235\n\n\npack-793a9e93286d6c656941977d2e5b49e28566edcd.pack\n\nBLOB : 1158\nCOMMIT: 6512\nDELTA : 18715\nTAG : 90\nTREE : 820\n====== ==========\nTotal : 27295\n\nGitzilla_1: 7957552 32 7957520 -120209 -4.4041 -6.4231\nGitzilla_2: 7944784 32 7944752 -132977 -4.8718 -7.1054\nPack_2 : 8077761 32 8077729 0 0.0000 0.0000\nPack_3 : 8077566 32 8077534 -195 -0.0071 -0.0104\n\n\npack-92b2a535e63e4a97eba2a13f60c3da922372f03a.pack\n\nBLOB : 1149\nCOMMIT: 5969\nDELTA : 16930\nTAG : 84\nTREE : 750\n====== ==========\nTotal : 24882\n\nGitzilla_1: 7243503 32 7243471 -108475 -4.3596 -6.4073\nGitzilla_2: 7231901 32 7231869 -120077 -4.8259 -7.0926\nPack_2 : 7351978 32 7351946 0 0.0000 0.0000\nPack_3 : 7351841 32 7351809 -137 -0.0055 -0.0081\n\n\npack-9f1f94e6f50261b5d99c04349bfa3d315cfb4118.pack\n\nBLOB : 1190\nCOMMIT: 6244\nDELTA : 17881\nTAG : 87\nTREE : 810\n====== ==========\nTotal : 26212\n\nGitzilla_1: 7920476 32 7920444 -115214 -4.3955 -6.4434\nGitzilla_2: 7908256 32 7908224 -127434 -4.8617 -7.1268\nPack_2 : 8035690 32 8035658 0 0.0000 0.0000\nPack_3 : 8035529 32 8035497 -161 -0.0061 -0.0090\n\n\npack-a875e0c11c739866b000dc9b34d1b0daead84a00.pack\n\nBLOB : 20\nCOMMIT: 9\nDELTA : 15\nTAG : 1\nTREE : 3\n====== ==========\nTotal : 48\n\nGitzilla_1: 71748 32 71716 -54 -1.1250 -3.6000\nGitzilla_2: 71728 32 71696 -74 -1.5417 -4.9333\nPack_2 : 71802 32 71770 0 0.0000 0.0000\nPack_3 : 71802 32 71770 0 0.0000 0.0000\n\n\npack-abbe9cdea12803663015a7e23b7ae61c64e56499.pack\n\nBLOB : 259\nCOMMIT: 342\nDELTA : 705\nTAG : 13\nTREE : 47\n====== ==========\nTotal : 1366\n\nGitzilla_1: 1086337 32 1086305 -3878 -2.8389 -5.5007\nGitzilla_2: 1085773 32 1085741 -4442 -3.2518 -6.3007\nPack_2 : 1090215 32 1090183 0 0.0000 0.0000\nPack_3 : 1090215 32 1090183 0 0.0000 0.0000\n\n\npack-bd5109ab74dd67d5b0a42f26688a4fa0a579e9fa.pack\n\nBLOB : 29212\nCOMMIT: 103241\nDELTA : 702986\nTAG : 182\nTREE : 37102\n====== ==========\nTotal : 872723\n\nGitzilla_1: 282786611 32 282786579 -3647429 -4.1794 -5.1885\nGitzilla_2: 282143551 32 282143519 -4290489 -4.9162 -6.1032\nPack_2 : 286434040 32 286434008 0 0.0000 0.0000\nPack_3 : 286404302 32 286404270 -29738 -0.0341 -0.0423\n\n\npack-d18e6cccf9e472ba05e108254c827cc7ac0fe2a9.pack\n\nBLOB : 1564\nCOMMIT: 3118\nDELTA : 8288\nTAG : 51\nTREE : 365\n====== ==========\nTotal : 13386\n\nGitzilla_1: 5638236 32 5638204 -44212 -3.3029 -5.3345\nGitzilla_2: 5632126 32 5632094 -50322 -3.7593 -6.0717\nPack_2 : 5682448 32 5682416 0 0.0000 0.0000\nPack_3 : 5682423 32 5682391 -25 -0.0019 -0.0030\n\n\npack-d25faec39a55935d787ae66e4f4a69d3add16417.pack\n\nBLOB : 1180\nCOMMIT: 6090\nDELTA : 17458\nTAG : 85\nTREE : 761\n====== ==========\nTotal : 25574\n\nGitzilla_1: 7646842 32 7646810 -112816 -4.4114 -6.4621\nGitzilla_2: 7634964 32 7634932 -124694 -4.8758 -7.1425\nPack_2 : 7759658 32 7759626 0 0.0000 0.0000\nPack_3 : 7759521 32 7759489 -137 -0.0054 -0.0078\n\n\npack-d453bb50fef8757a0d7f9fcc88429e9ce6f74077.pack\n\nBLOB : 28\nCOMMIT: 35\nDELTA : 46\nTAG : 2\nTREE : 6\n====== ==========\nTotal : 117\n\nGitzilla_1: 177544 32 177512 -266 -2.2735 -5.7826\nGitzilla_2: 177478 32 177446 -332 -2.8376 -7.2174\nPack_2 : 177810 32 177778 0 0.0000 0.0000\nPack_3 : 177806 32 177774 -4 -0.0342 -0.0870\n\n\npack-d83305b8608cb685ecd025fb141bf9d1588ae9c5.pack\n\nBLOB : 91\nCOMMIT: 108\nDELTA : 202\nTAG : 2\nTREE : 26\n====== ==========\nTotal : 429\n\nGitzilla_1: 473503 32 473471 -1112 -2.5921 -5.5050\nGitzilla_2: 473269 32 473237 -1346 -3.1375 -6.6634\nPack_2 : 474615 32 474583 0 0.0000 0.0000\nPack_3 : 474603 32 474571 -12 -0.0280 -0.0594\n\n\npack-ee22eefd6bad2b54358d52ad6221ecabdc79d6f5.pack\n\nBLOB : 175\nCOMMIT: 210\nDELTA : 541\nTAG : 2\nTREE : 38\n====== ==========\nTotal : 966\n\nGitzilla_1: 662650 32 662618 -3230 -3.3437 -5.9704\nGitzilla_2: 662150 32 662118 -3730 -3.8613 -6.8946\nPack_2 : 665880 32 665848 0 0.0000 0.0000\nPack_3 : 665865 32 665833 -15 -0.0155 -0.0277\n\n\npack-f0c530478b9dd6e96a69482066ec66eb5f6edbbf.pack\n\nBLOB : 1154\nCOMMIT: 5797\nDELTA : 16300\nTAG : 83\nTREE : 739\n====== ==========\nTotal : 24073\n\nGitzilla_1: 7212953 32 7212921 -102252 -4.2476 -6.2731\nGitzilla_2: 7201730 32 7201698 -113475 -4.7138 -6.9617\nPack_2 : 7315205 32 7315173 0 0.0000 0.0000\nPack_3 : 7315059 32 7315027 -146 -0.0061 -0.0090\n"},{"id":"26453","messageId":"9e4733910609061623k73086dbey4a600ecf2852c024@mail.gmail.com","threadId":"5501","inReplyTo":"44FF41F4.1090906@gmail.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-06T23:23:16Z","receivedAt":"2006-09-06T23:23:16Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/6/06, A Large Angry SCM wrote:\n> TREE objects do not delta or deflate well.\n\nI can understand why they don't deflate, the path names are pretty\nmuch unique and the sha1s are incompressible. By why don't they delta\nwell? Does sorting them by size mess up the delta process?\n\nShawn is doing some prototype work on true dictionary based\ncompression. I don't know how far along he is but it has potential for\ntaking 30% off the Mozilla pack.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26454","messageId":"44FF5C27.2040300@gmail.com","threadId":"5501","inReplyTo":"9e4733910609061623k73086dbey4a600ecf2852c024@mail.gmail.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2006-09-06T23:39:19Z","receivedAt":"2006-09-06T23:39:19Z","isPatch":false,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Jon Smirl wrote:\n> On 9/6/06, A Large Angry SCM wrote:\n>> TREE objects do not delta or deflate well.\n> \n> I can understand why they don't deflate, the path names are pretty\n> much unique and the sha1s are incompressible. By why don't they delta\n> well? Does sorting them by size mess up the delta process?\n\nMy guess would be the TREEs would only delta well against other TREE\nversions for the same path.\n\n> Shawn is doing some prototype work on true dictionary based\n> compression. I don't know how far along he is but it has potential for\n> taking 30% off the Mozilla pack.\n\nJust looking at the structures in non-BLOBS, I see a lot of potential\nfor the use of a set dictionaries when deflating TREEs and another set\nof dictionaries when deflating COMMITs and TAGs. The low hanging fruit\nis to create dictionaries of the most referenced IDs across all TREE or\nCOMMIT/TAG objects.\n"},{"id":"26456","messageId":"Pine.LNX.4.64.0609061651500.27779@g5.osdl.org","threadId":"5501","inReplyTo":"44FF5C27.2040300@gmail.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-06T23:56:05Z","receivedAt":"2006-09-06T23:56:05Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 6 Sep 2006, A Large Angry SCM wrote:\n\n> Jon Smirl wrote:\n> > On 9/6/06, A Large Angry SCM wrote:\n> >> TREE objects do not delta or deflate well.\n> > \n> > I can understand why they don't deflate, the path names are pretty\n> > much unique and the sha1s are incompressible. By why don't they delta\n> > well? Does sorting them by size mess up the delta process?\n> \n> My guess would be the TREEs would only delta well against other TREE\n> versions for the same path.\n\nThat's what you'd normally have in a real project, though. I wonder if \nyour \"pack mashup\" lost the normal behaviour: we very much sort trees \ntogether normally, thanks to the \"sort-by-filename, then by size\" \nbehaviour that git-pack-objects should have (for trees, the size normally \nshouldn't change, so the sorting should basically boil down to \"sort the \nsame directory together, keeping the ordering it had from git-rev-list\").\n\nBtw, that \"keeping the ordering it had\" part I'm not convinced we actually \nenforce. That would depend on the sort algorithm used by \"qsort()\", I \nthink. So there might be room for improvement there in order to keep \nthings in recency order.\n\n> Just looking at the structures in non-BLOBS, I see a lot of potential\n> for the use of a set dictionaries when deflating TREEs and another set\n> of dictionaries when deflating COMMITs and TAGs. The low hanging fruit\n> is to create dictionaries of the most referenced IDs across all TREE or\n> COMMIT/TAG objects.\n\nIs there any way to get zlib to just generate a suggested dictionary from \na given set of input?\n\n\t\tLinus\n"},{"id":"26457","messageId":"9e4733910609061704s429c449etcf0475841556c26b@mail.gmail.com","threadId":"5501","inReplyTo":"44FF5C27.2040300@gmail.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-07T00:04:02Z","receivedAt":"2006-09-07T00:04:02Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/6/06, A Large Angry SCM wrote:\n> Jon Smirl wrote:\n> > On 9/6/06, A Large Angry SCM wrote:\n> >> TREE objects do not delta or deflate well.\n> >\n> > I can understand why they don't deflate, the path names are pretty\n> > much unique and the sha1s are incompressible. By why don't they delta\n> > well? Does sorting them by size mess up the delta process?\n>\n> My guess would be the TREEs would only delta well against other TREE\n> versions for the same path.\n\nI would have thought that the TREE delta code would have already taken\nthis into account. Is there enough info around to match up all of the\nTREEs for a specific path into a delta chain?\n\nThe repack code could build a model of the tree as it is repacking,\nthat is what fast-import does. If you have a model of the tree then\nwhen you change a TREE node you track the last sha1 that corresponded\nto that directory path. Now you know what to diff to.\n\n> > Shawn is doing some prototype work on true dictionary based\n> > compression. I don't know how far along he is but it has potential for\n> > taking 30% off the Mozilla pack.\n>\n> Just looking at the structures in non-BLOBS, I see a lot of potential\n> for the use of a set dictionaries when deflating TREEs and another set\n> of dictionaries when deflating COMMITs and TAGs. The low hanging fruit\n> is to create dictionaries of the most referenced IDs across all TREE or\n> COMMIT/TAG objects.\n\nDoing this will get 4-7% according to our small tests, to get more you\nneed a different type of compression algorithm. For true dictionary\nbased compression you parse all of the input documents into words. The\nwords are put into a single giant huffman table. Then the huffman\ncodes for the words are concatenated together to form the compressed\ndocument. This is one of the highest possible compression methods\nsince it takes into account you are compressing something that is\nhuman readable. gzip is sort of like this but the dictionary is\nlimited to 32KB.\n\nSearch engines use true dictionary compression since it is easy to add\non search indices to the compressed data. For a search index you make\na bit vector that corresponds to each word in the dictionary and then\nset a bit if that document number contains the word. The vectors and\ndictionary are stored compressed. There are algorithms for doing\nand/or on the compressed vectors. The and/or stage lets you identify\nlikely hits, you retrieve those and then do an exact match on the\nsearch terms to be sure.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26459","messageId":"Pine.LNX.4.63.0609061705160.4398@qynat.qvtvafvgr.pbz","threadId":"5501","inReplyTo":"9e4733910609061710x4fb48d86o58b9c5ec8e527135@mail.gmail.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"David Lang","fromEmail":"dlang@digitalinsight.com","sentAt":"2006-09-07T00:06:54Z","receivedAt":"2006-09-07T00:06:54Z","isPatch":false,"sender":{"key":"dlang@digitalinsight.com","avatar":null},"body":"On Wed, 6 Sep 2006, Jon Smirl wrote:\n\n> On 9/6/06, Linus Torvalds wrote:\n>> Is there any way to get zlib to just generate a suggested dictionary from\n>> a given set of input?\n>\n> No, I asked the author. Apparently it is a hard problem, there have\n> been research papers written about it.\n>\n> Shawn has a Perl script that makes a guess at a dictionary. That\n> scripts gets 4-7% improvement. The number one thing that ended up in\n> the Mozilla dictionary was the five different license versions that\n> had each been copied into 50,000 files over time.\n\nfor the mozilla project it may make sense to feed all these license files from \nall over as one string to git, as an exception to your normal process of going \nfile by file. if you can do this then the delta functionality should reduce \nthese files to practicaly nothing.\n\nDavid Lang\n"},{"id":"26458","messageId":"9e4733910609061710x4fb48d86o58b9c5ec8e527135@mail.gmail.com","threadId":"5501","inReplyTo":"Pine.LNX.4.64.0609061651500.27779@g5.osdl.org","subject":"Re: A look at some alternative PACK file encodings","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-07T00:10:39Z","receivedAt":"2006-09-07T00:10:39Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/6/06, Linus Torvalds wrote:\n> Is there any way to get zlib to just generate a suggested dictionary from\n> a given set of input?\n\nNo, I asked the author. Apparently it is a hard problem, there have\nbeen research papers written about it.\n\nShawn has a Perl script that makes a guess at a dictionary. That\nscripts gets 4-7% improvement. The number one thing that ended up in\nthe Mozilla dictionary was the five different license versions that\nhad each been copied into 50,000 files over time.\n\nI think what happens in practice is that when people get to the point\nof trying to optimize zlib dictionaries they switch compression\nmethods.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26460","messageId":"44FF6586.8080206@gmail.com","threadId":"5501","inReplyTo":"Pine.LNX.4.64.0609061651500.27779@g5.osdl.org","subject":"Re: A look at some alternative PACK file encodings","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2006-09-07T00:19:18Z","receivedAt":"2006-09-07T00:19:18Z","isPatch":false,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Linus Torvalds wrote:\n> \n> On Wed, 6 Sep 2006, A Large Angry SCM wrote:\n> \n>> Jon Smirl wrote:\n>>> On 9/6/06, A Large Angry SCM wrote:\n>>>> TREE objects do not delta or deflate well.\n>>> I can understand why they don't deflate, the path names are pretty\n>>> much unique and the sha1s are incompressible. By why don't they delta\n>>> well? Does sorting them by size mess up the delta process?\n>> My guess would be the TREEs would only delta well against other TREE\n>> versions for the same path.\n> \n> That's what you'd normally have in a real project, though. I wonder if \n> your \"pack mashup\" lost the normal behaviour: we very much sort trees \n> together normally, thanks to the \"sort-by-filename, then by size\" \n> behaviour that git-pack-objects should have (for trees, the size normally \n> shouldn't change, so the sorting should basically boil down to \"sort the \n> same directory together, keeping the ordering it had from git-rev-list\").\n\nThe mashup is just all the projects in a single repository with a bushy\nrefs tree so I can view the updates in a single gitk window.\n\nThe sorting by name, then by path may be breaking the object version\nrelationship for wide graphs.\n\n> Btw, that \"keeping the ordering it had\" part I'm not convinced we actually \n> enforce. That would depend on the sort algorithm used by \"qsort()\", I \n> think. So there might be room for improvement there in order to keep \n> things in recency order.\n\nqsort() is not stable.\n\n>> Just looking at the structures in non-BLOBS, I see a lot of potential\n>> for the use of a set dictionaries when deflating TREEs and another set\n>> of dictionaries when deflating COMMITs and TAGs. The low hanging fruit\n>> is to create dictionaries of the most referenced IDs across all TREE or\n>> COMMIT/TAG objects.\n>\n> Is there any way to get zlib to just generate a suggested dictionary from \n> a given set of input?\n\nThe docs suggest \"no\".\n"},{"id":"26462","messageId":"Pine.LNX.4.64.0609062030510.18635@xanadu.home","threadId":"5501","inReplyTo":"Pine.LNX.4.64.0609061651500.27779@g5.osdl.org","subject":"Re: A look at some alternative PACK file encodings","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-09-07T00:37:30Z","receivedAt":"2006-09-07T00:37:30Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 6 Sep 2006, Linus Torvalds wrote:\n"},{"id":"26463","messageId":"Pine.LNX.4.64.0609062037560.18635@xanadu.home","threadId":"5501","inReplyTo":"9e4733910609061623k73086dbey4a600ecf2852c024@mail.gmail.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-09-07T00:40:40Z","receivedAt":"2006-09-07T00:40:40Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 6 Sep 2006, Jon Smirl wrote:\n\n> Shawn is doing some prototype work on true dictionary based\n> compression. I don't know how far along he is but it has potential for\n> taking 30% off the Mozilla pack.\n\nBTW I'm half-way done with support for deltas which base object is \nreferenced with an offset in the pack instead of a hash. It is quite \nmessy though since it touches pretty core code all over the place when \nit comes to fetching objects out of a pack.\n\n\nNicolas\n"},{"id":"26465","messageId":"Pine.LNX.4.64.0609061737040.27779@g5.osdl.org","threadId":"5501","inReplyTo":"44FF6586.8080206@gmail.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-07T00:45:01Z","receivedAt":"2006-09-07T00:45:01Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 6 Sep 2006, A Large Angry SCM wrote:\n> \n> > Btw, that \"keeping the ordering it had\" part I'm not convinced we actually \n> > enforce. That would depend on the sort algorithm used by \"qsort()\", I \n> > think. So there might be room for improvement there in order to keep \n> > things in recency order.\n> \n> qsort() is not stable.\n\nWell, quicksort isn't, but a lot of systems don't actually use quicksort \nto implement qsort() - despite the name.\n\nI think, for example, that glibc uses a merge-sort when there are lots of \nentries (to avoid any potential bad behaviour with quicksort), and that \nshould be stable. But I didn't actually check..\n\nIn fact, I didn't even think of this issue originally, but it might \nactually be worthwhile doing our own sort, exactly because we'll otherwise \nhave different systems generating different pack-files due to issues like \nthis.\n\nSo even if we don't actually _care_ whether the sorting is stable or not, \nwe might well care that we always get the same results, regardless of what \nC library we have.\n\n> > Is there any way to get zlib to just generate a suggested dictionary from \n> > a given set of input?\n> \n> The docs suggest \"no\".\n\nOh, well.\n\n\t\t\tLinus\n"},{"id":"26467","messageId":"9e4733910609061759m2aae9e31ja146e309dc449628@mail.gmail.com","threadId":"5501","inReplyTo":"Pine.LNX.4.64.0609062037560.18635@xanadu.home","subject":"Re: A look at some alternative PACK file encodings","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-07T00:59:29Z","receivedAt":"2006-09-07T00:59:29Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/6/06, Nicolas Pitre wrote:\n> On Wed, 6 Sep 2006, Jon Smirl wrote:\n>\n> > Shawn is doing some prototype work on true dictionary based\n> > compression. I don't know how far along he is but it has potential for\n> > taking 30% off the Mozilla pack.\n>\n> BTW I'm half-way done with support for deltas which base object is\n> referenced with an offset in the pack instead of a hash. It is quite\n> messy though since it touches pretty core code all over the place when\n> it comes to fetching objects out of a pack.\n\nWould it help to change all of the references in the pack from sha1 to\nencoded relative offsets? Then collect all of the object fetch code\ninto a single subroutine which would change it algorithm depending on\nwhich type of pack it is operating on. Now the pack wouldn't mix\nreference types, they would all be encoded relative or sha1.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26468","messageId":"7v1wqo5vlz.fsf@assigned-by-dhcp.cox.net","threadId":"5501","inReplyTo":"Pine.LNX.4.64.0609062037560.18635@xanadu.home","subject":"Re: A look at some alternative PACK file encodings","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-07T01:11:20Z","receivedAt":"2006-09-07T01:11:20Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> On Wed, 6 Sep 2006, Jon Smirl wrote:\n>\n>> Shawn is doing some prototype work on true dictionary based\n>> compression. I don't know how far along he is but it has potential for\n>> taking 30% off the Mozilla pack.\n>\n> BTW I'm half-way done with support for deltas which base object is \n> referenced with an offset in the pack instead of a hash. It is quite \n> messy though since it touches pretty core code all over the place when \n> it comes to fetching objects out of a pack.\n\nI wonder how you made unpack-objects to work with it. Do you\nstore an extra bit in the packed stream to say \"this object will\nbe used as a delta base for later objects so remember its offset\nand resulting SHA1\", or do you just remember every entry as you\nunpack?\n"},{"id":"26470","messageId":"Pine.LNX.4.64.0609062221490.18635@xanadu.home","threadId":"5501","inReplyTo":"9e4733910609061759m2aae9e31ja146e309dc449628@mail.gmail.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-09-07T02:30:59Z","receivedAt":"2006-09-07T02:30:59Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 6 Sep 2006, Jon Smirl wrote:\n\n> On 9/6/06, Nicolas Pitre wrote:\n> > On Wed, 6 Sep 2006, Jon Smirl wrote:\n> >\n> > > Shawn is doing some prototype work on true dictionary based\n> > > compression. I don't know how far along he is but it has potential for\n> > > taking 30% off the Mozilla pack.\n> >\n> > BTW I'm half-way done with support for deltas which base object is\n> > referenced with an offset in the pack instead of a hash. It is quite\n> > messy though since it touches pretty core code all over the place when\n> > it comes to fetching objects out of a pack.\n> \n> Would it help to change all of the references in the pack from sha1 to\n> encoded relative offsets? Then collect all of the object fetch code\n> into a single subroutine which would change it algorithm depending on\n> which type of pack it is operating on. Now the pack wouldn't mix\n> reference types, they would all be encoded relative or sha1.\n\nNo. The problem is more about sha1_file.c using a mix of sha1 refs \nand/or pack,offset tuples to reference deltas. I converted most of them \nto pack,offset tuples. This also has a mnice side effect of having less \nstack usage when recursing down a delta chain.\n\nWhen a delta with sha1 reference is encountered the code turns that \nreference into the appropriate offset with a binary search in the pack \nindex. When a delta with offset reference is encountered then no search \nin the index is needed.\n\nThis is not really complicated but only spread all over so that the \ndiffstat is a bit scary.\n\n\nNicolas\n"},{"id":"26471","messageId":"44FF84E2.5040201@gmail.com","threadId":"5501","inReplyTo":"9e4733910609061759m2aae9e31ja146e309dc449628@mail.gmail.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2006-09-07T02:33:06Z","receivedAt":"2006-09-07T02:33:06Z","isPatch":false,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Jon Smirl wrote:\n> On 9/6/06, Nicolas Pitre wrote:\n>> On Wed, 6 Sep 2006, Jon Smirl wrote:\n>>\n>> > Shawn is doing some prototype work on true dictionary based\n>> > compression. I don't know how far along he is but it has potential for\n>> > taking 30% off the Mozilla pack.\n>>\n>> BTW I'm half-way done with support for deltas which base object is\n>> referenced with an offset in the pack instead of a hash. It is quite\n>> messy though since it touches pretty core code all over the place when\n>> it comes to fetching objects out of a pack.\n> \n> Would it help to change all of the references in the pack from sha1 to\n> encoded relative offsets? Then collect all of the object fetch code\n> into a single subroutine which would change it algorithm depending on\n> which type of pack it is operating on. Now the pack wouldn't mix\n> reference types, they would all be encoded relative or sha1.\n> \n\nSupport for 'thin' packs would pretty much require mixing IDs and\n(relative) offsets in the same pack file.\n"},{"id":"26472","messageId":"Pine.LNX.4.64.0609062231070.18635@xanadu.home","threadId":"5501","inReplyTo":"7v1wqo5vlz.fsf@assigned-by-dhcp.cox.net","subject":"Re: A look at some alternative PACK file encodings","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-09-07T02:47:05Z","receivedAt":"2006-09-07T02:47:05Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 6 Sep 2006, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> > BTW I'm half-way done with support for deltas which base object is \n> > referenced with an offset in the pack instead of a hash. It is quite \n> > messy though since it touches pretty core code all over the place when \n> > it comes to fetching objects out of a pack.\n> \n> I wonder how you made unpack-objects to work with it. Do you\n> store an extra bit in the packed stream to say \"this object will\n> be used as a delta base for later objects so remember its offset\n> and resulting SHA1\", or do you just remember every entry as you\n> unpack?\n\nEvery entries. Much simpler that way.\n\nAnd the client must ask explicitly whether or not a fetched pack can \nhave base objects referenced by sha1 or offset. So if you're really \nreally tight on memory (like if you cannot afford the extra 50MB of RAM \nor so for the Mozilla repo for example) then this could be turned off.\n\nBut if we decide to not explode packs upon a fetch but keep the \ndownloaded pack as is (after validation) then index generation will come \nfor free.\n\n\nNicolas\n"},{"id":"26475","messageId":"20060907043300.GA31376@spearce.org","threadId":"5501","inReplyTo":"Pine.LNX.4.64.0609062037560.18635@xanadu.home","subject":"Re: A look at some alternative PACK file encodings","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-07T04:33:00Z","receivedAt":"2006-09-07T04:33:00Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> On Wed, 6 Sep 2006, Jon Smirl wrote:\n> \n> > Shawn is doing some prototype work on true dictionary based\n> > compression. I don't know how far along he is but it has potential for\n> > taking 30% off the Mozilla pack.\n> \n> BTW I'm half-way done with support for deltas which base object is \n> referenced with an offset in the pack instead of a hash. It is quite \n> messy though since it touches pretty core code all over the place when \n> it comes to fetching objects out of a pack.\n\nAnd I'm half-way done with the 64 bit mmap sliding window. You,\nJunio and I are all hacking on the same tiny bit of core code for\ndifferent reasons. :-)\n\nRight now I'm struggling with merging my 32 bit sliding window onto\nJunio's 64 bit index in pu. The merge is almost done, but so is\nmy dinner. So dinner first. I don't think I'm going to get the\nsliding window code out tonight.\n\n-- \nShawn.\n"},{"id":"26476","messageId":"20060907052155.GA31580@spearce.org","threadId":"5501","inReplyTo":"9e4733910609061623k73086dbey4a600ecf2852c024@mail.gmail.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-07T05:21:56Z","receivedAt":"2006-09-07T05:21:56Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jon Smirl wrote:\n> Shawn is doing some prototype work on true dictionary based\n> compression. I don't know how far along he is but it has potential for\n> taking 30% off the Mozilla pack.\n\nNot very far. I've put some work into it but got distracted by the\nsliding mmap window bit. So I don't have anything worth sharing yet.\nWhich is why I've been quiet on the subject. :-)\n\n-- \nShawn.\n"},{"id":"26477","messageId":"7vslj4455z.fsf@assigned-by-dhcp.cox.net","threadId":"5501","inReplyTo":"20060907043300.GA31376@spearce.org","subject":"Re: A look at some alternative PACK file encodings","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-07T05:27:52Z","receivedAt":"2006-09-07T05:27:52Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> And I'm half-way done with the 64 bit mmap sliding window. You,\n> Junio and I are all hacking on the same tiny bit of core code for\n> different reasons. :-)\n\nWhich makes me quite nervous, actually.\n"},{"id":"26481","messageId":"20060907053424.GB31580@spearce.org","threadId":"5501","inReplyTo":"44FF5C27.2040300@gmail.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-07T05:34:24Z","receivedAt":"2006-09-07T05:34:24Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"A Large Angry SCM wrote:\n> Just looking at the structures in non-BLOBS, I see a lot of potential\n> for the use of a set dictionaries when deflating TREEs and another set\n> of dictionaries when deflating COMMITs and TAGs. The low hanging fruit\n> is to create dictionaries of the most referenced IDs across all TREE or\n> COMMIT/TAG objects.\n\nThe most referenced IDs should be getting reused through deltas.\nThat is IDs which are highly referenced are probably referenced\nin the same tree over many versions of that tree. Since the data\nisn't changing it should be getting copied by a delta copy command\nrather than appearing as a literal.\n\nThe Mozilla pack appears to have the bulk of its storage taken up\nby blobs (both bases and deltas). I suspect this is because the\nbases compress to approx. 50% of their original size but share a\nlot of common tokens. Those common tokens are being repeated in\nevery private zlib dictionary. The same thing happens in a delta,\nexcept here we are probably copying a lot from the base so the\naverage size is greatly reduced but we are still repeating tokens\nin the zlib dictionary for anything that is a literal in the delta\n(as it didn't appear in the base).\n\nA large dictionary containing all tokens for the project should\ngreatly reduce the size of each blob, base and delta alike. It also\nlends itself to creating an efficient full text index.\n\n-- \nShawn.\n"},{"id":"26478","messageId":"44FFB076.4020408@gmail.com","threadId":"5501","inReplyTo":"9e4733910609061617m6783d6c4xaca2f9575e12d455@mail.gmail.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2006-09-07T05:39:02Z","receivedAt":"2006-09-07T05:39:02Z","isPatch":false,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Jon Smirl wrote:\n> If you need more data to play with you can download the Mozilla pack\n> file from here.\n\nResults are about the same as for the other pack files.\n\n\npack-a80bec5339b6c50e9f3c8b0dce3e2175cd89b12f.pack\n\nBLOB : 49860\nCOMMIT: 197613\nDELTA : 1560153\nTAG : 1203\nTREE : 154496\n====== ==========\nTotal : 1963325\n\nGitzilla_1: 443428349 32 443428317 -7775014 -3.9601\n-4.9835\nGitzilla_2: 442177053 32 442177021 -9026310 -4.5975\n-5.7855\nPack_2 : 451203363 32 451203331 0 0.0000\n0.0000\nPack_3 : 451010859 32 451010827 -192504 -0.0980\n-0.1234\n"},{"id":"26480","messageId":"20060907054126.GC31580@spearce.org","threadId":"5501","inReplyTo":"9e4733910609061704s429c449etcf0475841556c26b@mail.gmail.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-07T05:41:26Z","receivedAt":"2006-09-07T05:41:26Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jon Smirl wrote:\n> The repack code could build a model of the tree as it is repacking,\n> that is what fast-import does. If you have a model of the tree then\n> when you change a TREE node you track the last sha1 that corresponded\n> to that directory path. Now you know what to diff to.\n\nRight. But that's horribly expensive. For the most part\npack-objects does a good job estimating this by hashing the trees\nby their name and size into the same hash bucket. And its fast.\n\nBesides its better to store reverse deltas (like what CVS does)\nas faster access to the more recent stuff is more interesting than\nfaster access to the older stuff. pack-objects tries to do this\nbased on the order given by rev-list.\n\n-- \nShawn.\n"},{"id":"26479","messageId":"20060907054651.GD31580@spearce.org","threadId":"5501","inReplyTo":"7vslj4455z.fsf@assigned-by-dhcp.cox.net","subject":"Re: A look at some alternative PACK file encodings","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-07T05:46:51Z","receivedAt":"2006-09-07T05:46:51Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> Shawn Pearce writes:\n> \n> > And I'm half-way done with the 64 bit mmap sliding window. You,\n> > Junio and I are all hacking on the same tiny bit of core code for\n> > different reasons. :-)\n> \n> Which makes me quite nervous, actually.\n\nWhat order do you want the patches in then?\n\nI'm willing to go before or after Nico's offset changes, and before\nor after your 64 bit index changes.\n\nEither way two of us are going to have to redo our work on top of\nthe others. I'm finding that I'm basically rewriting the sliding\nwindow code onto your 64 bit version - there's no easy merge here.\nAnd Nico's got the same problem, he's in unpack_delta_entry too.\n\n-- \nShawn.\n"},{"id":"26533","messageId":"7virjzy0hu.fsf@assigned-by-dhcp.cox.net","threadId":"5501","inReplyTo":"20060907054651.GD31580@spearce.org","subject":"Re: A look at some alternative PACK file encodings","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-07T18:50:37Z","receivedAt":"2006-09-07T18:50:37Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> Junio C Hamano wrote:\n>> Shawn Pearce writes:\n>> \n>> > And I'm half-way done with the 64 bit mmap sliding window. You,\n>> > Junio and I are all hacking on the same tiny bit of core code for\n>> > different reasons. :-)\n>> \n>> Which makes me quite nervous, actually.\n>\n> What order do you want the patches in then?\n>\n> I'm willing to go before or after Nico's offset changes, and before\n> or after your 64 bit index changes.\n>\n> Either way two of us are going to have to redo our work on top of\n> the others. I'm finding that I'm basically rewriting the sliding\n> window code onto your 64 bit version - there's no easy merge here.\n> And Nico's got the same problem, he's in unpack_delta_entry too.\n\nWhile 64-bit offset exercise was a good way for me to see where\nthe assumption lies in the current code, and\nwhile it would have been the right way to do so in the ideal\nworld, I realize that it may not be the best way to do things in\nthe real world for a few reasons:\n\n - Always doing u64 arithmetic would be expensive, especially on\n 32-bit architectures, and doing so conditionally is quite an\n extra complexity.\n\n - Not necessarily everybody has large file offsets, so asking\n to mmap 8MB at file offset at 6GB may not be possible. Even\n on systems with large file offsets, truly huge single file is\n cumbersome to manage than a handful files under 32-bit offset\n (e.g. using a DVD-RW to back up your packs).\n\n - Mozilla may not be the largest project in the world, but it\n certainly is on the larger side than majority of our target\n audience, and even its entire history, 450MB, comfortably\n fits in 32-bit space.\n\nSo while I merged the 64-bit offset change in \"next\" branch, I\nam quite doubtful that it was a good change. As long as we\ndevise an easy way to keep each packfile under manageable size,\nthe current 32-bit arrangement would be more beneficial and\npractical than doing everything internally in 64-bit. Larger\nprojects, if needed, can use multiple packs, and even a project\nthat _could_ pack everything under 450MB would definitely want\nto use multiple packs anyway (i.e. one or more huge historical\npacks and one active pack) to avoid repacking and incremental\nupdate cost. Your \"mmap parts into windows\" update is of a far\nmore practical value than the idx with 64-bit offsets. So I am\nvery inclined to revert my 64-bit offset change from \"next\".\n\nBefore declaring it a failure, in order to keep the window open\nfor the future, we would need to make sure that we can change\nthings as needed to do everything we want with 32-bit offset\npacks. The changes we would need I can think of are in the\nfollowing areas:\n\n - \"git repack\" needs to be taught to limit the resulting packs\n under 32-bit offset. I think this is a given, and we would\n need some updates to the command because it needs to be\n taught not to touch \"huge historical packs\" anyway.\n\n - \"git send-pack\" and \"git fetch-pack\" are Ok -- the receiving\n end explodes the pack that comes over the wire using\n unpack-objects into loose objects, and there is no offset\n involved during the process. Note that pack-objects may need\n to keep the offset in the stream in u64 if we were to do the\n offset encoding of the base object, but that is pretty much\n an independent issue.\n\n - \"git fetch-pack -k\" has a problem. The daemon or sending\n side runs rev-list piped to pack-objects and there is no\n limit in the size of the pack generated in the pipeline.\n Worse yet, the protocol does not allow more than one packs to\n be sent, so we would need a protocol update to say \"the data\n you asked would result in a pack that is more than 4GB, so\n I'll send more than one packs -- here is one, here is\n another, that's all folks\". The receiving end needs to be\n taught to handle this.\n\nNote: I am not proposing to do any of the above right now, until\nthere is no need for this by any real project. We just need to\nbe sure that when need arises there is a way out.\n\nThe only case that can be problematic is when a single object is\nlarger than 4GB deflated, and at that point we would hit a very\nhard wall of 32-bit offset. But handling such a huge object\nwould have other problems [*1*] anyway, so I think it is Ok to\ndeclare that there is a hard limit on deflated object size, at\nleast for now.\n\n[*1*]\n\nFor example, we tend to do everything in core, but doing diffs\nor anything on such a huge blob should probably be done by\nswapping in only parts of it at a time).\n\nAlso we give the whole deflated size to zlib as avail_in, which\nis \"uInt\", so on architectures where int is shorter than 64-bit\nwe lose (my 64-bit index patch does not deal with this). This\nhowever is something your \"mmap parts into windows\" update would\nsolve if it were updated to deal with the internal 64-bit\noffsets.\n"}]}