On Sat, 31 Mar 2007, Linus Torvalds wrote: > The thing is, I think the index-pack could be improved, but I think we can > get a bigger improvement from just being more intelligent about searching > than from actually needing to re-organize the pack. > > Here's a few clues: > - one of the fundamental rules about cryptographic hashes is that they > are *evenly*distributed* I was thinking about that too. > So here's a suggestion: > > - start finding a range using the 256-entry fan-out, exactly the way we > did for the binary search. It's cheap. We could probably avoid EVEN > THIS, and just do one more newton-raphson iteration more. But since we > have the data, we migth as well use it. After all, it really *is* just > a first approximation of newton-raphson, and while it uses only 8 bits > (and we could do better), at least it's an *exact* one. > > - 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. > > - do a linear search once you're close enough. I like that. Nicolas - 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