[PATCH v3 00/16] refs: batch refname availability checks
- From
Patrick Steinhardt <ps@pks.im>
- Date
- Feb 25, 2025, 08:55 UTC
- Message-ID
- <20250225-pks-update-ref-optimization-v3-0-77c3687cda75@pks.im>
- In-Reply-To
- <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im>
Hi,
this patch series has been inspired by brian's report that the reftable backend is significantly slower when writing many references compared to the files backend. As explained in that thread, the underlying issue is the design of tombstone references: when we first delete all references in a repository and then recreate them, we still have all the tombstones and thus we need to churn through all of them to figure out that they have been deleted in the first place. The files backend does not have this issue.
I consider the benchmark itself to be kind of broken, as it stems from us deleting all refs and then recreating them. And if you pack refs in between then the "reftable" backend outperforms the "files" backend.
But there are a couple of opportunities here anyway. While we cannot make the underlying issue of tombstones being less efficient go away, this has prompted me to have a deeper look at where we spend all the time. There are three ideas in this series:
- git-update-ref(1) performs ambiguity checks for any full-size object
ID, which triggers a lot of reads. This is somewhat pointless though
given that the manpage explicitly points out that the command is
about object IDs, even though it does know to parse refs. But being
part of plumbing, emitting the warning here does not make a ton of
sense, and favoring object IDs over references in these cases is the
obvious thing to do anyway. - For each ref "refs/heads/bar", we need to verify that neither
"refs/heads" nor "refs" exists. This was repeated for every refname,
but because most refnames use common prefixes this made us re-check
a lot of prefixes. This is addressed by using a `strset` of already
checked prefixes. - For each ref "refs/heads/bar", we need to verify that no ref
"refs/heads/bar/*" exists. We always created a new ref iterator for
this check, which requires us to discard all internal state and then
recreate it. The reftable library has already been refactored though
to have reseekable iterators, so we backfill this functionality to
all the other iterators and then reuse the iterator.With the (somewhat broken) benchmark we see a small speedup with the "files" backend:
Benchmark 1: update-ref (refformat = files, revision = master)
Time (mean ± σ): 234.4 ms ± 1.9 ms [User: 75.6 ms, System: 157.2 ms]
Range (min … max): 232.2 ms … 236.9 ms 10 runs Benchmark 2: update-ref (refformat = files, revision = HEAD)
Time (mean ± σ): 184.2 ms ± 2.0 ms [User: 62.8 ms, System: 119.9 ms]
Range (min … max): 181.1 ms … 187.0 ms 10 runs Summary
update-ref (refformat = files, revision = HEAD) ran
1.27 ± 0.02 times faster than update-ref (refformat = files, revision = master)And a huge speedup with the "reftable" backend:
Benchmark 1: update-ref (refformat = reftable, revision = master)
Time (mean ± σ): 16.852 s ± 0.061 s [User: 16.754 s, System: 0.059 s]
Range (min … max): 16.785 s … 16.982 s 10 runs Benchmark 2: update-ref (refformat = reftable, revision = HEAD)
Time (mean ± σ): 2.230 s ± 0.009 s [User: 2.192 s, System: 0.029 s]
Range (min … max): 2.215 s … 2.244 s 10 runs Summary
update-ref (refformat = reftable, revision = HEAD) ran
7.56 ± 0.04 times faster than update-ref (refformat = reftable, revision = master)We're still not up to speed with the "files" backend, but considerably better. Given that this is an extreme edge case and not reflective of the general case I'm okay with this result for now.
But more importantly, this refactoring also has a positive effect when updating references in a repository with preexisting refs, which I consider to be the more realistic scenario. The following benchmark creates 10k refs with 100k preexisting refs.
With the "files" backend we see a modest improvement:
Benchmark 1: update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = master)
Time (mean ± σ): 478.4 ms ± 11.9 ms [User: 96.7 ms, System: 379.6 ms]
Range (min … max): 465.4 ms … 496.6 ms 10 runs Benchmark 2: update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = HEAD)
Time (mean ± σ): 388.5 ms ± 10.3 ms [User: 52.0 ms, System: 333.8 ms]
Range (min … max): 376.5 ms … 403.1 ms 10 runs Summary
update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = HEAD) ran
1.23 ± 0.04 times faster than update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = master)But with the "reftable" backend we see an almost 5x improvement, where it's now ~15x faster than the "files" backend:
Benchmark 1: update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = master)
Time (mean ± σ): 153.9 ms ± 2.0 ms [User: 96.5 ms, System: 56.6 ms]
Range (min … max): 150.5 ms … 158.4 ms 18 runs Benchmark 2: update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD)
Time (mean ± σ): 32.2 ms ± 1.2 ms [User: 27.6 ms, System: 4.3 ms]
Range (min … max): 29.8 ms … 38.6 ms 71 runs Summary
update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD) ran
4.78 ± 0.19 times faster than update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = master)The series is structured as follows:
- Patches 1 to 4 implement the logic to skip ambiguity checks in
git-update-ref(1).- Patch 5 to 8 introduce batched checks.
- Patch 9 deduplicates the ref prefix checks.
- Patch 10 to 16 implement the infrastructure to reseek iterators.
- Patch 17 starts to reuse iterators for nested ref checks.
Changes in v2:
- Point out why we also have to touch up the `dir_iterator`.
- Fix up the comment explaining `ITER_DONE`.
- Fix up comments that show usage patterns of the ref and dir iterator
interfaces.
- Start batching availability checks in the "files" backend, as well.
- Improve the commit message that drops the ambiguity check so that we
also point to 25fba78d36b (cat-file: disable object/refname
ambiguity check for batch mode, 2013-07-12).
- Link to v1: https://lore.kernel.org/r/20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.imChanges in v3:
- Fix one case where we didn't skip ambiguity checks in
git-update-ref(1).
- Document better that only the prefix can change on reseeking
iterators. Other internal state will remain the same.
- Fix a memory leak in the ref-cache iterator.
- Don't ignore errors returned by `packed_ref_iterator_seek()`.
- Link to v2: https://lore.kernel.org/r/20250219-pks-update-ref-optimization-v2-0-e696e7220b22@pks.imThanks!
Patrick
[1]: <Z602dzQggtDdcgCX@tapette.crustytoothpaste.net>
---
Patrick Steinhardt (16):
object-name: introduce `repo_get_oid_with_flags()`
object-name: allow skipping ambiguity checks in `get_oid()` family
builtin/update-ref: skip ambiguity checks when parsing object IDs
refs: introduce function to batch refname availability checks
refs/reftable: batch refname availability checks
refs/files: batch refname availability checks for normal transactions
refs/files: batch refname availability checks for initial transactions
refs: stop re-verifying common prefixes for availability
refs/iterator: separate lifecycle from iteration
refs/iterator: provide infrastructure to re-seek iterators
refs/iterator: implement seeking for merged iterators
refs/iterator: implement seeking for reftable iterators
refs/iterator: implement seeking for ref-cache iterators
refs/iterator: implement seeking for packed-ref iterators
refs/iterator: implement seeking for files iterators
refs: reuse iterators when determining refname availabilitybuiltin/clone.c | 2 + builtin/update-ref.c | 15 ++-- dir-iterator.c | 24 +++--- dir-iterator.h | 11 +-- hash.h | 1 + iterator.h | 2 +- object-name.c | 18 +++-- object-name.h | 6 ++ refs.c | 186 ++++++++++++++++++++++++++----------------- refs.h | 12 +++ refs/debug.c | 20 +++-- refs/files-backend.c | 117 +++++++++++++++++---------- refs/iterator.c | 145 +++++++++++++++++---------------- refs/packed-backend.c | 92 ++++++++++++--------- refs/ref-cache.c | 88 ++++++++++++-------- refs/refs-internal.h | 53 +++++++----- refs/reftable-backend.c | 85 +++++++++++--------- t/helper/test-dir-iterator.c | 1 + 18 files changed, 528 insertions(+), 350 deletions(-)
Range-diff versus v2:
1: b7b3e057628 ! 1: 34198fbc1c0 object-name: introduce `repo_get_oid_with_flags()`
@@ object-name.c: void object_context_release(struct object_context *ctx)
- * notably "xyz^" for "parent of xyz"
- */
-int repo_get_oid(struct repository *r, const char *name, struct object_id *oid)
-+int repo_get_oid_with_flags(struct repository *r, const char *name, struct object_id *oid,
-+ unsigned flags)
++int repo_get_oid_with_flags(struct repository *r, const char *name,
++ struct object_id *oid, unsigned flags)
{
struct object_context unused;
- int ret = get_oid_with_context(r, name, 0, oid, &unused);
@@ object-name.h: void strbuf_repo_add_unique_abbrev(struct strbuf *sb, struct repo
+ * This is like "get_oid_basic()", except it allows "object ID expressions",
+ * notably "xyz^" for "parent of xyz". Accepts GET_OID_* flags.
+ */
-+int repo_get_oid_with_flags(struct repository *r, const char *str, struct object_id *oid,
-+ unsigned flags);
++int repo_get_oid_with_flags(struct repository *r, const char *str,
++ struct object_id *oid, unsigned flags);
int repo_get_oid(struct repository *r, const char *str, struct object_id *oid);
__attribute__((format (printf, 2, 3)))
int get_oidf(struct object_id *oid, const char *fmt, ...);
2: 3cba1ffa8aa = 2: f5d4d2a67ce object-name: allow skipping ambiguity checks in `get_oid()` family
3: 80dfc2ee6b7 ! 3: 0512c256641 builtin/update-ref: skip ambiguity checks when parsing object IDs
@@ builtin/update-ref.c: static int parse_next_oid(const char **next, const char *e
goto invalid;
} else if (flags & PARSE_SHA1_ALLOW_EMPTY) {
/* With -z, treat an empty value as all zeros: */
+@@ builtin/update-ref.c: static void parse_cmd_symref_update(struct ref_transaction *transaction,
+ die("symref-update %s: expected old value", refname);
+
+ if (!strcmp(old_arg, "oid")) {
+- if (repo_get_oid(the_repository, old_target, &old_oid))
++ if (repo_get_oid_with_flags(the_repository, old_target, &old_oid,
++ GET_OID_SKIP_AMBIGUITY_CHECK))
+ die("symref-update %s: invalid oid: %s", refname, old_target);
+
+ have_old_oid = 1;
@@ builtin/update-ref.c: int cmd_update_ref(int argc,
refname = argv[0];
value = argv[1];
4: 9bd05801ac0 = 4: ad7bf4bed31 refs: introduce function to batch refname availability checks
5: 0104c9759aa = 5: 132f09c4584 refs/reftable: batch refname availability checks
6: fba06e5fcb7 = 6: bd7e5fa7bf1 refs/files: batch refname availability checks for normal transactions
7: dfb4be26147 = 7: a907f62d2c2 refs/files: batch refname availability checks for initial transactions
8: e7abe4bae25 = 8: 866e5f4b4cc refs: stop re-verifying common prefixes for availability
9: 1deae95c53a = 9: 736f1bd9afd refs/iterator: separate lifecycle from iteration
10: 8b942563e65 ! 10: 71d4c4c4655 refs/iterator: provide infrastructure to re-seek iterators
@@ Commit message
the reftable backend.
Introduce a new `.seek` function in the ref iterator vtable that allows
- callers to re-seek an iterator. It is expected to be functionally the
- same as calling `refs_ref_iterator_begin()` with a different (or the
- same) prefix.
+ callers to seek an iterator multiple times. It is expected to be
+ functionally the same as calling `refs_ref_iterator_begin()` with a
+ different (or the same) prefix.
+
+ Note that it is not possible to adjust parameters other than the seeked
+ prefix for now, so exclude patterns, trimmed prefixes and flags will
+ remain unchanged. We do not have a usecase for changing these parameters
+ right now, but if we ever find one we can adapt accordingly.
Implement the callback for trivial cases. The other iterators will be
implemented in subsequent commits.
@@ refs/refs-internal.h: struct ref_iterator {
+ *
+ * This function is expected to behave as if a new ref iterator with the same
+ * prefix had been created, but allows reuse of iterators and thus may allow
-+ * the backend to optimize.
++ * the backend to optimize. Parameters other than the prefix that have been
++ * passed when creating the iterator will remain unchanged.
+ *
+ * Returns 0 on success, a negative error code otherwise.
+ */
11: ad4f063ef06 = 11: 5a0412d754b refs/iterator: implement seeking for merged iterators
12: ddac957862f ! 12: ece7e500ecd refs/iterator: implement seeking for reftable iterators
@@ Commit message
iterators already support seeking this change is straight-forward. Two
notes though:
- - We do not support seeking on reflog iterators.
+ - We do not support seeking on reflog iterators. It is unclear what
+ seeking would even look like in this context, as you typically would
+ want to seek to a specific entry in the reflog for a specific ref.
+ There is not currently a usecase for this, but if there ever is we
+ can implement seeking in the future.
- We start to check whether `reftable_stack_init_ref_iterator()` is
successful.
13: 87b81552acf ! 13: f693de656b5 refs/iterator: implement seeking for ref-cache iterators
@@ Commit message
Note that we cannot use the optimization anymore where we return an
empty ref iterator when there aren't any references, as otherwise it
wouldn't be possible to reseek the iterator to a different prefix that
- may exist. This shouldn't be much of a performance corncern though as we
+ may exist. This shouldn't be much of a performance concern though as we
now start to bail out early in case `advance()` sees that there are no
more directories to be searched.
@@ refs/ref-cache.c: struct cache_ref_iterator {
*/
size_t levels_nr;
+@@ refs/ref-cache.c: struct cache_ref_iterator {
+ * The prefix is matched textually, without regard for path
+ * component boundaries.
+ */
+- const char *prefix;
++ char *prefix;
+
+ /*
+ * A stack of levels. levels[0] is the uppermost level that is
@@ refs/ref-cache.c: struct cache_ref_iterator {
struct cache_ref_iterator_level *levels;
@@ refs/ref-cache.c: static int cache_ref_iterator_advance(struct ref_iterator *ref
+{
+ struct cache_ref_iterator *iter =
+ (struct cache_ref_iterator *)ref_iterator;
++ struct cache_ref_iterator_level *level;
+ struct ref_dir *dir;
+
+ dir = get_ref_dir(iter->cache->root);
+ if (prefix && *prefix)
+ dir = find_containing_dir(dir, prefix);
++ if (!dir) {
++ iter->levels_nr = 0;
++ return 0;
++ }
+
-+ if (dir) {
-+ struct cache_ref_iterator_level *level;
-+
-+ if (iter->prime_dir)
-+ prime_ref_dir(dir, prefix);
-+ iter->levels_nr = 1;
-+ level = &iter->levels[0];
-+ level->index = -1;
-+ level->dir = dir;
++ if (iter->prime_dir)
++ prime_ref_dir(dir, prefix);
++ iter->levels_nr = 1;
++ level = &iter->levels[0];
++ level->index = -1;
++ level->dir = dir;
+
-+ if (prefix && *prefix) {
-+ iter->prefix = xstrdup(prefix);
-+ level->prefix_state = PREFIX_WITHIN_DIR;
-+ } else {
-+ level->prefix_state = PREFIX_CONTAINS_DIR;
-+ }
++ if (prefix && *prefix) {
++ free(iter->prefix);
++ iter->prefix = xstrdup(prefix);
++ level->prefix_state = PREFIX_WITHIN_DIR;
+ } else {
-+ iter->levels_nr = 0;
++ FREE_AND_NULL(iter->prefix);
++ level->prefix_state = PREFIX_CONTAINS_DIR;
+ }
+
+ return 0;
@@ refs/ref-cache.c: static int cache_ref_iterator_advance(struct ref_iterator *ref
struct object_id *peeled)
{
@@ refs/ref-cache.c: static void cache_ref_iterator_release(struct ref_iterator *ref_iterator)
+ {
+ struct cache_ref_iterator *iter =
+ (struct cache_ref_iterator *)ref_iterator;
+- free((char *)iter->prefix);
++ free(iter->prefix);
+ free(iter->levels);
+ }
static struct ref_iterator_vtable cache_ref_iterator_vtable = {
.advance = cache_ref_iterator_advance,
14: 2619de30fe1 ! 14: ac71647ee94 refs/iterator: implement seeking for `packed-ref` iterators
@@ Metadata
Author: Patrick Steinhardt <ps@pks.im>
## Commit message ##
- refs/iterator: implement seeking for `packed-ref` iterators
+ refs/iterator: implement seeking for packed-ref iterators
Implement seeking of `packed-ref` iterators. The implementation is again
straight forward, except that we cannot continue to use the prefix
@@ refs/packed-backend.c: static struct ref_iterator *packed_ref_iterator_begin(
- if (prefix && *prefix)
- /* Stop iteration after we've gone *past* prefix: */
- ref_iterator = prefix_ref_iterator_begin(ref_iterator, prefix, 0);
-+ packed_ref_iterator_seek(&iter->base, prefix);
++ if (packed_ref_iterator_seek(&iter->base, prefix) < 0) {
++ ref_iterator_free(&iter->base);
++ return NULL;
++ }
return ref_iterator;
}
15: d4f76e6480b ! 15: 02cafca513c refs/iterator: implement seeking for "files" iterators
@@ Metadata
Author: Patrick Steinhardt <ps@pks.im>
## Commit message ##
- refs/iterator: implement seeking for "files" iterators
+ refs/iterator: implement seeking for files iterators
Implement seeking for "files" iterators. As we simply use a ref-cache
iterator under the hood the implementation is straight-forward. Note
16: 49017050289 = 16: baed7615a97 refs: reuse iterators when determining refname availability--- base-commit: e2067b49ecaef9b7f51a17ce251f9207f72ef52d change-id: 20250217-pks-update-ref-optimization-15c795e66e2b