Re: [PATCH 09/16] documentation: add documentation for the bitmap format

From: Jeff King <peff@peff.net>
Date: Jul 7, 2013, 09:46 UTC
Message-ID: <20130707094646.GA18120@sigill.intra.peff.net>
In-Reply-To: <CAFFbUKKm89n0HG6xUhYMLs_yjRJ8n0jFtOEEN=vXxJfWKLx5FA@mail.gmail.com>

On Mon, Jul 01, 2013 at 11:47:32AM -0700, Colby Ranger wrote:

Show 9 quoted lines

> > 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, 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.

-Peff