Compression and dictionaries

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> wrote:

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.

On 8/13/06, Shawn Pearce <spearce@spearce.org> 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.

A fixed dictionary could conceivably take 5-10% off the size of each entry.

Jon Smirl <jonsmirl@gmail.com> wrote:

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.
 

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.

On 8/14/06, Shawn Pearce <spearce@spearce.org> wrote:

BTW, kenel repo rapidly becomes "less than common load" for git ;)

On Mon, Aug 14, 2006 at 12:07:45AM -0400, Jon Smirl wrote:

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

Hi,

On Sun, 13 Aug 2006, Jon Smirl wrote:

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.

On 8/14/06, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:

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.

Hi,

On Mon, 14 Aug 2006, Jon Smirl wrote:

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.

I _think_ that it would not matter much. The deltas have a more important impact.

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

On 8/14/06, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:

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.

On Mon, 14 Aug 2006, Jon Smirl 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.

David Lang

David Lang wrote:

Or use some error-correcting code for storing dictionary.

Jakub Narebski wrote:

Error-correcting code?  We have sha1 hash to determine validity...

	Jeff

On Mon, 14 Aug 2006, Jeff Garzik 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.

David Lang

David Lang wrote:

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

On 8/14/06, David Lang <dlang@digitalinsight.com> 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.

On Mon, 14 Aug 2006, Jon Smirl wrote:

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

Hi,

On Mon, 14 Aug 2006, David Lang wrote:

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

On 8/14/06, Jon Smirl <jonsmirl@gmail.com> wrote:

will the old git installations, without the maps, still be able to decode the pack created this way?

Hi,

On Mon, 14 Aug 2006, Alex Riesen wrote:

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