git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
From: Brandon Casey <bcasey@nvidia.com>
To: Jeff King <peff@peff.net>
Cc: Junio C Hamano <gitster@pobox.com>,
	Brandon Casey <drafnel@gmail.com>,
	"git@vger.kernel.org" <git@vger.kernel.org>,
	Martin Fick <mfick@codeaurora.org>
Subject: Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list
Date: Wed, 3 Jul 2013 13:05:09 -0700	[thread overview]
Message-ID: <51D483F5.6020702@nvidia.com> (raw)
In-Reply-To: <20130703190047.GA349@sigill.intra.peff.net>

On 7/3/2013 12:00 PM, Jeff King wrote:
> On Wed, Jul 03, 2013 at 11:40:12AM -0700, 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.
> 
> I don't think by much. If we have "m" local refs to push and "n" remote
> refs, right now we do O(m*n) work ("m" linear searches of the remote
> namespace). With Brandon's patch, we do O(n log n) to build the index,

Whoops, yes, n log n, not linear as I misspoke.

> plus O(m log n) for lookups.
> 
> So our break-even point is basically m = log n, and for m smaller than
> that, we do more work building the index. Your absolute biggest
> difference would be pushing a single ref to a repository with a very
> large number of refs.
> 
> Here are the timings before and after Brandon's patch for pushing a
> no-op single ref from a normal repo to one with 370K refs (the same
> pathological repo from the upload-pack tests). Times are
> best-of-five.
> 
>              before     after
>      real    0m1.087s   0m1.156s
>      user    0m1.344s   0m1.412s
>      sys     0m0.288s   0m0.284s
> 
> So it's measurable, but even on a pathological worst-case, we're talking
> about 6% slowdown.

That agrees with what I've observed.

> You could try to guess about when to build the index based on the size
> of "m" and "n", but I suspect you'd waste more time calculating whether
> to build the index than you would simply building it in most cases.

I agree, I don't think it's worth trying to guess when to build an index
and when to just perform linear searches.  If building the payload for
each element in the index was more expensive than just assigning to a
pointer, than it could be worth it, but we're not, so I don't think it
is worth it.

-Brandon

  reply	other threads:[~2013-07-03 20:05 UTC|newest]

Thread overview: 12+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2013-07-02 23:53 [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list Brandon Casey
2013-07-03  6:23 ` Jeff King
2013-07-03 18:12   ` Brandon Casey
2013-07-03 18:40     ` Junio C Hamano
2013-07-03 19:00       ` Jeff King
2013-07-03 20:05         ` Brandon Casey [this message]
2013-07-03 19:21       ` Brandon Casey
2013-07-03 20:22         ` Junio C Hamano
2013-07-08  7:02           ` [PATCH v2] remote.c: avoid O(m*n) behavior in match_push_refs Brandon Casey
2013-07-08  7:50             ` Jeff King
2013-07-08  8:58               ` [PATCH v2 w/prune index] " Brandon Casey
2013-07-08 16:12                 ` Junio C Hamano

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=51D483F5.6020702@nvidia.com \
    --to=bcasey@nvidia.com \
    --cc=drafnel@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=mfick@codeaurora.org \
    --cc=peff@peff.net \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).