Re: [PATCH] RFC: git lazy clone proof-of-concept

["Jon Smirl" <jonsmirl@gmail.com>]

On 2/12/08, Linus Torvalds <torvalds@linux-foundation.org> wrote:
>
>
> On Tue, 12 Feb 2008, Linus Torvalds wrote:
> >
> >  (b) we compare each object to the "window-1" preceding objects, which is
> >      how I got the O(windowsize^2)
>
> That's not really true, of course. But my (broken and inexact) logic is
> that we get one cost multiplier from the number of objects, and one from
> the size of the objects.
>
> So *if* we have the situation of not limiting the window size, we
> basically have a big slowdown from raising the window in number of
> objects: not only do we get a slowdown from comparing more objects, we
> spend relatively more time comparing the *large* ones to begin with and
> having more of them just makes it even more skewed - when we hit a series
> of big blocks, the window will also contain more big blocks, so it kind of
> a double whammy.
>
> But I don't think calling it O(windowsize^2) is really correct. It's still
> O(windowsize), it's just that the purely "number-of-object" thing doesn't
> account for big objects being much more expensive to diff. So you really
> want to make the *memory* limiter the big one, because that's the one that
> actually approximates how much time you end up spending.
>
> So ignore that O(n^2) blather. It's not correct. What _is_ correct is that
> we want to aggressively limit memory size, because CPU cost goes up
> linearly not just with number of objects, but also super-linearly with
> size of the object ("super-linear" due to bad cache behavior and in worst
> case due to paging).


In the gcc case I wasn't running out memory. I believe was CPU bound
for an hour processing a single object chain with 2000 entries. That
sure doesn't feel like O(windowsize).

Maybe someone playing the the OO repo can stick in an appropriate
printf and see how many diffs are really being done just to make sure
they match what we think the number should be.


>
>                         Linus
>


-- 
Jon Smirl
jonsmirl@gmail.com