Speed up connectivity checks via bitmaps

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 <[email protected]> [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

2.32.0

We'll the connectivity check logic for git-receive-pack(1) in the following commits to make it perform better. As a preparatory step, add some benchmarks such that we can measure these changes.

---
 t/perf/p5400-receive-pack.sh | 97 ++++++++++++++++++++++++++++++++++++
 1 file changed, 97 insertions(+)
 create mode 100755 t/perf/p5400-receive-pack.sh

new file mode 100755
index 0000000000..a945e014a3
@@ -0,0 +1,97 @@
+#!/bin/sh
+
+test_description="Tests performance of receive-pack"
+
+. ./perf-lib.sh
+
+test_perf_large_repo
+
+test_expect_success 'setup' '
+	# Create a main branch such that we do not have to rely on any specific
+	# branch to exist in the perf repository.
+	git switch --force-create main &&
+
+	# Set up a pre-receive hook such that no refs will ever be changed.
+	# This easily allows multiple perf runs, but still exercises
+	# server-side reference negotiation and checking for consistency.
+	mkdir hooks &&
+	write_script hooks/pre-receive <<-EOF &&
+		#!/bin/sh
+		echo "failed in pre-receive hook"
+		exit 1
+	EOF
+	cat >config <<-EOF &&
+		[core]
+			hooksPath=$(pwd)/hooks
+	EOF
+	GIT_CONFIG_GLOBAL="$(pwd)/config" &&
+	export GIT_CONFIG_GLOBAL &&
+
+	git switch --create updated &&
+	test_commit --no-tag updated
+'
+
+setup_empty() {
+	git init --bare "$2"
+}
+
+setup_clone() {
+	git clone --bare --no-local --branch main "$1" "$2"
+}
+
+setup_clone_bitmap() {
+	git clone --bare --no-local --branch main "$1" "$2" &&
+	git -C "$2" repack -Adb
+}
+
+# Create a reference for each commit in the target repository with extra-refs.
+# While this may be an atypical setup, biggish repositories easily end up with
+# hundreds of thousands of refs, and this is a good enough approximation.
+setup_extrarefs() {
+	git clone --bare --no-local --branch main "$1" "$2" &&
+	git -C "$2" log --all --format="tformat:create refs/commit/%h %H" |
+		git -C "$2" update-ref --stdin
+}
+
+# Create a reference for each commit in the target repository with extra-refs.
+# While this may be an atypical setup, biggish repositories easily end up with
+# hundreds of thousands of refs, and this is a good enough approximation.
+setup_extrarefs_bitmap() {
+	git clone --bare --no-local --branch main "$1" "$2" &&
+	git -C "$2" log --all --format="tformat:create refs/commit/%h %H" |
+		git -C "$2" update-ref --stdin &&
+	git -C "$2" repack -Adb
+}
+
+for repo in empty clone clone_bitmap extrarefs extrarefs_bitmap
+do
+	test_expect_success "$repo setup" '
+		rm -rf target.git &&
+		setup_$repo "$(pwd)" target.git
+	'
+
+	# If the target repository is the empty one, then the only thing we can
+	# do is to create a new branch.
+	case "$repo" in
+	empty)
+		refspecs="updated:new";;
+	*)
+		refspecs="updated:new updated:main main~10:main :main";;
+	esac
+
+	for refspec in $refspecs
+	do
+		test_expect_success "$repo seed $refspec" "
+			test_must_fail git push --force target.git '$refspec' \
+				--receive-pack='tee pack | git receive-pack' 2>err &&
+			grep 'failed in pre-receive hook' err
+		"
+
+		test_perf "$repo receive-pack $refspec" "
+			git receive-pack target.git <pack >negotiation &&
+			grep 'pre-receive hook declined' negotiation
+		"
+	done
+done
+
+test_done

2.32.0

I did these tests for 3/3 with git.git first, and results were significantly different. The performance issues I'm trying to fix with the connectivity check really only start to show up with largish repositories.

Makes sense.

Yup, will change.

I originally had code like this, but the issue with first creating all the repos is that it requires lots of disk space with large repos given that we'll clone it once per setup. Combined with the fact that I often run tests in tmpfs, this led to out-of-memory situations quite fast given that I had 3x6GB repositories plus the seeded packfiles in RAM.

This is why I've changed the setup to do the setup as we go, to bring disk usage down to something sane.

Patrick

Ah, I see. In that case wouldn't it be even better/faster with/without my suggestion to not use "clone" here, which would either be manually set up with alternates, or removing the --no-local flag.

You'd then share bulk of the object database, and just have different references. B.t.w. you'll probably get less noise/more relevant results if you then do a "pack-refs" after creating those N references.

So you should have:

0. Your "big" test repop (not used directly)
1. An empty repo
2. The "big" test repo itself, but just the HEAD branch, using alternates to point to #0
3. Ditto, but we create a crapload of refs for each commit for a version of #2.
4. Ditto #3 (could even "cp" over the packed refs file to save time), but add a bitmap on top.

Well, presumably for #4 we'd actually want to do the "git repack -Adb" for #2 (or enforce that #0 must have it), then just move the *.bitmap file(s) to #4. Now the test case conflates whether we have bitmaps with how well (re)packed something is.

I think this might also allow you to get rid of the pre-receive hook for a "real" push test, since the side-repos would be so cheap at this point that you could perhaps setup N of them to push into.

In the case where git-receive-pack(1) receives only commands which delete references, then per technical specification the client MUST NOT send a packfile. As a result, we know that no new objects have been received, which makes it a moot point to check whether all received objects are fully connected.

Fix this by not doing a connectivity check in case there were no pushed objects. Given that git-rev-walk(1) with only negative references will not do any graph walk, no performance improvements are to be expected. Conceptionally, it is still the right thing to do though.

The following tests were executed on linux.git and back up above expectation:

Test origin/master HEAD
---------------------------------------------------------------------------------------------------------

5400.4: empty receive-pack updated:new                178.36(428.22+164.36)   177.62(421.33+164.48) -0.4%
5400.7: clone receive-pack updated:new                0.10(0.08+0.02)         0.10(0.08+0.02) +0.0%
5400.9: clone receive-pack updated:main               0.10(0.08+0.02)         0.11(0.08+0.02) +10.0%
5400.11: clone receive-pack main~10:main              0.15(0.11+0.04)         0.15(0.10+0.05) +0.0%
5400.13: clone receive-pack :main                     0.01(0.00+0.01)         0.01(0.01+0.00) +0.0%
5400.16: clone_bitmap receive-pack updated:new        0.10(0.07+0.02)         0.09(0.06+0.02) -10.0%
5400.18: clone_bitmap receive-pack updated:main       0.10(0.07+0.02)         0.10(0.08+0.02) +0.0%
5400.20: clone_bitmap receive-pack main~10:main       0.15(0.11+0.03)         0.15(0.12+0.03) +0.0%
5400.22: clone_bitmap receive-pack :main              0.02(0.01+0.01)         0.01(0.00+0.00) -50.0%
5400.25: extrarefs receive-pack updated:new           32.34(20.72+11.86)      32.56(20.82+11.95) +0.7%
5400.27: extrarefs receive-pack updated:main          32.42(21.02+11.61)      32.52(20.64+12.10) +0.3%
5400.29: extrarefs receive-pack main~10:main          32.53(20.74+12.01)      32.39(20.63+11.97) -0.4%
5400.31: extrarefs receive-pack :main                 7.13(3.53+3.59)         7.15(3.80+3.34) +0.3%
5400.34: extrarefs_bitmap receive-pack updated:new    32.55(20.72+12.04)      32.65(20.68+12.18) +0.3%
5400.36: extrarefs_bitmap receive-pack updated:main   32.50(20.90+11.86)      32.67(20.93+11.94) +0.5%
5400.38: extrarefs_bitmap receive-pack main~10:main   32.43(20.88+11.75)      32.35(20.68+11.89) -0.2%
5400.40: extrarefs_bitmap receive-pack :main          7.21(3.58+3.63)         7.18(3.61+3.57) -0.4%

---
 builtin/receive-pack.c | 49 ++++++++++++++++++++++++++----------------
 1 file changed, 30 insertions(+), 19 deletions(-)

index a34742513a..b9263cec15 100644
@@ -1918,11 +1918,8 @@ static void execute_commands(struct command *commands,
 			     struct shallow_info *si,
 			     const struct string_list *push_options)
 {
-	struct check_connected_options opt = CHECK_CONNECTED_INIT;
 	struct command *cmd;
 	struct iterate_data data;
-	struct async muxer;
-	int err_fd = 0;
 	int run_proc_receive = 0;
 
 	if (unpacker_error) {

@@ -1931,25 +1928,39 @@ static void execute_commands(struct command *commands,
 		return;
 	}
 
-	if (use_sideband) {
-		memset(&muxer, 0, sizeof(muxer));
-		muxer.proc = copy_to_sideband;
-		muxer.in = -1;
-		if (!start_async(&muxer))
-			err_fd = muxer.in;
-		/* ...else, continue without relaying sideband */
-	}
-
 	data.cmds = commands;
 	data.si = si;
-	opt.err_fd = err_fd;
-	opt.progress = err_fd && !quiet;
-	opt.env = tmp_objdir_env(tmp_objdir);
-	if (check_connected(iterate_receive_command_list, &data, &opt))
-		set_connectivity_errors(commands, si);
 
-	if (use_sideband)
-		finish_async(&muxer);
+	/*
+	 * If received commands only consist of deletions, then the client MUST
+	 * NOT send a packfile because there cannot be any new objects in the
+	 * first place. As a result, we do not set up a quarantine environment
+	 * because we know no new objects will be received. And that in turn
+	 * means that we can skip connectivity checks here.
+	 */
+	if (tmp_objdir) {
+		struct check_connected_options opt = CHECK_CONNECTED_INIT;
+		struct async muxer;
+		int err_fd = 0;
+
+		if (use_sideband) {
+			memset(&muxer, 0, sizeof(muxer));
+			muxer.proc = copy_to_sideband;
+			muxer.in = -1;
+			if (!start_async(&muxer))
+				err_fd = muxer.in;
+			/* ...else, continue without relaying sideband */
+		}
+
+		opt.err_fd = err_fd;
+		opt.progress = err_fd && !quiet;
+		opt.env = tmp_objdir_env(tmp_objdir);
+		if (check_connected(iterate_receive_command_list, &data, &opt))
+			set_connectivity_errors(commands, si);
+
+		if (use_sideband)
+			finish_async(&muxer);
+	}
 
 	reject_updates_to_hidden(commands);
 

2.32.0

Is it just per specification, or do we also have assertions/tests for what happens in that case?

We're doing less work so I'd expect to te be faster, but do these tests really back that up? From eyeballing these I can't find a line where the confidence intervals don't overlap, e.g. the +10% regresison is a .10->.11 "regression" with a [+-] 0.02 (so within the error bars) etc, ditto for the -50% improvement.

Perhaps the error bars will reduce with a high GIT_PERF_REPEAT_COUNT, or the re-arrangement for keeping things hotter in cache that I suggested in 1/3.

Urgh, nevermind. Just after I sent this I re-read t/perf/README. I'd somehow recalled that we'd emit error bars from it, but that's Elapsed(User + System), not Time(.. + errorbar) as I thought, nevermind. Still, numbers are such that I wonder if the differences are getting lost in some noise...

I'm not sure whether we have any tests for this, but I've seen several hangs already in case the server did expect a packfile or errors in case the client sent one. In any case, the technical specification in Documentation/technical/pack-protocol.txt is quite clear on this:

The packfile MUST NOT be sent if the only command used is 'delete'.

As I've layed out in the commit message, all we save now is spawning git-rev-list(1). The command list iterator which is used to feed data into git-rev-list(1) wouldn't provide any references given that it skips over all queued updates whose new OID is the null OID. So git-rev-list(1) doesn't receive any input except --not --all and thus can exit without doing a graph walk.

Above numbers simply show that this saving is not significant and gets lost in the noise, at least on Linux. Windows may show slightly different numbers given that spawning of processes is slower there, but I don't expect it to matter much there, either.

Patrick

Even though it's not producing any exciting results, I agree this is still a reasonable thing to do.

I'm actually surprised it didn't help in your many-ref cases, just because I think the traversal machinery is pretty eager to parse tags and commits which are fed as tips.

If I run "git rev-list --not --all --stdin </dev/null" in linux.git, it takes about 35ms. But if I make a ton of refs, like:

  git rev-list HEAD |
  perl -lpe 's{.*}{update refs/foo/commit$. $&}' |
  git update-ref --stdin
  git pack-refs --all --prune

then it takes about 2000ms (if you don't pack it's even worse, as you might expect).

So how come we don't see that improvement in your "extrarefs" cases? Looking at patch 1, they also seem to make one ref for every commit.

I think the answer may be below...

          if (fn(cb_data, &oid)) {
                  if (opt->err_fd)
                          close(opt->err_fd);
                  return err;
          }

The "--stdin" should be before "--not", of course, to mimic a real connectivity check. But it doesn't matter in this case because we're feeding an empty input. :)

-Peff

Hah, thanks for solving this riddle. I always kind of wondered what this was supposed to do, where my assumption simply was "It's in case the callback returns an error". But your explanation is obviously correct and neatly explains what's going on. So yes, I'll drop this patch.

Patrick

The connectivity checks are currently implemented via git-rev-list(1):
we simply ignore any objects which are reachable from preexisting refs via --not --all, and pass all new refs which are to be checked via its stdin. While this works well enough for repositories which do not have a lot of references, it's clear that --not --all will linearly scale with the number of refs which do exist: for each reference, we'll walk through its commit as well as its five parent commits (defined via SLOP). Given that many major hosting sites which use a pull/merge request workflow keep refs to the request's HEAD, this effectively means that --not --all will do a nearly complete graph walk.

This commit implements an alternate strategy if the target repository has bitmaps. Objects referenced by a bitmap are by definition always fully connected, so they form a natural boundary between old revisions and new revisions. With this alternate strategy, we walk all given new object IDs. Whenever we hit any object which is covered by the bitmap, we stop the walk.

The logic only kicks in in case we have a bitmap in the repository. If not, we wouldn't be able to efficiently abort the walk because we cannot easily tell whether an object already exists in the target repository and, if it does, whether it's fully connected. As a result, we'd have to perform a always do graph walk in this case. Naturally, we could do the same thing the previous git-rev-list(1) implementation did in that case and just use preexisting branch tips as boundaries. But for now, we just keep the old implementation for simplicity's sake given that performance characteristics are likely not significantly different.

An easier solution may have been to simply add --use-bitmap-index to the git-rev-list(1) invocation, but benchmarks have shown that this is not effective: performance characteristics remain the same except for some cases where the bitmap walks performs much worse compared to the non-bitmap walk

The following benchmarks have been performed in linux.git:

Test origin/master HEAD
---------------------------------------------------------------------------------------------------------

5400.4: empty receive-pack updated:new                176.02(387.28+175.12)   176.86(388.75+175.51) +0.5%
5400.7: clone receive-pack updated:new                0.10(0.09+0.01)         0.08(0.06+0.03) -20.0%
5400.9: clone receive-pack updated:main               0.09(0.08+0.01)         0.09(0.06+0.03) +0.0%
5400.11: clone receive-pack main~10:main              0.14(0.11+0.03)         0.13(0.11+0.02) -7.1%
5400.13: clone receive-pack :main                     0.01(0.01+0.00)         0.02(0.01+0.00) +100.0%
5400.16: clone_bitmap receive-pack updated:new        0.10(0.09+0.01)         0.28(0.13+0.15) +180.0%
5400.18: clone_bitmap receive-pack updated:main       0.10(0.08+0.02)         0.28(0.12+0.16) +180.0%
5400.20: clone_bitmap receive-pack main~10:main       0.13(0.11+0.02)         0.26(0.12+0.14) +100.0%
5400.22: clone_bitmap receive-pack :main              0.01(0.01+0.00)         0.01(0.01+0.00) +0.0%
5400.25: extrarefs receive-pack updated:new           32.14(20.76+11.59)      32.35(20.52+12.03) +0.7%
5400.27: extrarefs receive-pack updated:main          32.08(20.54+11.75)      32.10(20.78+11.53) +0.1%
5400.29: extrarefs receive-pack main~10:main          32.14(20.66+11.68)      32.27(20.65+11.83) +0.4%
5400.31: extrarefs receive-pack :main                 7.09(3.56+3.53)         7.10(3.70+3.40) +0.1%
5400.34: extrarefs_bitmap receive-pack updated:new    32.41(20.59+12.02)      7.36(3.76+3.60) -77.3%
5400.36: extrarefs_bitmap receive-pack updated:main   32.26(20.53+11.95)      7.34(3.56+3.78) -77.2%
5400.38: extrarefs_bitmap receive-pack main~10:main   32.44(20.77+11.90)      7.40(3.70+3.70) -77.2%
5400.40: extrarefs_bitmap receive-pack :main          7.09(3.62+3.46)         7.17(3.79+3.38) +1.1%

As expected, performance doesn't change in cases where we do not have a bitmap available given that the old code path still kicks in. In case we do have bitmaps, this is kind of a mixed bag: while git-receive-pack(1) is slower in a "normal" clone of linux.git, it is significantly faster for a clone with lots of references. The slowness can potentially be explained by the overhead of loading the bitmap. On the other hand, the new code is faster as expected in repos which have lots of references given that we do not have to mark all negative references anymore.

---
 connected.c   | 136 ++++++++++++++++++++++++++++++++++++++++++++++++++
 pack-bitmap.c |   4 +-
 pack-bitmap.h |   2 +
 3 files changed, 140 insertions(+), 2 deletions(-)

index b18299fdf0..474275a52f 100644
@@ -6,6 +6,127 @@
 #include "transport.h"
 #include "packfile.h"
 #include "promisor-remote.h"
+#include "object.h"
+#include "tree-walk.h"
+#include "commit.h"
+#include "tag.h"
+#include "progress.h"
+#include "oidset.h"
+#include "pack-bitmap.h"
+
+#define QUEUED (1u<<0)
+
+static int queue_object(struct repository *repo,
+			struct bitmap_index *bitmap,
+			struct object_array *pending,
+			const struct object_id *oid)
+{
+	struct object *object;
+
+	/*
+	 * If the object ID is part of the bitmap, then we know that it must by
+	 * definition be reachable in the target repository and be fully
+	 * connected. We can thus skip checking the objects' referenced
+	 * objects.
+	 */
+	if (bitmap_position(bitmap, oid) >= 0)
+		return 0;
+
+	/* Otherwise the object is queued up for a connectivity check. */
+	object = parse_object(repo, oid);
+	if (!object) {
+		/* Promisor objects do not need to be traversed. */
+		if (is_promisor_object(oid))
+			return 0;
+		return -1;
+	}
+
+	/*
+	 * If the object has been queued before already, then we don't need to
+	 * do so again.
+	 */
+	if (object->flags & QUEUED)
+		return 0;
+	object->flags |= QUEUED;
+
+	/*
+	 * We do not need to queue up blobs given that they don't reference any
+	 * other objects anyway.
+	 */
+	if (object->type == OBJ_BLOB)
+		return 0;
+
+	add_object_array(object, NULL, pending);
+
+	return 0;
+}
+
+static int check_object(
+	struct repository *repo,
+	struct bitmap_index *bitmap,
+	struct object_array *pending,
+	const struct object *object)
+{
+	int ret = 0;
+
+	if (object->type == OBJ_TREE) {
+		struct tree *tree = (struct tree *)object;
+		struct tree_desc tree_desc;
+		struct name_entry entry;
+
+		if (init_tree_desc_gently(&tree_desc, tree->buffer, tree->size))
+			return error(_("cannot parse tree entry"));
+		while (tree_entry_gently(&tree_desc, &entry))
+			ret |= queue_object(repo, bitmap, pending, &entry.oid);
+
+		free_tree_buffer(tree);
+	} else if (object->type == OBJ_COMMIT) {
+		struct commit *commit = (struct commit *) object;
+		struct commit_list *parents;
+
+		for (parents = commit->parents; parents; parents = parents->next)
+			ret |= queue_object(repo, bitmap, pending, &parents->item->object.oid);
+
+		free_commit_buffer(repo->parsed_objects, commit);
+	} else if (object->type == OBJ_TAG) {
+		ret |= queue_object(repo, bitmap, pending, get_tagged_oid((struct tag *) object));
+	} else {
+		return error(_("unexpected object type"));
+	}
+
+	return ret;
+}
+
+/*
+ * If the target repository has a bitmap, then we treat all objects reachable
+ * via the bitmap as fully connected. Bitmapped objects thus serve as the
+ * boundary between old and new objects.
+ */
+static int check_connected_with_bitmap(struct repository *repo,
+				       struct bitmap_index *bitmap,
+				       oid_iterate_fn fn, void *cb_data,
+				       struct check_connected_options *opt)
+{
+	struct object_array pending = OBJECT_ARRAY_INIT;
+	struct progress *progress = NULL;
+	size_t checked_objects = 0;
+	struct object_id oid;
+	int ret = 0;
+
+	if (opt->progress)
+		progress = start_delayed_progress("Checking connectivity", 0);
+
+	while (!fn(cb_data, &oid))
+		ret |= queue_object(repo, bitmap, &pending, &oid);
+	while (pending.nr) {
+		ret |= check_object(repo, bitmap, &pending, object_array_pop(&pending));
+		display_progress(progress, ++checked_objects);
+	}
+
+	stop_progress(&progress);
+	object_array_clear(&pending);
+	return ret;
+}
 
 /*
  * If we feed all the commits we want to verify to this command

@@ -28,12 +149,27 @@ int check_connected(oid_iterate_fn fn, void *cb_data,
 	int err = 0;
 	struct packed_git *new_pack = NULL;
 	struct transport *transport;
+	struct bitmap_index *bitmap;
 	size_t base_len;
 
 	if (!opt)
 		opt = &defaults;
 	transport = opt->transport;
 
+	bitmap = prepare_bitmap_git(the_repository);
+	if (bitmap) {
+		/*
+		 * If we have a bitmap, then we can reuse the bitmap as
+		 * boundary between old and new objects.
+		 */
+		err = check_connected_with_bitmap(the_repository, bitmap,
+						  fn, cb_data, opt);
+		if (opt->err_fd)
+			close(opt->err_fd);
+		free_bitmap_index(bitmap);
+		return err;
+	}
+
 	if (fn(cb_data, &oid)) {
 		if (opt->err_fd)
 			close(opt->err_fd);

index d90e1d9d8c..d88a882ee1 100644
@@ -418,8 +418,8 @@ static inline int bitmap_position_packfile(struct bitmap_index *bitmap_git,
 	return pos;
 }
 
-static int bitmap_position(struct bitmap_index *bitmap_git,
-			   const struct object_id *oid)
+int bitmap_position(struct bitmap_index *bitmap_git,
+		    const struct object_id *oid)
 {
 	int pos = bitmap_position_packfile(bitmap_git, oid);
 	return (pos >= 0) ? pos : bitmap_position_extended(bitmap_git, oid);

index 99d733eb26..7b4b386107 100644
@@ -63,6 +63,8 @@ int rebuild_existing_bitmaps(struct bitmap_index *, struct packing_data *mapping
 void free_bitmap_index(struct bitmap_index *);
 int bitmap_walk_contains(struct bitmap_index *,
 			 struct bitmap *bitmap, const struct object_id *oid);
+int bitmap_position(struct bitmap_index *bitmap_git,
+		    const struct object_id *oid);
 
 /*
  * After a traversal has been performed by prepare_bitmap_walk(), this can be

2.32.0

I haven't had a chance to look closely at your patches yet, but I like the idea of using an object's presence in the reachability bitmap to perform the connectivity checks.

I have wondered how much performance we could eek out by being able to load the .bitmap file without having to read each individual bitmap contained in it. (I believe Peff mentioned this elsewhere, but) I would be be interested in something as simple as an optional .bitmap extension which indicates the list of commits which have a bitmap, and their offset within the bitmap.

I'll try this out myself and see if it's worth it. (As an aside, I'll be offline next week, so it may take me a little while to post something to the list).

I gave implementing this a shot and it seems to have produced some good improvements, although there are definitely some areas where it does better than others.

Here are some results running on linux.git with a cold cache, counting objects for commit 2ab38c17aa, which I picked deliberately since I know it has a bitmap:

    $ hyperfine \
      'GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2' \
      'GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2' \
      --prepare='sync; echo 3 | sudo tee /proc/sys/vm/drop_caches'

		Benchmark #1: GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2
			Time (mean ± σ):     141.1 ms ±   2.5 ms    [User: 13.0 ms, System: 64.3 ms]
			Range (min … max):   136.2 ms … 143.4 ms    10 runs

		Benchmark #2: GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2
			Time (mean ± σ):      28.7 ms ±   3.2 ms    [User: 6.5 ms, System: 10.0 ms]
			Range (min … max):    22.0 ms …  31.0 ms    21 runs

		Summary
			'GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2' ran
				4.91 ± 0.55 times faster than 'GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2'

That's sort of a best-case scenario, because we're not doing any traversal between the bitmapped commits and the traversal tips. But even if we do have some traversal, the results are still pretty good. Swapping out 2ab38c17aa for --branches yields a 5.02x improvement from 141.0ms down to 28.1ms.

Adding in --tags basically negates any improvement (having the commit table extension eeks out a 1.03x improvement from 645.7ms down to 626.0ms. perf record shows that 30% of time is spent outside of the bitmap code.

If you want to give this a try yourself, I highly recommend generating your bitmap while packing with -c pack.writeReverseIndex. Building a reverse index on-the-fly also seems to negate any performance improvements here, so having an on-disk reverse index is more or less a prerequisite to testing this out.

Extremely gross and inscrutable code can be found on the 'tb/bitmap-commit-table' branch of my fork [1].

Thanks,
Taylor

[1]: https://github.com/git/git/compare/master...ttaylorr:tb/bitmap-commit-table

I was curious why your machine is so much slower than mine. With the current bitmap format, I can run that command pretty consistently in ~22ms. But I think the trick here is the cache-dropping. The cold-cache performance is going to be very dependent on faulting in the extra bytes (and you can see that the actual CPU time in the first case is much smaller than the runtime, so it really is waiting on the disk).

In the warm-cache case, the improvement seems to go away (or maybe I'm holding it wrong; even in the cold-cache case I don't get anywhere near as impressive a speedup as you showed above). Which isn't to say that cold-cache isn't sometimes important, and this may still be worth doing. But it really seems like the CPU involve in walking over the file isn't actually that much.

I got an even more curious result when adding in "--not --all" (which the connectivity check under discussion would do). There the improvement from your patch should be even less, because we'd end up reading most of the bitmaps anyway. But I got:

  $ hyperfine \
       'GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2 --not --all' \
       'GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2 --not --all' \
       --prepare='sync; echo 3 | sudo tee /proc/sys/vm/drop_caches'

  Benchmark #1: GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2 --not --all
    Time (mean ± σ):      4.197 s ±  0.823 s    [User: 284.7 ms, System: 734.5 ms]
    Range (min … max):    2.612 s …  5.009 s    10 runs
   
  Benchmark #2: GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2 --not --all
    Time (mean ± σ):      4.498 s ±  0.612 s    [User: 315.3 ms, System: 829.7 ms]
    Range (min … max):    3.010 s …  5.072 s    10 runs
   
  Summary
    'GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2 --not --all' ran
      1.07 ± 0.26 times faster than 'GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2 --not --all'

which was actually faster _without_ the extra table. 7% isn't a lot, especially for a cold-cache test, so that may just be noise. But it doesn't seem like a clear win to me.

-Peff

Hmm. I think that you might be holding it wrong, or at least I'm able to reproduce some substantial improvements in the warm cache case with limited traversals. Here are a few runs of the same hyperfine invocation, just swapping the --prepare which drops the disk cache with --warmup 3 which populates them.

  $ hyperfine \
    'GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2' \
    'GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2' \
    --warmup 3
  Benchmark #1: GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2
    Time (mean ± σ):      23.1 ms ±   6.4 ms    [User: 9.4 ms, System: 13.6 ms]
    Range (min … max):    13.8 ms …  35.8 ms    161 runs

  Benchmark #2: GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2
    Time (mean ± σ):      11.2 ms ±   1.8 ms    [User: 7.5 ms, System: 3.7 ms]
    Range (min … max):     4.7 ms …  12.6 ms    238 runs

Swapping just loading an individual commit to look at all branches, I get the following 2.01x improvement:

  Benchmark #1: GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index --branches
    Time (mean ± σ):      22.5 ms ±   5.8 ms    [User: 8.5 ms, System: 14.0 ms]
    Range (min … max):    14.1 ms …  34.9 ms    157 runs

  Benchmark #2: GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index --branches
    Time (mean ± σ):      11.2 ms ±   1.9 ms    [User: 7.1 ms, System: 4.1 ms]
    Range (min … max):     4.7 ms …  13.4 ms    239 runs

But there are some diminishing returns when I include --tags, too, since I assume that there is some more traversal involved in older parts of the kernel's history which aren't as well covered by bitmaps. But it's still an improvement of 1.17x (give or take .31x, according to hyperfine).

  Benchmark #1: GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index --branches --tags
    Time (mean ± σ):      66.8 ms ±  12.4 ms    [User: 43.6 ms, System: 23.1 ms]
    Range (min … max):    54.4 ms …  92.3 ms    39 runs

  Benchmark #2: GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index --branches --tags
    Time (mean ± σ):      57.3 ms ±  10.9 ms    [User: 37.5 ms, System: 19.8 ms]
    Range (min … max):    44.0 ms …  79.5 ms    45 runs

Interesting. Discussion about that series aside, I go from 28.6ms without reading the table to 35.1ms reading it, which is much better in absolute timings, but much worse relatively speaking.

I can't quite seem to make sense of the perf report on that command. Most of the time is spent faulting pages in, but most of the time measured in the "git" object is in ubc_check. I don't really know how to interpret that, but I'd be curious if you had any thoughts.

I was just looking at:

  $ GIT_READ_COMMIT_TABLE=1 perf record -F997 -g \
      git.compile rev-list --count --objects \
      --use-bitmap-index 2ab38c17aac --not --all
  $ perf report

Thanks,
Taylor

OK, I definitely was holding it wrong. It turns out that it helps to run the custom version of Git when passing in the pack.writebitmapcomittable option. (I regret there is no portable way to communicate a facepalm image over plain text).

So that helped, but I did seem some other interesting bits.

Here's my cold-cache time for the commit you selected:

  $ export commit=2ab38c17aac10bf55ab3efde4c4db3893d8691d2
  $ hyperfine \
      -L table 0,1 \
      'GIT_READ_COMMIT_TABLE={table} git.compile rev-list --count --objects --use-bitmap-index $commit' \
      --prepare='sync; echo 3 | sudo tee /proc/sys/vm/drop_caches'

  Benchmark #1: GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index $commit
    Time (mean ± σ):      1.420 s ±  0.162 s    [User: 196.1 ms, System: 293.7 ms]
    Range (min … max):    1.083 s …  1.540 s    10 runs
   
  Benchmark #2: GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index $commit
    Time (mean ± σ):      1.319 s ±  0.256 s    [User: 171.1 ms, System: 237.1 ms]
    Range (min … max):    0.773 s …  1.588 s    10 runs
   
  Summary
    'GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index $commit' ran
      1.08 ± 0.24 times faster than 'GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index $commit'

So better, but well within the noise (and I had a few runs where it actually performed worse). But you picked that commit because you knew it was bitmapped, and it's not in my repo. If I switch to a commit that is covered in my repo, then I get similar results to yours:

  $ export commit=9b1ea29bc0d7b94d420f96a0f4121403efc3dd85
  $ hyperfine \
        -L table 0,1 \
        'GIT_READ_COMMIT_TABLE={table} git.compile rev-list --count --objects --use-bitmap-index $commit' \
        --prepare='sync; echo 3 | sudo tee /proc/sys/vm/drop_caches'

  Benchmark #1: GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index $commit
    Time (mean ± σ):     309.3 ms ±  61.0 ms    [User: 19.4 ms, System: 79.0 ms]
    Range (min … max):   154.4 ms … 386.7 ms    10 runs
   
  Benchmark #2: GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index $commit
    Time (mean ± σ):      33.7 ms ±   2.5 ms    [User: 3.3 ms, System: 3.6 ms]
    Range (min … max):    31.5 ms …  46.5 ms    33 runs

  Summary
  'GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index $commit' ran
    9.19 ± 1.94 times faster than 'GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index $commit'

And the effect continues in the warm cache case, though the absolute numbers are much tinier:

  Benchmark #1: GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index $commit
    Time (mean ± σ):      12.0 ms ±   0.3 ms    [User: 4.6 ms, System: 7.4 ms]
    Range (min … max):    11.4 ms …  13.2 ms    219 runs

  Benchmark #2: GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index $commit
    Time (mean ± σ):       3.0 ms ±   0.4 ms    [User: 2.3 ms, System: 0.8 ms]
    Range (min … max):     2.6 ms …   5.5 ms    851 runs

  Summary
    'GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index $commit' ran
      3.95 ± 0.55 times faster than 'GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index $commit'

That implies to me that yes, it really is saving time, especially in the cold-cache case. But if you have to do any actual fill-in traversal, the benefits get totally lost in the noise. _Especially_ in the cold-cache case, because then we're faulting in the actual object data, etc.

By the way, one other thing I noticed is that having a fully-build commit-graph also made a big difference (much bigger than this patch), especially for the non-bitmapped commit. Which makes sense, since it is saving us from loading commit objects from disk during fill-in traversal.

So I dunno. There's absolutely savings for some cases, but I suspect in practice it's not going to really be noticeable. Part of me says "well, if it ever provides a benefit and there isn't a downside, why not?". So just devil's advocating on downsides for a moment:

- there's some extra complexity in the file format and code to read and write these (and still fall back to the old system when they're absent). I don't think it's a deal-breaker, as it's really not that complicated a feature.

- we're using extra bytes on disk (and the associated cold block cache effects there). It's not very many bytes, though (I guess 20 for the hash, plus a few offset integers; if we wanted to really penny-pinch, we could probably store 32-bit pointers to the hashes in the associated .idx file, at the cost of an extra level of indirection while binary searching). But that is only for a few hundred commits that are bitmapped, not all of them. And it's balanced by not needing to allocate a similar in-memory lookup table in each command. So it's probably a net win.

I suspect that's mostly noise. With "--not --all" in a regular linux.git repo, I don't find any statistical difference.

In a fake repo with one ref per commit, everything is even more lost in the noise (because we spend like 2000ms loading up all the tip commits). I suspect it's worse on a real repo with lots of refs (the "spiky branches" thing I mentioned earlier in the thread), since there we'd have to do even more fill-in traversal.

ubc_check() is basically "computing sha1" (we check the sha1 on every object we call parse_object() for). I'd guess it's just time spent loading the negative tips (commits if you don't have a commit graph, plus tags to peel, though I guess we should be using the packed-refs peel optimization here).

-Peff

That's definitely true. I would say that any patches in this direction would have the general sense of "this helps in some cases where we don't have to do much traversal by eliminating an unnecessarily eager part of loading bitmaps, and does not make anything worse when the bitmap coverage is incomplete (and requires traversing)."

I would add that these effects change with the size of the bitmap. Let's just consider the "count the number of objects in a bitmapped commit". On my local copy of the kernel, I see a relatively modest improvement:

    $ tip=2ab38c17aac10bf55ab3efde4c4db3893d8691d2
    $ hyperfine \
      'GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index $tip' \
      'GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index $tip' \
      --warmup=3
    Benchmark #1: GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index $tip
      Time (mean ± σ):      21.5 ms ±   5.6 ms    [User: 8.7 ms, System: 12.7 ms]
      Range (min … max):    12.4 ms …  34.2 ms    170 runs

    Benchmark #2: GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index $tip
      Time (mean ± σ):      10.6 ms ±   1.6 ms    [User: 7.1 ms, System: 3.5 ms]
      Range (min … max):     4.5 ms …  11.9 ms    258 runs

but on my copy of the kernel's fork network repo (that containing all of torvalds/linux's objects, as well as all of its fork's objects, too), the magnitude of the effect is much bigger:

    Benchmark #1: GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index $tip
      Time (mean ± σ):     332.3 ms ±  12.6 ms    [User: 210.4 ms, System: 121.8 ms]
      Range (min … max):   322.7 ms … 362.4 ms    10 runs

    Benchmark #2: GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index $tip
      Time (mean ± σ):     260.0 ms ±   9.3 ms    [User: 191.0 ms, System: 69.0 ms]
      Range (min … max):   250.4 ms … 272.8 ms    11 runs

That's a more modest 1.28x improvement (versus 2.03x in just linux.git), but the overall magnitude is much bigger.

This is basically an effect of the bitmaps themselves. In the latter example, there are more bitmaps (around 1.6k of them, versus just over 500 in my copy of just the kernel), and each of them are much wider (because there are far more objects, 40.2M versus just 7.8M). So there is more work to do, and the page cache is less efficient for us because we can't fit as much of the .bitmap file in the page cache at once.

Likewise having an reverse index helps a lot, too. That radix sort scales linearly with the number of objects in the bitmapped pack (plus you're paying the cost to allocate more heap, etc).

This clouded up some of my timings in p5310, which made me think that it would be a good idea to git config pack.writeReverseIndex true in the setup for those tests, but an even better direction would be to change the default of pack.writeReverseIndex to true everywhere.

I agree with both of these. The complexity is manageable, I think, especially since I dropped support for the extended offset table (having a bitmap file that is >2GiB seems extremely unlikely to me, and it's possible to add support for it in the future) and
fanout table (there are usually less than <1k commits with bitmaps, so a 256-entry fanout table doesn't seem to help much in benchmarking).

So what's left of the format is really just:

- a table of object id's
- a table of (uint32_t, uint32_t) tuples describing the (short) offset of the bitmap, and an index position of the xor'd bitmap (if one exists).

Worth benchmarking, at least.

I'll be offline for the next ~week and a half for my wedding, but I'll post some patches to the list shortly after I get back.

Thanks,
Taylor

Thanks, this is much more compelling. 70ms is a lot of startup time to save. I am a little surprised that a no-traversal bitmap query like this would still take 300ms. I wonder if 2ab38c17aac actually got a bitmap in your second example (and if not, then there are probably cases where the relative speedup would be even more impressive).

Yes, I'd be in favor of that. IMHO the reason to make it configurable at all was not because it's ever a bad idea, but just to phase it in and get experience with it (and to give an escape hatch for debugging it).

It's probably _less_ useful for local clones that are not serving fetches. But every push is already generating the same thing in-memory, so it seems like a good tradeoff to just use it everywhere.

Yeah, that really seems quite simple. I'd have to judge after seeing the cleaned up code, but I suspect it's not going to be a burden.

Yep, no rush. Thanks for looking into this.

-Peff

Hmm. We _do_ still have to mark those negative references now, though (the bitmap code still considers each as a reachability tip for the "have" side of the traversal). It's just that we may have to do less traversal on them, if they're mentioned by other bitmaps.

So in that sense I don't think your "a ref for every commit" cases are all that interesting. Any bitmap near the tip of history is going to include a bit for all those old commits, because our fake set of refs are all reachable. A much more interesting history is when you have a bunch of little unreachable spikes coming off the main history.

This is common if you have a lot of branches in the repo, but also if you maintain a lot of book-keeping refs (like the refs/pull/* we do at GitHub; I assume GitLab does something similar).

Here are some real-world numbers from one of the repos that gives us frequent problems with bitmaps. refs/pull/9937/head in this case is an unmerged PR with 8 commits on it.

[without bitmaps, full check but with count to suppress output]

  $ time git rev-list --count refs/pull/9937/head --objects --not --all
  0
  real	0m1.280s
  user	0m1.131s
  sys	0m0.148s

  [same, but with bitmaps]
  $ time git rev-list --count refs/pull/9937/head --objects --not --all --use-bitmap-index
  0

real 1m38.146s
user 1m30.015s
sys 0m3.443s

Yikes. Now this is a pretty extreme case, as it has a lot of bookkeeping refs. If we limited ourselves to just the branches (in which case our unmerged PR will appear to have a couple new commits), though, we still get:

  $ time git rev-list --count refs/pull/9937/head --objects --not --branches
  64
  real	0m0.366s
  user	0m0.272s
  sys	0m0.093s

  $ time git rev-list --count refs/pull/9937/head --objects --not --branches --use-bitmap-index
  61
  real	0m10.372s
  user	0m9.633s
  sys	0m0.736s

which is still a pretty bad regression (the difference in the output is expected; the regular traversal is not as thorough at finding objects which appear in non-contiguous sections of history).

Again, this is one of the repositories that routinely gives us problems. But even on git/git, which is usually not a problematic repo, I get:

  $ time git rev-list refs/pull/986/head --objects --not --all
  real	0m0.121s
  user	0m0.024s
  sys	0m0.097s

  $ time git rev-list refs/pull/986/head --objects --not --all --use-bitmap-index
  real	0m12.406s
  user	0m5.843s
  sys	0m0.734s

So even if this tradeoff might help on balance, it really makes some cases pathologically bad.

-Peff

Yeah, this kind of brings us back to the old topic of pathological performance combined with bitmaps. As I said in the cover letter, I haven't been particularly happy with the results of this version, but rather intended it as an RFC. Taylor's extension does look quite interesting, but ultimately I'm not sure whether we want to use bitmaps for connectivity checks. Your spiky-branches example neatly highlights that it cannot really work in the general case.

I wonder where that leaves us. I'm out of ideas on how to solve this in the general case for any push/connectivity check, so I guess that any alternative approach would instead make use of heuristics.

In the current context, I care mostly about the user-side context, which is interactive pushes. Without knowing the numbers, my bet is that the most frequent usecase here is the push of a single branch with only a bunch of commits. If the pushed commit is a descendant of any existing commit, then we can limit the connectivity check to git rev-list --objects $newoid --not $oldoid instead of --not --all. There's two issues:

- "descendant of any existing commit" is again the same territory performance-wise as --all. So we can heuristically limit this either to the to-be-updated-target reference if it exists, or HEAD.

- Calculating ancestry can be expensive if there's too many commits in between or if history is unrelated. We may limit this check to a small number like only checking the most recent 16 commits.

If these conditions hold, then we can do above optimized check, otherwise we fall back to the old check.

Do we actually gain anything by this? The following was executed with linux.git and stable tags. afeb391 is an empty commit on top of master.

    Benchmark #1: git rev-list afeb391 --not --all
      Time (mean ± σ):      64.1 ms ±   8.0 ms    [User: 52.8 ms, System: 11.1 ms]
      Range (min … max):    58.2 ms …  79.5 ms    37 runs

    Benchmark #2: git rev-list afeb391 --not master
      Time (mean ± σ):       1.6 ms ±   0.5 ms    [User: 1.0 ms, System: 1.0 ms]
      Range (min … max):     0.4 ms …   2.2 ms    1678 runs

Obviously not a real-world example, but it serves as a hint that it would help in some cases and potentially pay out quite well.

Patrick

Hi,

I finally found some time again to have another look at my old problem of slow connectivity checks. After my previous two approaches of using the quarantine directory and using bitmaps proved to not really be viable, I've taken a step back yet again. The result is this series, which speeds up the connectivity checks by optimizing "revison.c". More specifically, I'm mostly tweaking how we're queueing up references, which is the most pressing issue we've observed at GitLab when doing connectivity checks in repos with many references.

The following optimizations are part of this series. All benchmarks were done on [1], which is a repository with about 2.2 million references (even though most of them are hidden to public users) with git rev-list --objects --quiet --unsorted-input --not --all --not $newrev.

1. We used to sort the input references in git-rev-list(1). This is moot in the context of connectivity checks, so a new flag suppresses this sorting. This improves the command by ~30% from 7.6s to 4.9s.

2. We did some busy-work, loading each reference twice via get_reference(). We now don't anymore, resulting in a ~8% speedup from 5.0s to 4.6s.

3. An optimization was done to how we load objects. Previously, we always called oid_object_info(), even if we had already loaded the object. This was tweaked to use lookup_unknown_object(), which is a performance-memory tradeoff. This saves us another 7%, going from 4.7s to 4.4s, but it's a prereq for (4).

4. We now make better use of the commit-graph in that we first try loading from there before we load it from the ODB. This is a 40% speedup, going from 4.4s to 2.8s.

The result is a speedup of about 65%. The nice thing compared to previous versions is that this should also be visible when directly executing git-rev-list(1) or doing a revwalk.

Patch #1 still needs some polishing if we agree that this patch series makes sense, given that it's still missing documentation.

Patrick

[1]: https://gitlab.com/gitlab-org/gitlab.git

Patrick Steinhardt (4):
connected: do not sort input revisions
revision: stop retrieving reference twice
revision: avoid loading object headers multiple times
revision: avoid hitting packfiles when commits are in commit-graph

 commit-graph.c | 55 +++++++++++++++++++++++++++++++++++++++-----------
 commit-graph.h |  2 ++
 connected.c    |  1 +
 revision.c     | 23 ++++++++++++++++-----
 revision.h     |  1 +
 5 files changed, 65 insertions(+), 17 deletions(-)

2.32.0

In order to compute whether objects reachable from a set of tips are all connected, we do a revision walk with these tips as positive references and --not --all. --not --all will cause the revision walk to load all preexisting references as uninteresting, which can be very expensive in repositories with many references.

Benchmarking the git-rev-list(1) command highlights that by far the most expensive single phase is initial sorting of the input revisions: after all references have been loaded, we first sort commits by author date. In a real-world repository with about 2.2 million references, it makes up about 40% of the total runtime of git-rev-list(1).

Ultimately, the connectivity check shouldn't really bother about the order of input revisions at all. We only care whether we can actually walk all objects until we hit the cut-off point. So sorting the input is a complete waste of time.

Introduce a new "--unsorted-input" flag to git-rev-list(1) which will cause it to not sort the commits and adjust the connectivity check to always pass the flag. This results in the following speedups, executed in a clone of gitlab-org/gitlab [1]:

    Benchmark #1: git rev-list  --objects --quiet --not --all --not $(cat newrev)
      Time (mean ± σ):      7.639 s ±  0.065 s    [User: 7.304 s, System: 0.335 s]
      Range (min … max):    7.543 s …  7.742 s    10 runs

    Benchmark #2: git rev-list --unsorted-input --objects --quiet --not --all --not $newrev
      Time (mean ± σ):      4.995 s ±  0.044 s    [User: 4.657 s, System: 0.337 s]
      Range (min … max):    4.909 s …  5.048 s    10 runs

    Summary
      'git rev-list --unsorted-input --objects --quiet --not --all --not $(cat newrev)' ran
        1.53 ± 0.02 times faster than 'git rev-list  --objects --quiet --not --all --not $newrev'

[1]: https://gitlab.com/gitlab-org/gitlab.git. Note that not all refs
are visible to clients.

---
 connected.c | 1 +
 revision.c  | 4 +++-
 revision.h  | 1 +
 3 files changed, 5 insertions(+), 1 deletion(-)

index b18299fdf0..b5f9523a5f 100644
@@ -106,6 +106,7 @@ int check_connected(oid_iterate_fn fn, void *cb_data,
 	if (opt->progress)
 		strvec_pushf(&rev_list.args, "--progress=%s",
 			     _("Checking connectivity"));
+	strvec_push(&rev_list.args, "--unsorted-input");
 
 	rev_list.git_cmd = 1;
 	rev_list.env = opt->env;

index cddd0542a6..7eb09009ba 100644
@@ -2256,6 +2256,8 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
 	} else if (!strcmp(arg, "--author-date-order")) {
 		revs->sort_order = REV_SORT_BY_AUTHOR_DATE;
 		revs->topo_order = 1;
+	} else if (!strcmp(arg, "--unsorted-input")) {
+		revs->unsorted_input = 1;
 	} else if (!strcmp(arg, "--early-output")) {
 		revs->early_output = 100;
 		revs->topo_order = 1;

@@ -3584,7 +3586,7 @@ 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;

index fbb068da9f..ef6998509a 100644
@@ -134,6 +134,7 @@ 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,

2.32.0

Really good results:

Just bikeshedding for a potential re-roll, perhaps --unordered-input, so that it matches/rhymes with the existing "git cat-file --unordered", which serves the same conceptual purpose (except this one's input, that one's output).

[snip]

Yeah, I wasn't quite sure how to name it myself either. Internally, we typically use "unsorted" instead of "unordered", and there's also the preexisting "--no-walk=(sorted|unsorted)" flag for git-rev-list(1). With the latter in mind, I think that "unsorted" fits a bit better given that we already use it in the same command, but I don't particularly mind.

For now, I'll keep "--unsorted-input", but please feel free to give me another shout if you disagree with my reasoning.

Patrick

Sounds good. I didn't mean it as a strong suggestion, unsorted does indeed sounds better in this context, just a gentle poke to check if you knew about that similar option...

Thanks.

Nice finding.

Sorting of positive side is done to help both performance and correctness in regular use of the traversal machinery, especially when reachability bitmap is not in effect, but on the negative side I do not think there is any downside to omit sorting offhand. The only case that may get affected is when the revision.c::SLOP kicks in to deal with oddball commits with incorrect committer timestamps, but then the result of the sorting isn't to be trusted anyway, so...

So is this the 2.2 million refs thing?

[snip]

Yeah, it is. The repo itself got 2.2 million refs, even though only 800k are publicly visible. It got even more when one considers its alternate, where it grows to 3.4 million in total.

Right. The question also is what to do when the user calls git rev-list --no-walk=sorted --unsorted-input. Do we sort? Don't we? Should we mark these options as incompatible with each other and bail out? I guess just bailing out would be the easiest solution for now.

Patrick

I'd say so. Even without the future clean-up to get rid of the NO_WALK_UNSORTED, the issue already exists with this series, and when in doubt, it is easiest to start tight and take our time to figure out what the right behaviour should be while we initially do not allow both to be used at the same time.

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.

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:

    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]
      Range (min … max):    4.970 s …  5.089 s    10 runs

    Benchmark #2: HEAD: rev-list --unsorted-input --objects --quiet --not --all --not $newrev
      Time (mean ± σ):      4.606 s ±  0.029 s    [User: 4.260 s, System: 0.345 s]
      Range (min … max):    4.565 s …  4.657 s    10 runs

    Summary
      'HEAD: rev-list --unsorted-input --objects --quiet --not --all --not $newrev' ran
        1.09 ± 0.01 times faster than 'HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev'

---
 revision.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index 7eb09009ba..f06a5d63a3 100644
@@ -1534,7 +1534,7 @@ static int handle_one_ref(const char *path, const struct object_id *oid,
 
 	object = get_reference(cb->all_revs, path, oid, cb->all_flags);
 	add_rev_cmdline(cb->all_revs, object, path, REV_CMD_REF, cb->all_flags);
-	add_pending_oid(cb->all_revs, path, oid, cb->all_flags);
+	add_pending_object(cb->all_revs, object, path);
 	return 0;
 }
 

2.32.0

It might be worth calling out explicitly that it's not just "effectively", but that add_pending_oid() is just a thin wrapper for get_reference() followed by add_pending_object(), so we're guaranteed to get the exact same result here as before, just without the duplicate work.

I.e. we're not going down some other lookup path that uses object lookups with different flags or whatever as a result of this change.

When loading references, we try to optimize loading of commits by using the commit graph. To do so, we first need to determine whether the object actually is a commit or not, which is why we always execute oid_object_info() first. Like this, we'll unpack the object header of each object first.

This pattern can be quite inefficient in case many references point to the same commit: if the object didn't end up in the cached objects, then we'll repeatedly unpack the same object header, even if we've already seen the object before.

Optimize this pattern by using lookup_unknown_object() first in order to determine whether we've seen the object before. If so, then we don't need to re-parse the header but can directly use its object information and thus gain a modest performance improvement. Executed in a real-world repository with around 2.2 million references:

    Benchmark #1: HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev
      Time (mean ± σ):      4.771 s ±  0.238 s    [User: 4.440 s, System: 0.330 s]
      Range (min … max):    4.539 s …  5.219 s    10 runs

    Benchmark #2: HEAD: rev-list --unsorted-input --objects --quiet --not --all --not $newrev
      Time (mean ± σ):      4.454 s ±  0.037 s    [User: 4.122 s, System: 0.332 s]
      Range (min … max):    4.375 s …  4.496 s    10 runs

    Summary
      'HEAD: rev-list --unsorted-input --objects --quiet --not --all --not $newrev' ran
        1.07 ± 0.05 times faster than 'HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev'

The downside is that lookup_unknown_object() is forced to always allocate an object such that it's big enough to host all object types' structs and thus we may waste memory here. This tradeoff is probably worth it though considering the following struct sizes:

- commit: 72 bytes
- tree: 56 bytes
- blob: 40 bytes
- tag: 64 bytes

Assuming that in almost all repositories, most references will point to either a tag or a commit, we'd have a modest increase in memory consumption of about 12.5% here.

---
 revision.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)

index f06a5d63a3..671b6d6513 100644
@@ -359,14 +359,22 @@ static struct object *get_reference(struct rev_info *revs, const char *name,
 				    const struct object_id *oid,
 				    unsigned int flags)
 {
-	struct object *object;
+	struct object *object = lookup_unknown_object(revs->repo, oid);
+
+	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 the repository has commit graphs, repo_parse_commit() avoids
 	 * reading the object buffer, so use it whenever possible.
 	 */
-	if (oid_object_info(revs->repo, oid, NULL) == OBJ_COMMIT) {
-		struct commit *c = lookup_commit(revs->repo, oid);
+	if (object->type == OBJ_COMMIT) {
+		struct commit *c = (struct commit *) object;
 		if (!repo_parse_commit(revs->repo, c))
 			object = (struct object *) c;
 		else

@@ -375,6 +383,7 @@ static struct object *get_reference(struct rev_info *revs, const char *name,
 		object = parse_object(revs->repo, oid);
 	}
 
+out:
 	if (!object) {
 		if (revs->ignore_missing)
 			return object;

2.32.0

[snip]

oid_object_info() does return an int though, so it feels kind of weird to me to stuff it into an enum right away. Furthermore, while OBJ_BAD does map to -1, the documentation of oid_object_info() currently asks for what I'm doing: """returns enum object_type or negative""".

Patrick

I wonder if we can also say almost all repositories, the majority of refs point at the same object. If that holds, this would certainly be a win, but otherwise, it is not so clear.

I doubt that's the case in general. I rather assume that it's typically going to be a smallish subset that points to the same commit, but for these cases we at least avoid doing the lookup multiple times. As I said, it's definitely a tradeoff between memory and performance: in the worst case (all references point to different blobs) we allocate 33% more memory without having any speedups. A more realistic scenario would probably be something like a trunk-based development repo, where there's a single branch only and the rest is tags. There we'd allocate 11% more memory without any speedups. In general, it's going to be various shades of gray, where we allocate something from 0% to 11% more memory while getting some modest speedups in some cases.

So if we only inspect this commit as a standalone it's definitely debatable whether we'd want to take it or not. But one important thing is that it's a prerequisite for patch 4/4: in order to not parse commits in case they're part of the commit-graph, we need to first obtain an object such that we can fill it in via the graph. So we have to call lookup_unknown_object() anyway. Might be sensible to document this as part of the commit message.

Patrick

Scratch that: we can just rewrite this to use lookup_object() to check whether we already know the object, and then we can rewrite the parse_commit_in_graph_gently() to be lookup_commit_in_graph(), which does a lookup_commit() to create the object in case the OID was found in the graph. That's also got nicer calling semantics..

It's negligibly slower (3.021s instead of 2.983s), but it doesn't need me arguing about the performance/memory tradeoff. Which is a good thing I guess: there will always be that one repo that's completely different and where such assumptions don't hold.

Patrick

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.

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:

    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

    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

    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'

---
 commit-graph.c | 55 +++++++++++++++++++++++++++++++++++++++-----------
 commit-graph.h |  2 ++
 revision.c     | 10 +++++----
 3 files changed, 51 insertions(+), 16 deletions(-)

index 3860a0d847..a81d5cebc0 100644
@@ -864,6 +864,48 @@ static int fill_commit_in_graph(struct repository *r,
 	return 1;
 }
 
+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)
+{
+	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;
+
+	if (!find_object_id_in_graph(&object->oid, repo->objects->commit_graph, &pos))
+		return -1;
+
+	commit = object_as_type(object, OBJ_COMMIT, 1);
+	if (!commit)
+		return -1;
+	if (!fill_commit_in_graph(repo, commit, repo->objects->commit_graph, pos))
+		return -1;
+
+	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);

@@ -871,18 +913,7 @@ 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);
 	}
 }
 

index 96c24fb577..f373fab4c0 100644
@@ -139,6 +139,8 @@ int write_commit_graph(struct object_directory *odb,
 		       enum commit_graph_write_flags flags,
 		       const struct commit_graph_opts *opts);
 
+int find_object_in_graph(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);

index 671b6d6513..c3f9cf2998 100644
@@ -362,10 +362,12 @@ static struct object *get_reference(struct rev_info *revs, const char *name,
 	struct object *object = lookup_unknown_object(revs->repo, oid);
 
 	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) {
+			int type = oid_object_info(revs->repo, oid, NULL);
+			if (type < 0 || !object_as_type(object, type, 1)) {
+				object = NULL;
+				goto out;
+			}
 		}
 	}
 

2.32.0

[snip]

Fair point. The only caller for now only calls the function if the object's type is unknown, so it really is "Resolve the commit if it is one". I'll adjust the function's name.

Will do.

One thing that occurred to me this morning after waking up is that this commit changes semantics: if we're able to look up the commit via the commit-graph, then we'll happily consider it to exist in the repository. But given that we don't hit the object database at all anymore, it may be that the commit-graph was out of date while the commit got unreachable and thus pruned. So it may not even exist anymore in the repository.

I wonder what our stance on this is. I can definitely understand the angle that this would be a deal breaker given that we now claim commits exist which don't anymore. On the other hand, we update commit-graphs via git-gc(1), which makes this scenario a lot less likely nowadays. Is there any precedent in our codebase where we treat commits part of the commit-graph as existing? If not, do we want to make that assumption?

Patrick

An optimization that produces a wrong result very fast is a useless optimization that has no place in our codebase. But don't we have some clue recorded in the commit graph file that tells us with what packfile the graph is to be used (iow, if the named packfile still exists there, the objects recorded in the graph file are to be found there) or something?

Unfortunately, no. For bitmaps we have this information given that a bitmap is tied to a specific pack anyway. But for commit-graphs, the story is different given that they don't really care about the packs per se, but only about the commits.

I was briefly wondering whether we can somehow use generation numbers to cut off parsing some commits: given we have already observed a commit with generation number N and we have determined that this commit's object exists, and we now see a commit with generation number M with M<N, then we can skip the object lookup because M is reachable by N and thus its object must exist. But generation numbers cannot determine reachability, but only unreachability, so I fear this is not possible.

We can do the following on top though:

index 3527ef3f65..9e62de20ab 100644
@@ -368,6 +368,8 @@ static struct object *get_reference(struct rev_info *revs, const char *name,
 				object = NULL;
 				goto out;
 			}
+		} else if (!repo_has_object_file(revs->repo, oid)) {
+			die("bad object %s", name);
 		}
 	}
 

We assert that the object exists, but repo_has_object_file() won't try to unpack the object header given that we request no info about the object. And because the object ID has been part of the commit-graph, we know that it's a commit. It's a bit slower compared to the version where we don't assert object existence, but still a lot faster compared to looking up the object type via the ODB:

    Benchmark #1: HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $(cat newrev)
      Time (mean ± σ):      4.512 s ±  0.057 s    [User: 4.131 s, System: 0.381 s]
      Range (min … max):    4.435 s …  4.632 s    10 runs

    Benchmark #2: without-existence rev-list --unsorted-input --objects --quiet --not --all --not $(cat newrev)
      Time (mean ± σ):      2.903 s ±  0.022 s    [User: 2.533 s, System: 0.369 s]
      Range (min … max):    2.878 s …  2.954 s    10 runs

    Benchmark #3: with-existence: rev-list --unsorted-input --objects --quiet --not --all --not $(cat newrev)
      Time (mean ± σ):      3.071 s ±  0.014 s    [User: 2.712 s, System: 0.358 s]
      Range (min … max):    3.050 s …  3.088 s    10 runs

    Summary
      'without-existence: rev-list --unsorted-input --objects --quiet --not --all --not $(cat newrev)' ran
        1.06 ± 0.01 times faster than 'with-existance: rev-list --unsorted-input --objects --quiet --not --all --not $(cat newrev)'
        1.55 ± 0.02 times faster than 'HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $(cat newrev)'

Patrick

[jc: refreshed Cc: list to limit to those in "shortlog commit-graph.[ch]"]

On this subject, I'd ask those who have worked on the commit-graph for ideas. It would be a glaring flaw _if_ the data structure that is designed to be a "cache of precomputed summary that would help runtime performance" has no way to detect out-of-date cache and/or to invalidate when it goes stale, but I somehow doubt that is the case, given the caliber of folks who have worked in it. To me, it feels a lot more likely that we may be missing an existing mechanism to do so. It could be that ...

... the above is the designed way to correctly use the commit-graph data? That is, you find an object in the commit-graph, and you make sure the object exists in the object store in some other means (because there is no mechanism for commit-graph to prevent a gc from pruning an object recorded in it away) before you consider you can use the object.

Thoughts and help?

Thanks.

I don't think there is, but don't see why given the performance benefits it should not at least be exposed in this form for those that think they know what they're doing.

But right now the way we write the commit graph seems guaranteed to produce races in this area, i.e. we expire objects first, and then we write a new graph (see cmd_gc()). I.e. something like:

1. (Re)pack reachable objects
2. Prune unrechable and old
3. Write a new commit graph using discovered tips

I don't see a good reason other than just that this needs some refactoring to not instead do:

1. Discover reachable refs
2. (Re)pack reachable objects from those refs
3. Write a new commit graph using those ref tips, i.e. don't re-run for_each_ref() in write_commit_graph_reachable() but call write_commit_graph() with those OIDs directly.
4. Prune unreachable and old

Which I think would nicely get around this particular race condition, which also doesn't exist if you call "git commit-graph write", it's just if we write a new graph and then expire objects without being aware that the graph needs updating.

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 <[email protected]>
     
    + ## 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.
+

## 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 <[email protected]>
     
      ## 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

The --no-walk flag supports two modes: either it sorts the revisions given as input input or it doesn't. This is reflected in a single no_walk flag, which reflects one of the three states "walk", "don't walk but without sorting" and "don't walk but with sorting".

Split up the flag into two separate bits, one indicating whether we should walk or not and one indicating whether the input should be sorted or not. This will allow us to more easily introduce a new flag --unsorted-input, which only impacts the sorting bit.

---
 builtin/log.c    | 2 +-
 builtin/revert.c | 3 ++-
 revision.c       | 9 +++++----
 revision.h       | 7 ++-----
 4 files changed, 10 insertions(+), 11 deletions(-)

index 3d7717ba5c..f75d87e8d7 100644
@@ -637,7 +637,7 @@ int cmd_show(int argc, const char **argv, const char *prefix)
 	repo_init_revisions(the_repository, &rev, prefix);
 	rev.diff = 1;
 	rev.always_show_header = 1;
-	rev.no_walk = REVISION_WALK_NO_WALK_SORTED;
+	rev.no_walk = 1;
 	rev.diffopt.stat_width = -1; 	/* Scale to real terminal size */
 
 	memset(&opt, 0, sizeof(opt));

index 237f2f18d4..2e13660e4b 100644
@@ -191,7 +191,8 @@ static int run_sequencer(int argc, const char **argv, struct replay_opts *opts)
 		struct setup_revision_opt s_r_opt;
 		opts->revs = xmalloc(sizeof(*opts->revs));
 		repo_init_revisions(the_repository, opts->revs, NULL);
-		opts->revs->no_walk = REVISION_WALK_NO_WALK_UNSORTED;
+		opts->revs->no_walk = 1;
+		opts->revs->unsorted_input = 1;
 		if (argc < 2)
 			usage_with_options(usage_str, options);
 		if (!strcmp(argv[1], "-"))

index cddd0542a6..86bbcd10d2 100644
@@ -2651,16 +2651,17 @@ static int handle_revision_pseudo_opt(const char *submodule,
 	} else if (!strcmp(arg, "--not")) {
 		*flags ^= UNINTERESTING | BOTTOM;
 	} else if (!strcmp(arg, "--no-walk")) {
-		revs->no_walk = REVISION_WALK_NO_WALK_SORTED;
+		revs->no_walk = 1;
 	} else if (skip_prefix(arg, "--no-walk=", &optarg)) {
 		/*
 		 * 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"))
-			revs->no_walk = REVISION_WALK_NO_WALK_SORTED;
+			revs->unsorted_input = 0;
 		else if (!strcmp(optarg, "unsorted"))
-			revs->no_walk = REVISION_WALK_NO_WALK_UNSORTED;
+			revs->unsorted_input = 1;
 		else
 			return error("invalid argument to --no-walk");
 	} else if (!strcmp(arg, "--do-walk")) {

@@ -3584,7 +3585,7 @@ 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->unsorted_input)
 		commit_list_sort_by_date(&revs->commits);
 	if (revs->no_walk)
 		return 0;

index fbb068da9f..0c65a760ee 100644
@@ -79,10 +79,6 @@ struct rev_cmdline_info {
 	} *rev;
 };
 
-#define REVISION_WALK_WALK 0
-#define REVISION_WALK_NO_WALK_SORTED 1
-#define REVISION_WALK_NO_WALK_UNSORTED 2
-
 struct oidset;
 struct topo_walk_info;
 

@@ -129,7 +125,8 @@ struct rev_info {
 	/* Traversal flags */
 	unsigned int	dense:1,
 			prune:1,
-			no_walk:2,
+			no_walk:1,
+			unsorted_input:1,
 			remove_empty_trees:1,
 			simplify_history:1,
 			show_pulls:1,

2.32.0

Every line of changes in the patch is very satisfying ;-)

In order to compute whether objects reachable from a set of tips are all connected, we do a revision walk with these tips as positive references and --not --all. --not --all will cause the revision walk to load all preexisting references as uninteresting, which can be very expensive in repositories with many references.

Benchmarking the git-rev-list(1) command highlights that by far the most expensive single phase is initial sorting of the input revisions: after all references have been loaded, we first sort commits by author date. In a real-world repository with about 2.2 million references, it makes up about 40% of the total runtime of git-rev-list(1).

Ultimately, the connectivity check shouldn't really bother about the order of input revisions at all. We only care whether we can actually walk all objects until we hit the cut-off point. So sorting the input is a complete waste of time.

Introduce a new "--unsorted-input" flag to git-rev-list(1) which will cause it to not sort the commits and adjust the connectivity check to always pass the flag. This results in the following speedups, executed in a clone of gitlab-org/gitlab [1]:

    Benchmark #1: git rev-list  --objects --quiet --not --all --not $(cat newrev)
      Time (mean ± σ):      7.639 s ±  0.065 s    [User: 7.304 s, System: 0.335 s]
      Range (min … max):    7.543 s …  7.742 s    10 runs

    Benchmark #2: git rev-list --unsorted-input --objects --quiet --not --all --not $newrev
      Time (mean ± σ):      4.995 s ±  0.044 s    [User: 4.657 s, System: 0.337 s]
      Range (min … max):    4.909 s …  5.048 s    10 runs

    Summary
      'git rev-list --unsorted-input --objects --quiet --not --all --not $(cat newrev)' ran
        1.53 ± 0.02 times faster than 'git rev-list  --objects --quiet --not --all --not $newrev'

[1]: https://gitlab.com/gitlab-org/gitlab.git. Note that not all refs
are visible to clients.

---
 Documentation/rev-list-options.txt |  8 ++++++-
 connected.c                        |  1 +
 revision.c                         | 13 ++++++++--
 t/t6000-rev-list-misc.sh           | 38 ++++++++++++++++++++++++++++++
 4 files changed, 57 insertions(+), 3 deletions(-)

index 24569b06d1..b7bd27e171 100644
@@ -968,6 +968,11 @@ 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

@@ -975,7 +980,8 @@ 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`.

index b18299fdf0..b5f9523a5f 100644
@@ -106,6 +106,7 @@ int check_connected(oid_iterate_fn fn, void *cb_data,
 	if (opt->progress)
 		strvec_pushf(&rev_list.args, "--progress=%s",
 			     _("Checking connectivity"));
+	strvec_push(&rev_list.args, "--unsorted-input");
 
 	rev_list.git_cmd = 1;
 	rev_list.env = opt->env;

index 86bbcd10d2..793f76a509 100644
@@ -2256,6 +2256,10 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
 	} else if (!strcmp(arg, "--author-date-order")) {
 		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;

@@ -2651,6 +2655,8 @@ 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)) {
 		/*

@@ -2658,9 +2664,12 @@ 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");

index 12def7bcbf..8e213eb413 100755
@@ -169,4 +169,42 @@ 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.32.0

Wouldn't that effectively change semantics though? If the user passes git rev-list --no-walk=unsorted --no-walk, then the result is a sorted revwalk right now. One may argue that most likely, nobody is doing that, but you never really know.

An easier approach which keeps existing semantics is to just make --no-walk and --unsorted-input mutually exclusive:

- If the unsorted_input bit is set and no_walk isn't, and we observe any --no-walk option, then we bail.

- Likewise, if the no_walk bit is set, then we bail when we see --unsorted-input regardless of the value of unsorted_input. This would keep current semantics of --no-walk, but prohobit using it together with the new option.

Patrick

True.

True again. As I said, I do prefer going in the "start tight to forbid combination" route. But as I pointed out, the coverage by the posted patch seemed to have gap(s).

Thanks.

When queueing up references for the revision walk, handle_one_ref() 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() 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]
      Range (min … max):    4.970 s …  5.089 s    10 runs

    Benchmark #2: HEAD: rev-list --unsorted-input --objects --quiet --not --all --not $newrev
      Time (mean ± σ):      4.606 s ±  0.029 s    [User: 4.260 s, System: 0.345 s]
      Range (min … max):    4.565 s …  4.657 s    10 runs

    Summary
      'HEAD: rev-list --unsorted-input --objects --quiet --not --all --not $newrev' ran
        1.09 ± 0.01 times faster than 'HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev'

---
 revision.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index 793f76a509..0d99413856 100644
@@ -1534,7 +1534,7 @@ static int handle_one_ref(const char *path, const struct object_id *oid,
 
 	object = get_reference(cb->all_revs, path, oid, cb->all_flags);
 	add_rev_cmdline(cb->all_revs, object, path, REV_CMD_REF, cb->all_flags);
-	add_pending_oid(cb->all_revs, path, oid, cb->all_flags);
+	add_pending_object(cb->all_revs, object, path);
 	return 0;
 }
 

2.32.0

When loading references, we try to optimize loading of commits by using the commit graph. To do so, we first need to determine whether the object actually is a commit or not, which is why we always execute oid_object_info() first. Like this, we'll unpack the object header of each object first.

This pattern can be quite inefficient in case many references point to the same commit: if the object didn't end up in the cached objects, then we'll repeatedly unpack the same object header, even if we've already seen the object before.

Optimize this pattern by using lookup_unknown_object() first in order to determine whether we've seen the object before. If so, then we don't need to re-parse the header but can directly use its object information and thus gain a modest performance improvement. Executed in a real-world repository with around 2.2 million references:

    Benchmark #1: HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev
      Time (mean ± σ):      4.771 s ±  0.238 s    [User: 4.440 s, System: 0.330 s]
      Range (min … max):    4.539 s …  5.219 s    10 runs

    Benchmark #2: HEAD: rev-list --unsorted-input --objects --quiet --not --all --not $newrev
      Time (mean ± σ):      4.454 s ±  0.037 s    [User: 4.122 s, System: 0.332 s]
      Range (min … max):    4.375 s …  4.496 s    10 runs

    Summary
      'HEAD: rev-list --unsorted-input --objects --quiet --not --all --not $newrev' ran
        1.07 ± 0.05 times faster than 'HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev'

The downside is that lookup_unknown_object() is forced to always allocate an object such that it's big enough to host all object types' structs and thus we may waste memory here. This tradeoff is probably worth it though considering the following struct sizes:

- commit: 72 bytes
- tree: 56 bytes
- blob: 40 bytes
- tag: 64 bytes

Assuming that in almost all repositories, most references will point to 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.

---
 revision.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)

index 0d99413856..25f4784fdd 100644
@@ -359,14 +359,22 @@ static struct object *get_reference(struct rev_info *revs, const char *name,
 				    const struct object_id *oid,
 				    unsigned int flags)
 {
-	struct object *object;
+	struct object *object = lookup_unknown_object(revs->repo, oid);
+
+	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 the repository has commit graphs, repo_parse_commit() avoids
 	 * reading the object buffer, so use it whenever possible.
 	 */
-	if (oid_object_info(revs->repo, oid, NULL) == OBJ_COMMIT) {
-		struct commit *c = lookup_commit(revs->repo, oid);
+	if (object->type == OBJ_COMMIT) {
+		struct commit *c = (struct commit *) object;
 		if (!repo_parse_commit(revs->repo, c))
 			object = (struct object *) c;
 		else

@@ -375,6 +383,7 @@ static struct object *get_reference(struct rev_info *revs, const char *name,
 		object = parse_object(revs->repo, oid);
 	}
 
+out:
 	if (!object) {
 		if (revs->ignore_missing)
 			return object;

2.32.0

The function find_commit_in_graph() assumes that the caller has passed an object which was already determined to be a commit given that it will access the commit's graph position, which is stored in a commit slab. In a subsequent patch, we want to search for an object ID though without knowing whether it is a commit or not, which is not currently possible.

Split out the logic to search the commit graph for a given object ID to prepare for this change. This commit also renames the function to find_commit_pos_in_graph(), which more accurately reflects what this function does. Furthermore, in order to allow for the searched object ID to be const, we need to adjust bsearch_graph()'s signature to accept a constant object ID as input, too.

---
 commit-graph.c | 55 +++++++++++++++++++++++++++-----------------------
 1 file changed, 30 insertions(+), 25 deletions(-)

index 3860a0d847..8c4c7262c8 100644
@@ -723,7 +723,7 @@ void close_commit_graph(struct raw_object_store *o)
 	o->commit_graph = NULL;
 }
 
-static int bsearch_graph(struct commit_graph *g, struct object_id *oid, uint32_t *pos)
+static int bsearch_graph(struct commit_graph *g, const struct object_id *oid, uint32_t *pos)
 {
 	return bsearch_hash(oid->hash, g->chunk_oid_fanout,
 			    g->chunk_oid_lookup, g->hash_len, pos);

@@ -864,25 +864,30 @@ static int fill_commit_in_graph(struct repository *r,
 	return 1;
 }
 
-static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos)
+static int search_commit_pos_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, 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;
+}
+
+static int find_commit_pos_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos)
 {
 	uint32_t graph_pos = commit_graph_position(item);
 	if (graph_pos != COMMIT_NOT_FROM_GRAPH) {
 		*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 search_commit_pos_in_graph(&item->object.oid, g, pos);
 	}
 }
 

@@ -895,7 +900,7 @@ static int parse_commit_in_graph_one(struct repository *r,
 	if (item->object.parsed)
 		return 1;
 
-	if (find_commit_in_graph(item, g, &pos))
+	if (find_commit_pos_in_graph(item, g, &pos))
 		return fill_commit_in_graph(r, item, g, pos);
 
 	return 0;

@@ -921,7 +926,7 @@ void load_commit_graph_info(struct repository *r, struct commit *item)
 	uint32_t pos;
 	if (!prepare_commit_graph(r))
 		return;
-	if (find_commit_in_graph(item, r->objects->commit_graph, &pos))
+	if (find_commit_pos_in_graph(item, r->objects->commit_graph, &pos))
 		fill_commit_graph_info(item, r->objects->commit_graph, pos);
 }
 

@@ -1091,9 +1096,9 @@ static int write_graph_chunk_data(struct hashfile *f,
 				edge_value += ctx->new_num_commits_in_base;
 			else if (ctx->new_base_graph) {
 				uint32_t pos;
-				if (find_commit_in_graph(parent->item,
-							 ctx->new_base_graph,
-							 &pos))
+				if (find_commit_pos_in_graph(parent->item,
+							     ctx->new_base_graph,
+							     &pos))
 					edge_value = pos;
 			}
 

@@ -1122,9 +1127,9 @@ static int write_graph_chunk_data(struct hashfile *f,
 				edge_value += ctx->new_num_commits_in_base;
 			else if (ctx->new_base_graph) {
 				uint32_t pos;
-				if (find_commit_in_graph(parent->item,
-							 ctx->new_base_graph,
-							 &pos))
+				if (find_commit_pos_in_graph(parent->item,
+							     ctx->new_base_graph,
+							     &pos))
 					edge_value = pos;
 			}
 

@@ -1235,9 +1240,9 @@ static int write_graph_chunk_extra_edges(struct hashfile *f,
 				edge_value += ctx->new_num_commits_in_base;
 			else if (ctx->new_base_graph) {
 				uint32_t pos;
-				if (find_commit_in_graph(parent->item,
-							 ctx->new_base_graph,
-							 &pos))
+				if (find_commit_pos_in_graph(parent->item,
+							     ctx->new_base_graph,
+							     &pos))
 					edge_value = pos;
 			}
 

2.32.0

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.

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.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 ± σ):      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.47 ± 0.02 times faster than 'HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev'

---
 commit-graph.c | 26 ++++++++++++++++++++++++++
 commit-graph.h |  7 +++++++
 revision.c     | 17 +++++++++++++++--
 3 files changed, 48 insertions(+), 2 deletions(-)

index 8c4c7262c8..cc7136243d 100644
@@ -891,6 +891,32 @@ static int find_commit_pos_in_graph(struct commit *item, struct commit_graph *g,
 	}
 }
 
+int parse_commit_in_graph_gently(struct repository *repo, struct object *object)
+{
+	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;
+
+	if (!search_commit_pos_in_graph(&object->oid, repo->objects->commit_graph, &pos))
+		return -1;
+
+	commit = object_as_type(object, OBJ_COMMIT, 1);
+	if (!commit)
+		return -1;
+	if (!fill_commit_in_graph(repo, commit, repo->objects->commit_graph, pos))
+		return -1;
+
+	return 0;
+}
+
 static int parse_commit_in_graph_one(struct repository *r,
 				     struct commit_graph *g,
 				     struct commit *item)

index 96c24fb577..e2e93b0ee1 100644
@@ -40,6 +40,13 @@ int open_commit_graph(const char *graph_file, int *fd, struct stat *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.
+ */
+int parse_commit_in_graph_gently(struct repository *repo, struct object *object);
+
 /*
  * It is possible that we loaded commit contents from the commit buffer,
  * but we also want to ensure the commit-graph content is correctly

index 25f4784fdd..318b43026e 100644
@@ -362,8 +362,21 @@ static struct object *get_reference(struct rev_info *revs, const char *name,
 	struct object *object = lookup_unknown_object(revs->repo, oid);
 
 	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;
 		}

2.32.0

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.

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                         | 42 +++++++++-------
 revision.h                         |  7 +--
 t/t6000-rev-list-misc.sh           | 38 ++++++++++++++
 9 files changed, 138 insertions(+), 50 deletions(-)

Range-diff against v4:

1:  67232910ac = 1:  67232910ac revision: separate walk and unsorted flags
2:  9d7f484907 = 2:  9d7f484907 connected: do not sort input revisions
3:  d8e63d0943 = 3:  d8e63d0943 revision: stop retrieving reference twice
4:  ba8df5cad0 < -:  ---------- revision: avoid loading object headers multiple times
5:  e33cd51ebf = 4:  549d85e5c2 commit-graph: split out function to search commit position
6:  900c5a9c60 ! 5:  4b893d943f 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'

@@ 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)

2.32.0

You can ignore this version. I realized I forgot to address some feedback while I was sending mails out. I'll resend in some minutes.

Patrick

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'

@@ 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)

2.32.0

The --no-walk flag supports two modes: either it sorts the revisions given as input input or it doesn't. This is reflected in a single no_walk flag, which reflects one of the three states "walk", "don't walk but without sorting" and "don't walk but with sorting".

Split up the flag into two separate bits, one indicating whether we should walk or not and one indicating whether the input should be sorted or not. This will allow us to more easily introduce a new flag --unsorted-input, which only impacts the sorting bit.

---
 builtin/log.c    | 2 +-
 builtin/revert.c | 3 ++-
 revision.c       | 9 +++++----
 revision.h       | 7 ++-----
 4 files changed, 10 insertions(+), 11 deletions(-)

index 3d7717ba5c..f75d87e8d7 100644
@@ -637,7 +637,7 @@ int cmd_show(int argc, const char **argv, const char *prefix)
 	repo_init_revisions(the_repository, &rev, prefix);
 	rev.diff = 1;
 	rev.always_show_header = 1;
-	rev.no_walk = REVISION_WALK_NO_WALK_SORTED;
+	rev.no_walk = 1;
 	rev.diffopt.stat_width = -1; 	/* Scale to real terminal size */
 
 	memset(&opt, 0, sizeof(opt));

index 237f2f18d4..2e13660e4b 100644
@@ -191,7 +191,8 @@ static int run_sequencer(int argc, const char **argv, struct replay_opts *opts)
 		struct setup_revision_opt s_r_opt;
 		opts->revs = xmalloc(sizeof(*opts->revs));
 		repo_init_revisions(the_repository, opts->revs, NULL);
-		opts->revs->no_walk = REVISION_WALK_NO_WALK_UNSORTED;
+		opts->revs->no_walk = 1;
+		opts->revs->unsorted_input = 1;
 		if (argc < 2)
 			usage_with_options(usage_str, options);
 		if (!strcmp(argv[1], "-"))

index cddd0542a6..86bbcd10d2 100644
@@ -2651,16 +2651,17 @@ static int handle_revision_pseudo_opt(const char *submodule,
 	} else if (!strcmp(arg, "--not")) {
 		*flags ^= UNINTERESTING | BOTTOM;
 	} else if (!strcmp(arg, "--no-walk")) {
-		revs->no_walk = REVISION_WALK_NO_WALK_SORTED;
+		revs->no_walk = 1;
 	} else if (skip_prefix(arg, "--no-walk=", &optarg)) {
 		/*
 		 * 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"))
-			revs->no_walk = REVISION_WALK_NO_WALK_SORTED;
+			revs->unsorted_input = 0;
 		else if (!strcmp(optarg, "unsorted"))
-			revs->no_walk = REVISION_WALK_NO_WALK_UNSORTED;
+			revs->unsorted_input = 1;
 		else
 			return error("invalid argument to --no-walk");
 	} else if (!strcmp(arg, "--do-walk")) {

@@ -3584,7 +3585,7 @@ 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->unsorted_input)
 		commit_list_sort_by_date(&revs->commits);
 	if (revs->no_walk)
 		return 0;

index fbb068da9f..0c65a760ee 100644
@@ -79,10 +79,6 @@ struct rev_cmdline_info {
 	} *rev;
 };
 
-#define REVISION_WALK_WALK 0
-#define REVISION_WALK_NO_WALK_SORTED 1
-#define REVISION_WALK_NO_WALK_UNSORTED 2
-
 struct oidset;
 struct topo_walk_info;
 

@@ -129,7 +125,8 @@ struct rev_info {
 	/* Traversal flags */
 	unsigned int	dense:1,
 			prune:1,
-			no_walk:2,
+			no_walk:1,
+			unsorted_input:1,
 			remove_empty_trees:1,
 			simplify_history:1,
 			show_pulls:1,

2.32.0

In order to compute whether objects reachable from a set of tips are all connected, we do a revision walk with these tips as positive references and --not --all. --not --all will cause the revision walk to load all preexisting references as uninteresting, which can be very expensive in repositories with many references.

Benchmarking the git-rev-list(1) command highlights that by far the most expensive single phase is initial sorting of the input revisions: after all references have been loaded, we first sort commits by author date. In a real-world repository with about 2.2 million references, it makes up about 40% of the total runtime of git-rev-list(1).

Ultimately, the connectivity check shouldn't really bother about the order of input revisions at all. We only care whether we can actually walk all objects until we hit the cut-off point. So sorting the input is a complete waste of time.

Introduce a new "--unsorted-input" flag to git-rev-list(1) which will cause it to not sort the commits and adjust the connectivity check to always pass the flag. This results in the following speedups, executed in a clone of gitlab-org/gitlab [1]:

    Benchmark #1: git rev-list  --objects --quiet --not --all --not $(cat newrev)
      Time (mean ± σ):      7.639 s ±  0.065 s    [User: 7.304 s, System: 0.335 s]
      Range (min … max):    7.543 s …  7.742 s    10 runs

    Benchmark #2: git rev-list --unsorted-input --objects --quiet --not --all --not $newrev
      Time (mean ± σ):      4.995 s ±  0.044 s    [User: 4.657 s, System: 0.337 s]
      Range (min … max):    4.909 s …  5.048 s    10 runs

    Summary
      'git rev-list --unsorted-input --objects --quiet --not --all --not $(cat newrev)' ran
        1.53 ± 0.02 times faster than 'git rev-list  --objects --quiet --not --all --not $newrev'

[1]: https://gitlab.com/gitlab-org/gitlab.git. Note that not all refs
are visible to clients.

---
 Documentation/rev-list-options.txt |  8 +++++++-
 connected.c                        |  1 +
 revision.c                         |  9 +++++++++
 t/t6000-rev-list-misc.sh           | 31 ++++++++++++++++++++++++++++++
 4 files changed, 48 insertions(+), 1 deletion(-)

index 24569b06d1..b7bd27e171 100644
@@ -968,6 +968,11 @@ 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

@@ -975,7 +980,8 @@ 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`.

index b18299fdf0..b5f9523a5f 100644
@@ -106,6 +106,7 @@ int check_connected(oid_iterate_fn fn, void *cb_data,
 	if (opt->progress)
 		strvec_pushf(&rev_list.args, "--progress=%s",
 			     _("Checking connectivity"));
+	strvec_push(&rev_list.args, "--unsorted-input");
 
 	rev_list.git_cmd = 1;
 	rev_list.env = opt->env;

index 86bbcd10d2..47541407d2 100644
@@ -2256,6 +2256,10 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
 	} else if (!strcmp(arg, "--author-date-order")) {
 		revs->sort_order = REV_SORT_BY_AUTHOR_DATE;
 		revs->topo_order = 1;
+	} else if (!strcmp(arg, "--unsorted-input")) {
+		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;
 		revs->topo_order = 1;

@@ -2651,8 +2655,13 @@ 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->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"));
+
 		/*
 		 * Detached form ("--no-walk X" as opposed to "--no-walk=X")
 		 * not allowed, since the argument is optional.

index 12def7bcbf..ef849e5bc8 100755
@@ -169,4 +169,35 @@ 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 incompatible with --no-walk' '
+	cat >expect <<-EOF &&
+		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 &&
+	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
+	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
+'
+
 test_done

2.32.0

When queueing up references for the revision walk, handle_one_ref() 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() 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]
      Range (min … max):    4.970 s …  5.089 s    10 runs

    Benchmark #2: HEAD: rev-list --unsorted-input --objects --quiet --not --all --not $newrev
      Time (mean ± σ):      4.606 s ±  0.029 s    [User: 4.260 s, System: 0.345 s]
      Range (min … max):    4.565 s …  4.657 s    10 runs

    Summary
      'HEAD: rev-list --unsorted-input --objects --quiet --not --all --not $newrev' ran
        1.09 ± 0.01 times faster than 'HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev'

---
 revision.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index 47541407d2..80a59896b9 100644
@@ -1534,7 +1534,7 @@ static int handle_one_ref(const char *path, const struct object_id *oid,
 
 	object = get_reference(cb->all_revs, path, oid, cb->all_flags);
 	add_rev_cmdline(cb->all_revs, object, path, REV_CMD_REF, cb->all_flags);
-	add_pending_oid(cb->all_revs, path, oid, cb->all_flags);
+	add_pending_object(cb->all_revs, object, path);
 	return 0;
 }
 

2.32.0

The function find_commit_in_graph() assumes that the caller has passed an object which was already determined to be a commit given that it will access the commit's graph position, which is stored in a commit slab. In a subsequent patch, we want to search for an object ID though without knowing whether it is a commit or not, which is not currently possible.

Split out the logic to search the commit graph for a given object ID to prepare for this change. This commit also renames the function to find_commit_pos_in_graph(), which more accurately reflects what this function does. Furthermore, in order to allow for the searched object ID to be const, we need to adjust bsearch_graph()'s signature to accept a constant object ID as input, too.

---
 commit-graph.c | 55 +++++++++++++++++++++++++++-----------------------
 1 file changed, 30 insertions(+), 25 deletions(-)

index 3860a0d847..8c4c7262c8 100644
@@ -723,7 +723,7 @@ void close_commit_graph(struct raw_object_store *o)
 	o->commit_graph = NULL;
 }
 
-static int bsearch_graph(struct commit_graph *g, struct object_id *oid, uint32_t *pos)
+static int bsearch_graph(struct commit_graph *g, const struct object_id *oid, uint32_t *pos)
 {
 	return bsearch_hash(oid->hash, g->chunk_oid_fanout,
 			    g->chunk_oid_lookup, g->hash_len, pos);

@@ -864,25 +864,30 @@ static int fill_commit_in_graph(struct repository *r,
 	return 1;
 }
 
-static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos)
+static int search_commit_pos_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, 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;
+}
+
+static int find_commit_pos_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos)
 {
 	uint32_t graph_pos = commit_graph_position(item);
 	if (graph_pos != COMMIT_NOT_FROM_GRAPH) {
 		*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 search_commit_pos_in_graph(&item->object.oid, g, pos);
 	}
 }
 

@@ -895,7 +900,7 @@ static int parse_commit_in_graph_one(struct repository *r,
 	if (item->object.parsed)
 		return 1;
 
-	if (find_commit_in_graph(item, g, &pos))
+	if (find_commit_pos_in_graph(item, g, &pos))
 		return fill_commit_in_graph(r, item, g, pos);
 
 	return 0;

@@ -921,7 +926,7 @@ void load_commit_graph_info(struct repository *r, struct commit *item)
 	uint32_t pos;
 	if (!prepare_commit_graph(r))
 		return;
-	if (find_commit_in_graph(item, r->objects->commit_graph, &pos))
+	if (find_commit_pos_in_graph(item, r->objects->commit_graph, &pos))
 		fill_commit_graph_info(item, r->objects->commit_graph, pos);
 }
 

@@ -1091,9 +1096,9 @@ static int write_graph_chunk_data(struct hashfile *f,
 				edge_value += ctx->new_num_commits_in_base;
 			else if (ctx->new_base_graph) {
 				uint32_t pos;
-				if (find_commit_in_graph(parent->item,
-							 ctx->new_base_graph,
-							 &pos))
+				if (find_commit_pos_in_graph(parent->item,
+							     ctx->new_base_graph,
+							     &pos))
 					edge_value = pos;
 			}
 

@@ -1122,9 +1127,9 @@ static int write_graph_chunk_data(struct hashfile *f,
 				edge_value += ctx->new_num_commits_in_base;
 			else if (ctx->new_base_graph) {
 				uint32_t pos;
-				if (find_commit_in_graph(parent->item,
-							 ctx->new_base_graph,
-							 &pos))
+				if (find_commit_pos_in_graph(parent->item,
+							     ctx->new_base_graph,
+							     &pos))
 					edge_value = pos;
 			}
 

@@ -1235,9 +1240,9 @@ static int write_graph_chunk_extra_edges(struct hashfile *f,
 				edge_value += ctx->new_num_commits_in_base;
 			else if (ctx->new_base_graph) {
 				uint32_t pos;
-				if (find_commit_in_graph(parent->item,
-							 ctx->new_base_graph,
-							 &pos))
+				if (find_commit_pos_in_graph(parent->item,
+							     ctx->new_base_graph,
+							     &pos))
 					edge_value = pos;
 			}
 

2.32.0

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 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.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.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.44 ± 0.02 times faster than 'HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev'

---
 commit-graph.c | 24 ++++++++++++++++++++++++
 commit-graph.h |  8 ++++++++
 revision.c     | 18 ++++++++----------
 3 files changed, 40 insertions(+), 10 deletions(-)

index 8c4c7262c8..00614acd65 100644
@@ -891,6 +891,30 @@ static int find_commit_pos_in_graph(struct commit *item, struct commit_graph *g,
 	}
 }
 
+struct commit *lookup_commit_in_graph(struct repository *repo, const struct object_id *id)
+{
+	struct commit *commit;
+	uint32_t pos;
+
+	if (!repo->objects->commit_graph)
+		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;
+
+	commit = lookup_commit(repo, id);
+	if (!commit)
+		return NULL;
+	if (commit->object.parsed)
+		return commit;
+
+	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,
 				     struct commit_graph *g,
 				     struct commit *item)

index 96c24fb577..04a94e1830 100644
@@ -40,6 +40,14 @@ int open_commit_graph(const char *graph_file, int *fd, struct stat *st);
  */
 int parse_commit_in_graph(struct repository *r, struct commit *item);
 
+/*
+ * 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`.
+ */
+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,
  * but we also want to ensure the commit-graph content is correctly

index 80a59896b9..0dabb5a0bc 100644
@@ -360,20 +360,18 @@ static struct object *get_reference(struct rev_info *revs, const char *name,
 				    unsigned int flags)
 {
 	struct object *object;
+	struct commit *commit;
 
 	/*
-	 * 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)

2.32.0