| Message ID | cover.1624858240.git.ps@pks.im (mailing list archive) |
|---|---|
| Headers | show |
| Series | Speed up connectivity checks via bitmaps | expand |
Hi,
this is the fifth version of my series to speed up connectivity checks
in the context of repos with many refs. While the original goal has been
to speed up connectivity checks only, the series is now optimizing
git-rev-list(1) in general to be able to more efficiently load
references. Like this, `--not --all` is a lot faster in the context of
many refs, but other usecases benefit, too.
Changes compared to v4:
- I've changed the interface to load commits via the commit-graph.
Instead of the previous version where you'd had to pass in a
`struct object`, which forced us to use `lookup_unknown_object()`,
one now only passes in an object ID. If the object ID is found in
the commit graph and if the corresponding object exists in the
ODB, then we return the parsed commit object.
This also avoids a previous pitfal: we'd have parsed the commit
via the graph and thus had allocated the object even if the
corresponding object didn't exist. While we knew to handle this in
`get_reference()` by asserting object existence, any other caller
which executes `lookup_commit()` would get the parsed commit and
assume that it exists. This now cannot happen anymore given that
we only create the commit object in case we know the ID exists in
the ODB.
- With this change, I could now drop the patch which avoided loading
objects multiple times: we don't need `lookup_unknown_object()`
anymore and thus don't thave the memory/perf tradeoff. And with
the new interface to load commits via the graph, the deduplication
only resulted in a ~1% speedup.
- `--unsorted-input` and `--no-walk` are now mutually exclusive
regardless of whether `--no-walk` is sorted or unsorted,
simplifying the logic.
Patrick
Patrick Steinhardt (5):
revision: separate walk and unsorted flags
connected: do not sort input revisions
revision: stop retrieving reference twice
commit-graph: split out function to search commit position
revision: avoid hitting packfiles when commits are in commit-graph
Documentation/rev-list-options.txt | 8 ++-
builtin/log.c | 2 +-
builtin/revert.c | 3 +-
commit-graph.c | 79 ++++++++++++++++++++----------
commit-graph.h | 8 +++
connected.c | 1 +
revision.c | 38 ++++++++------
revision.h | 7 +--
t/t6000-rev-list-misc.sh | 31 ++++++++++++
9 files changed, 129 insertions(+), 48 deletions(-)
Range-diff against v4:
1: 67232910ac = 1: 67232910ac revision: separate walk and unsorted flags
2: 9d7f484907 ! 2: d3f498a563 connected: do not sort input revisions
@@ revision.c: static int handle_revision_opt(struct rev_info *revs, int argc, cons
revs->sort_order = REV_SORT_BY_AUTHOR_DATE;
revs->topo_order = 1;
+ } else if (!strcmp(arg, "--unsorted-input")) {
-+ if (revs->no_walk && !revs->unsorted_input)
-+ die(_("--unsorted-input is incompatible with --no-walk and --no-walk=sorted"));
++ if (revs->no_walk)
++ die(_("--unsorted-input is incompatible with --no-walk"));
+ revs->unsorted_input = 1;
} else if (!strcmp(arg, "--early-output")) {
revs->early_output = 100;
@@ revision.c: static int handle_revision_pseudo_opt(const char *submodule,
} else if (!strcmp(arg, "--not")) {
*flags ^= UNINTERESTING | BOTTOM;
} else if (!strcmp(arg, "--no-walk")) {
-+ if (revs->unsorted_input)
-+ die(_("--no-walk is incompatible with --no-walk=unsorted and --unsorted-input"));
++ if (!revs->no_walk && revs->unsorted_input)
++ die(_("--no-walk is incompatible with --unsorted-input"));
revs->no_walk = 1;
} else if (skip_prefix(arg, "--no-walk=", &optarg)) {
++ if (!revs->no_walk && revs->unsorted_input)
++ die(_("--no-walk is incompatible with --unsorted-input"));
++
/*
-@@ revision.c: static int handle_revision_pseudo_opt(const char *submodule,
+ * Detached form ("--no-walk X" as opposed to "--no-walk=X")
* not allowed, since the argument is optional.
- */
- revs->no_walk = 1;
-- if (!strcmp(optarg, "sorted"))
-+ if (!strcmp(optarg, "sorted")) {
-+ if (revs->unsorted_input)
-+ die(_("--no-walk=sorted is incompatible with --no-walk=unsorted "
-+ "and --unsorted-input"));
- revs->unsorted_input = 0;
-- else if (!strcmp(optarg, "unsorted"))
-+ } else if (!strcmp(optarg, "unsorted"))
- revs->unsorted_input = 1;
- else
- return error("invalid argument to --no-walk");
## t/t6000-rev-list-misc.sh ##
@@ t/t6000-rev-list-misc.sh: test_expect_success 'rev-list --count --objects' '
@@ t/t6000-rev-list-misc.sh: test_expect_success 'rev-list --count --objects' '
+ test_cmp first.sorted second.sorted
+'
+
-+test_expect_success 'rev-list --unsorted-input compatible with --no-walk=unsorted' '
-+ git rev-list --unsorted-input --no-walk=unsorted HEAD HEAD~ >actual &&
-+ git rev-parse HEAD >expect &&
-+ git rev-parse HEAD~ >>expect &&
-+ test_cmp expect actual
-+'
-+
-+test_expect_success 'rev-list --unsorted-input incompatible with --no-walk=sorted' '
++test_expect_success 'rev-list --unsorted-input incompatible with --no-walk' '
+ cat >expect <<-EOF &&
-+ fatal: --no-walk is incompatible with --no-walk=unsorted and --unsorted-input
++ fatal: --no-walk is incompatible with --unsorted-input
+ EOF
+ test_must_fail git rev-list --unsorted-input --no-walk HEAD 2>error &&
+ test_cmp expect error &&
-+
-+ cat >expect <<-EOF &&
-+ fatal: --no-walk=sorted is incompatible with --no-walk=unsorted and --unsorted-input
-+ EOF
+ test_must_fail git rev-list --unsorted-input --no-walk=sorted HEAD 2>error &&
+ test_cmp expect error &&
++ test_must_fail git rev-list --unsorted-input --no-walk=unsorted HEAD 2>error &&
++ test_cmp expect error &&
+
+ cat >expect <<-EOF &&
-+ fatal: --unsorted-input is incompatible with --no-walk and --no-walk=sorted
++ fatal: --unsorted-input is incompatible with --no-walk
+ EOF
+ test_must_fail git rev-list --no-walk --unsorted-input HEAD 2>error &&
+ test_cmp expect error &&
+ test_must_fail git rev-list --no-walk=sorted --unsorted-input HEAD 2>error &&
++ test_cmp expect error &&
++ test_must_fail git rev-list --no-walk=unsorted --unsorted-input HEAD 2>error &&
+ test_cmp expect error
+'
+
3: d8e63d0943 = 3: c9a630927b revision: stop retrieving reference twice
4: ba8df5cad0 < -: ---------- revision: avoid loading object headers multiple times
5: e33cd51ebf = 4: bc89325fdf commit-graph: split out function to search commit position
6: 900c5a9c60 ! 5: fdb1fa9d57 revision: avoid hitting packfiles when commits are in commit-graph
@@ Metadata
## Commit message ##
revision: avoid hitting packfiles when commits are in commit-graph
- When queueing references in git-rev-list(1), we try to either reuse an
- already parsed object or alternatively we load the object header from
- disk in order to determine its type. This is inefficient for commits
- though in cases where we have a commit graph available: instead of
- hitting the real object on disk to determine its type, we may instead
- search the object graph for the object ID. In case it's found, we can
- directly fill in the commit object, otherwise we can still hit the disk
- to determine the object's type.
+ When queueing references in git-rev-list(1), we try to optimize parsing
+ of commits via the commit-graph. To do so, we first look up the object's
+ type, and if it is a commit we call `repo_parse_commit()` instead of
+ `parse_object()`. This is quite inefficient though given that we're
+ always uncompressing the object header in order to determine the type.
+ Instead, we can opportunistically search the commit-graph for the object
+ ID: in case it's found, we know it's a commit and can directly fill in
+ the commit object without having to uncompress the object header.
- Expose a new function `parse_commit_in_graph_gently()`, which fills in
- an object of unknown type in case we find its object ID in the graph.
- This provides a big performance win in cases where there is a
- commit-graph available in the repository in case we load lots of
- references. The following has been executed in a real-world repository
- with about 2.2 million refs:
+ Expose a new function `lookup_commit_in_graph()`, which tries to find a
+ commit in the commit-graph by ID, and convert `get_reference()` to use
+ this function. This provides a big performance win in cases where we
+ load references in a repository with lots of references pointing to
+ commits. The following has been executed in a real-world repository with
+ about 2.2 million refs:
Benchmark #1: HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev
- Time (mean ± σ): 4.508 s ± 0.039 s [User: 4.131 s, System: 0.377 s]
- Range (min … max): 4.455 s … 4.576 s 10 runs
+ Time (mean ± σ): 4.458 s ± 0.044 s [User: 4.115 s, System: 0.342 s]
+ Range (min … max): 4.409 s … 4.534 s 10 runs
Benchmark #2: HEAD: rev-list --unsorted-input --objects --quiet --not --all --not $newrev
- Time (mean ± σ): 3.072 s ± 0.031 s [User: 2.707 s, System: 0.365 s]
- Range (min … max): 3.040 s … 3.144 s 10 runs
+ Time (mean ± σ): 3.089 s ± 0.015 s [User: 2.768 s, System: 0.321 s]
+ Range (min … max): 3.061 s … 3.105 s 10 runs
Summary
'HEAD: rev-list --unsorted-input --objects --quiet --not --all --not $newrev' ran
- 1.47 ± 0.02 times faster than 'HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev'
+ 1.44 ± 0.02 times faster than 'HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev'
Signed-off-by: Patrick Steinhardt <ps@pks.im>
@@ commit-graph.c: static int find_commit_pos_in_graph(struct commit *item, struct
}
}
-+int parse_commit_in_graph_gently(struct repository *repo, struct object *object)
++struct commit *lookup_commit_in_graph(struct repository *repo, const struct object_id *id)
+{
+ struct commit *commit;
+ uint32_t pos;
+
-+ if (object->parsed) {
-+ if (object->type != OBJ_COMMIT)
-+ return -1;
-+ return 0;
-+ }
-+
+ if (!repo->objects->commit_graph)
-+ return -1;
++ return NULL;
++ if (!search_commit_pos_in_graph(id, repo->objects->commit_graph, &pos))
++ return NULL;
++ if (!repo_has_object_file(repo, id))
++ return NULL;
+
-+ if (!search_commit_pos_in_graph(&object->oid, repo->objects->commit_graph, &pos))
-+ return -1;
-+
-+ commit = object_as_type(object, OBJ_COMMIT, 1);
++ commit = lookup_commit(repo, id);
+ if (!commit)
-+ return -1;
-+ if (!fill_commit_in_graph(repo, commit, repo->objects->commit_graph, pos))
-+ return -1;
++ return NULL;
++ if (commit->object.parsed)
++ return commit;
+
-+ return 0;
++ if (!fill_commit_in_graph(repo, commit, repo->objects->commit_graph, pos))
++ return NULL;
++
++ return commit;
+}
+
static int parse_commit_in_graph_one(struct repository *r,
@@ commit-graph.h: int open_commit_graph(const char *graph_file, int *fd, struct st
int parse_commit_in_graph(struct repository *r, struct commit *item);
+/*
-+ * Given an object of unknown type, try to fill in the object in case it is a
-+ * commit part of the commit-graph. Returns 0 if the object is a parsed commit
-+ * or if it could be filled in via the commit graph, otherwise it returns -1.
++ * Look up the given commit ID in the commit-graph. This will only return a
++ * commit if the ID exists both in the graph and in the object database such
++ * that we don't return commits whose object has been pruned. Otherwise, this
++ * function returns `NULL`.
+ */
-+int parse_commit_in_graph_gently(struct repository *repo, struct object *object);
++struct commit *lookup_commit_in_graph(struct repository *repo, const struct object_id *id);
+
/*
* It is possible that we loaded commit contents from the commit buffer,
@@ commit-graph.h: int open_commit_graph(const char *graph_file, int *fd, struct st
## revision.c ##
@@ revision.c: static struct object *get_reference(struct rev_info *revs, const char *name,
- struct object *object = lookup_unknown_object(revs->repo, oid);
+ unsigned int flags)
+ {
+ struct object *object;
++ struct commit *commit;
- if (object->type == OBJ_NONE) {
-- int type = oid_object_info(revs->repo, oid, NULL);
-- if (type < 0 || !object_as_type(object, type, 1)) {
-+ /*
-+ * It's likely that the reference points to a commit, so we
-+ * first try to look it up via the commit-graph. If successful,
-+ * then we know it's a commit and don't have to unpack the
-+ * object header. We still need to assert that the object
-+ * exists, but given that we don't request any info about the
-+ * object this is a lot faster than `oid_object_info()`.
-+ */
-+ if (parse_commit_in_graph_gently(revs->repo, object) < 0) {
-+ int type = oid_object_info(revs->repo, oid, NULL);
-+ if (type < 0 || !object_as_type(object, type, 1)) {
-+ object = NULL;
-+ goto out;
-+ }
-+ } else if (!repo_has_object_file(revs->repo, oid)) {
- object = NULL;
- goto out;
- }
+ /*
+- * If the repository has commit graphs, repo_parse_commit() avoids
+- * reading the object buffer, so use it whenever possible.
++ * If the repository has commit graphs, we try to opportunistically
++ * look up the object ID in those graphs. Like this, we can avoid
++ * parsing commit data from disk.
+ */
+- if (oid_object_info(revs->repo, oid, NULL) == OBJ_COMMIT) {
+- struct commit *c = lookup_commit(revs->repo, oid);
+- if (!repo_parse_commit(revs->repo, c))
+- object = (struct object *) c;
+- else
+- object = NULL;
+- } else {
++ commit = lookup_commit_in_graph(revs->repo, oid);
++ if (commit)
++ object = &commit->object;
++ else
+ object = parse_object(revs->repo, oid);
+- }
+
+ if (!object) {
+ if (revs->ignore_missing)
Hi, this is version 2 of my patch series which tries to speed up connectivity checks in git-receive-pack(1). This version is a complete rewrite after my initial approach of using the quarantine directory has been shot down due to changes in semantics. This second version is thus an alternative approach using bitmaps. The implementation is quite simple: if we have a bitmap, then we walk the new tips until we hit a bitmapped object. Given that bitmapped objects are by definition fully connected, we can then be sure that all pushed tips are, too. I'm not sure I'm happy with results in this series. While it does show a speedup in the area I'm trying to optimize (repos with many refs), there are two things which make me hesitant: - First, there seems to be significant overhead in loading the packfile. This is something Peff has already pointed out in <YMypONmXt142dhbb@coredump.intra.peff.net> [1]. - In repos which have out-of-date bitmaps, we're potentially going to walk a lot more objects than we used to. Taking these two issues together, this version is probably more of a request for comments: do we want to make above tradeoffs? Are there better alternatives? Any input is welcome. Patrick Patrick Steinhardt (3): p5400: add perf tests for git-receive-pack(1) receive-pack: skip connectivity checks on delete-only commands connected: implement connectivity check using bitmaps builtin/receive-pack.c | 49 ++++++++----- connected.c | 136 +++++++++++++++++++++++++++++++++++ pack-bitmap.c | 4 +- pack-bitmap.h | 2 + t/perf/p5400-receive-pack.sh | 97 +++++++++++++++++++++++++ 5 files changed, 267 insertions(+), 21 deletions(-) create mode 100755 t/perf/p5400-receive-pack.sh