Re: [RFC] pack-objects: compression level for non-blobs

On Sun, Dec 30, 2012 at 07:53:48PM +0700, Nguyen Thai Ngoc Duy wrote:

Agreed. The current code has a 4-byte magic, followed by a 4-byte version number, followed by a 4-byte record size[1]. Then the data, followed by the pack sha1, followed by a sha1 of all of the preceding data. So you can verify the validity of any cache file (both its checksum, and that it matches the right packfile), just as you can with a ".idx" file.

[1] Probably the magic and version should be per-file-type, and the
    record size should be implicit from that; right now I make
    assumptions about what is in the files based on their names, but
    that is not part of the checksum.

Yeah, in the long run that may work. The steps I figured were:

  1. Optional, external command. Let people experiment.

  2. Once it has proven itself, run the command from index-pack by
     default (or with a config option).

  3. If it turns out too slow, move the generation directly into the
     index-pack process.

The current iteration does not seem all that slow, but that is because I am mostly picking static data out of the commits. So I have to load the commits, and that's it. But something like reachability might be more expensive (OTOH, it will always be more expensive, whether we have the objects in memory or not).

Right. My implementation is very similar to what Shawn said there. I.e., the timestamps file is literally 4 bytes times the number of commits. The parents file is 40 bytes per commit (2 parents, with a marker to indicate "more or less than 2"), though a lot of it is zero bytes.

Some alternatives I'm thinking about are:

  1. Using non-fixed-size records, which would allow trivial compression
     of entries like null sha1s. This would mean adding a separate
     lookup table, though, mapping sha1s to offsets. Still, even a
     32-bit offset is only 4 bytes per commit. If it meant dropping 40
     bytes of zeroes from the 2nd parent field out of half of all
     commits, that would be a win space-wise. It would be a
     double-indirect lookup, but it's constant effort, and only two page
     hits (which would be warm after the first lookup anyway).

  2. Storing offsets to objects in the packfile rather than their sha1s.
     This would save a lot of space, but would mean we couldn't refer to
     parents outside of the pack, but that may be OK. This is an
     optimization, and the case we want to target is a fully (or mostly)
     packed repo. It's OK to have the lookup fail and fallback to
     accessing the object.

  3. Dropping the "commits" file and just using the pack-*.idx as the
     index. The problem is that it is sparse in the commit space. So
     just naively storing 40 bytes per entry is going to waste a lot of
     space. If we had a separate index as in (1) above, that could be
     dropped to (say) 4 bytes of offset per object. But still, right now
     the commits file for linux-2.6 is about 7.2M (20 bytes times ~376K
     commits). There are almost 3 million total objects, so even storing
     4 bytes per object is going to be worse.

  4. Making a new index version that stores the sha1s separated by type.
     This means we can piggy-back on the regular index to get a packed
     list of just commits. But it also means that regular sha1 lookups
     of the objects have to look in several places (unless the caller
     annotates the call to read_sha1_object with "I am expecting this
     sha1 to be a commit"). And of course it means bumping the index
     version, which is a pain. The external index means it can be
     completely optional on top of the current index/pack.

I do not care too much about the cost of running merge on a large working tree. Of course it's better to make our optimizations as generally applicable as possible, but there is a lot of other work going on in a merge. The really painful, noticeable, repetitive bits right now are:

  1. Running git-prune.

  2. Creating a pack from git-upload-pack.

Which are both just reachability problems. Something like "git log -- <pathspec>" would also be helped by packv4-ish tree access patterns, though, but not by reachability bitmaps. And that may be something worth caring about.

I hadn't thought about that. But yeah, because of the optional, external nature, there's no reason you couldn't have extra bitmap sets for specialized situations.

-Peff