Re: [PATCH 09/16] documentation: add documentation for the bitmap format
- From
Shawn Pearce <spearce@spearce.org>
- Date
- Jul 7, 2013, 17:27 UTC
- Message-ID
- <CAJo=hJsUr1osy5rDZja1WBAgzczY5Yp0CJuLoAQs7J59PsX7Zw@mail.gmail.com>
- In-Reply-To
- <20130707094646.GA18120@sigill.intra.peff.net>
On Sun, Jul 7, 2013 at 2:46 AM, Jeff King <peff@peff.net> wrote:
Show 15 quoted lines
> On Mon, Jul 01, 2013 at 11:47:32AM -0700, Colby Ranger wrote: > >> > But I think we are comparing >> > apples to steaks here, Vincent is (rightfully) concerned about process >> > startup performance, whereas our timings were assuming the process was >> > already running. >> > >> >> I did some timing on loading the reverse index for the kernel and it >> is pretty slow (~1200ms). I just submitted a fix to do a bucket sort >> and reduced that to ~450ms, which is still slow but much better: > > On my machine, loading the kernel revidx in C git is about ~830ms. I > switched the qsort() call to a radix/bucket sort, and have it down to > ~200ms. So definitely much better,
This is a very nice reduction. pack-objects would benefit from it even without bitmaps. Since it doesn't require a data format change this is a pretty harmless patch to include in Git. We may later conclude caching the revidx is worthwhile, but until then a bucket sort doesn't hurt. :-)
Show 5 quoted lines
> though that still leaves a bit to be > desired for quick commands. E.g., "git rev-list --count A..B" should > become fairly instantaneous with bitmaps, but in many cases the revindex > loading will take longer than it would have to simply do the actual > traversal.
Yea, we don't know of a way around this. In a few cases the bitmap code in JGit is slower than the naive traversal, but these are only on small segments of history. I wonder if you could guess which algorithm to use by looking at the offsets of A and B using the idx file. If they are near each other in the pack, run the naive algorithm without bitmaps and revidx. If they are farther apart assume the bitmap would help more than traversal and use bitmap+revidx.
Working out what the correct "distance" should be before switching algorithms is hard. A and B could be megabytes apart in the pack but A could be B's grandparent and traversed in milliseconds. I wonder how often that is in practice, certainly if A and B are within a few hundred kilobytes of each other the naive traversal should be almost instant.