Re: [PATCH/RFC 0/6] commit caching

[Shawn Pearce <spearce@spearce.org>]

On Tue, Jan 29, 2013 at 1:14 AM, Jeff King <peff@peff.net> wrote:
> This is the cleaned-up version of the commit caching patches I mentioned
> here:
>
>   http://article.gmane.org/gmane.comp.version-control.git/212329
...
> The short of it is that for an extra 31M of disk
> space (~4%), I get a warm-cache speedup for "git rev-list --all" of
> ~4.2s to ~0.66s.

I have to admit, this is a nice gain. I don't think users often dig
through all commits to the root but I can see how this might improve
git log with a path filter.

> Coupled with using compression level 0 for trees (which do not compress
> well at all, and yield only a 2% increase in size when left
> uncompressed), my "git rev-list --objects --all" time drops from ~40s to
> ~25s.

This uhm.... is nice?

But consider reachability bitmaps. ~40s to ~80ms. :-)

> Perf reveals that we're spending most of the remaining time in
> lookup_object. I've spent a fair bit of time trying to optimize that,
> but with no luck; I think it's fairly close to optimal. The problem is
> just that we call it a very large number of times, since it is the
> mechanism by which we recognize that we have already processed each
> sha1.

Yup. I have also futzed with the one in JGit for quite a while now. I
pull some tricks there like making it a 2 level directory to reduce
the need to find a contiguous array of 8M entries when processing the
Linux kernel, and I try to preallocate the first level table based on
the number of objects in pack-*.idx files. But the bottleneck is
basically the cache lookups and hits, these happen like 100M times on
2M objects, because its every link in nearly every tree.

Reachability bitmaps basically let you skip this. So they go fast. But
I have another that you could try.

If we modified pack-objects' delta compressor for tree objects to only
generate delta instructions at tree record boundaries, a delta-encoded
tree can be processed without inflating the full content of that tree.
Because of the way deltas are created, "most" tree deltas should have
their delta base scanned by the object traversal before the delta is
considered. This means the tree delta just needs to consider the much
smaller records that are inserted into the base. We know these are
different SHA-1s than what was there before, so they are more likely
to be new to the lookup_object table.

So the --objects traversal algorithm can change to get the delta base
SHA-1 and raw tree delta from the pack storage. Perform a
lookup_object on the base to see if it has been scanned. If it has,
just scan the delta insert instructions. If the base has not yet been
scanned, inflate the tree to its normal format and scan the entire
tree.

This is an approximation of what Nico and I were talking about doing
for pack v4. But doesn't require a file format change. :-)