From: Junio C Hamano Date: Sat, 31 Mar 2007 20:54:07 GMT Subject: Re: [RFC] Packing large repositories Message-ID: <7vslbl8780.fsf@assigned-by-dhcp.cox.net> In-Reply-To: Linus Torvalds 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.