Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive

From: Junio C Hamano <gitster@pobox.com>
Date: Dec 30, 2007, 21:49 UTC
Message-ID: <7vodc77t0o.fsf@gitster.siamese.dyndns.org>
In-Reply-To: <alpine.LFD.1.00.0712301150120.32517@woody.linux-foundation.org>

Linus Torvalds <torvalds@linux-foundation.org> writes:

Show 8 quoted lines

> On Sun, 30 Dec 2007, Junio C Hamano wrote:
>> 
>> With this patch, we actually see slight improvements in
>> execution time as well.  In the same partial kde repository
>> (3.0GB pack, 95MB idx; the numbers are from the same machine as
>> before, best of 5 runs):
>
> Ok, I tried this a year ago, and never got any real improvement.

Yes, I remember that one.

Show 6 quoted lines

> and I decided it wasn't worth it. Yours looks much better, and seems to 
> get a real performance improvement, so go for it, but I doubt that the 
> actual object lookup is really ever the main issue. I've never seen it 
> stand out in the real profiles, although if it is able to cut down on IO 
> (and your minor fault numbers are promising!), it might be more important 
> than I'd otherwise think.

The cost of the key comparison done in each round is insignificant compared to the actual cost of accessing the object data through zlib. The only potential performance benefit that could come from this patch to reduce the average number of rounds in the search is I/O reduction.

The only case I can think of that this may matter in real life is accessing only small number of objects in a history with a huge pack. Once you dig down the history deep enough to check enough number of objects inside a single process, you would need to touch every page of the mapped idx and the minor-fault gain rapidly diminishes.

Accessing only small number of objects in a huge history most often happens when building near the tip of the history (e.g. commit, rebase, merge), but these operations tend to deal with very young objects, often unpacked. We check pack first and then loose objects, so the search for young loose objects will benefit from the patch because the negative look-up to notice that they do not live in any pack also becomes cheaper, but I do not think it is such a big deal.