Re: [RFC] Packing large repositories

From: Junio C Hamano <junkio@cox.net>
Date: Mar 31, 2007, 20:54 UTC
Message-ID: <7vslbl8780.fsf@assigned-by-dhcp.cox.net>
In-Reply-To: <Pine.LNX.4.64.0703311033290.6730@woody.linux-foundation.org>

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

Show 9 quoted lines

> In other words, the 256-entry fan-out was meant to avoid the first eight 
> levels of binary lookup. But the thing is, we should be able to generally 
> do a *lot* better than any binary lookup by just doing a LINEAR SEARCH, 
> which is also more cache-friendly, and prefetches much better when it's 
> not in the cache.
> ...
>  - use newton-raphson to iterate closer. It should be a much faster way to 
>    find the rough area for the entry we're searching for than binary 
>    search. Two or three iterations should get us there, easily.

This is another egg of columbus moment that makes me feel it was worth to have been in git community ;-).

I like it.