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

[Brandon Casey <bcasey@nvidia.com>]

On 7/3/2013 11:40 AM, Junio C Hamano wrote:
> 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

>> ...  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