Re: [RFC] Packing large repositories

[Junio C Hamano <junkio@cox.net>]

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

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