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

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

Brandon Casey [off-list ref] writes:

quoted

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

quoted

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