Re: [RFC] Packing large repositories

[Nicolas Pitre <nico@cam.org>]

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