# Compression and dictionaries 20 messages from 2006-08-14 to 2006-08-14. Participants: Jon Smirl, Shawn Pearce, Alex Riesen, Erik Mouw, Johannes Schindelin, David Lang, Jakub Narebski, Jeff Garzik. Thread: https://gitlist.dev/t/5236 ## Jon Smirl, 2006-08-14 03:37 Subject: Compression and dictionaries Message-ID: <9e4733910608132037t4297c3bbq9b0cd6ebaa03b979@mail.gmail.com> URL: https://gitlist.dev/e/9e4733910608132037t4297c3bbq9b0cd6ebaa03b979%40mail.gmail.com ``` >From what I remember from long ago most compression schemes build dictionaries as a way of achieving significant compression. If so, since we zlib compress each entry in a pack individually, are there many copies of very similar dictionaries in the pack? Some compression schemes support being initialized with a fixed dictionary and sharing it over all entries. A fixed dictionary could be built by analysing a large pack file. Sharing a compression dictionary would probably be a win for me since I have 1M+ entries in a pack. Poking around in the zlib it appears that zlib supports precomputed dictionaries. http://www.zlib.net/manual.html int deflateSetDictionary (z_streamp strm, const Bytef *dictionary, uInt dictLength); -- Jon Smirl jonsmirl@gmail.com ``` ## Shawn Pearce, 2006-08-14 03:56 Subject: Re: Compression and dictionaries Message-ID: <20060814035603.GB18667@spearce.org> URL: https://gitlist.dev/e/20060814035603.GB18667%40spearce.org In-Reply-To: <9e4733910608132037t4297c3bbq9b0cd6ebaa03b979@mail.gmail.com> ``` Jon Smirl wrote: > From what I remember from long ago most compression schemes build > dictionaries as a way of achieving significant compression. If so, > since we zlib compress each entry in a pack individually, are there > many copies of very similar dictionaries in the pack? Yes, possibly. Every object in the pack has its own dictionary. But I'm not sure if there would be any savings from sharing dictionaries. One problem is you probably don't want a single massive dictionary for the entire pack as it could be very large, plus updating it with additions would likely require recompressing every entry. Typically once an entry in the pack has been compressed GIT won't recompress it. However whenever possible deltas get used between objects. This allows an object to copy content from another object, with copy commands typically taking just a couple of bytes to copy a whole range of bytes from the other object. This works pretty well when the current revision of a file is stored with just zlib compression and older revisions copy their content from the current revision using the delta format. I should note that delta compression works on trees, commits and tags too, however it gets the most benefit out of trees when only a fraction of the files in the tree are modified. Commits and tags are harder to delta as they tend to be mostly different. My fast-import computes deltas in the order you are feeding it objects, so each blob is deltafied against the prior object. Since you are feeding them in reverse RCS order (newest to oldest) you are probably getting a reasonably good delta compression. -- Shawn. ``` ## Jon Smirl, 2006-08-14 04:07 Subject: Re: Compression and dictionaries Message-ID: <9e4733910608132107j7bca0271g360de3447febbf51@mail.gmail.com> URL: https://gitlist.dev/e/9e4733910608132107j7bca0271g360de3447febbf51%40mail.gmail.com In-Reply-To: <20060814035603.GB18667@spearce.org> ``` On 8/13/06, Shawn Pearce wrote: > Jon Smirl wrote: > > From what I remember from long ago most compression schemes build > > dictionaries as a way of achieving significant compression. If so, > > since we zlib compress each entry in a pack individually, are there > > many copies of very similar dictionaries in the pack? > > Yes, possibly. Every object in the pack has its own dictionary. > > But I'm not sure if there would be any savings from sharing > dictionaries. One problem is you probably don't want a single > massive dictionary for the entire pack as it could be very large, > plus updating it with additions would likely require recompressing > every entry. Typically once an entry in the pack has been compressed > GIT won't recompress it. The zlib doc says to put your most common strings into the fixed dictionary. If a string isn't in the fixed dictionary it will get handled with an internal dictionary entry. By default zlib runs with an empty fixed dictionary and handles everything with the internal dictionary. Since we are encoding C many strings will always be present (if, static, define, const, char, include, int, void, while, continue, etc). Do you have any tools to identify the top 500 strings in C code? The fixed dictionary would get hardcoded into the git apps. A fixed dictionary could conceivably take 5-10% off the size of each entry. > However whenever possible deltas get used between objects. > This allows an object to copy content from another object, with > copy commands typically taking just a couple of bytes to copy a > whole range of bytes from the other object. This works pretty > well when the current revision of a file is stored with just zlib > compression and older revisions copy their content from the current > revision using the delta format. > > I should note that delta compression works on trees, commits and > tags too, however it gets the most benefit out of trees when only > a fraction of the files in the tree are modified. Commits and tags > are harder to delta as they tend to be mostly different. > > My fast-import computes deltas in the order you are feeding > it objects, so each blob is deltafied against the prior object. > Since you are feeding them in reverse RCS order (newest to oldest) > you are probably getting a reasonably good delta compression. > > -- > Shawn. > -- Jon Smirl jonsmirl@gmail.com ``` ## Shawn Pearce, 2006-08-14 04:17 Subject: Re: Compression and dictionaries Message-ID: <20060814041705.GD18667@spearce.org> URL: https://gitlist.dev/e/20060814041705.GD18667%40spearce.org In-Reply-To: <9e4733910608132107j7bca0271g360de3447febbf51@mail.gmail.com> ``` Jon Smirl wrote: > The zlib doc says to put your most common strings into the fixed > dictionary. If a string isn't in the fixed dictionary it will get > handled with an internal dictionary entry. By default zlib runs with > an empty fixed dictionary and handles everything with the internal > dictionary. > Since we are encoding C many strings will always be present (if, > static, define, const, char, include, int, void, while, continue, > etc). Do you have any tools to identify the top 500 strings in C > code? The fixed dictionary would get hardcoded into the git apps. Actually GIT itself may also benefit from other strings beyond those common found in C-like languages: '10644 ' '40000 ' 'parent ' 'tree ' 'author ' 'committer ' as these occur frequently in trees and commits. > A fixed dictionary could conceivably take 5-10% off the size of each entry. Could be an interesting experiment to see if that's really true for common loads (e.g. the kernel repo). I don't think anyone has tried it. -- Shawn. ``` ## Alex Riesen, 2006-08-14 07:48 Subject: Re: Compression and dictionaries Message-ID: <81b0412b0608140048s2dae66edj4af76a6cd564af7d@mail.gmail.com> URL: https://gitlist.dev/e/81b0412b0608140048s2dae66edj4af76a6cd564af7d%40mail.gmail.com In-Reply-To: <20060814041705.GD18667@spearce.org> ``` On 8/14/06, Shawn Pearce wrote: > > A fixed dictionary could conceivably take 5-10% off the size of each entry. > > Could be an interesting experiment to see if that's really true > for common loads (e.g. the kernel repo). I don't think anyone has > tried it. BTW, kenel repo rapidly becomes "less than common load" for git ;) ``` ## Erik Mouw, 2006-08-14 10:06 Subject: Re: Compression and dictionaries Message-ID: <20060814100636.GA26859@harddisk-recovery.com> URL: https://gitlist.dev/e/20060814100636.GA26859%40harddisk-recovery.com In-Reply-To: <9e4733910608132107j7bca0271g360de3447febbf51@mail.gmail.com> ``` On Mon, Aug 14, 2006 at 12:07:45AM -0400, Jon Smirl wrote: > Since we are encoding C many strings will always be present (if, > static, define, const, char, include, int, void, while, continue, > etc). Do you have any tools to identify the top 500 strings in C > code? The fixed dictionary would get hardcoded into the git apps. We are not only encoding C anymore. Git might have started as a tool to maintain the linux kernel tree, but its use got beyond that. Erik -- +-- Erik Mouw -- www.harddisk-recovery.com -- +31 70 370 12 90 -- | Lab address: Delftechpark 26, 2628 XH, Delft, The Netherlands ``` ## Johannes Schindelin, 2006-08-14 12:33 Subject: Re: Compression and dictionaries Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.63.0608141415560.10541%40wbgn013.biozentrum.uni-wuerzburg.de In-Reply-To: <9e4733910608132037t4297c3bbq9b0cd6ebaa03b979@mail.gmail.com> ``` Hi, On Sun, 13 Aug 2006, Jon Smirl wrote: > > From what I remember from long ago most compression schemes build > dictionaries as a way of achieving significant compression. If so, > since we zlib compress each entry in a pack individually, are there > many copies of very similar dictionaries in the pack? No, there are no dictionaries in the pack. At least no explicit ones. The trick is that the dictionary builds up with the data incrementally: both the encoding process and the decoding process construct it identically, on the fly. Example: A very primitive example of compression is the arithmetic coder of single characters. Given a probability distribution of the characters, each character is encoded such that the length of the encoding of one character is reciprocal to its probability *Footnote 1*. If you want to compress context-free, i.e. without looking at the characters before or after the current character when encoding or decoding, this is provably optimal. Now, if you do not have a probability distribution (because you haven't looked at the file yet), you can build an histogram as approximation on the fly. Whenever a character is encoded, you take the current histogram to approximate the probability distribution, and adjust the histogram for that character. For zlib, it is a little more involved (it is not a simple histogram), but the principle holds: if you do not have a dictionary, you just build one from the data seen so far. BTW I doubt that an explicit dictionary would be good: Either you distribute it with git, and have many people complaining that it is either too small, or too big, and in most cases does not fit their data well, or you have to create it for each local repository, which takes time. Further, if the pack-file becomes corrupt, you usually still have the pack index, or the start of the pack-file, and can reconstruct most of the objects. If you use a dictionary, and just one bit flips in it, you're screwed. Ciao, Dscho Footnote 1: If the probabilities are all powers of two (with negative exponent), the encodings can be fixed bit strings (because the lengths are integer numbers); if that is not the case, it gets a little more complicated; basically, you store a fractional bit as a state; that is why it is called arithmetic coding. ``` ## Jon Smirl, 2006-08-14 14:08 Subject: Re: Compression and dictionaries Message-ID: <9e4733910608140708i45e3d6day6b87676783fd6511@mail.gmail.com> URL: https://gitlist.dev/e/9e4733910608140708i45e3d6day6b87676783fd6511%40mail.gmail.com In-Reply-To: ``` On 8/14/06, Johannes Schindelin wrote: > Hi, > > On Sun, 13 Aug 2006, Jon Smirl wrote: > > > > From what I remember from long ago most compression schemes build > > dictionaries as a way of achieving significant compression. If so, > > since we zlib compress each entry in a pack individually, are there > > many copies of very similar dictionaries in the pack? > > No, there are no dictionaries in the pack. At least no explicit ones. > > The trick is that the dictionary builds up with the data incrementally: > both the encoding process and the decoding process construct it > identically, on the fly. > > Example: A very primitive example of compression is the arithmetic coder > of single characters. Given a probability distribution of the characters, > each character is encoded such that the length of the encoding of one > character is reciprocal to its probability *Footnote 1*. If you want to > compress context-free, i.e. without looking at the characters before or > after the current character when encoding or decoding, this is provably > optimal. > > Now, if you do not have a probability distribution (because you haven't > looked at the file yet), you can build an histogram as approximation on > the fly. Whenever a character is encoded, you take the current histogram > to approximate the probability distribution, and adjust the histogram for > that character. > > For zlib, it is a little more involved (it is not a simple histogram), but > the principle holds: if you do not have a dictionary, you just build one > from the data seen so far. Does a zlib dictionary just changes the probabilities in the histogram or does it turn the dictionary into a pre-loaded encoding tree? The other compression schemes I looked at let you load in a precomputed huffman/arithmetic encoding tree. By preloading an encoding tree you avoid storing the encoding of "void => 010101' in every item. Removing 1M encoding maps and using one common one should be a win. Items not in the map would still be stored using internal additions to the map. Changing the probabilities probably won't help much, but there may be good gains from partially eliminating 1M encoding maps. > > BTW I doubt that an explicit dictionary would be good: Either you > distribute it with git, and have many people complaining that it is either > too small, or too big, and in most cases does not fit their data well, or > you have to create it for each local repository, which takes time. > > Further, if the pack-file becomes corrupt, you usually still have the > pack index, or the start of the pack-file, and can reconstruct most of the > objects. If you use a dictionary, and just one bit flips in it, you're > screwed. > > Ciao, > Dscho > > Footnote 1: If the probabilities are all powers of two (with negative > exponent), the encodings can be fixed bit strings (because the lengths are > integer numbers); if that is not the case, it gets a little more > complicated; basically, you store a fractional bit as a state; that is why > it is called arithmetic coding. > -- Jon Smirl jonsmirl@gmail.com ``` ## Johannes Schindelin, 2006-08-14 14:45 Subject: Re: Compression and dictionaries Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.63.0608141641330.28360%40wbgn013.biozentrum.uni-wuerzburg.de In-Reply-To: <9e4733910608140708i45e3d6day6b87676783fd6511@mail.gmail.com> ``` Hi, On Mon, 14 Aug 2006, Jon Smirl wrote: > Does a zlib dictionary just changes the probabilities in the histogram > or does it turn the dictionary into a pre-loaded encoding tree? I have to admit that I do not know zlib well enough to tell off the top of my head, but I guess it would make more sense to have it as a preloaded encoding tree. > The other compression schemes I looked at let you load in a > precomputed huffman/arithmetic encoding tree. By preloading an > encoding tree you avoid storing the encoding of "void => 010101' in > every item. Removing 1M encoding maps and using one common one should > be a win. Items not in the map would still be stored using internal > additions to the map. > > Changing the probabilities probably won't help much, but there may be > good gains from partially eliminating 1M encoding maps. I _think_ that it would not matter much. The deltas have a more important impact. > > Further, if the pack-file becomes corrupt, you usually still have the > > pack index, or the start of the pack-file, and can reconstruct most of > > the objects. If you use a dictionary, and just one bit flips in it, > > you're screwed. I still think that this is important to think through: Is it worth a couple of kilobytes (I doubt that it would be as much as 1MB in _total_), and be on the unsafe side? Ciao, Dscho ``` ## Alex Riesen, 2006-08-14 15:14 Subject: Re: Compression and dictionaries Message-ID: <81b0412b0608140814h227517a0l5857389c84ef8ff8@mail.gmail.com> URL: https://gitlist.dev/e/81b0412b0608140814h227517a0l5857389c84ef8ff8%40mail.gmail.com In-Reply-To: <9e4733910608140708i45e3d6day6b87676783fd6511@mail.gmail.com> ``` On 8/14/06, Jon Smirl wrote: > Changing the probabilities probably won't help much, but there may be > good gains from partially eliminating 1M encoding maps. will the old git installations, without the maps, still be able to decode the pack created this way? ``` ## Johannes Schindelin, 2006-08-14 15:26 Subject: Re: Compression and dictionaries Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.63.0608141724140.28360%40wbgn013.biozentrum.uni-wuerzburg.de In-Reply-To: <81b0412b0608140814h227517a0l5857389c84ef8ff8@mail.gmail.com> ``` Hi, On Mon, 14 Aug 2006, Alex Riesen wrote: > On 8/14/06, Jon Smirl wrote: > > Changing the probabilities probably won't help much, but there may be > > good gains from partially eliminating 1M encoding maps. > > will the old git installations, without the maps, still be able to decode the > pack created this way? Probably not. But then, I would _not_ want this in upload-pack, so it is a strictly local thing -- either you repacked with a dictionary yourself, or there would be no explicit dictionary. However, as I said, I _think_ this discussion is moot. You'd probably be better off making the windows wider, activating stronger compression, basically investing more time for the repacker. Plus, this would benefit cloned repos as well. Ciao, Dscho ``` ## Jon Smirl, 2006-08-14 16:15 Subject: Re: Compression and dictionaries Message-ID: <9e4733910608140915i728004c1p216bf3d74fcc6ab7@mail.gmail.com> URL: https://gitlist.dev/e/9e4733910608140915i728004c1p216bf3d74fcc6ab7%40mail.gmail.com In-Reply-To: ``` On 8/14/06, Johannes Schindelin wrote: > I still think that this is important to think through: Is it worth a > couple of kilobytes (I doubt that it would be as much as 1MB in _total_), > and be on the unsafe side? The maps look something like this: void => 10101010 char => 111101 int => 1110101 tree => 11010111 commit => 101011001 These maps are repeated in every one of my 1M revisions including the deltas. I have 1GB pack files with 1M entries in them - 1K each entry. Each byte saved out of a zlib entry take 1MB off my pack. Note that the current internal maps aren't the same in each of each of the zlib blobs since the algorithm that builds the internal maps depends on the order the identifiers were encountered. If the git tools add a global dictionary the tools would still be able to read existing packs. If old tools try to read a new dictionary based pack they will get the zlib NEED_DICT error. If the entire file was one big zlib blob there would only be one dictionary and adding a fixed dictionary wouldn't make any difference. But since it is 1M little zlib blobs it is has 1M dictionaries. The only "unsafe" aspect I see to this is if the global dictionary doesn't contain any of the words in the documents being encoded. In that case the global dictionary will occupy the short huffman keys forcing longer internal keys. The keys for the words in the document would be longer by a about a bit on average. A solution for making this work over time would be to store the global dictionary at the front of the pack file and for the unpack tools to use the stored copy. This would let us change the global dictionary in the pack tool with no downside, you could even support multiple dictionaries in the pack tool. If someone wants to get fancy you could write a tool that would scan a pack file and compute an optimal fixed dictionary. Store it at the front of the pack file and repack using it. Global dictionaries are common in full text searching. I seem to recall an article stating that Google's global dictionary has about 250K entries in it. If git packs switch to a global dictionary model it's not a big leap to add a full text search index. You just need objects for each word in the dictionary pointing to the revisions that contain it. -- Jon Smirl jonsmirl@gmail.com ``` ## David Lang, 2006-08-14 16:32 Subject: Re: Compression and dictionaries Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.63.0608140930380.14796%40qynat.qvtvafvgr.pbz In-Reply-To: <9e4733910608140915i728004c1p216bf3d74fcc6ab7@mail.gmail.com> ``` On Mon, 14 Aug 2006, Jon Smirl wrote: > On 8/14/06, Johannes Schindelin wrote: >> I still think that this is important to think through: Is it worth a >> couple of kilobytes (I doubt that it would be as much as 1MB in _total_), >> and be on the unsafe side? > > The only "unsafe" aspect I see to this is if the global dictionary > doesn't contain any of the words in the documents being encoded. In > that case the global dictionary will occupy the short huffman keys > forcing longer internal keys. The keys for the words in the document > would be longer by a about a bit on average. the other factor that was mentioned was that a single-bit corruption in the dictionary would make the entire pack file useless. if this is really a concern then just store multiple copies of the dictionary. on a pack with lots of files in it it can still be a significant win. David Lang ``` ## Jakub Narebski, 2006-08-14 16:55 Subject: Re: Compression and dictionaries Message-ID: URL: https://gitlist.dev/e/ebq9tc%243gl%241%40sea.gmane.org In-Reply-To: ``` David Lang wrote: > the other factor that was mentioned was that a single-bit corruption in the > dictionary would make the entire pack file useless. if this is really a concern > then just store multiple copies of the dictionary. on a pack with lots of files > in it it can still be a significant win. Or use some error-correcting code for storing dictionary. -- Jakub Narebski Warsaw, Poland ShadeHawk on #git ``` ## Jeff Garzik, 2006-08-14 17:15 Subject: Re: Compression and dictionaries Message-ID: <44E0AFCB.10908@garzik.org> URL: https://gitlist.dev/e/44E0AFCB.10908%40garzik.org In-Reply-To: ``` Jakub Narebski wrote: > David Lang wrote: > >> the other factor that was mentioned was that a single-bit corruption in the >> dictionary would make the entire pack file useless. if this is really a concern >> then just store multiple copies of the dictionary. on a pack with lots of files >> in it it can still be a significant win. > > Or use some error-correcting code for storing dictionary. Error-correcting code? We have sha1 hash to determine validity... Jeff ``` ## David Lang, 2006-08-14 17:34 Subject: Re: Compression and dictionaries Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.63.0608141033080.14796%40qynat.qvtvafvgr.pbz In-Reply-To: <44E0AFCB.10908@garzik.org> ``` On Mon, 14 Aug 2006, Jeff Garzik wrote: > Date: Mon, 14 Aug 2006 13:15:55 -0400 > From: Jeff Garzik > To: Jakub Narebski > Cc: git@vger.kernel.org > Subject: Re: Compression and dictionaries > > Jakub Narebski wrote: >> David Lang wrote: >> >>> the other factor that was mentioned was that a single-bit corruption in >>> the dictionary would make the entire pack file useless. if this is really >>> a concern then just store multiple copies of the dictionary. on a pack >>> with lots of files in it it can still be a significant win. >> >> Or use some error-correcting code for storing dictionary. > > Error-correcting code? We have sha1 hash to determine validity... that would only tell you that what you have is garbage (and you need to restore from backup(, useing a ECC costs some space, but lets you recover from some errors without having to resort to backups. David Lang ``` ## Jeff Garzik, 2006-08-14 17:50 Subject: Re: Compression and dictionaries Message-ID: <44E0B7E7.6020207@garzik.org> URL: https://gitlist.dev/e/44E0B7E7.6020207%40garzik.org In-Reply-To: ``` David Lang wrote: > that would only tell you that what you have is garbage (and you need to > restore from backup(, useing a ECC costs some space, but lets you > recover from some errors without having to resort to backups. ECC permits you to recover from very specific, very-limited-damage scenarios like bit errors. On modern hard drives, single-bit data corruption is very very very rare (particularly since ECC is already employed on the platter). Jeff ``` ## Jon Smirl, 2006-08-14 18:48 Subject: Re: Compression and dictionaries Message-ID: <9e4733910608141148t636f9874wfcf66b56161352c3@mail.gmail.com> URL: https://gitlist.dev/e/9e4733910608141148t636f9874wfcf66b56161352c3%40mail.gmail.com In-Reply-To: ``` On 8/14/06, David Lang wrote: > On Mon, 14 Aug 2006, Jon Smirl wrote: > > > On 8/14/06, Johannes Schindelin wrote: > >> I still think that this is important to think through: Is it worth a > >> couple of kilobytes (I doubt that it would be as much as 1MB in _total_), > >> and be on the unsafe side? > > > > The only "unsafe" aspect I see to this is if the global dictionary > > doesn't contain any of the words in the documents being encoded. In > > that case the global dictionary will occupy the short huffman keys > > forcing longer internal keys. The keys for the words in the document > > would be longer by a about a bit on average. > > the other factor that was mentioned was that a single-bit corruption in the > dictionary would make the entire pack file useless. if this is really a concern > then just store multiple copies of the dictionary. on a pack with lots of files > in it it can still be a significant win. Bit errors can mess the pack up in lots of ways. If it hits a commit you won't be able to follow the tree back in time. Packs were never designed to be error tolerant. -- Jon Smirl jonsmirl@gmail.com ``` ## David Lang, 2006-08-14 19:08 Subject: Re: Compression and dictionaries Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.63.0608141206260.14796%40qynat.qvtvafvgr.pbz In-Reply-To: <9e4733910608141148t636f9874wfcf66b56161352c3@mail.gmail.com> ``` On Mon, 14 Aug 2006, Jon Smirl wrote: > On 8/14/06, David Lang wrote: >> On Mon, 14 Aug 2006, Jon Smirl wrote: >> >> > On 8/14/06, Johannes Schindelin wrote: >> >> I still think that this is important to think through: Is it worth a >> >> couple of kilobytes (I doubt that it would be as much as 1MB in >> _total_), >> >> and be on the unsafe side? >> > >> > The only "unsafe" aspect I see to this is if the global dictionary >> > doesn't contain any of the words in the documents being encoded. In >> > that case the global dictionary will occupy the short huffman keys >> > forcing longer internal keys. The keys for the words in the document >> > would be longer by a about a bit on average. >> >> the other factor that was mentioned was that a single-bit corruption in the >> dictionary would make the entire pack file useless. if this is really a >> concern >> then just store multiple copies of the dictionary. on a pack with lots of >> files >> in it it can still be a significant win. > > Bit errors can mess the pack up in lots of ways. If it hits a commit > you won't be able to follow the tree back in time. Packs were never > designed to be error tolerant. I'm not claiming that this is a problem, I'm reponding to other people's claim that useing a global dictionary for a pack is a problem becouse if something happens to that dictionary the whole pack is worthless by pointing out that, if this is viewed as a real problem, it's easy to solve. David Lang ``` ## Johannes Schindelin, 2006-08-14 19:38 Subject: Re: Compression and dictionaries Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.63.0608142133150.28360%40wbgn013.biozentrum.uni-wuerzburg.de In-Reply-To: ``` Hi, On Mon, 14 Aug 2006, David Lang wrote: > On Mon, 14 Aug 2006, Jon Smirl wrote: > > > Bit errors can mess the pack up in lots of ways. If it hits a commit > > you won't be able to follow the tree back in time. Packs were never > > designed to be error tolerant. > > I'm not claiming that this is a problem, I'm reponding to other people's > claim that useing a global dictionary for a pack is a problem becouse if > something happens to that dictionary the whole pack is worthless by > pointing out that, if this is viewed as a real problem, it's easy to > solve. Let's not solve problems we do not have. I refuse to think about this problem further, before there are actually some hard numbers showing an improvement there. If the numbers do not show an improvement, we do not have that problem at all! Make a _global_ dictionary, optimize the heck out of it, _use_ that dictionary to repack a sizeable repository (I think linux-2.6.git should be enough for first tests), and tell the world about the size of the dictionary, the original pack, and the new pack. You would not need to implement this cleanly, just a hack to prove that this idea is worth following up. Ciao, Dscho ```