Actually that's fewer memory accesses on average. If you look at the maximum number of memory accesses the crossover is around 2^13.
In git, there's a 256-entry meta-index which reduces the number of probes in a bisection search by 8, but is probably less useful than a single iteration of the secant method when N > 2^16. Each index entry is 24 bytes, so 168 of them fit in a page. This implies that git won't see a clear benefit from the secant method until you get packs of 350 million objects, which is not really feasible when pack files are limited to 4GB :-) But this does explain why it isn't a win when large repositories currently have one or two million objects.
no subject
Date: 2009-07-31 11:30 (UTC)In git, there's a 256-entry meta-index which reduces the number of probes in a bisection search by 8, but is probably less useful than a single iteration of the secant method when N > 2^16. Each index entry is 24 bytes, so 168 of them fit in a page. This implies that git won't see a clear benefit from the secant method until you get packs of 350 million objects, which is not really feasible when pack files are limited to 4GB :-) But this does explain why it isn't a win when large repositories currently have one or two million objects.