Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules

From: Jens Lehmann <jens.lehmann@web.de>
Date: Sep 14, 2011, 18:26 UTC
Message-ID: <4E70F1BD.70804@web.de>
In-Reply-To: <4E6FB05C.6010202@web.de>

Am 13.09.2011 21:34, schrieb Jens Lehmann:

Show 15 quoted lines

> Am 12.09.2011 22:21, schrieb Junio C Hamano:
>> Jeff King <peff@peff.net> writes:
>>
>>> Instead, this patch structures the code like this:
>>
>> Yup, I agree that's the right way to do the other half of the issue.
> 
> Ack from me too! I tested it on the repo with 3k refs and the time went
> down from 142s to 1s (when applied to 3793ac56b4, as later versions of
> master contain my other half which would skip Peff's code).
> 
> On current master including my other half this takes 0.90s, while running
> with Peff's code on top of 3793ac56b4 it takes .96s. That is 6 hundreds
> of a second (7%) extra for not having to worry if one must run "git fetch
> --recurse-submodules" or not.

Just for the record: Martin Fick was so kind to run Peff's fix (without my half) on his 100k refs repo that showed this regression. Here are the results of some test runs:

 1.7.7.rc0.189.gab72a

    10m8.133s  9m7.971s  8m16.600s 13m57.821s
     8m34.974s 8m41.527s

 1.7.7.rc0.189.gab72a  --no-recurse-submodules

    10m43.833s  7m41.283s 8m17.889s  8m4.549s
    8m12.668s  7m59.180s

The fastest runs are 8% apart, which is pretty much the same slowdown as in the 3k ref repo. Looks like we do have O(n) now :-)