Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx> 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. - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html