Re: Compression and dictionaries

From: Shawn Pearce <spearce@spearce.org>
Date: Aug 14, 2006, 03:56 UTC
Message-ID: <20060814035603.GB18667@spearce.org>
In-Reply-To: <9e4733910608132037t4297c3bbq9b0cd6ebaa03b979@mail.gmail.com>

Jon Smirl <jonsmirl@gmail.com> 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.