From: Junio C Hamano <gitster@pobox.com>
To: Brandon Casey <drafnel@gmail.com>
Cc: peff@peff.net, git@vger.kernel.org, mfick@codeaurora.org,
bcasey@nvidia.com
Subject: Re: [PATCH v2 w/prune index] remote.c: avoid O(m*n) behavior in match_push_refs
Date: Mon, 08 Jul 2013 09:12:37 -0700 [thread overview]
Message-ID: <7vmwpx1156.fsf@alter.siamese.dyndns.org> (raw)
In-Reply-To: <1373273919-32005-1-git-send-email-drafnel@gmail.com> (Brandon Casey's message of "Mon, 8 Jul 2013 01:58:39 -0700")
Brandon Casey <drafnel@gmail.com> writes:
> ...
> Using an index takes 41 ms longer, or roughly 7.8% longer.
>
> Jeff King measured a no-op push of a single ref into a remote repo
> with 370,000 refs:
>
> before after
> real 0m1.087s 0m1.156s
> user 0m1.344s 0m1.412s
> sys 0m0.288s 0m0.284s
>
> Using an index takes 69 ms longer, or roughly 6.3% longer.
>
> None of the measurements above required transferring any objects to
> the remote repository. If the push required transferring objects and
> updating the refs in the remote repository, the impact of preparing
> the search index would be even smaller.
>
> A similar operation is performed in the reverse direction when pruning
> using a matching or pattern refspec. Let's avoid O(m*n) behavior in
> the same way by lazily preparing an index on the local refs.
Thanks. Both the explanation and the code change makes sense to me.
Will queue.
prev parent reply other threads:[~2013-07-08 16:12 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
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 [this message]
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=7vmwpx1156.fsf@alter.siamese.dyndns.org \
--to=gitster@pobox.com \
--cc=bcasey@nvidia.com \
--cc=drafnel@gmail.com \
--cc=git@vger.kernel.org \
--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).