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

From: Shawn Pearce <spearce@spearce.org>
Date: Jan 31, 2013, 17:14 UTC
Message-ID: <CAJo=hJtTYZg+1+RZVfEGTgOGzqxQbN1CLYWrvUp+WHKGxGwHMQ@mail.gmail.com>
In-Reply-To: <20130129091434.GA6975@sigill.intra.peff.net>

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. :-)

Show 6 quoted lines

> 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. :-)