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

From: Junio C Hamano <gitster@pobox.com>
Date: Jul 3, 2013, 20:22 UTC
Message-ID: <7v7gh7e6mh.fsf@alter.siamese.dyndns.org>
In-Reply-To: <51D479BA.1070207@nvidia.com>

Brandon Casey <bcasey@nvidia.com> writes:

Show 14 quoted lines

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

My repository git.git and Linus's kernel are not "normal". It did not matter so far to have O(n*m) when pushing to our histories.

The case that matters is for somebody to be pushing one (or a few) refs against a repository with many many refs, like pushing a review request to Gerrit instance, which I think Martin has in mind.