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

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: May 28, 2007, 16:22 UTC
Message-ID: <alpine.LFD.0.98.0705280907290.26602@woody.linux-foundation.org>
In-Reply-To: <alpine.LFD.0.99.0705271929480.3366@xanadu.home>

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.

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.

But regardless, we end up testing "a few" values. Both for the binary search and for Newton-Raphson.

So every time you talk about O-notation, you should also consider the constant costs, especially if the function in question is a slow-changing one (ie when we start talking O(N**3) we can start ignoring the constants. With O(logn), you sure as hell cannot!)

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.

Now, I'm sure the thing could be tweaked. Maybe I didn't do a very good job at my initial implementation. It was a quick hack. But before somebody makes a better one and actually shows better performance, I'd say that the jury is still out.

		Linus