Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list

From: Brandon Casey <bcasey@nvidia.com>
Date: Jul 3, 2013, 19:21 UTC
Message-ID: <51D479BA.1070207@nvidia.com>
In-Reply-To: <7vhagbfpwz.fsf@alter.siamese.dyndns.org>

On 7/3/2013 11:40 AM, Junio C Hamano wrote:

Show 13 quoted lines

> Brandon Casey <drafnel@gmail.com> writes:
> 
>> Right.  For repos with few refs on either side, I don't think there
>> will be any measurable difference.  When pushing a single ref to a
>> repo with a very large number of refs, we will see a very small net
>> loss for the time required to prepare the string list (which grows
>> linearly with the number of remote refs).  After 2 or 3 refs, we
>> should see a net gain.
>>
>> So we're really just improving our worst case performance here.
> 
> ... by penalizing the common case by how much?  If it is not too
> much, then this obviously would be a good change.

For something the size of the git repo, 5 branches, and pushing with matching refspecs, I can't measure any difference. The fastest time I record with or without this patch is the same:

   $ time git push -n
   real    0m0.178s
   user    0m0.020s
   sys     0m0.008s

Ditto, when only pushing a single branch. Preparing the string list for a repo with a "normal" number of refs has very little overhead.

When the remote side has very many refs, then there is a small penalty when the local side is pushing very few refs. But still, the penalty is small.

My measurements for pushing from a repo with a single local branch into my 100000+ ref repo showed <10% hit and the numbers were in the tens of milliseconds.

        before    after
real    0m0.525s  0m0.566s
user    0m0.243s  0m0.279s
sys     0m0.075s  0m0.099s

Show 6 quoted lines

>> ...  But, I don't see a down side to doing the lazy prepare in
>> the other loop too, and in fact, it looks like we may be able to avoid
>> building the string list when only explicit refspecs are used.  So,
>> yeah, we should lazy build in both loops.
> 
> OK, so will see a reroll sometime?

Yeah, I'll reroll.

-Brandon