Re: [RFC] Packing large repositories
On Sat, 31 Mar 2007, Linus Torvalds wrote:
Show 7 quoted lines
> 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.
Show 14 quoted lines
> 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.
Nicolas Pitre <nico@cam.org>