From: Taylor Blau <me@ttaylorr.com>
To: git@vger.kernel.org
Cc: Jeff King <peff@peff.net>,
Derrick Stolee <derrickstolee@github.com>,
Junio C Hamano <gitster@pobox.com>
Subject: [PATCH 00/15] refs: implement skip lists for packed backend
Date: Mon, 8 May 2023 17:59:38 -0400 [thread overview]
Message-ID: <cover.1683581621.git.me@ttaylorr.com> (raw)
This series implements the concept of a skip list for the packed refs
backend. In situations where the caller has many references they want to
exclude, the packed-refs iterator maintains a list of (start, end)
tuples of regions to jump over (i.e. if `iter->pos == start`, jump
forward to `end`).
This series implements that concept, and uses it to power a couple of
new things:
- `git for-each-ref --exclude`, which allows callers to specify
prefixes they wish to discard.
In a synthetic example, the naive implementation improved runtime
from ~820ms to enumerate all references and discard unwanted ones,
down to ~106ms with `--exclude`. By the end of the series, this time
drops to under ~5ms.
- `git receive-pack` uses the new skip-list machinery to avoid
visiting references hidden via a hideRefs rule.
- `git upload-pack` has an analogous optimization as above (though it
can't kick in quite as often for reasons described in that patch).
The series is laid out as follows:
- The first five patches are preparatory (various refs.c and
ref-filter cleanup).
- The sixth patch provides a naive implementation of `--exclude`.
- The next four patches prepare for and implement skip lists in the
packed-refs backend.
- The last five patches apply the optimization in `upload-pack` and
`receive-pack`.
The series is ordered so that any prefix of sections list above could be
queued independently. Thanks in advance for your review.
Jeff King (5):
refs.c: rename `ref_filter`
ref-filter.h: provide `REF_FILTER_INIT`
ref-filter: clear reachable list pointers after freeing
ref-filter: add ref_filter_clear()
ref-filter.c: parameterize match functions over patterns
Taylor Blau (10):
builtin/for-each-ref.c: add `--exclude` option
refs: plumb `exclude_patterns` argument throughout
refs/packed-backend.c: refactor `find_reference_location()`
refs/packed-backend.c: implement skip lists to avoid excluded
pattern(s)
refs/packed-backend.c: add trace2 counters for skip list
revision.h: store hidden refs in a `strvec`
refs/packed-backend.c: ignore complicated hidden refs rules
refs.h: let `for_each_namespaced_ref()` take excluded patterns
upload-pack.c: avoid enumerating hidden refs where possible
builtin/receive-pack.c: avoid enumerating hidden references
Documentation/git-for-each-ref.txt | 6 +
builtin/branch.c | 4 +-
builtin/for-each-ref.c | 8 +-
builtin/receive-pack.c | 7 +-
builtin/tag.c | 4 +-
http-backend.c | 2 +-
ls-refs.c | 8 +-
ref-filter.c | 61 ++++++--
ref-filter.h | 12 ++
refs.c | 61 ++++----
refs.h | 15 +-
refs/debug.c | 5 +-
refs/files-backend.c | 5 +-
refs/packed-backend.c | 222 ++++++++++++++++++++++++++---
refs/refs-internal.h | 7 +-
revision.c | 4 +-
revision.h | 5 +-
t/helper/test-reach.c | 2 +-
t/helper/test-ref-store.c | 10 ++
t/t1419-exclude-refs.sh | 131 +++++++++++++++++
t/t6300-for-each-ref.sh | 35 +++++
trace2.h | 2 +
trace2/tr2_ctr.c | 5 +
upload-pack.c | 43 ++++--
24 files changed, 559 insertions(+), 105 deletions(-)
create mode 100755 t/t1419-exclude-refs.sh
--
2.40.1.477.g956c797dfc
next reply other threads:[~2023-05-08 21:59 UTC|newest]
Thread overview: 149+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-05-08 21:59 Taylor Blau [this message]
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 ` [PATCH v3 15/16] upload-pack.c: avoid enumerating hidden refs where possible Taylor Blau
2023-06-07 10:42 ` [PATCH v3 16/16] ls-refs.c: " 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=cover.1683581621.git.me@ttaylorr.com \
--to=me@ttaylorr.com \
--cc=derrickstolee@github.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.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 read-only IMAP folder(s) and NNTP newsgroup(s).