{"thread":{"id":"5236","subject":"Compression and dictionaries","startedAt":"2006-08-14T03:37:21Z","lastAt":"2006-08-14T19:38:31Z","messageCount":20,"participants":["Jon Smirl","Shawn Pearce","Alex Riesen","Erik Mouw","Johannes Schindelin","David Lang","Jakub Narebski","Jeff Garzik"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"25213","messageId":"9e4733910608132037t4297c3bbq9b0cd6ebaa03b979@mail.gmail.com","threadId":"5236","inReplyTo":null,"subject":"Compression and dictionaries","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-14T03:37:21Z","receivedAt":"2006-08-14T03:37:21Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":">From what I remember from long ago most compression schemes build\ndictionaries as a way of achieving significant compression. If so,\nsince we zlib compress each entry in a pack individually, are there\nmany copies of very similar dictionaries in the pack?\n\nSome compression schemes support being initialized with a fixed\ndictionary and sharing it over all entries. A fixed dictionary could\nbe built by analysing a large pack file. Sharing a compression\ndictionary would probably be a win for me since I have 1M+ entries in\na pack.\n\nPoking around in the zlib it appears that zlib supports precomputed\ndictionaries.\nhttp://www.zlib.net/manual.html\n\n int deflateSetDictionary (z_streamp strm, const Bytef *dictionary,\nuInt dictLength);\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25214","messageId":"20060814035603.GB18667@spearce.org","threadId":"5236","inReplyTo":"9e4733910608132037t4297c3bbq9b0cd6ebaa03b979@mail.gmail.com","subject":"Re: Compression and dictionaries","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-14T03:56:03Z","receivedAt":"2006-08-14T03:56:03Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jon Smirl wrote:\n> From what I remember from long ago most compression schemes build\n> dictionaries as a way of achieving significant compression. If so,\n> since we zlib compress each entry in a pack individually, are there\n> many copies of very similar dictionaries in the pack?\n\nYes, possibly. Every object in the pack has its own dictionary.\n\nBut I'm not sure if there would be any savings from sharing\ndictionaries. One problem is you probably don't want a single\nmassive dictionary for the entire pack as it could be very large,\nplus updating it with additions would likely require recompressing\nevery entry. Typically once an entry in the pack has been compressed\nGIT won't recompress it.\n\nHowever whenever possible deltas get used between objects.\nThis allows an object to copy content from another object, with\ncopy commands typically taking just a couple of bytes to copy a\nwhole range of bytes from the other object. This works pretty\nwell when the current revision of a file is stored with just zlib\ncompression and older revisions copy their content from the current\nrevision using the delta format.\n\nI should note that delta compression works on trees, commits and\ntags too, however it gets the most benefit out of trees when only\na fraction of the files in the tree are modified. Commits and tags\nare harder to delta as they tend to be mostly different.\n\nMy fast-import computes deltas in the order you are feeding\nit objects, so each blob is deltafied against the prior object.\nSince you are feeding them in reverse RCS order (newest to oldest)\nyou are probably getting a reasonably good delta compression.\n\n-- \nShawn.\n"},{"id":"25215","messageId":"9e4733910608132107j7bca0271g360de3447febbf51@mail.gmail.com","threadId":"5236","inReplyTo":"20060814035603.GB18667@spearce.org","subject":"Re: Compression and dictionaries","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-14T04:07:45Z","receivedAt":"2006-08-14T04:07:45Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/13/06, Shawn Pearce wrote:\n> Jon Smirl wrote:\n> > From what I remember from long ago most compression schemes build\n> > dictionaries as a way of achieving significant compression. If so,\n> > since we zlib compress each entry in a pack individually, are there\n> > many copies of very similar dictionaries in the pack?\n>\n> Yes, possibly. Every object in the pack has its own dictionary.\n>\n> But I'm not sure if there would be any savings from sharing\n> dictionaries. One problem is you probably don't want a single\n> massive dictionary for the entire pack as it could be very large,\n> plus updating it with additions would likely require recompressing\n> every entry. Typically once an entry in the pack has been compressed\n> GIT won't recompress it.\n\nThe zlib doc says to put your most common strings into the fixed\ndictionary. If a string isn't in the fixed dictionary it will get\nhandled with an internal dictionary entry. By default zlib runs with\nan empty fixed dictionary and handles everything with the internal\ndictionary.\n\nSince we are encoding C many strings will always be present (if,\nstatic, define, const, char, include, int, void, while, continue,\netc). Do you have any tools to identify the top 500 strings in C\ncode? The fixed dictionary would get hardcoded into the git apps.\n\nA fixed dictionary could conceivably take 5-10% off the size of each entry.\n\n> However whenever possible deltas get used between objects.\n> This allows an object to copy content from another object, with\n> copy commands typically taking just a couple of bytes to copy a\n> whole range of bytes from the other object. This works pretty\n> well when the current revision of a file is stored with just zlib\n> compression and older revisions copy their content from the current\n> revision using the delta format.\n>\n> I should note that delta compression works on trees, commits and\n> tags too, however it gets the most benefit out of trees when only\n> a fraction of the files in the tree are modified. Commits and tags\n> are harder to delta as they tend to be mostly different.\n>\n> My fast-import computes deltas in the order you are feeding\n> it objects, so each blob is deltafied against the prior object.\n> Since you are feeding them in reverse RCS order (newest to oldest)\n> you are probably getting a reasonably good delta compression.\n>\n> --\n> Shawn.\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25216","messageId":"20060814041705.GD18667@spearce.org","threadId":"5236","inReplyTo":"9e4733910608132107j7bca0271g360de3447febbf51@mail.gmail.com","subject":"Re: Compression and dictionaries","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-14T04:17:05Z","receivedAt":"2006-08-14T04:17:05Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jon Smirl wrote:\n> The zlib doc says to put your most common strings into the fixed\n> dictionary. If a string isn't in the fixed dictionary it will get\n> handled with an internal dictionary entry. By default zlib runs with\n> an empty fixed dictionary and handles everything with the internal\n> dictionary.\n \n> Since we are encoding C many strings will always be present (if,\n> static, define, const, char, include, int, void, while, continue,\n> etc). Do you have any tools to identify the top 500 strings in C\n> code? The fixed dictionary would get hardcoded into the git apps.\n\nActually GIT itself may also benefit from other strings beyond\nthose common found in C-like languages:\n\n\t'10644 '\n\t'40000 '\n\t'parent '\n\t'tree '\n\t'author '\n\t'committer '\n\nas these occur frequently in trees and commits.\n \n> A fixed dictionary could conceivably take 5-10% off the size of each entry.\n\nCould be an interesting experiment to see if that's really true\nfor common loads (e.g. the kernel repo). I don't think anyone has\ntried it.\n\n-- \nShawn.\n"},{"id":"25230","messageId":"81b0412b0608140048s2dae66edj4af76a6cd564af7d@mail.gmail.com","threadId":"5236","inReplyTo":"20060814041705.GD18667@spearce.org","subject":"Re: Compression and dictionaries","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-08-14T07:48:47Z","receivedAt":"2006-08-14T07:48:47Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 8/14/06, Shawn Pearce wrote:\n> > A fixed dictionary could conceivably take 5-10% off the size of each entry.\n>\n> Could be an interesting experiment to see if that's really true\n> for common loads (e.g. the kernel repo). I don't think anyone has\n> tried it.\n\nBTW, kenel repo rapidly becomes \"less than common load\" for git ;)\n"},{"id":"25235","messageId":"20060814100636.GA26859@harddisk-recovery.com","threadId":"5236","inReplyTo":"9e4733910608132107j7bca0271g360de3447febbf51@mail.gmail.com","subject":"Re: Compression and dictionaries","fromName":"Erik Mouw","fromEmail":"erik@harddisk-recovery.com","sentAt":"2006-08-14T10:06:36Z","receivedAt":"2006-08-14T10:06:36Z","isPatch":false,"sender":{"key":"erik@harddisk-recovery.com","avatar":null},"body":"On Mon, Aug 14, 2006 at 12:07:45AM -0400, Jon Smirl wrote:\n> Since we are encoding C many strings will always be present (if,\n> static, define, const, char, include, int, void, while, continue,\n> etc). Do you have any tools to identify the top 500 strings in C\n> code? The fixed dictionary would get hardcoded into the git apps.\n\nWe are not only encoding C anymore. Git might have started as a tool to\nmaintain the linux kernel tree, but its use got beyond that.\n\n\nErik\n\n-- \n+-- Erik Mouw -- www.harddisk-recovery.com -- +31 70 370 12 90 --\n| Lab address: Delftechpark 26, 2628 XH, Delft, The Netherlands\n"},{"id":"25251","messageId":"Pine.LNX.4.63.0608141415560.10541@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5236","inReplyTo":"9e4733910608132037t4297c3bbq9b0cd6ebaa03b979@mail.gmail.com","subject":"Re: Compression and dictionaries","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-14T12:33:39Z","receivedAt":"2006-08-14T12:33:39Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 13 Aug 2006, Jon Smirl wrote:\n\n> > From what I remember from long ago most compression schemes build\n> dictionaries as a way of achieving significant compression. If so,\n> since we zlib compress each entry in a pack individually, are there\n> many copies of very similar dictionaries in the pack?\n\nNo, there are no dictionaries in the pack. At least no explicit ones.\n\nThe trick is that the dictionary builds up with the data incrementally: \nboth the encoding process and the decoding process construct it \nidentically, on the fly.\n\nExample: A very primitive example of compression is the arithmetic coder \nof single characters. Given a probability distribution of the characters, \neach character is encoded such that the length of the encoding of one \ncharacter is reciprocal to its probability *Footnote 1*. If you want to \ncompress context-free, i.e. without looking at the characters before or \nafter the current character when encoding or decoding, this is provably \noptimal.\n\nNow, if you do not have a probability distribution (because you haven't \nlooked at the file yet), you can build an histogram as approximation on \nthe fly. Whenever a character is encoded, you take the current histogram \nto approximate the probability distribution, and adjust the histogram for \nthat character.\n\nFor zlib, it is a little more involved (it is not a simple histogram), but \nthe principle holds: if you do not have a dictionary, you just build one \nfrom the data seen so far.\n\nBTW I doubt that an explicit dictionary would be good: Either you \ndistribute it with git, and have many people complaining that it is either \ntoo small, or too big, and in most cases does not fit their data well, or \nyou have to create it for each local repository, which takes time.\n\nFurther, if the pack-file becomes corrupt, you usually still have the \npack index, or the start of the pack-file, and can reconstruct most of the \nobjects. If you use a dictionary, and just one bit flips in it, you're \nscrewed.\n\nCiao,\nDscho\n\nFootnote 1: If the probabilities are all powers of two (with negative \nexponent), the encodings can be fixed bit strings (because the lengths are \ninteger numbers); if that is not the case, it gets a little more \ncomplicated; basically, you store a fractional bit as a state; that is why \nit is called arithmetic coding.\n"},{"id":"25254","messageId":"9e4733910608140708i45e3d6day6b87676783fd6511@mail.gmail.com","threadId":"5236","inReplyTo":"Pine.LNX.4.63.0608141415560.10541@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: Compression and dictionaries","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-14T14:08:33Z","receivedAt":"2006-08-14T14:08:33Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/14/06, Johannes Schindelin wrote:\n> Hi,\n>\n> On Sun, 13 Aug 2006, Jon Smirl wrote:\n>\n> > > From what I remember from long ago most compression schemes build\n> > dictionaries as a way of achieving significant compression. If so,\n> > since we zlib compress each entry in a pack individually, are there\n> > many copies of very similar dictionaries in the pack?\n>\n> No, there are no dictionaries in the pack. At least no explicit ones.\n>\n> The trick is that the dictionary builds up with the data incrementally:\n> both the encoding process and the decoding process construct it\n> identically, on the fly.\n>\n> Example: A very primitive example of compression is the arithmetic coder\n> of single characters. Given a probability distribution of the characters,\n> each character is encoded such that the length of the encoding of one\n> character is reciprocal to its probability *Footnote 1*. If you want to\n> compress context-free, i.e. without looking at the characters before or\n> after the current character when encoding or decoding, this is provably\n> optimal.\n>\n> Now, if you do not have a probability distribution (because you haven't\n> looked at the file yet), you can build an histogram as approximation on\n> the fly. Whenever a character is encoded, you take the current histogram\n> to approximate the probability distribution, and adjust the histogram for\n> that character.\n>\n> For zlib, it is a little more involved (it is not a simple histogram), but\n> the principle holds: if you do not have a dictionary, you just build one\n> from the data seen so far.\n\nDoes a zlib dictionary just changes the probabilities in the histogram\nor does it turn the dictionary into a pre-loaded encoding tree?\n\nThe other compression schemes I looked at let you load in a\nprecomputed huffman/arithmetic encoding tree. By preloading an\nencoding tree you avoid storing the encoding of \"void => 010101' in\nevery item. Removing 1M encoding maps and using one common one should\nbe a win. Items not in the map would still be stored using internal\nadditions to the map.\n\nChanging the probabilities probably won't help much, but there may be\ngood gains from partially eliminating 1M encoding maps.\n\n>\n> BTW I doubt that an explicit dictionary would be good: Either you\n> distribute it with git, and have many people complaining that it is either\n> too small, or too big, and in most cases does not fit their data well, or\n> you have to create it for each local repository, which takes time.\n>\n> Further, if the pack-file becomes corrupt, you usually still have the\n> pack index, or the start of the pack-file, and can reconstruct most of the\n> objects. If you use a dictionary, and just one bit flips in it, you're\n> screwed.\n>\n> Ciao,\n> Dscho\n>\n> Footnote 1: If the probabilities are all powers of two (with negative\n> exponent), the encodings can be fixed bit strings (because the lengths are\n> integer numbers); if that is not the case, it gets a little more\n> complicated; basically, you store a fractional bit as a state; that is why\n> it is called arithmetic coding.\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25257","messageId":"Pine.LNX.4.63.0608141641330.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5236","inReplyTo":"9e4733910608140708i45e3d6day6b87676783fd6511@mail.gmail.com","subject":"Re: Compression and dictionaries","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-14T14:45:34Z","receivedAt":"2006-08-14T14:45:34Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 14 Aug 2006, Jon Smirl wrote:\n\n> Does a zlib dictionary just changes the probabilities in the histogram \n> or does it turn the dictionary into a pre-loaded encoding tree?\n\nI have to admit that I do not know zlib well enough to tell off the top of \nmy head, but I guess it would make more sense to have it as a preloaded \nencoding tree.\n\n> The other compression schemes I looked at let you load in a\n> precomputed huffman/arithmetic encoding tree. By preloading an\n> encoding tree you avoid storing the encoding of \"void => 010101' in\n> every item. Removing 1M encoding maps and using one common one should\n> be a win. Items not in the map would still be stored using internal\n> additions to the map.\n> \n> Changing the probabilities probably won't help much, but there may be\n> good gains from partially eliminating 1M encoding maps.\n\nI _think_ that it would not matter much. The deltas have a more important \nimpact.\n\n> > Further, if the pack-file becomes corrupt, you usually still have the \n> > pack index, or the start of the pack-file, and can reconstruct most of \n> > the objects. If you use a dictionary, and just one bit flips in it, \n> > you're screwed.\n\nI still think that this is important to think through: Is it worth a \ncouple of kilobytes (I doubt that it would be as much as 1MB in _total_), \nand be on the unsafe side?\n\nCiao,\nDscho\n"},{"id":"25259","messageId":"81b0412b0608140814h227517a0l5857389c84ef8ff8@mail.gmail.com","threadId":"5236","inReplyTo":"9e4733910608140708i45e3d6day6b87676783fd6511@mail.gmail.com","subject":"Re: Compression and dictionaries","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-08-14T15:14:36Z","receivedAt":"2006-08-14T15:14:36Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 8/14/06, Jon Smirl wrote:\n> Changing the probabilities probably won't help much, but there may be\n> good gains from partially eliminating 1M encoding maps.\n\nwill the old git installations, without the maps, still be able to decode the\npack created this way?\n"},{"id":"25260","messageId":"Pine.LNX.4.63.0608141724140.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5236","inReplyTo":"81b0412b0608140814h227517a0l5857389c84ef8ff8@mail.gmail.com","subject":"Re: Compression and dictionaries","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-14T15:26:31Z","receivedAt":"2006-08-14T15:26:31Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 14 Aug 2006, Alex Riesen wrote:\n\n> On 8/14/06, Jon Smirl wrote:\n> > Changing the probabilities probably won't help much, but there may be\n> > good gains from partially eliminating 1M encoding maps.\n> \n> will the old git installations, without the maps, still be able to decode the\n> pack created this way?\n\nProbably not. But then, I would _not_ want this in upload-pack, so it is a \nstrictly local thing -- either you repacked with a dictionary yourself, or \nthere would be no explicit dictionary.\n\nHowever, as I said, I _think_ this discussion is moot. You'd probably be \nbetter off making the windows wider, activating stronger compression, \nbasically investing more time for the repacker. Plus, this would benefit \ncloned repos as well.\n\nCiao,\nDscho\n"},{"id":"25261","messageId":"9e4733910608140915i728004c1p216bf3d74fcc6ab7@mail.gmail.com","threadId":"5236","inReplyTo":"Pine.LNX.4.63.0608141641330.28360@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: Compression and dictionaries","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-14T16:15:29Z","receivedAt":"2006-08-14T16:15:29Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/14/06, Johannes Schindelin wrote:\n> I still think that this is important to think through: Is it worth a\n> couple of kilobytes (I doubt that it would be as much as 1MB in _total_),\n> and be on the unsafe side?\n\nThe maps look something like this:\nvoid => 10101010\nchar => 111101\nint => 1110101\ntree => 11010111\ncommit => 101011001\n\nThese maps are repeated in every one of my 1M revisions including the\ndeltas. I have 1GB pack files with 1M entries in them - 1K each entry.\nEach byte saved out of a zlib entry take 1MB off my pack.\n\nNote that the current internal maps aren't the same in each of each of\nthe zlib blobs since the algorithm that builds the internal maps\ndepends on the order the identifiers were encountered.\n\nIf the git tools add a global dictionary the tools would still be able\nto read existing packs. If old tools try to read a new dictionary\nbased pack they will get the zlib NEED_DICT error.\n\nIf the entire file was one big zlib blob there would only be one\ndictionary and adding a fixed dictionary wouldn't make any difference.\nBut since it is 1M little zlib blobs it is has 1M dictionaries.\n\nThe only \"unsafe\" aspect I see to this is if the global dictionary\ndoesn't contain any of the words in the documents being encoded. In\nthat case the global dictionary will occupy the short huffman keys\nforcing longer internal keys. The keys for the words in the document\nwould be longer by a about a bit on average.\n\nA solution for making this work over time would be to store the global\ndictionary at the front of the pack file and for the unpack tools to\nuse the stored copy. This would let us change the global dictionary in\nthe pack tool with no downside, you could even support multiple\ndictionaries in the pack tool.\n\nIf someone wants to get fancy you could write a tool that would scan a\npack file and compute an optimal fixed dictionary. Store it at the\nfront of the pack file and repack using it.\n\nGlobal dictionaries are common in full text searching. I seem to\nrecall an article stating that Google's global dictionary has about\n250K entries in it. If git packs switch to a global dictionary model\nit's not a big leap to add a full text search index. You just need\nobjects for each word in the dictionary pointing to the revisions that\ncontain it.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25262","messageId":"Pine.LNX.4.63.0608140930380.14796@qynat.qvtvafvgr.pbz","threadId":"5236","inReplyTo":"9e4733910608140915i728004c1p216bf3d74fcc6ab7@mail.gmail.com","subject":"Re: Compression and dictionaries","fromName":"David Lang","fromEmail":"dlang@digitalinsight.com","sentAt":"2006-08-14T16:32:50Z","receivedAt":"2006-08-14T16:32:50Z","isPatch":false,"sender":{"key":"dlang@digitalinsight.com","avatar":null},"body":"On Mon, 14 Aug 2006, Jon Smirl wrote:\n\n> On 8/14/06, Johannes Schindelin wrote:\n>> I still think that this is important to think through: Is it worth a\n>> couple of kilobytes (I doubt that it would be as much as 1MB in _total_),\n>> and be on the unsafe side?\n>\n> The only \"unsafe\" aspect I see to this is if the global dictionary\n> doesn't contain any of the words in the documents being encoded. In\n> that case the global dictionary will occupy the short huffman keys\n> forcing longer internal keys. The keys for the words in the document\n> would be longer by a about a bit on average.\n\nthe other factor that was mentioned was that a single-bit corruption in the \ndictionary would make the entire pack file useless. if this is really a concern \nthen just store multiple copies of the dictionary. on a pack with lots of files \nin it it can still be a significant win.\n\nDavid Lang\n"},{"id":"25266","messageId":"ebq9tc$3gl$1@sea.gmane.org","threadId":"5236","inReplyTo":"Pine.LNX.4.63.0608140930380.14796@qynat.qvtvafvgr.pbz","subject":"Re: Compression and dictionaries","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-08-14T16:55:53Z","receivedAt":"2006-08-14T16:55:53Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"David Lang wrote:\n\n> the other factor that was mentioned was that a single-bit corruption in the \n> dictionary would make the entire pack file useless. if this is really a concern \n> then just store multiple copies of the dictionary. on a pack with lots of files \n> in it it can still be a significant win.\n\nOr use some error-correcting code for storing dictionary.\n\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"25268","messageId":"44E0AFCB.10908@garzik.org","threadId":"5236","inReplyTo":"ebq9tc$3gl$1@sea.gmane.org","subject":"Re: Compression and dictionaries","fromName":"Jeff Garzik","fromEmail":"jeff@garzik.org","sentAt":"2006-08-14T17:15:55Z","receivedAt":"2006-08-14T17:15:55Z","isPatch":false,"sender":{"key":"jeff@garzik.org","avatar":null},"body":"Jakub Narebski wrote:\n> David Lang wrote:\n> \n>> the other factor that was mentioned was that a single-bit corruption in the \n>> dictionary would make the entire pack file useless. if this is really a concern \n>> then just store multiple copies of the dictionary. on a pack with lots of files \n>> in it it can still be a significant win.\n> \n> Or use some error-correcting code for storing dictionary.\n\nError-correcting code? We have sha1 hash to determine validity...\n\n\tJeff\n"},{"id":"25269","messageId":"Pine.LNX.4.63.0608141033080.14796@qynat.qvtvafvgr.pbz","threadId":"5236","inReplyTo":"44E0AFCB.10908@garzik.org","subject":"Re: Compression and dictionaries","fromName":"David Lang","fromEmail":"dlang@digitalinsight.com","sentAt":"2006-08-14T17:34:12Z","receivedAt":"2006-08-14T17:34:12Z","isPatch":false,"sender":{"key":"dlang@digitalinsight.com","avatar":null},"body":"On Mon, 14 Aug 2006, Jeff Garzik wrote:\n\n> Date: Mon, 14 Aug 2006 13:15:55 -0400\n> From: Jeff Garzik \n> To: Jakub Narebski \n> Cc: git@vger.kernel.org\n> Subject: Re: Compression and dictionaries\n> \n> Jakub Narebski wrote:\n>> David Lang wrote:\n>> \n>>> the other factor that was mentioned was that a single-bit corruption in \n>>> the dictionary would make the entire pack file useless. if this is really \n>>> a concern then just store multiple copies of the dictionary. on a pack \n>>> with lots of files in it it can still be a significant win.\n>> \n>> Or use some error-correcting code for storing dictionary.\n>\n> Error-correcting code? We have sha1 hash to determine validity...\n\nthat would only tell you that what you have is garbage (and you need to restore \nfrom backup(, useing a ECC costs some space, but lets you recover from some \nerrors without having to resort to backups.\n\nDavid Lang\n"},{"id":"25271","messageId":"44E0B7E7.6020207@garzik.org","threadId":"5236","inReplyTo":"Pine.LNX.4.63.0608141033080.14796@qynat.qvtvafvgr.pbz","subject":"Re: Compression and dictionaries","fromName":"Jeff Garzik","fromEmail":"jeff@garzik.org","sentAt":"2006-08-14T17:50:31Z","receivedAt":"2006-08-14T17:50:31Z","isPatch":false,"sender":{"key":"jeff@garzik.org","avatar":null},"body":"David Lang wrote:\n> that would only tell you that what you have is garbage (and you need to \n> restore from backup(, useing a ECC costs some space, but lets you \n> recover from some errors without having to resort to backups.\n\nECC permits you to recover from very specific, very-limited-damage \nscenarios like bit errors.\n\nOn modern hard drives, single-bit data corruption is very very very rare \n(particularly since ECC is already employed on the platter).\n\n\tJeff\n"},{"id":"25274","messageId":"9e4733910608141148t636f9874wfcf66b56161352c3@mail.gmail.com","threadId":"5236","inReplyTo":"Pine.LNX.4.63.0608140930380.14796@qynat.qvtvafvgr.pbz","subject":"Re: Compression and dictionaries","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-14T18:48:56Z","receivedAt":"2006-08-14T18:48:56Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/14/06, David Lang wrote:\n> On Mon, 14 Aug 2006, Jon Smirl wrote:\n>\n> > On 8/14/06, Johannes Schindelin wrote:\n> >> I still think that this is important to think through: Is it worth a\n> >> couple of kilobytes (I doubt that it would be as much as 1MB in _total_),\n> >> and be on the unsafe side?\n> >\n> > The only \"unsafe\" aspect I see to this is if the global dictionary\n> > doesn't contain any of the words in the documents being encoded. In\n> > that case the global dictionary will occupy the short huffman keys\n> > forcing longer internal keys. The keys for the words in the document\n> > would be longer by a about a bit on average.\n>\n> the other factor that was mentioned was that a single-bit corruption in the\n> dictionary would make the entire pack file useless. if this is really a concern\n> then just store multiple copies of the dictionary. on a pack with lots of files\n> in it it can still be a significant win.\n\nBit errors can mess the pack up in lots of ways. If it hits a commit\nyou won't be able to follow the tree back in time. Packs were never\ndesigned to be error tolerant.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25276","messageId":"Pine.LNX.4.63.0608141206260.14796@qynat.qvtvafvgr.pbz","threadId":"5236","inReplyTo":"9e4733910608141148t636f9874wfcf66b56161352c3@mail.gmail.com","subject":"Re: Compression and dictionaries","fromName":"David Lang","fromEmail":"dlang@digitalinsight.com","sentAt":"2006-08-14T19:08:04Z","receivedAt":"2006-08-14T19:08:04Z","isPatch":false,"sender":{"key":"dlang@digitalinsight.com","avatar":null},"body":"On Mon, 14 Aug 2006, Jon Smirl wrote:\n\n> On 8/14/06, David Lang wrote:\n>> On Mon, 14 Aug 2006, Jon Smirl wrote:\n>> \n>> > On 8/14/06, Johannes Schindelin wrote:\n>> >> I still think that this is important to think through: Is it worth a\n>> >> couple of kilobytes (I doubt that it would be as much as 1MB in \n>> _total_),\n>> >> and be on the unsafe side?\n>> >\n>> > The only \"unsafe\" aspect I see to this is if the global dictionary\n>> > doesn't contain any of the words in the documents being encoded. In\n>> > that case the global dictionary will occupy the short huffman keys\n>> > forcing longer internal keys. The keys for the words in the document\n>> > would be longer by a about a bit on average.\n>> \n>> the other factor that was mentioned was that a single-bit corruption in the\n>> dictionary would make the entire pack file useless. if this is really a \n>> concern\n>> then just store multiple copies of the dictionary. on a pack with lots of \n>> files\n>> in it it can still be a significant win.\n>\n> Bit errors can mess the pack up in lots of ways. If it hits a commit\n> you won't be able to follow the tree back in time. Packs were never\n> designed to be error tolerant.\n\nI'm not claiming that this is a problem, I'm reponding to other people's claim \nthat useing a global dictionary for a pack is a problem becouse if something \nhappens to that dictionary the whole pack is worthless by pointing out that, if \nthis is viewed as a real problem, it's easy to solve.\n\nDavid Lang\n"},{"id":"25279","messageId":"Pine.LNX.4.63.0608142133150.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5236","inReplyTo":"Pine.LNX.4.63.0608141206260.14796@qynat.qvtvafvgr.pbz","subject":"Re: Compression and dictionaries","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-14T19:38:31Z","receivedAt":"2006-08-14T19:38:31Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 14 Aug 2006, David Lang wrote:\n\n> On Mon, 14 Aug 2006, Jon Smirl wrote:\n> \n> > Bit errors can mess the pack up in lots of ways. If it hits a commit \n> > you won't be able to follow the tree back in time. Packs were never \n> > designed to be error tolerant.\n> \n> I'm not claiming that this is a problem, I'm reponding to other people's \n> claim that useing a global dictionary for a pack is a problem becouse if \n> something happens to that dictionary the whole pack is worthless by \n> pointing out that, if this is viewed as a real problem, it's easy to \n> solve.\n\nLet's not solve problems we do not have. I refuse to think about this \nproblem further, before there are actually some hard numbers showing an \nimprovement there. If the numbers do not show an improvement, we do not \nhave that problem at all!\n\nMake a _global_ dictionary, optimize the heck out of it, _use_ that \ndictionary to repack a sizeable repository (I think linux-2.6.git should \nbe enough for first tests), and tell the world about the size of the \ndictionary, the original pack, and the new pack.\n\nYou would not need to implement this cleanly, just a hack to prove that \nthis idea is worth following up. \n\nCiao,\nDscho\n"}]}