Re: Newton-Raphson, was Re: Performance issue of 'git branch'
- From
Tony Finch <dot@dotat.at>
- Date
- Jul 23, 2009, 23:50 UTC
- Message-ID
- <alpine.LSU.2.00.0907240031470.12180@hermes-2.csi.cam.ac.uk>
- In-Reply-To
- <alpine.DEB.1.00.0907240114410.8306@pacific.mpi-cbg.de>
On Fri, 24 Jul 2009, Johannes Schindelin wrote:
Show 5 quoted lines
> > Think about it, absent any further information than "it is a hash, i.e. > distributed pretty equally in _any_ byte", even subsets of a sorted list > will me more or less linear. And assuming that they are linear is _still_ > your best bet.
The even distribution of the lower-order bytes is irrelevant. We're looking at the top 20-ish bits for a pack with a million-ish objects. The more you zoom in the less linear a sorted list of hashes will be, so assuming linearity at all scales is wrong. It's a bit like fractal mountains.
> There is no way to achieve [O(1) seeks], best thing you can hope for is > _expected_ O(1) (e.g. with a hashmap, with exponential worst case).
Of course it's expected. However the worst case is nowhere near exponential: it's linear because the second-order search is a linear pagewise scan. But I think in practice, the larger the pack the more that the randomization of the hash function will smooth out performance oddities. (Sorry, I don't know enough statistics to be able to say what the expected error of the linear interpolation is, though I expect it's a fairly simple formula.) For small packs the number of seeks is 1 anyway.
Tony.
-- f.anthony.n.finch <dot@dotat.at> http://dotat.at/ GERMAN BIGHT HUMBER: SOUTHWEST 5 TO 7. MODERATE OR ROUGH. SQUALLY SHOWERS. MODERATE OR GOOD.