From: Jacob Vosmaer <jacob@gitlab.com>
To: Taylor Blau <me@ttaylorr.com>
Cc: Git Mailing List <git@vger.kernel.org>, Jeff King <peff@peff.net>
Subject: Re: [PATCH 2/2] ls-refs.c: traverse longest common ref prefix
Date: Wed, 20 Jan 2021 12:00:56 +0100 [thread overview]
Message-ID: <CADMWQoO+163mJBXctb+GHFebGCbKQRPAtMJ676_GwfEt-BedAw@mail.gmail.com> (raw)
In-Reply-To: <fb8681d12864d724108c524834f9498d91e270e6.1611080326.git.me@ttaylorr.com>
On Tue, Jan 19, 2021 at 7:19 PM Taylor Blau <me@ttaylorr.com> wrote:
>
> ls-refs performs a single revision walk over the whole ref namespace,
> and sends ones that match with one of the given ref prefixes down to the
> user.
>
> This can be expensive if there are many refs overall, but the portion of
> them covered by the given prefixes is small by comparison.
>
> To attempt to reduce the difference between the number of refs
> traversed, and the number of refs sent, only traverse references which
> are in the longest common prefix of the given prefixes. This is very
> reminiscent of the approach taken in b31e2680c4 (ref-filter.c: find
> disjoint pattern prefixes, 2019-06-26) which does an analogous thing for
> multi-patterned 'git for-each-ref' invocations.
>
> The only difference here is that we are operating on ref prefixes, which
> do not necessarily point to a single reference. That is just fine, since
> all we care about is finding the longest common prefix among prefixes
> which can be thought of as refspecs for our purposes here.
>
> Similarly, for_each_fullref_in_prefixes may return more results than the
> caller asked for (since the longest common prefix might match something
> that a longer prefix in the same set wouldn't match) but
> ls-refs.c:send_ref() discards such results.
>
> The code introduced in b31e2680c4 is resilient to stop early (and
> return a shorter prefix) when it encounters a metacharacter (as
> mentioned in that patch, there is some opportunity to improve this, but
> nobody has done it).
>
> There are two remaining small items in this patch:
>
> - If no prefixes were provided, then implicitly add the empty string
> (which will match all references).
>
> - Since we are manually munging the prefixes, make sure that we
> initialize it ourselves (previously this wasn't necessary since the
> first strvec_push would do so).
>
> Original-patch-by: Jacob Vosmaer <jacob@gitlab.com>
> Signed-off-by: Taylor Blau <me@ttaylorr.com>
> ---
> ls-refs.c | 6 +++++-
> 1 file changed, 5 insertions(+), 1 deletion(-)
>
> diff --git a/ls-refs.c b/ls-refs.c
> index a1e0b473e4..eaaa36d0df 100644
> --- a/ls-refs.c
> +++ b/ls-refs.c
> @@ -90,6 +90,7 @@ int ls_refs(struct repository *r, struct strvec *keys,
> struct ls_refs_data data;
>
> memset(&data, 0, sizeof(data));
> + strvec_init(&data.prefixes);
>
> git_config(ls_refs_config, NULL);
>
> @@ -109,7 +110,10 @@ int ls_refs(struct repository *r, struct strvec *keys,
> die(_("expected flush after ls-refs arguments"));
>
> head_ref_namespaced(send_ref, &data);
> - for_each_namespaced_ref(send_ref, &data);
> + if (!data.prefixes.nr)
> + strvec_push(&data.prefixes, "");
The old code, with for_each_namespaced_ref, would walk
"${NAMESPACE}refs/". The new code would walk "${NAMESPACE}" because
we're pushing "" onto data.prefixes. So if there is anything in the
namespace that does not start with "refs/" it will get yielded.
Does that matter?
> + for_each_fullref_in_prefixes(get_git_namespace(), data.prefixes.v,
> + send_ref, &data, 0);
> packet_flush(1);
> strvec_clear(&data.prefixes);
> return 0;
> --
> 2.30.0.138.g6d7191ea01
next prev parent reply other threads:[~2021-01-20 11:51 UTC|newest]
Thread overview: 35+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-01-19 14:42 [PATCH 0/1] ls-refs.c: minimize number of refs visited Jacob Vosmaer
2021-01-19 14:42 ` [PATCH 1/1] " Jacob Vosmaer
2021-01-19 16:12 ` Taylor Blau
2021-01-19 17:42 ` Jacob Vosmaer
2021-01-19 18:19 ` [PATCH 0/2] ls-refs: only traverse through longest common ref prefix Taylor Blau
2021-01-19 18:19 ` [PATCH 1/2] refs: expose 'for_each_fullref_in_prefixes' Taylor Blau
2021-01-19 18:19 ` [PATCH 2/2] ls-refs.c: traverse longest common ref prefix Taylor Blau
2021-01-19 23:09 ` Jeff King
2021-01-19 23:52 ` Taylor Blau
2021-01-20 0:08 ` Jeff King
2021-01-20 11:00 ` Jacob Vosmaer [this message]
2021-01-20 16:04 ` [PATCH v2 0/3] ls-refs: traverse prefixes of disjoint "ref-prefix" sets Taylor Blau
2021-01-20 16:04 ` [PATCH v2 1/3] refs: expose 'for_each_fullref_in_prefixes' Taylor Blau
2021-01-20 19:56 ` Jeff King
2021-01-20 20:12 ` Taylor Blau
2021-01-23 2:59 ` Junio C Hamano
2021-01-25 1:35 ` Taylor Blau
2021-01-20 16:04 ` [PATCH v2 2/3] ls-refs.c: initialize 'prefixes' before using it Taylor Blau
2021-01-20 19:58 ` Jeff King
2021-01-20 20:13 ` Taylor Blau
2021-01-20 21:50 ` Jacob Vosmaer
2021-01-20 16:04 ` [PATCH v2 3/3] ls-refs.c: traverse prefixes of disjoint "ref-prefix" sets Taylor Blau
2021-01-23 17:55 ` [PATCH v2 0/3] ls-refs: " Junio C Hamano
2021-01-19 19:09 ` [PATCH 1/1] ls-refs.c: minimize number of refs visited Taylor Blau
2021-01-19 21:59 ` Jeff King
2021-01-19 22:15 ` Jeff King
2021-01-19 22:23 ` Taylor Blau
2021-01-19 22:52 ` Jeff King
2021-01-19 22:59 ` Jeff King
2021-01-19 23:02 ` Taylor Blau
2021-01-19 22:53 ` Jeff King
2021-01-19 23:00 ` Taylor Blau
2021-01-19 23:11 ` Jeff King
2021-01-20 10:40 ` Jacob Vosmaer
2021-01-20 10:44 ` Jacob Vosmaer
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
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CADMWQoO+163mJBXctb+GHFebGCbKQRPAtMJ676_GwfEt-BedAw@mail.gmail.com \
--to=jacob@gitlab.com \
--cc=git@vger.kernel.org \
--cc=me@ttaylorr.com \
--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.
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 NNTP newsgroup(s).