Re: [PATCH 1/3] Lazily open pack index files on demand

[Nicolas Pitre <nico@cam.org>]

On Mon, 28 May 2007, Linus Torvalds wrote:

> On Sun, 27 May 2007, Nicolas Pitre wrote:
> > 
> > It helps irrespective of the number of pack files.  With the current 
> > binary search the lookup cost is O(log n).  With a Newton method this 
> > cost is almost O(1).
> 
> This is not true.
> 
> First off, when comparing O(logn) to O(1), with "n" being less than a 
> billion, they are pretty much exactly the same. Think of it this way: 
> O(logn) == O(9) == O(1), if you know that n < 10**9.

Agreed.

> Secondly, the cost of Newton isn't "almost O(1)". I don't know _what_ it 
> is (the rule of thumb with Newton-Raphson should be that the number of 
> significant correct digits in the answer doubles with each iteration: I 
> think that probably means that it should approximate O(loglog(n)), but I 
> haven't thought deeply about it.

Sure.  But given the reasoning you gave above for O(log N) being about 
the same as O(1) for a small enough N, I think that O(log log N) is even 
closer to O(1) in that regard.

> And the thing is, Newton-Raphson didn't actually speed anything up in my 
> tests. Sometimes it was better, sometimes it was worse, most of the time 
> it was in the noise.

OK I didn't remember the difference was so unconclusive.
The constant cost is certainly a big factor in the equation.

Maybe we didn't test with a big enough repo yet (big in the sense of 
number of objects) to see the variable cost actually dominate.

Did you try with the KDE repo at the time?  It has over 4M objects.
The binary search would require 14 itterations while the Newton search 
should take around 3 or 4 itterations if the log O(log N) esttimate is 
right.  Of course the evaluation of the next mid point is more costly 
with the Newton method.


Nicolas