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

Linus Torvalds [off-list ref] writes:

On Sun, 30 Dec 2007, Junio C Hamano wrote:

quoted

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.

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.