Hi, this is version 4 of my series to speed up connectivity checks. Given that v3 has received positive feedback, I finally stuck to the approach and only have a bunch of iterative changes based on your feedback. Changes compared to v3: - Patch 1/6 is new and splits up revs->no_walk into revs->no_walk which now only indicates whether to walk and revs->unserted_input, which indicates whether to sort input. - Patch 2/6 got some documentation for the new `--unsorted-input` option. Furthermore, we refuse `--no-walk`/`--no-walk=sorted` and `--unsorted-input` if used together. I've also added some tests for the new option. - Patch 3/6 has an updated commit message, detailing that `add_pending_oid()` only is a thin wrapper around `add_pending_object()`. - Patch 4/6 has an update commit message, stating that it's a prerequisite for 6/6. - Patch 5/6 is new, splitting out the logic to find a commit ID in the commit graph as a prerequisite for 6/6. - Patch 6/6 now also verifies that commits parsed only via the commit-graph exist in the ODB. I've also renamed `find_object_in_graph()` to `parse_commit_in_graph_gently()` to better reflect what the function does. With the added existence check in 6/6, the speedup is not as big as before (1.47x faster instead of 1.55x). But it's still very much worth it. In total, this patch series decreases `git rev-list --objects --unsorted --not --all --not $newrev` from 7.6s to 3.0s in my test repository. Thanks for all your feedback! Patrick Patrick Steinhardt (6): revision: separate walk and unsorted flags connected: do not sort input revisions revision: stop retrieving reference twice revision: avoid loading object headers multiple times 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 | 75 +++++++++++++++++++++--------- commit-graph.h | 7 +++ connected.c | 1 + revision.c | 52 +++++++++++++++++---- revision.h | 7 +-- t/t6000-rev-list-misc.sh | 38 +++++++++++++++ 9 files changed, 153 insertions(+), 40 deletions(-) Range-diff against v3: -: ---------- > 1: 67232910ac revision: separate walk and unsorted flags 1: 1fd83f726a ! 2: 9d7f484907 connected: do not sort input revisions @@ Commit message Signed-off-by: Patrick Steinhardt + ## Documentation/rev-list-options.txt ## +@@ Documentation/rev-list-options.txt: list of the missing objects. Object IDs are prefixed with a ``?'' character. + objects. + endif::git-rev-list[] + ++--unsorted-input:: ++ Show commits in the order they were given on the command line instead ++ of sorting them in reverse chronological order by commit time. Cannot ++ be combined with `--no-walk` or `--no-walk=sorted`. ++ + --no-walk[=(sorted|unsorted)]:: + Only show the given commits, but do not traverse their ancestors. + This has no effect if a range is specified. If the argument +@@ Documentation/rev-list-options.txt: endif::git-rev-list[] + given on the command line. Otherwise (if `sorted` or no argument + was given), the commits are shown in reverse chronological order + by commit time. +- Cannot be combined with `--graph`. ++ Cannot be combined with `--graph`. Cannot be combined with ++ `--unsorted-input` if `sorted` or no argument was given. + + --do-walk:: + Overrides a previous `--no-walk`. + ## connected.c ## @@ connected.c: int check_connected(oid_iterate_fn fn, void *cb_data, if (opt->progress) @@ 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")); + revs->unsorted_input = 1; } else if (!strcmp(arg, "--early-output")) { revs->early_output = 100; revs->topo_order = 1; -@@ revision.c: int prepare_revision_walk(struct rev_info *revs) - - if (!revs->reflog_info) - prepare_to_use_bloom_filter(revs); -- if (revs->no_walk != REVISION_WALK_NO_WALK_UNSORTED) -+ if (revs->no_walk != REVISION_WALK_NO_WALK_UNSORTED && !revs->unsorted_input) - commit_list_sort_by_date(&revs->commits); - if (revs->no_walk) - return 0; +@@ 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")); + revs->no_walk = 1; + } else if (skip_prefix(arg, "--no-walk=", &optarg)) { + /* +@@ revision.c: static int handle_revision_pseudo_opt(const char *submodule, + * 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"); - ## revision.h ## -@@ revision.h: struct rev_info { - simplify_history:1, - show_pulls:1, - topo_order:1, -+ unsorted_input:1, - simplify_merges:1, - simplify_by_decoration:1, - single_worktree:1, + ## t/t6000-rev-list-misc.sh ## +@@ t/t6000-rev-list-misc.sh: test_expect_success 'rev-list --count --objects' ' + test_line_count = $count actual + ' + ++test_expect_success 'rev-list --unsorted-input results in different sorting' ' ++ git rev-list --unsorted-input HEAD HEAD~ >first && ++ git rev-list --unsorted-input HEAD~ HEAD >second && ++ ! test_cmp first second && ++ sort first >first.sorted && ++ sort second >second.sorted && ++ 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' ' ++ cat >expect <<-EOF && ++ fatal: --no-walk is incompatible with --no-walk=unsorted and --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 && ++ ++ cat >expect <<-EOF && ++ fatal: --unsorted-input is incompatible with --no-walk and --no-walk=sorted ++ 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_done 2: db85480649 ! 3: d8e63d0943 revision: stop retrieving reference twice @@ Commit message revision: stop retrieving reference twice When queueing up references for the revision walk, `handle_one_ref()` - will resolve the reference's object ID and then queue the ID as pending - object via `add_pending_oid()`. But `add_pending_oid()` will again try - to resolve the object ID to an object, effectively duplicating the work - its caller already did before. + will resolve the reference's object ID via `get_reference()` and then + queue the ID as pending object via `add_pending_oid()`. But given that + `add_pending_oid()` is only a thin wrapper around `add_pending_object()` + which fist calls `get_reference()`, we effectively resolve the reference + twice and thus duplicate some of the work. - Fix the issue by instead calling `add_pending_object()`, which takes the - already-resolved object as input. In a repository with lots of refs, - this translates in a nearly 10% speedup: + Fix the issue by instead calling `add_pending_object()` directly, which + takes the already-resolved object as input. In a repository with lots of + refs, this translates into a near 10% speedup: Benchmark #1: HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev Time (mean ± σ): 5.015 s ± 0.038 s [User: 4.698 s, System: 0.316 s] 3: b9897e102a ! 4: ba8df5cad0 revision: avoid loading object headers multiple times @@ Commit message either a tag or a commit, we'd have a modest increase in memory consumption of about 12.5% here. + Note that on its own, this patch may not seem like a clear win. But it + is a prerequisite for the following patch, which will result in another + 37% speedup. + Signed-off-by: Patrick Steinhardt ## revision.c ## -: ---------- > 5: e33cd51ebf commit-graph: split out function to search commit position 4: f6fc2a5e6d ! 6: 900c5a9c60 revision: avoid hitting packfiles when commits are in commit-graph @@ Commit message directly fill in the commit object, otherwise we can still hit the disk to determine the object's type. - Expose a new function `find_object_in_graph()`, 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 `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: Benchmark #1: HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev - Time (mean ± σ): 4.465 s ± 0.037 s [User: 4.144 s, System: 0.320 s] - Range (min … max): 4.411 s … 4.514 s 10 runs + 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 Benchmark #2: HEAD: rev-list --unsorted-input --objects --quiet --not --all --not $newrev - Time (mean ± σ): 2.886 s ± 0.032 s [User: 2.570 s, System: 0.316 s] - Range (min … max): 2.826 s … 2.933 s 10 runs + 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 Summary 'HEAD: rev-list --unsorted-input --objects --quiet --not --all --not $newrev' ran - 1.55 ± 0.02 times faster than 'HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev' + 1.47 ± 0.02 times faster than 'HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev' Signed-off-by: Patrick Steinhardt ## commit-graph.c ## -@@ commit-graph.c: static int fill_commit_in_graph(struct repository *r, - return 1; +@@ commit-graph.c: static int find_commit_pos_in_graph(struct commit *item, struct commit_graph *g, + } } -+static int find_object_id_in_graph(const struct object_id *id, struct commit_graph *g, uint32_t *pos) -+{ -+ struct commit_graph *cur_g = g; -+ uint32_t lex_index; -+ -+ while (cur_g && !bsearch_graph(cur_g, (struct object_id *)id, &lex_index)) -+ cur_g = cur_g->base_graph; -+ -+ if (cur_g) { -+ *pos = lex_index + cur_g->num_commits_in_base; -+ return 1; -+ } -+ -+ return 0; -+} -+ -+int find_object_in_graph(struct repository *repo, struct object *object) ++int parse_commit_in_graph_gently(struct repository *repo, struct object *object) +{ + struct commit *commit; + uint32_t pos; @@ commit-graph.c: static int fill_commit_in_graph(struct repository *r, + if (!repo->objects->commit_graph) + return -1; + -+ if (!find_object_id_in_graph(&object->oid, repo->objects->commit_graph, &pos)) ++ if (!search_commit_pos_in_graph(&object->oid, repo->objects->commit_graph, &pos)) + return -1; + + commit = object_as_type(object, OBJ_COMMIT, 1); @@ commit-graph.c: static int fill_commit_in_graph(struct repository *r, + return 0; +} + - static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos) - { - uint32_t graph_pos = commit_graph_position(item); -@@ commit-graph.c: static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uin - *pos = graph_pos; - return 1; - } else { -- struct commit_graph *cur_g = g; -- uint32_t lex_index; -- -- while (cur_g && !bsearch_graph(cur_g, &(item->object.oid), &lex_index)) -- cur_g = cur_g->base_graph; -- -- if (cur_g) { -- *pos = lex_index + cur_g->num_commits_in_base; -- return 1; -- } -- -- return 0; -+ return find_object_id_in_graph(&item->object.oid, g, pos); - } - } - + static int parse_commit_in_graph_one(struct repository *r, + struct commit_graph *g, + struct commit *item) ## commit-graph.h ## -@@ commit-graph.h: int write_commit_graph(struct object_directory *odb, - enum commit_graph_write_flags flags, - const struct commit_graph_opts *opts); +@@ commit-graph.h: int open_commit_graph(const char *graph_file, int *fd, struct stat *st); + */ + int parse_commit_in_graph(struct repository *r, struct commit *item); -+int find_object_in_graph(struct repository *repo, struct object *object); ++/* ++ * 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. ++ */ ++int parse_commit_in_graph_gently(struct repository *repo, struct object *object); + - #define COMMIT_GRAPH_VERIFY_SHALLOW (1 << 0) - - int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags); + /* + * It is possible that we loaded commit contents from the commit buffer, + * but we also want to ensure the commit-graph content is correctly ## revision.c ## @@ revision.c: static struct object *get_reference(struct rev_info *revs, const char *name, @@ revision.c: static struct object *get_reference(struct rev_info *revs, const cha if (object->type == OBJ_NONE) { - int type = oid_object_info(revs->repo, oid, NULL); - if (type < 0 || !object_as_type(object, type, 1)) { -- object = NULL; -- goto out; -+ if (find_object_in_graph(revs->repo, object) < 0) { ++ /* ++ * 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; } - } - -- 2.32.0