{"thread":{"id":"8347","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","startedAt":"2007-05-29T00:09:49Z","lastAt":"2007-05-29T03:26:42Z","messageCount":2,"participants":["linux@horizon.com","Linus Torvalds"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"43531","messageId":"20070529000949.28007.qmail@science.horizon.com","threadId":"8347","inReplyTo":null,"subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2007-05-29T00:09:49Z","receivedAt":"2007-05-29T00:09:49Z","isPatch":true,"sender":{"key":"linux@horizon.com","avatar":null},"body":"> First off, when comparing O(logn) to O(1), with \"n\" being less than a \n> billion, they are pretty much exactly the same. Think of it this way: \n> O(logn) == O(9) == O(1), if you know that n < 10**9.\n\nWell, binary searches mean binary logarithms, so O(log n) = O(30).\nStill, pretty low.\n\n> Secondly, the cost of Newton isn't \"almost O(1)\". I don't know _what_ it \n> is (the rule of thumb with Newton-Raphson should be that the number of \n> significant correct digits in the answer doubles with each iteration: I \n> think that probably means that it should approximate O(loglog(n)), but I \n> haven't thought deeply about it.\n\nExcellent intuition!  The algorithm is most commonly known in the computer\nscience literature as \"interpolation search\" and it does indeed take O(log\nlog n) time for uniformly distributed data, which is a good assumption\nfor SHA-1 hashes.\n\nOf course, for n = 10**9, log(n) is 30 and log log n is 5.\nMore to the point, for n = 10**6, log(n) is 20 and log(log(n)) is still 5.\n\nEven losing a constant factor of 2, it still seems like it might offer a\nfactor-of-2 speedup for large repositories.\n"},{"id":"43539","messageId":"alpine.LFD.0.98.0705282014480.26602@woody.linux-foundation.org","threadId":"8347","inReplyTo":"20070529000949.28007.qmail@science.horizon.com","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-05-29T03:26:42Z","receivedAt":"2007-05-29T03:26:42Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 28 May 2007, linux@horizon.com wrote:\n> \n> Even losing a constant factor of 2, it still seems like it might offer a \n> factor-of-2 speedup for large repositories.\n\nWell, not so much according to the numbers I had.\n\nYes, SHA-1's are very nicely distributed on a larger scale, but on a \n_small_ scale they aren't. \n\nSo you end up being able to get very good initial guesses for the first \nfew iterations, but once you get \"close enough\", you can't do anything at \nall, and then you're actually worse off.\n\nAlso, please do realize that the binary search is actually a *smart* \nbinary search, which does a radix-256 fan-out at the beginning, getting \nrid of the first 8 levels of searching for free.\n\nThe Newton-Raphson thing can do that too (and in my trial patch, did), but \nit means that you actually get rid of just the initial guess (the one that \nworked the best!) and you still have the problem that once you get close \nenough, the distribution at a local level is not at all nice and linear.\n\nSo what I did with my patch (you can find it in the archives - search for \nNewton-Raphson, I'd say about 3 months ago) was to do three cycles of \napproximating, and then a linear search. The linear search has good cache \nbehaviour, so it's not as horrid as it might sound, but for some numbers I \ndid, my approximate thing would hit on the exact first entry about half \nthe time, but would have to walk up to ~20 entries occasionally.\n\nWhich meant that the binary search (with the initial radix-256 fan-out) \nactually mostly outperformed the Newton-Raphson thing.\n\nAlso, object lookup is certainly noticeable, but the biggest cost of it is \nthe cache misses, and even then it's not really _that_ noticeable. And \nit's really neither slow nor stupid as it is.\n\nSo I'd love to see somebody try to do a _proper_ apprixmation of Newton- \nRaphson, not the quick hack I did. But I think factor-of-two is actually \noptimistic, even for pretty large repos. And it would have to be no worse \nthan what we have now for average-sized ones.\n\n(And object lookup time is generally not the dominant cost, so while it's \nnoticeable, cutting it down by even a whole 50% isn't going to speed up \nany normal git operations by more than a couple of percent.. Generating \ndiffs in particular is a much more costly op for things like \"git blame\")\n\n\t\tLinus\n"}]}