Git Mailing List Archive mirror
 help / color / mirror / Atom feed
From: Taylor Blau <me@ttaylorr.com>
To: git@vger.kernel.org
Cc: Chris Torek <chris.torek@gmail.com>,
	Derrick Stolee <derrickstolee@github.com>,
	Jeff King <peff@peff.net>, Junio C Hamano <gitster@pobox.com>,
	Patrick Steinhardt <ps@pks.im>
Subject: [PATCH v3 15/16] upload-pack.c: avoid enumerating hidden refs where possible
Date: Wed, 7 Jun 2023 06:42:07 -0400	[thread overview]
Message-ID: <014243ebe6586313b38fe0eb2a57941b27131423.1686134440.git.me@ttaylorr.com> (raw)
In-Reply-To: <cover.1686134440.git.me@ttaylorr.com>

In a similar fashion as a previous commit, teach `upload-pack` to avoid
enumerating hidden references where possible.

Note, however, that there are certain cases where cannot avoid
enumerating even hidden references, in particular when either of:

  - `uploadpack.allowTipSHA1InWant`, or
  - `uploadpack.allowReachableSHA1InWant`

are set, corresponding to `ALLOW_TIP_SHA1` and `ALLOW_REACHABLE_SHA1`,
respectively.

When either of these bits are set, upload-pack's `is_our_ref()` function
needs to consider the `HIDDEN_REF` bit of the referent's object flags.
So we must visit all references, including the hidden ones, in order to
mark their referents with the `HIDDEN_REF` bit.

When neither `ALLOW_TIP_SHA1` nor `ALLOW_REACHABLE_SHA1` are set, the
`is_our_ref()` function considers only the `OUR_REF` bit, and not the
`HIDDEN_REF` one. `OUR_REF` is applied via `mark_our_ref()`, and only
to objects at the tips of non-hidden references, so we do not need to
visit hidden references in this case.

When neither of those bits are set, `upload-pack` can potentially avoid
enumerating a large number of references. In the same example as a
previous commit (linux.git with one hidden reference per commit,
"refs/pull/N"):

    $ printf 0000 >in
    $ hyperfine --warmup=1 \
      'git -c transfer.hideRefs=refs/pull upload-pack . <in' \
      'git.compile -c transfer.hideRefs=refs/pull -c uploadpack.allowTipSHA1InWant upload-pack . <in' \
      'git.compile -c transfer.hideRefs=refs/pull upload-pack . <in'
    Benchmark 1: git -c transfer.hideRefs=refs/pull upload-pack . <in
      Time (mean ± σ):     406.9 ms ±   1.1 ms    [User: 357.3 ms, System: 49.5 ms]
      Range (min … max):   405.7 ms … 409.2 ms    10 runs

    Benchmark 2: git.compile -c transfer.hideRefs=refs/pull -c uploadpack.allowTipSHA1InWant upload-pack . <in
      Time (mean ± σ):     406.5 ms ±   1.3 ms    [User: 356.5 ms, System: 49.9 ms]
      Range (min … max):   404.6 ms … 408.8 ms    10 runs

    Benchmark 3: git.compile -c transfer.hideRefs=refs/pull upload-pack . <in
      Time (mean ± σ):       4.7 ms ±   0.2 ms    [User: 0.7 ms, System: 3.9 ms]
      Range (min … max):     4.3 ms …   6.1 ms    472 runs

    Summary
      'git.compile -c transfer.hideRefs=refs/pull upload-pack . <in' ran
       86.62 ± 4.33 times faster than 'git.compile -c transfer.hideRefs=refs/pull -c uploadpack.allowTipSHA1InWant upload-pack . <in'
       86.70 ± 4.33 times faster than 'git -c transfer.hideRefs=refs/pull upload-pack . <in'

As above, we must visit every reference when
uploadPack.allowTipSHA1InWant is set. But when it is unset, we can visit
far fewer references.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 upload-pack.c | 33 +++++++++++++++++++++++++++------
 1 file changed, 27 insertions(+), 6 deletions(-)

diff --git a/upload-pack.c b/upload-pack.c
index 99d216938c..366a101d8d 100644
--- a/upload-pack.c
+++ b/upload-pack.c
@@ -602,11 +602,32 @@ static int get_common_commits(struct upload_pack_data *data,
 	}
 }
 
+static int allow_hidden_refs(enum allow_uor allow_uor)
+{
+	return allow_uor & (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1);
+}
+
+static void for_each_namespaced_ref_1(each_ref_fn fn,
+				      struct upload_pack_data *data)
+{
+	/*
+	 * If `data->allow_uor` allows fetching hidden refs, we need to
+	 * mark all references (including hidden ones), to check in
+	 * `is_our_ref()` below.
+	 *
+	 * Otherwise, we only care about whether each reference's object
+	 * has the OUR_REF bit set or not, so do not need to visit
+	 * hidden references.
+	 */
+	if (allow_hidden_refs(data->allow_uor))
+		for_each_namespaced_ref(NULL, fn, data);
+	else
+		for_each_namespaced_ref(data->hidden_refs.v, fn, data);
+}
+
 static int is_our_ref(struct object *o, enum allow_uor allow_uor)
 {
-	int allow_hidden_ref = (allow_uor &
-				(ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1));
-	return o->flags & ((allow_hidden_ref ? HIDDEN_REF : 0) | OUR_REF);
+	return o->flags & ((allow_hidden_refs(allow_uor) ? HIDDEN_REF : 0) | OUR_REF);
 }
 
 /*
@@ -855,7 +876,7 @@ static void deepen(struct upload_pack_data *data, int depth)
 		 * marked with OUR_REF.
 		 */
 		head_ref_namespaced(check_ref, data);
-		for_each_namespaced_ref(NULL, check_ref, data);
+		for_each_namespaced_ref_1(check_ref, data);
 
 		get_reachable_list(data, &reachable_shallows);
 		result = get_shallow_commits(&reachable_shallows,
@@ -1386,7 +1407,7 @@ void upload_pack(const int advertise_refs, const int stateless_rpc,
 		if (advertise_refs)
 			data.no_done = 1;
 		head_ref_namespaced(send_ref, &data);
-		for_each_namespaced_ref(NULL, send_ref, &data);
+		for_each_namespaced_ref_1(send_ref, &data);
 		if (!data.sent_capabilities) {
 			const char *refname = "capabilities^{}";
 			write_v0_ref(&data, refname, refname, null_oid());
@@ -1400,7 +1421,7 @@ void upload_pack(const int advertise_refs, const int stateless_rpc,
 		packet_flush(1);
 	} else {
 		head_ref_namespaced(check_ref, &data);
-		for_each_namespaced_ref(NULL, check_ref, &data);
+		for_each_namespaced_ref_1(check_ref, &data);
 	}
 
 	if (!advertise_refs) {
-- 
2.41.0.16.g26cd413590


  parent reply	other threads:[~2023-06-07 10:42 UTC|newest]

Thread overview: 149+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-05-08 21:59 [PATCH 00/15] refs: implement skip lists for packed backend Taylor Blau
2023-05-08 21:59 ` [PATCH 01/15] refs.c: rename `ref_filter` Taylor Blau
2023-05-08 21:59 ` [PATCH 02/15] ref-filter.h: provide `REF_FILTER_INIT` Taylor Blau
2023-05-08 21:59 ` [PATCH 03/15] ref-filter: clear reachable list pointers after freeing Taylor Blau
2023-05-08 21:59 ` [PATCH 04/15] ref-filter: add ref_filter_clear() Taylor Blau
2023-05-08 22:29   ` Junio C Hamano
2023-05-08 22:33     ` Taylor Blau
2023-05-09 15:14   ` Patrick Steinhardt
2023-05-09 19:11     ` Taylor Blau
2023-05-08 21:59 ` [PATCH 05/15] ref-filter.c: parameterize match functions over patterns Taylor Blau
2023-05-08 22:36   ` Junio C Hamano
2023-05-09 20:13     ` Taylor Blau
2023-05-08 21:59 ` [PATCH 06/15] builtin/for-each-ref.c: add `--exclude` option Taylor Blau
2023-05-08 23:22   ` Junio C Hamano
2023-05-09 20:22     ` Taylor Blau
2023-05-08 22:00 ` [PATCH 07/15] refs: plumb `exclude_patterns` argument throughout Taylor Blau
2023-05-09 15:14   ` Patrick Steinhardt
2023-05-09 20:23     ` Taylor Blau
2023-05-08 22:00 ` [PATCH 08/15] refs/packed-backend.c: refactor `find_reference_location()` Taylor Blau
2023-05-08 23:56   ` Junio C Hamano
2023-05-09 20:29     ` Taylor Blau
2023-05-08 22:00 ` [PATCH 09/15] refs/packed-backend.c: implement skip lists to avoid excluded pattern(s) Taylor Blau
2023-05-09  0:10   ` Chris Torek
2023-05-09 20:39     ` Taylor Blau
2023-05-09 15:15   ` Patrick Steinhardt
2023-05-09 20:55     ` Taylor Blau
2023-05-09 21:15       ` Taylor Blau
2023-05-10  7:25       ` Patrick Steinhardt
2023-05-09 23:40   ` Junio C Hamano
2023-05-10  2:30     ` Taylor Blau
2023-05-08 22:00 ` [PATCH 10/15] refs/packed-backend.c: add trace2 counters for skip list Taylor Blau
2023-05-08 22:00 ` [PATCH 11/15] revision.h: store hidden refs in a `strvec` Taylor Blau
2023-05-08 22:00 ` [PATCH 12/15] refs/packed-backend.c: ignore complicated hidden refs rules Taylor Blau
2023-05-08 22:00 ` [PATCH 13/15] refs.h: let `for_each_namespaced_ref()` take excluded patterns Taylor Blau
2023-05-08 22:00 ` [PATCH 14/15] upload-pack.c: avoid enumerating hidden refs where possible Taylor Blau
2023-05-09 15:15   ` Patrick Steinhardt
2023-05-09 21:34     ` Taylor Blau
2023-05-08 22:00 ` [PATCH 15/15] builtin/receive-pack.c: avoid enumerating hidden references Taylor Blau
2023-05-15 19:23 ` [PATCH v2 00/16] refs: implement jump lists for packed backend Taylor Blau
2023-05-15 19:23   ` [PATCH v2 01/16] refs.c: rename `ref_filter` Taylor Blau
2023-05-15 19:23   ` [PATCH v2 02/16] ref-filter.h: provide `REF_FILTER_INIT` Taylor Blau
2023-05-15 19:23   ` [PATCH v2 03/16] ref-filter: clear reachable list pointers after freeing Taylor Blau
2023-05-15 19:23   ` [PATCH v2 04/16] ref-filter: add `ref_filter_clear()` Taylor Blau
2023-05-15 19:23   ` [PATCH v2 05/16] ref-filter.c: parameterize match functions over patterns Taylor Blau
2023-05-15 19:23   ` [PATCH v2 06/16] builtin/for-each-ref.c: add `--exclude` option Taylor Blau
2023-05-15 19:23   ` [PATCH v2 07/16] refs: plumb `exclude_patterns` argument throughout Taylor Blau
2023-05-15 19:23   ` [PATCH v2 08/16] refs/packed-backend.c: refactor `find_reference_location()` Taylor Blau
2023-05-15 19:23   ` [PATCH v2 09/16] refs/packed-backend.c: implement jump lists to avoid excluded pattern(s) Taylor Blau
2023-06-06  7:00     ` Patrick Steinhardt
2023-06-20 12:15       ` Taylor Blau
2023-05-15 19:23   ` [PATCH v2 10/16] refs/packed-backend.c: add trace2 counters for jump list Taylor Blau
2023-05-15 19:23   ` [PATCH v2 11/16] revision.h: store hidden refs in a `strvec` Taylor Blau
2023-06-06  7:00     ` Patrick Steinhardt
2023-06-20 12:16       ` Taylor Blau
2023-05-15 19:23   ` [PATCH v2 12/16] refs/packed-backend.c: ignore complicated hidden refs rules Taylor Blau
2023-05-15 19:23   ` [PATCH v2 13/16] refs.h: let `for_each_namespaced_ref()` take excluded patterns Taylor Blau
2023-06-06  7:01     ` Patrick Steinhardt
2023-06-20 12:18       ` Taylor Blau
2023-05-15 19:23   ` [PATCH v2 14/16] builtin/receive-pack.c: avoid enumerating hidden references Taylor Blau
2023-05-15 19:23   ` [PATCH v2 15/16] upload-pack.c: avoid enumerating hidden refs where possible Taylor Blau
2023-05-15 19:23   ` [PATCH v2 16/16] ls-refs.c: " Taylor Blau
2023-06-06  7:01   ` [PATCH v2 00/16] refs: implement jump lists for packed backend Patrick Steinhardt
2023-06-20 12:22     ` Taylor Blau
2023-06-07 10:40 ` [PATCH v3 " Taylor Blau
2023-06-07 10:40   ` [PATCH v3 01/16] refs.c: rename `ref_filter` Taylor Blau
2023-06-13 22:19     ` Junio C Hamano
2023-06-07 10:40   ` [PATCH v3 02/16] ref-filter.h: provide `REF_FILTER_INIT` Taylor Blau
2023-06-07 10:41   ` [PATCH v3 03/16] ref-filter: clear reachable list pointers after freeing Taylor Blau
2023-06-07 10:41   ` [PATCH v3 04/16] ref-filter: add `ref_filter_clear()` Taylor Blau
2023-06-07 10:41   ` [PATCH v3 05/16] ref-filter.c: parameterize match functions over patterns Taylor Blau
2023-06-13 22:37     ` Junio C Hamano
2023-06-07 10:41   ` [PATCH v3 06/16] builtin/for-each-ref.c: add `--exclude` option Taylor Blau
2023-06-07 10:41   ` [PATCH v3 07/16] refs: plumb `exclude_patterns` argument throughout Taylor Blau
2023-06-13 23:42     ` Junio C Hamano
2023-06-20 11:52       ` Taylor Blau
2023-06-07 10:41   ` [PATCH v3 08/16] refs/packed-backend.c: refactor `find_reference_location()` Taylor Blau
2023-06-07 10:41   ` [PATCH v3 09/16] refs/packed-backend.c: implement jump lists to avoid excluded pattern(s) Taylor Blau
2023-06-14  0:27     ` Junio C Hamano
2023-06-20 12:05       ` Taylor Blau
2023-06-20 18:49         ` Junio C Hamano
2023-06-07 10:41   ` [PATCH v3 10/16] refs/packed-backend.c: add trace2 counters for jump list Taylor Blau
2023-06-14  0:32     ` Junio C Hamano
2023-06-20 12:08       ` Taylor Blau
2023-06-07 10:41   ` [PATCH v3 11/16] revision.h: store hidden refs in a `strvec` Taylor Blau
2023-06-07 10:41   ` [PATCH v3 12/16] refs/packed-backend.c: ignore complicated hidden refs rules Taylor Blau
2023-06-14  0:40     ` Junio C Hamano
2023-06-07 10:41   ` [PATCH v3 13/16] refs.h: let `for_each_namespaced_ref()` take excluded patterns Taylor Blau
2023-06-07 10:42   ` [PATCH v3 14/16] builtin/receive-pack.c: avoid enumerating hidden references Taylor Blau
2023-06-07 10:42   ` Taylor Blau [this message]
2023-06-07 10:42   ` [PATCH v3 16/16] ls-refs.c: avoid enumerating hidden refs where possible Taylor Blau
2023-06-12 21:05   ` [PATCH v3 00/16] refs: implement jump lists for packed backend Junio C Hamano
2023-06-20 14:20 ` [PATCH v4 " Taylor Blau
2023-06-20 14:21   ` [PATCH v4 01/16] refs.c: rename `ref_filter` Taylor Blau
2023-07-03  5:13     ` Jeff King
2023-06-20 14:21   ` [PATCH v4 02/16] ref-filter.h: provide `REF_FILTER_INIT` Taylor Blau
2023-07-03  5:15     ` Jeff King
2023-07-03 17:07       ` Taylor Blau
2023-06-20 14:21   ` [PATCH v4 03/16] ref-filter: clear reachable list pointers after freeing Taylor Blau
2023-07-03  5:16     ` Jeff King
2023-06-20 14:21   ` [PATCH v4 04/16] ref-filter: add `ref_filter_clear()` Taylor Blau
2023-07-03  5:19     ` Jeff King
2023-07-03 17:13       ` Taylor Blau
2023-07-03 17:32         ` Jeff King
2023-06-20 14:21   ` [PATCH v4 05/16] ref-filter.c: parameterize match functions over patterns Taylor Blau
2023-07-03  5:27     ` Jeff King
2023-07-03 17:18       ` Taylor Blau
2023-07-03 17:22         ` Taylor Blau
2023-07-03 17:33           ` Jeff King
2023-06-20 14:21   ` [PATCH v4 06/16] builtin/for-each-ref.c: add `--exclude` option Taylor Blau
2023-06-20 14:21   ` [PATCH v4 07/16] refs: plumb `exclude_patterns` argument throughout Taylor Blau
2023-06-20 14:21   ` [PATCH v4 08/16] refs/packed-backend.c: refactor `find_reference_location()` Taylor Blau
2023-06-20 14:21   ` [PATCH v4 09/16] refs/packed-backend.c: implement jump lists to avoid excluded pattern(s) Taylor Blau
2023-07-03  5:56     ` Jeff King
2023-07-03 17:38       ` Taylor Blau
2023-06-20 14:21   ` [PATCH v4 10/16] refs/packed-backend.c: add trace2 counters for jump list Taylor Blau
2023-06-20 14:21   ` [PATCH v4 11/16] revision.h: store hidden refs in a `strvec` Taylor Blau
2023-07-03  5:59     ` Jeff King
2023-06-20 14:22   ` [PATCH v4 12/16] refs/packed-backend.c: ignore complicated hidden refs rules Taylor Blau
2023-07-03  6:18     ` Jeff King
2023-07-04 18:22       ` Taylor Blau
2023-06-20 14:22   ` [PATCH v4 13/16] refs.h: let `for_each_namespaced_ref()` take excluded patterns Taylor Blau
2023-06-20 14:22   ` [PATCH v4 14/16] builtin/receive-pack.c: avoid enumerating hidden references Taylor Blau
2023-06-20 14:22   ` [PATCH v4 15/16] upload-pack.c: avoid enumerating hidden refs where possible Taylor Blau
2023-07-03  6:26     ` Jeff King
2023-07-04 18:43       ` Taylor Blau
2023-06-20 14:22   ` [PATCH v4 16/16] ls-refs.c: " Taylor Blau
2023-07-03  6:27     ` Jeff King
2023-07-03  6:29   ` [PATCH v4 00/16] refs: implement jump lists for packed backend Jeff King
2023-07-10 21:12 ` [PATCH v5 " Taylor Blau
2023-07-10 21:12   ` [PATCH v5 01/16] refs.c: rename `ref_filter` Taylor Blau
2023-07-10 21:12   ` [PATCH v5 02/16] ref-filter.h: provide `REF_FILTER_INIT` Taylor Blau
2023-07-10 21:12   ` [PATCH v5 03/16] ref-filter: clear reachable list pointers after freeing Taylor Blau
2023-07-10 21:12   ` [PATCH v5 04/16] ref-filter: add `ref_filter_clear()` Taylor Blau
2023-07-10 21:12   ` [PATCH v5 05/16] ref-filter.c: parameterize match functions over patterns Taylor Blau
2023-07-10 21:12   ` [PATCH v5 06/16] builtin/for-each-ref.c: add `--exclude` option Taylor Blau
2023-07-10 21:12   ` [PATCH v5 07/16] refs: plumb `exclude_patterns` argument throughout Taylor Blau
2023-07-10 21:12   ` [PATCH v5 08/16] refs/packed-backend.c: refactor `find_reference_location()` Taylor Blau
2023-07-10 21:12   ` [PATCH v5 09/16] refs/packed-backend.c: implement jump lists to avoid excluded pattern(s) Taylor Blau
2023-07-10 21:12   ` [PATCH v5 10/16] refs/packed-backend.c: add trace2 counters for jump list Taylor Blau
2023-07-10 21:12   ` [PATCH v5 11/16] revision.h: store hidden refs in a `strvec` Taylor Blau
2023-07-10 21:12   ` [PATCH v5 12/16] refs.h: let `for_each_namespaced_ref()` take excluded patterns Taylor Blau
2023-07-10 21:12   ` [PATCH v5 13/16] refs.h: implement `hidden_refs_to_excludes()` Taylor Blau
2023-07-10 21:12   ` [PATCH v5 14/16] builtin/receive-pack.c: avoid enumerating hidden references Taylor Blau
2023-07-10 21:12   ` [PATCH v5 15/16] upload-pack.c: avoid enumerating hidden refs where possible Taylor Blau
2023-07-10 21:12   ` [PATCH v5 16/16] ls-refs.c: " Taylor Blau
2023-07-10 22:35   ` [PATCH v5 00/16] refs: implement jump lists for packed backend Junio C Hamano
2023-07-11  9:37     ` Patrick Steinhardt
2023-07-11 15:56       ` Junio C Hamano
2023-07-11 17:19         ` Taylor Blau

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=014243ebe6586313b38fe0eb2a57941b27131423.1686134440.git.me@ttaylorr.com \
    --to=me@ttaylorr.com \
    --cc=chris.torek@gmail.com \
    --cc=derrickstolee@github.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=peff@peff.net \
    --cc=ps@pks.im \
    /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 read-only IMAP folder(s) and NNTP newsgroup(s).