[PATCH v2 0/3] Speed up connectivity checks via bitmaps

[PATCH v2 0/3] Speed up connectivity checks via bitmaps

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 1856 bytes --]

Hi,

this is version 2 of my patch series which tries to speed up
connectivity checks in git-receive-pack(1).

This version is a complete rewrite after my initial approach of using
the quarantine directory has been shot down due to changes in semantics.
This second version is thus an alternative approach using bitmaps. The
implementation is quite simple: if we have a bitmap, then we walk the
new tips until we hit a bitmapped object. Given that bitmapped objects
are by definition fully connected, we can then be sure that all pushed
tips are, too.

I'm not sure I'm happy with results in this series. While it does show a
speedup in the area I'm trying to optimize (repos with many refs), there
are two things which make me hesitant:

    - First, there seems to be significant overhead in loading the
      packfile. This is something Peff has already pointed out in 
      <YMypONmXt142dhbb@coredump.intra.peff.net> [1].

    - In repos which have out-of-date bitmaps, we're potentially going
      to walk a lot more objects than we used to.

Taking these two issues together, this version is probably more of a
request for comments: do we want to make above tradeoffs? Are there
better alternatives? Any input is welcome.

Patrick

Patrick Steinhardt (3):
  p5400: add perf tests for git-receive-pack(1)
  receive-pack: skip connectivity checks on delete-only commands
  connected: implement connectivity check using bitmaps

 builtin/receive-pack.c       |  49 ++++++++-----
 connected.c                  | 136 +++++++++++++++++++++++++++++++++++
 pack-bitmap.c                |   4 +-
 pack-bitmap.h                |   2 +
 t/perf/p5400-receive-pack.sh |  97 +++++++++++++++++++++++++
 5 files changed, 267 insertions(+), 21 deletions(-)
 create mode 100755 t/perf/p5400-receive-pack.sh

-- 
2.32.0


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v2 1/3] p5400: add perf tests for git-receive-pack(1)

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 3499 bytes --]

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.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 t/perf/p5400-receive-pack.sh | 97 ++++++++++++++++++++++++++++++++++++
 1 file changed, 97 insertions(+)
 create mode 100755 t/perf/p5400-receive-pack.sh

diff --git a/t/perf/p5400-receive-pack.sh b/t/perf/p5400-receive-pack.sh
new file mode 100755
index 0000000000..a945e014a3
--- /dev/null
+++ b/t/perf/p5400-receive-pack.sh
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v2 1/3] p5400: add perf tests for git-receive-pack(1)

[Ævar Arnfjörð Bjarmason]

On Mon, Jun 28 2021, Patrick Steinhardt wrote:

> [[PGP Signed Part:Undecided]]
> 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.
>
> Signed-off-by: Patrick Steinhardt <ps@pks.im>
> ---
>  t/perf/p5400-receive-pack.sh | 97 ++++++++++++++++++++++++++++++++++++
>  1 file changed, 97 insertions(+)
>  create mode 100755 t/perf/p5400-receive-pack.sh
>
> diff --git a/t/perf/p5400-receive-pack.sh b/t/perf/p5400-receive-pack.sh
> new file mode 100755
> index 0000000000..a945e014a3
> --- /dev/null
> +++ b/t/perf/p5400-receive-pack.sh
> @@ -0,0 +1,97 @@
> +#!/bin/sh
> +
> +test_description="Tests performance of receive-pack"
> +
> +. ./perf-lib.sh
> +
> +test_perf_large_repo

From the runtime I think this just needs test_perf_default_repo, no?
I.e. we should only have *_large_* for cases where git.git is too small
to produce meaningful results.

Part of th problem is that git.git has become larger over time...

> +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

You don't need the #!/bin/sh here, and it won't be used. write_script()
adds it (or the wanted shell path).

> +		echo "failed in pre-receive hook"
> +		exit 1
> +	EOF
> +	cat >config <<-EOF &&
> +		[core]
> +			hooksPath=$(pwd)/hooks
> +	EOF

Easier understood IMO as:

    git config -f config core.hooksPath ...

> +	GIT_CONFIG_GLOBAL="$(pwd)/config" &&
> +	export GIT_CONFIG_GLOBAL &&
> +
> +	git switch --create updated &&
> +	test_commit --no-tag updated
> +'
> +
> +setup_empty() {
> +	git init --bare "$2"
> +}

I searched ahead for setup_empty, looked unused, but...

> +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

...here we use it via interpolation.

I'd find this whole pattern much easier to understand if the setups were
just a bunch of test_expect_success that created a repo_empty.git,
repo_extrarefs.git etc. Then this loop would be:

    for repo in repo*.git ...

I'd think that would also give you more meaningful perf data, as now the
OS will churn between the clone & the subsequent push tests, better to
do all the setup, then all the different perf tests.

Perhaps there's also a way to re-use this setup across different runs, I
don't know/can't remember if t/perf has a less transient thing than the
normal trash directory to use for that.

Re: [PATCH v2 1/3] p5400: add perf tests for git-receive-pack(1)

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 5248 bytes --]

On Mon, Jun 28, 2021 at 09:49:54AM +0200, Ævar Arnfjörð Bjarmason wrote:
> 
> On Mon, Jun 28 2021, Patrick Steinhardt wrote:
> 
> > [[PGP Signed Part:Undecided]]
> > 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.
> >
> > Signed-off-by: Patrick Steinhardt <ps@pks.im>
> > ---
> >  t/perf/p5400-receive-pack.sh | 97 ++++++++++++++++++++++++++++++++++++
> >  1 file changed, 97 insertions(+)
> >  create mode 100755 t/perf/p5400-receive-pack.sh
> >
> > diff --git a/t/perf/p5400-receive-pack.sh b/t/perf/p5400-receive-pack.sh
> > new file mode 100755
> > index 0000000000..a945e014a3
> > --- /dev/null
> > +++ b/t/perf/p5400-receive-pack.sh
> > @@ -0,0 +1,97 @@
> > +#!/bin/sh
> > +
> > +test_description="Tests performance of receive-pack"
> > +
> > +. ./perf-lib.sh
> > +
> > +test_perf_large_repo
> 
> From the runtime I think this just needs test_perf_default_repo, no?
> I.e. we should only have *_large_* for cases where git.git is too small
> to produce meaningful results.
> 
> Part of th problem is that git.git has become larger over time...

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.

> > +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
> 
> You don't need the #!/bin/sh here, and it won't be used. write_script()
> adds it (or the wanted shell path).

Makes sense.

> > +		echo "failed in pre-receive hook"
> > +		exit 1
> > +	EOF
> > +	cat >config <<-EOF &&
> > +		[core]
> > +			hooksPath=$(pwd)/hooks
> > +	EOF
> 
> Easier understood IMO as:
> 
>     git config -f config core.hooksPath ...

Yup, will change.

> > +	GIT_CONFIG_GLOBAL="$(pwd)/config" &&
> > +	export GIT_CONFIG_GLOBAL &&
> > +
> > +	git switch --create updated &&
> > +	test_commit --no-tag updated
> > +'
> > +
> > +setup_empty() {
> > +	git init --bare "$2"
> > +}
> 
> I searched ahead for setup_empty, looked unused, but...
> 
> > +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
> 
> ...here we use it via interpolation.
> 
> I'd find this whole pattern much easier to understand if the setups were
> just a bunch of test_expect_success that created a repo_empty.git,
> repo_extrarefs.git etc. Then this loop would be:
> 
>     for repo in repo*.git ...
> 
> I'd think that would also give you more meaningful perf data, as now the
> OS will churn between the clone & the subsequent push tests, better to
> do all the setup, then all the different perf tests.
> 
> Perhaps there's also a way to re-use this setup across different runs, I
> don't know/can't remember if t/perf has a less transient thing than the
> normal trash directory to use for that.

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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v2 1/3] p5400: add perf tests for git-receive-pack(1)

[Ævar Arnfjörð Bjarmason]

On Tue, Jun 29 2021, Patrick Steinhardt wrote:

> [[PGP Signed Part:Undecided]]
> On Mon, Jun 28, 2021 at 09:49:54AM +0200, Ævar Arnfjörð Bjarmason wrote:
>> 
>> On Mon, Jun 28 2021, Patrick Steinhardt wrote:
>> 
>> > [[PGP Signed Part:Undecided]]
>> > 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.
>> >
>> > Signed-off-by: Patrick Steinhardt <ps@pks.im>
>> > ---
>> >  t/perf/p5400-receive-pack.sh | 97 ++++++++++++++++++++++++++++++++++++
>> >  1 file changed, 97 insertions(+)
>> >  create mode 100755 t/perf/p5400-receive-pack.sh
>> >
>> > diff --git a/t/perf/p5400-receive-pack.sh b/t/perf/p5400-receive-pack.sh
>> > new file mode 100755
>> > index 0000000000..a945e014a3
>> > --- /dev/null
>> > +++ b/t/perf/p5400-receive-pack.sh
>> > @@ -0,0 +1,97 @@
>> > +#!/bin/sh
>> > +
>> > +test_description="Tests performance of receive-pack"
>> > +
>> > +. ./perf-lib.sh
>> > +
>> > +test_perf_large_repo
>> 
>> From the runtime I think this just needs test_perf_default_repo, no?
>> I.e. we should only have *_large_* for cases where git.git is too small
>> to produce meaningful results.
>> 
>> Part of th problem is that git.git has become larger over time...
>
> 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.
>
>> > +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
>> 
>> You don't need the #!/bin/sh here, and it won't be used. write_script()
>> adds it (or the wanted shell path).
>
> Makes sense.
>
>> > +		echo "failed in pre-receive hook"
>> > +		exit 1
>> > +	EOF
>> > +	cat >config <<-EOF &&
>> > +		[core]
>> > +			hooksPath=$(pwd)/hooks
>> > +	EOF
>> 
>> Easier understood IMO as:
>> 
>>     git config -f config core.hooksPath ...
>
> Yup, will change.
>
>> > +	GIT_CONFIG_GLOBAL="$(pwd)/config" &&
>> > +	export GIT_CONFIG_GLOBAL &&
>> > +
>> > +	git switch --create updated &&
>> > +	test_commit --no-tag updated
>> > +'
>> > +
>> > +setup_empty() {
>> > +	git init --bare "$2"
>> > +}
>> 
>> I searched ahead for setup_empty, looked unused, but...
>> 
>> > +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
>> 
>> ...here we use it via interpolation.
>> 
>> I'd find this whole pattern much easier to understand if the setups were
>> just a bunch of test_expect_success that created a repo_empty.git,
>> repo_extrarefs.git etc. Then this loop would be:
>> 
>>     for repo in repo*.git ...
>> 
>> I'd think that would also give you more meaningful perf data, as now the
>> OS will churn between the clone & the subsequent push tests, better to
>> do all the setup, then all the different perf tests.
>> 
>> Perhaps there's also a way to re-use this setup across different runs, I
>> don't know/can't remember if t/perf has a less transient thing than the
>> normal trash directory to use for that.
>
> 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
>
> [[End of PGP Signed Part]]

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.

[PATCH v2 2/3] receive-pack: skip connectivity checks on delete-only commands

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 5027 bytes --]

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%

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 builtin/receive-pack.c | 49 ++++++++++++++++++++++++++----------------
 1 file changed, 30 insertions(+), 19 deletions(-)

diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
index a34742513a..b9263cec15 100644
--- a/builtin/receive-pack.c
+++ b/builtin/receive-pack.c
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v2 2/3] receive-pack: skip connectivity checks on delete-only commands

[Ævar Arnfjörð Bjarmason]

On Mon, Jun 28 2021, Patrick Steinhardt wrote:

> [[PGP Signed Part:Undecided]]
> 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.

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

> [...]
> 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%

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.

Re: [PATCH v2 2/3] receive-pack: skip connectivity checks on delete-only commands

[Ævar Arnfjörð Bjarmason]

On Mon, Jun 28 2021, Ævar Arnfjörð Bjarmason wrote:

> On Mon, Jun 28 2021, Patrick Steinhardt wrote:
>
>> [[PGP Signed Part:Undecided]]
>> 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.
>
> Is it just per specification, or do we also have assertions/tests for
> what happens in that case?
>
>> [...]
>> 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%
>
> 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...

Re: [PATCH v2 2/3] receive-pack: skip connectivity checks on delete-only commands

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 4233 bytes --]

On Mon, Jun 28, 2021 at 10:00:26AM +0200, Ævar Arnfjörð Bjarmason wrote:
> 
> On Mon, Jun 28 2021, Patrick Steinhardt wrote:
> 
> > [[PGP Signed Part:Undecided]]
> > 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.
> 
> Is it just per specification, or do we also have assertions/tests for
> what happens in that case?

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'.

> > [...]
> > 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%
> 
> 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.

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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v2 2/3] receive-pack: skip connectivity checks on delete-only commands

[Jeff King]

On Mon, Jun 28, 2021 at 07:33:11AM +0200, Patrick Steinhardt wrote:

> 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.

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

I think this will work, but we're now making assumptions about how
tmp_objdir will be initialized by the rest of the code.

Could we make a more direct check of: skip calling rev-list if we have
no positive tips to feed? If we call iterate_receive_command() and it
returns end-of-list on the first call, then we know there is nothing to
feed (and as a bonus, this catches some more noop cases around shallow
repos; see iterate_receive_command).

But that made me think that check_connected() could be doing this
itself. And indeed, it seems to already. At the top of that function is:

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

So before we even spawn rev-list, if there's nothing to feed it, we'll
return right away ("err" will be "0" at this point). And I think that
has been there since the beginning of the function (it is even in the
old versions in builtin/fetch.c before it was factored out).

And that explains why you didn't see any performance improvement. We're
already doing this optimization. :)

-Peff

Re: [PATCH v2 2/3] receive-pack: skip connectivity checks on delete-only commands

[Jeff King]

On Tue, Jun 29, 2021 at 09:31:59PM -0400, Jeff King wrote:

> 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:

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

Re: [PATCH v2 2/3] receive-pack: skip connectivity checks on delete-only commands

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 3220 bytes --]

On Tue, Jun 29, 2021 at 09:31:59PM -0400, Jeff King wrote:
> On Mon, Jun 28, 2021 at 07:33:11AM +0200, Patrick Steinhardt wrote:
> 
> > 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.
> 
> 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 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) {
> 
> I think this will work, but we're now making assumptions about how
> tmp_objdir will be initialized by the rest of the code.
> 
> Could we make a more direct check of: skip calling rev-list if we have
> no positive tips to feed? If we call iterate_receive_command() and it
> returns end-of-list on the first call, then we know there is nothing to
> feed (and as a bonus, this catches some more noop cases around shallow
> repos; see iterate_receive_command).
> 
> But that made me think that check_connected() could be doing this
> itself. And indeed, it seems to already. At the top of that function is:
> 
>           if (fn(cb_data, &oid)) {
>                   if (opt->err_fd)
>                           close(opt->err_fd);
>                   return err;
>           }
> 
> So before we even spawn rev-list, if there's nothing to feed it, we'll
> return right away ("err" will be "0" at this point). And I think that
> has been there since the beginning of the function (it is even in the
> old versions in builtin/fetch.c before it was factored out).
> 
> And that explains why you didn't see any performance improvement. We're
> already doing this optimization. :)
> 
> -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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v2 3/3] connected: implement connectivity check using bitmaps

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 10482 bytes --]

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.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 connected.c   | 136 ++++++++++++++++++++++++++++++++++++++++++++++++++
 pack-bitmap.c |   4 +-
 pack-bitmap.h |   2 +
 3 files changed, 140 insertions(+), 2 deletions(-)

diff --git a/connected.c b/connected.c
index b18299fdf0..474275a52f 100644
--- a/connected.c
+++ b/connected.c
@@ -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);
diff --git a/pack-bitmap.c b/pack-bitmap.c
index d90e1d9d8c..d88a882ee1 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -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);
diff --git a/pack-bitmap.h b/pack-bitmap.h
index 99d733eb26..7b4b386107 100644
--- a/pack-bitmap.h
+++ b/pack-bitmap.h
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v2 3/3] connected: implement connectivity check using bitmaps

[Taylor Blau]

On Mon, Jun 28, 2021 at 07:33:15AM +0200, Patrick Steinhardt wrote:
> 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.

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

Re: [PATCH v2 3/3] connected: implement connectivity check using bitmaps

[Taylor Blau]

On Mon, Jun 28, 2021 at 04:23:23PM -0400, Taylor Blau wrote:
> 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

Re: [PATCH v2 3/3] connected: implement connectivity check using bitmaps

[Jeff King]

On Tue, Jun 29, 2021 at 06:44:03PM -0400, Taylor Blau wrote:

>     $ 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'

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

Re: [PATCH v2 3/3] connected: implement connectivity check using bitmaps

[Taylor Blau]

On Tue, Jun 29, 2021 at 10:04:56PM -0400, Jeff King wrote:
> 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.

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


> 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:

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

Re: [PATCH v2 3/3] connected: implement connectivity check using bitmaps

[Jeff King]

On Tue, Jun 29, 2021 at 11:07:47PM -0400, Taylor Blau wrote:

> On Tue, Jun 29, 2021 at 10:04:56PM -0400, Jeff King wrote:
> > 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.
> 
> 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.

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 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:
> 
> 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 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.

> 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.

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

Re: [PATCH v2 3/3] connected: implement connectivity check using bitmaps

[Taylor Blau]

On Wed, Jun 30, 2021 at 01:45:03AM -0400, Jeff King wrote:
> 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.

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.

> 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.

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.

> 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.

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

>   - 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.

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

Re: [PATCH v2 3/3] connected: implement connectivity check using bitmaps

[Jeff King]

On Fri, Jul 02, 2021 at 01:44:12PM -0400, Taylor Blau wrote:

> 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.

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

> 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.

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.

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

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.

> 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.

Yep, no rush. Thanks for looking into this.

-Peff

Re: [PATCH v2 3/3] connected: implement connectivity check using bitmaps

[Jeff King]

On Mon, Jun 28, 2021 at 07:33:15AM +0200, Patrick Steinhardt wrote:

> 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.

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

Re: [PATCH v2 3/3] connected: implement connectivity check using bitmaps

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 4141 bytes --]

On Tue, Jun 29, 2021 at 09:51:33PM -0400, Jeff King wrote:
> On Mon, Jun 28, 2021 at 07:33:15AM +0200, Patrick Steinhardt wrote:
> 
> > 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.
> 
> 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.

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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v3 0/4] Speed up connectivity checks

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 2662 bytes --]

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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v3 1/4] connected: do not sort input revisions

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 3762 bytes --]

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.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 connected.c | 1 +
 revision.c  | 4 +++-
 revision.h  | 1 +
 3 files changed, 5 insertions(+), 1 deletion(-)

diff --git a/connected.c b/connected.c
index b18299fdf0..b5f9523a5f 100644
--- a/connected.c
+++ b/connected.c
@@ -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;
diff --git a/revision.c b/revision.c
index cddd0542a6..7eb09009ba 100644
--- a/revision.c
+++ b/revision.c
@@ -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;
diff --git a/revision.h b/revision.h
index fbb068da9f..ef6998509a 100644
--- a/revision.h
+++ b/revision.h
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v3 1/4] connected: do not sort input revisions

[Ævar Arnfjörð Bjarmason]

On Mon, Aug 02 2021, Patrick Steinhardt wrote:

> [[PGP Signed Part:Undecided]]
> 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.

Really good results:

> 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'

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

Re: [PATCH v3 1/4] connected: do not sort input revisions

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 1880 bytes --]

On Mon, Aug 02, 2021 at 02:49:29PM +0200, Ævar Arnfjörð Bjarmason wrote:
> On Mon, Aug 02 2021, Patrick Steinhardt wrote:
[snip]
> > 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'
> 
> 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).

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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v3 1/4] connected: do not sort input revisions

[Ævar Arnfjörð Bjarmason]

On Tue, Aug 03 2021, Patrick Steinhardt wrote:

> [[PGP Signed Part:Undecided]]
> On Mon, Aug 02, 2021 at 02:49:29PM +0200, Ævar Arnfjörð Bjarmason wrote:
>> On Mon, Aug 02 2021, Patrick Steinhardt wrote:
> [snip]
>> > 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'
>> 
>> 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).
>
> 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.

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.

Re: [PATCH v3 1/4] connected: do not sort input revisions

[Junio C Hamano]

Patrick Steinhardt <ps@pks.im> writes:

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

Nice finding.

> 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.

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...

> 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]:
> ...
> [1]: https://gitlab.com/gitlab-org/gitlab.git. Note that not all refs
>      are visible to clients.

So is this the 2.2 million refs thing?

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

Looks quite straight-forward.

I however suspect that in the longer term it may be cleaner to get
rid of REVSISION_WALK_NO_WALK_UNSORTED if we do this.  The knob that
controls if we sort the initial traversal tips and the knob that
controls if we walk from these tips used to be tied to --no-walk
only because ca92e59e30b wanted to affect only no-walk case, but
with your new finding, it clearly is not limited to the no-walk case
to want to avoid sorting.

Re: [PATCH v3 1/4] connected: do not sort input revisions

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 1867 bytes --]

On Mon, Aug 02, 2021 at 12:00:02PM -0700, Junio C Hamano wrote:
> Patrick Steinhardt <ps@pks.im> writes:
[snip]
> > 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]:
> > ...
> > [1]: https://gitlab.com/gitlab-org/gitlab.git. Note that not all refs
> >      are visible to clients.
> 
> So is this the 2.2 million refs thing?

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.

> > @@ -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);
> 
> Looks quite straight-forward.
> 
> I however suspect that in the longer term it may be cleaner to get
> rid of REVSISION_WALK_NO_WALK_UNSORTED if we do this.  The knob that
> controls if we sort the initial traversal tips and the knob that
> controls if we walk from these tips used to be tied to --no-walk
> only because ca92e59e30b wanted to affect only no-walk case, but
> with your new finding, it clearly is not limited to the no-walk case
> to want to avoid sorting.

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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v3 1/4] connected: do not sort input revisions

[Junio C Hamano]

Patrick Steinhardt <ps@pks.im> writes:

>> I however suspect that in the longer term it may be cleaner to get
>> rid of REVSISION_WALK_NO_WALK_UNSORTED if we do this.  The knob that
>> controls if we sort the initial traversal tips and the knob that
>> controls if we walk from these tips used to be tied to --no-walk
>> only because ca92e59e30b wanted to affect only no-walk case, but
>> with your new finding, it clearly is not limited to the no-walk case
>> to want to avoid sorting.
>
> 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.

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.

[PATCH v3 2/4] revision: stop retrieving reference twice

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 1850 bytes --]

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'

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 revision.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/revision.c b/revision.c
index 7eb09009ba..f06a5d63a3 100644
--- a/revision.c
+++ b/revision.c
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v3 2/4] revision: stop retrieving reference twice

[Ævar Arnfjörð Bjarmason]

On Mon, Aug 02 2021, Patrick Steinhardt wrote:

> [[PGP Signed Part:Undecided]]
> 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'

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.

[PATCH v3 3/4] revision: avoid loading object headers multiple times

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 3533 bytes --]

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.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 revision.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)

diff --git a/revision.c b/revision.c
index f06a5d63a3..671b6d6513 100644
--- a/revision.c
+++ b/revision.c
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v3 3/4] revision: avoid loading object headers multiple times

[Ævar Arnfjörð Bjarmason]

On Mon, Aug 02 2021, Patrick Steinhardt wrote:

> [[PGP Signed Part:Undecided]]
> 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.
>
> Signed-off-by: Patrick Steinhardt <ps@pks.im>
> ---
>  revision.c | 15 ++++++++++++---
>  1 file changed, 12 insertions(+), 3 deletions(-)
>
> diff --git a/revision.c b/revision.c
> index f06a5d63a3..671b6d6513 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -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)) {

Let's s/int type/enum object_type, personally I think we should never do
"type < 0" either, and check OBJ_BAD explicitly, but I've seemingly lost
that discussion on-list before.

But I think the consensus is that we should not do !type, but rather
type == OBJ_NONE.

Re: [PATCH v3 3/4] revision: avoid loading object headers multiple times

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 1305 bytes --]

On Mon, Aug 02, 2021 at 02:55:09PM +0200, Ævar Arnfjörð Bjarmason wrote:
> On Mon, Aug 02 2021, Patrick Steinhardt wrote:
[snip]
> > diff --git a/revision.c b/revision.c
> > index f06a5d63a3..671b6d6513 100644
> > --- a/revision.c
> > +++ b/revision.c
> > @@ -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)) {
> 
> Let's s/int type/enum object_type, personally I think we should never do
> "type < 0" either, and check OBJ_BAD explicitly, but I've seemingly lost
> that discussion on-list before.
> 
> But I think the consensus is that we should not do !type, but rather
> type == OBJ_NONE.

`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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v3 3/4] revision: avoid loading object headers multiple times

[Junio C Hamano]

Patrick Steinhardt <ps@pks.im> writes:

> 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.
> ...
> 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.

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.

Re: [PATCH v3 3/4] revision: avoid loading object headers multiple times

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 2321 bytes --]

On Mon, Aug 02, 2021 at 12:40:56PM -0700, Junio C Hamano wrote:
> Patrick Steinhardt <ps@pks.im> writes:
> 
> > 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.
> > ...
> > 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.
> 
> 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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v3 3/4] revision: avoid loading object headers multiple times

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 3077 bytes --]

On Tue, Aug 03, 2021 at 11:07:29AM +0200, Patrick Steinhardt wrote:
> On Mon, Aug 02, 2021 at 12:40:56PM -0700, Junio C Hamano wrote:
> > Patrick Steinhardt <ps@pks.im> writes:
> > 
> > > 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.
> > > ...
> > > 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.
> > 
> > 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.

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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v3 4/4] revision: avoid hitting packfiles when commits are in commit-graph

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 4921 bytes --]

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'

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 commit-graph.c | 55 +++++++++++++++++++++++++++++++++++++++-----------
 commit-graph.h |  2 ++
 revision.c     | 10 +++++----
 3 files changed, 51 insertions(+), 16 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index 3860a0d847..a81d5cebc0 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -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);
 	}
 }
 
diff --git a/commit-graph.h b/commit-graph.h
index 96c24fb577..f373fab4c0 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -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);
diff --git a/revision.c b/revision.c
index 671b6d6513..c3f9cf2998 100644
--- a/revision.c
+++ b/revision.c
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v3 4/4] revision: avoid hitting packfiles when commits are in commit-graph

[Junio C Hamano]

Patrick Steinhardt <ps@pks.im> writes:

> diff --git a/commit-graph.c b/commit-graph.c
> index 3860a0d847..a81d5cebc0 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -864,6 +864,48 @@ static int fill_commit_in_graph(struct repository *r,
>  	return 1;
>  }


Describe return-value here.  0 for not-found, !0 for found?

> +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;
> +}

Likewise, or as this is public, perhaps in commit-graph.h next to
its declaration.

> +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;

This is puzzling---at least it is not consistent with what the
function name says ("please say if you find _this_ object in the
commit-graph file"---if that is not what this function does, it
needs a comment before the implementation).

The caller had object and we has already been parsed.  If the
function were "with help from commit-graph, please tell me if you
can positively say this is a commit", the above is understandable.
If we know positively that it is not commit, we say "no, it is not a
commit" (which may be suboptimal---if the caller falls back to
another codepath, the object will still not be a commit) and if we
know it is a commit, we can say "yes, it definitely is a commit" and
the caller can stop there.

I guess my only problem with this function is that its name and what
it does does not align.  If the caller uses it for the real purpose
of the function I guessed, then the logic itself may be OK.

> +	}
> +
> +	if (!repo->objects->commit_graph)
> +		return -1;

There is no commit-graph, then we decline to make a decision, which
makes sense.

> +	if (!find_object_id_in_graph(&object->oid, repo->objects->commit_graph, &pos))
> +		return -1;

If it does not exist in the graph, we cannot tell, either.

> +	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);

And I think this one is a op-op refactoring that does not change the
behaviour of find_commit_in_graph()?  It might be easier if done in
a separate preparatory step, but it is small enough.

> diff --git a/commit-graph.h b/commit-graph.h
> index 96c24fb577..f373fab4c0 100644
> --- a/commit-graph.h
> +++ b/commit-graph.h
> @@ -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);
> diff --git a/revision.c b/revision.c
> index 671b6d6513..c3f9cf2998 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -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;
> +			}
>  		}
>  	}

Re: [PATCH v3 4/4] revision: avoid hitting packfiles when commits are in commit-graph

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 3353 bytes --]

On Mon, Aug 02, 2021 at 01:01:03PM -0700, Junio C Hamano wrote:
> Patrick Steinhardt <ps@pks.im> writes:
[snip]
> > +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;
> 
> This is puzzling---at least it is not consistent with what the
> function name says ("please say if you find _this_ object in the
> commit-graph file"---if that is not what this function does, it
> needs a comment before the implementation).
> 
> The caller had object and we has already been parsed.  If the
> function were "with help from commit-graph, please tell me if you
> can positively say this is a commit", the above is understandable.
> If we know positively that it is not commit, we say "no, it is not a
> commit" (which may be suboptimal---if the caller falls back to
> another codepath, the object will still not be a commit) and if we
> know it is a commit, we can say "yes, it definitely is a commit" and
> the caller can stop there.
> 
> I guess my only problem with this function is that its name and what
> it does does not align.  If the caller uses it for the real purpose
> of the function I guessed, then the logic itself may be OK.

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.

> >  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);
> 
> And I think this one is a op-op refactoring that does not change the
> behaviour of find_commit_in_graph()?  It might be easier if done in
> a separate preparatory step, but it is small enough.

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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v3 4/4] revision: avoid hitting packfiles when commits are in commit-graph

[Junio C Hamano]

Patrick Steinhardt <ps@pks.im> writes:

> 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.

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?

Re: [PATCH v3 4/4] revision: avoid hitting packfiles when commits are in commit-graph

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 3400 bytes --]

On Tue, Aug 03, 2021 at 02:56:49PM -0700, Junio C Hamano wrote:
> Patrick Steinhardt <ps@pks.im> writes:
> 
> > 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.
> 
> 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:

diff --git a/revision.c b/revision.c
index 3527ef3f65..9e62de20ab 100644
--- a/revision.c
+++ b/revision.c
@@ -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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v3 4/4] revision: avoid hitting packfiles when commits are in commit-graph

[Junio C Hamano]

Patrick Steinhardt <ps@pks.im> writes:

> On Tue, Aug 03, 2021 at 02:56:49PM -0700, Junio C Hamano wrote:
>> Patrick Steinhardt <ps@pks.im> writes:
>> 
>> > 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.
>> 
>> 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.

[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 ...

> We can do the following on top though:
>
> diff --git a/revision.c b/revision.c
> index 3527ef3f65..9e62de20ab 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -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.

... 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.

Re: [PATCH v3 4/4] revision: avoid hitting packfiles when commits are in commit-graph

[Ævar Arnfjörð Bjarmason]

On Tue, Aug 03 2021, Patrick Steinhardt wrote:

> 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?

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.

[PATCH v4 0/6] Speed up connectivity checks

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 17702 bytes --]

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 <ps@pks.im>
     
    + ## Documentation/rev-list-options.txt ##
    +@@ Documentation/rev-list-options.txt: list of the missing objects.  Object IDs are prefixed with a ``?'' character.
    + 	objects.
    + endif::git-rev-list[]
    + 
    ++--unsorted-input::
    ++	Show commits in the order they were given on the command line instead
    ++	of sorting them in reverse chronological order by commit time. Cannot
    ++	be combined with `--no-walk` or `--no-walk=sorted`.
    ++
    + --no-walk[=(sorted|unsorted)]::
    + 	Only show the given commits, but do not traverse their ancestors.
    + 	This has no effect if a range is specified. If the argument
    +@@ Documentation/rev-list-options.txt: endif::git-rev-list[]
    + 	given on the command line. Otherwise (if `sorted` or no argument
    + 	was given), the commits are shown in reverse chronological order
    + 	by commit time.
    +-	Cannot be combined with `--graph`.
    ++	Cannot be combined with `--graph`. Cannot be combined with
    ++	`--unsorted-input` if `sorted` or no argument was given.
    + 
    + --do-walk::
    + 	Overrides a previous `--no-walk`.
    +
      ## connected.c ##
     @@ connected.c: int check_connected(oid_iterate_fn fn, void *cb_data,
      	if (opt->progress)
    @@ revision.c: static int handle_revision_opt(struct rev_info *revs, int argc, cons
      		revs->sort_order = REV_SORT_BY_AUTHOR_DATE;
      		revs->topo_order = 1;
     +	} else if (!strcmp(arg, "--unsorted-input")) {
    ++		if (revs->no_walk && !revs->unsorted_input)
    ++			die(_("--unsorted-input is incompatible with --no-walk and --no-walk=sorted"));
     +		revs->unsorted_input = 1;
      	} else if (!strcmp(arg, "--early-output")) {
      		revs->early_output = 100;
      		revs->topo_order = 1;
    -@@ revision.c: int prepare_revision_walk(struct rev_info *revs)
    - 
    - 	if (!revs->reflog_info)
    - 		prepare_to_use_bloom_filter(revs);
    --	if (revs->no_walk != REVISION_WALK_NO_WALK_UNSORTED)
    -+	if (revs->no_walk != REVISION_WALK_NO_WALK_UNSORTED && !revs->unsorted_input)
    - 		commit_list_sort_by_date(&revs->commits);
    - 	if (revs->no_walk)
    - 		return 0;
    +@@ revision.c: static int handle_revision_pseudo_opt(const char *submodule,
    + 	} else if (!strcmp(arg, "--not")) {
    + 		*flags ^= UNINTERESTING | BOTTOM;
    + 	} else if (!strcmp(arg, "--no-walk")) {
    ++		if (revs->unsorted_input)
    ++			die(_("--no-walk is incompatible with --no-walk=unsorted and --unsorted-input"));
    + 		revs->no_walk = 1;
    + 	} else if (skip_prefix(arg, "--no-walk=", &optarg)) {
    + 		/*
    +@@ revision.c: static int handle_revision_pseudo_opt(const char *submodule,
    + 		 * not allowed, since the argument is optional.
    + 		 */
    + 		revs->no_walk = 1;
    +-		if (!strcmp(optarg, "sorted"))
    ++		if (!strcmp(optarg, "sorted")) {
    ++			if (revs->unsorted_input)
    ++				die(_("--no-walk=sorted is incompatible with --no-walk=unsorted "
    ++				    "and --unsorted-input"));
    + 			revs->unsorted_input = 0;
    +-		else if (!strcmp(optarg, "unsorted"))
    ++		} else if (!strcmp(optarg, "unsorted"))
    + 			revs->unsorted_input = 1;
    + 		else
    + 			return error("invalid argument to --no-walk");
     
    - ## revision.h ##
    -@@ revision.h: struct rev_info {
    - 			simplify_history:1,
    - 			show_pulls:1,
    - 			topo_order:1,
    -+			unsorted_input:1,
    - 			simplify_merges:1,
    - 			simplify_by_decoration:1,
    - 			single_worktree:1,
    + ## t/t6000-rev-list-misc.sh ##
    +@@ t/t6000-rev-list-misc.sh: test_expect_success 'rev-list --count --objects' '
    + 	test_line_count = $count actual
    + '
    + 
    ++test_expect_success 'rev-list --unsorted-input results in different sorting' '
    ++	git rev-list --unsorted-input HEAD HEAD~ >first &&
    ++	git rev-list --unsorted-input HEAD~ HEAD >second &&
    ++	! test_cmp first second &&
    ++	sort first >first.sorted &&
    ++	sort second >second.sorted &&
    ++	test_cmp first.sorted second.sorted
    ++'
    ++
    ++test_expect_success 'rev-list --unsorted-input compatible with --no-walk=unsorted' '
    ++	git rev-list --unsorted-input --no-walk=unsorted HEAD HEAD~ >actual &&
    ++	git rev-parse HEAD >expect &&
    ++	git rev-parse HEAD~ >>expect &&
    ++	test_cmp expect actual
    ++'
    ++
    ++test_expect_success 'rev-list --unsorted-input incompatible with --no-walk=sorted' '
    ++	cat >expect <<-EOF &&
    ++		fatal: --no-walk is incompatible with --no-walk=unsorted and --unsorted-input
    ++	EOF
    ++	test_must_fail git rev-list --unsorted-input --no-walk HEAD 2>error &&
    ++	test_cmp expect error &&
    ++
    ++	cat >expect <<-EOF &&
    ++		fatal: --no-walk=sorted is incompatible with --no-walk=unsorted and --unsorted-input
    ++	EOF
    ++	test_must_fail git rev-list --unsorted-input --no-walk=sorted HEAD 2>error &&
    ++	test_cmp expect error &&
    ++
    ++	cat >expect <<-EOF &&
    ++		fatal: --unsorted-input is incompatible with --no-walk and --no-walk=sorted
    ++	EOF
    ++	test_must_fail git rev-list --no-walk --unsorted-input HEAD 2>error &&
    ++	test_cmp expect error &&
    ++	test_must_fail git rev-list --no-walk=sorted --unsorted-input HEAD 2>error &&
    ++	test_cmp expect error
    ++'
    ++
    + test_done
2:  db85480649 ! 3:  d8e63d0943 revision: stop retrieving reference twice
    @@ Commit message
         revision: stop retrieving reference twice
     
         When queueing up references for the revision walk, `handle_one_ref()`
    -    will resolve the reference's object ID and then queue the ID as pending
    -    object via `add_pending_oid()`. But `add_pending_oid()` will again try
    -    to resolve the object ID to an object, effectively duplicating the work
    -    its caller already did before.
    +    will resolve the reference's object ID via `get_reference()` and then
    +    queue the ID as pending object via `add_pending_oid()`. But given that
    +    `add_pending_oid()` is only a thin wrapper around `add_pending_object()`
    +    which fist calls `get_reference()`, we effectively resolve the reference
    +    twice and thus duplicate some of the work.
     
    -    Fix the issue by instead calling `add_pending_object()`, which takes the
    -    already-resolved object as input. In a repository with lots of refs,
    -    this translates in a nearly 10% speedup:
    +    Fix the issue by instead calling `add_pending_object()` directly, which
    +    takes the already-resolved object as input. In a repository with lots of
    +    refs, this translates into a near 10% speedup:
     
             Benchmark #1: HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev
               Time (mean ± σ):      5.015 s ±  0.038 s    [User: 4.698 s, System: 0.316 s]
3:  b9897e102a ! 4:  ba8df5cad0 revision: avoid loading object headers multiple times
    @@ Commit message
         either a tag or a commit, we'd have a modest increase in memory
         consumption of about 12.5% here.
     
    +    Note that on its own, this patch may not seem like a clear win. But it
    +    is a prerequisite for the following patch, which will result in another
    +    37% speedup.
    +
         Signed-off-by: Patrick Steinhardt <ps@pks.im>
     
      ## 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 <ps@pks.im>
     
      ## 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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v4 1/6] revision: separate walk and unsorted flags

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 3681 bytes --]

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.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 builtin/log.c    | 2 +-
 builtin/revert.c | 3 ++-
 revision.c       | 9 +++++----
 revision.h       | 7 ++-----
 4 files changed, 10 insertions(+), 11 deletions(-)

diff --git a/builtin/log.c b/builtin/log.c
index 3d7717ba5c..f75d87e8d7 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -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));
diff --git a/builtin/revert.c b/builtin/revert.c
index 237f2f18d4..2e13660e4b 100644
--- a/builtin/revert.c
+++ b/builtin/revert.c
@@ -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], "-"))
diff --git a/revision.c b/revision.c
index cddd0542a6..86bbcd10d2 100644
--- a/revision.c
+++ b/revision.c
@@ -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;
diff --git a/revision.h b/revision.h
index fbb068da9f..0c65a760ee 100644
--- a/revision.h
+++ b/revision.h
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v4 1/6] revision: separate walk and unsorted flags

[Junio C Hamano]

Patrick Steinhardt <ps@pks.im> writes:

> 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.
>
> Signed-off-by: Patrick Steinhardt <ps@pks.im>
> ---
>  builtin/log.c    | 2 +-
>  builtin/revert.c | 3 ++-
>  revision.c       | 9 +++++----
>  revision.h       | 7 ++-----
>  4 files changed, 10 insertions(+), 11 deletions(-)

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

[PATCH v4 2/6] connected: do not sort input revisions

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 7277 bytes --]

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.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 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(-)

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 24569b06d1..b7bd27e171 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -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`.
diff --git a/connected.c b/connected.c
index b18299fdf0..b5f9523a5f 100644
--- a/connected.c
+++ b/connected.c
@@ -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;
diff --git a/revision.c b/revision.c
index 86bbcd10d2..793f76a509 100644
--- a/revision.c
+++ b/revision.c
@@ -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");
diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
index 12def7bcbf..8e213eb413 100755
--- a/t/t6000-rev-list-misc.sh
+++ b/t/t6000-rev-list-misc.sh
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v4 2/6] connected: do not sort input revisions

[Junio C Hamano]

Patrick Steinhardt <ps@pks.im> writes:

> +	} 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;

So this can be used with --no-walk=unsorted, even though doing
so would be redundant and meaningless.  OK.

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

And likewise, --no-walk is --no-walk=sorted so we do not allow it to
be used with --unsorted-input or --no=walk=unsorted.  OK.

>  		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"));

OK.

>  			revs->unsorted_input = 0;
> -		else if (!strcmp(optarg, "unsorted"))
> +		} else if (!strcmp(optarg, "unsorted"))
>  			revs->unsorted_input = 1;

This is --no-walk=unsorted; could it have been given after --no-walk
or --no-walk=unsorted?

The application of the incompatibility rules seems a bit uneven.  An
earlier piece of code will reject "--no-walk=unsorted --no-walk" given
in this order (see "And likewise" above).  But here, this part of
the code will happily take "--no-walk --no-walk=unsorted".

Of course these details can be fixed with more careful code design,
but I wonder if it may be result in the code and behaviour that is
far simpler to explain (and probably implement) if we declare that

 * --no-walk is not a synonym to --no-walk=sorted; it just flips
   .no_walk member on.

 * --no-walk=sorted and --no-walk=unsorted flip .no_walk member on,
   and then flips .unsorted_input member off or on, respectively.

and define that the usual last-one-wins rule would apply?

Thanks.

Re: [PATCH v4 2/6] connected: do not sort input revisions

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 1961 bytes --]

On Thu, Aug 05, 2021 at 11:44:05AM -0700, Junio C Hamano wrote:
> Patrick Steinhardt <ps@pks.im> writes:
> >  			revs->unsorted_input = 0;
> > -		else if (!strcmp(optarg, "unsorted"))
> > +		} else if (!strcmp(optarg, "unsorted"))
> >  			revs->unsorted_input = 1;
> 
> This is --no-walk=unsorted; could it have been given after --no-walk
> or --no-walk=unsorted?
> 
> The application of the incompatibility rules seems a bit uneven.  An
> earlier piece of code will reject "--no-walk=unsorted --no-walk" given
> in this order (see "And likewise" above).  But here, this part of
> the code will happily take "--no-walk --no-walk=unsorted".
> 
> Of course these details can be fixed with more careful code design,
> but I wonder if it may be result in the code and behaviour that is
> far simpler to explain (and probably implement) if we declare that
> 
>  * --no-walk is not a synonym to --no-walk=sorted; it just flips
>    .no_walk member on.
> 
>  * --no-walk=sorted and --no-walk=unsorted flip .no_walk member on,
>    and then flips .unsorted_input member off or on, respectively.
> 
> and define that the usual last-one-wins rule would apply?
> 
> Thanks.

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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v4 2/6] connected: do not sort input revisions

[Junio C Hamano]

Patrick Steinhardt <ps@pks.im> writes:

> 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.

True.

> 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.

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.

[PATCH v4 3/6] revision: stop retrieving reference twice

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 1944 bytes --]

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'

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 revision.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/revision.c b/revision.c
index 793f76a509..0d99413856 100644
--- a/revision.c
+++ b/revision.c
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v4 4/6] revision: avoid loading object headers multiple times

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 3694 bytes --]

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.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 revision.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)

diff --git a/revision.c b/revision.c
index 0d99413856..25f4784fdd 100644
--- a/revision.c
+++ b/revision.c
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v4 5/6] commit-graph: split out function to search commit position

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 4561 bytes --]

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.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 commit-graph.c | 55 +++++++++++++++++++++++++++-----------------------
 1 file changed, 30 insertions(+), 25 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index 3860a0d847..8c4c7262c8 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v4 6/6] revision: avoid hitting packfiles when commits are in commit-graph

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 4757 bytes --]

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'

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 commit-graph.c | 26 ++++++++++++++++++++++++++
 commit-graph.h |  7 +++++++
 revision.c     | 17 +++++++++++++++--
 3 files changed, 48 insertions(+), 2 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index 8c4c7262c8..cc7136243d 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -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)
diff --git a/commit-graph.h b/commit-graph.h
index 96c24fb577..e2e93b0ee1 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -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
diff --git a/revision.c b/revision.c
index 25f4784fdd..318b43026e 100644
--- a/revision.c
+++ b/revision.c
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v5 0/5] Speed up connectivity checks

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 11372 bytes --]

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'
     
         Signed-off-by: Patrick Steinhardt <ps@pks.im>
     
    @@ commit-graph.c: static int find_commit_pos_in_graph(struct commit *item, struct
      	}
      }
      
    -+int parse_commit_in_graph_gently(struct repository *repo, struct object *object)
    ++struct commit *lookup_commit_in_graph(struct repository *repo, const struct object_id *id)
     +{
     +	struct commit *commit;
     +	uint32_t pos;
     +
    -+	if (object->parsed) {
    -+		if (object->type != OBJ_COMMIT)
    -+			return -1;
    -+		return 0;
    -+	}
    -+
     +	if (!repo->objects->commit_graph)
    -+		return -1;
    ++		return NULL;
    ++	if (!search_commit_pos_in_graph(id, repo->objects->commit_graph, &pos))
    ++		return NULL;
    ++	if (!repo_has_object_file(repo, id))
    ++		return NULL;
     +
    -+	if (!search_commit_pos_in_graph(&object->oid, repo->objects->commit_graph, &pos))
    -+		return -1;
    -+
    -+	commit = object_as_type(object, OBJ_COMMIT, 1);
    ++	commit = lookup_commit(repo, id);
     +	if (!commit)
    -+		return -1;
    -+	if (!fill_commit_in_graph(repo, commit, repo->objects->commit_graph, pos))
    -+		return -1;
    ++		return NULL;
    ++	if (commit->object.parsed)
    ++		return commit;
     +
    -+	return 0;
    ++	if (!fill_commit_in_graph(repo, commit, repo->objects->commit_graph, pos))
    ++		return NULL;
    ++
    ++	return commit;
     +}
     +
      static int parse_commit_in_graph_one(struct repository *r,
    @@ commit-graph.h: int open_commit_graph(const char *graph_file, int *fd, struct st
      int parse_commit_in_graph(struct repository *r, struct commit *item);
      
     +/*
    -+ * Given an object of unknown type, try to fill in the object in case it is a
    -+ * commit part of the commit-graph. Returns 0 if the object is a parsed commit
    -+ * or if it could be filled in via the commit graph, otherwise it returns -1.
    ++ * Look up the given commit ID in the commit-graph. This will only return a
    ++ * commit if the ID exists both in the graph and in the object database such
    ++ * that we don't return commits whose object has been pruned. Otherwise, this
    ++ * function returns `NULL`.
     + */
    -+int parse_commit_in_graph_gently(struct repository *repo, struct object *object);
    ++struct commit *lookup_commit_in_graph(struct repository *repo, const struct object_id *id);
     +
      /*
       * It is possible that we loaded commit contents from the commit buffer,
    @@ commit-graph.h: int open_commit_graph(const char *graph_file, int *fd, struct st
     
      ## revision.c ##
     @@ revision.c: static struct object *get_reference(struct rev_info *revs, const char *name,
    - 	struct object *object = lookup_unknown_object(revs->repo, oid);
    + 				    unsigned int flags)
    + {
    + 	struct object *object;
    ++	struct commit *commit;
      
    - 	if (object->type == OBJ_NONE) {
    --		int type = oid_object_info(revs->repo, oid, NULL);
    --		if (type < 0 || !object_as_type(object, type, 1)) {
    -+		/*
    -+		 * It's likely that the reference points to a commit, so we
    -+		 * first try to look it up via the commit-graph. If successful,
    -+		 * then we know it's a commit and don't have to unpack the
    -+		 * object header. We still need to assert that the object
    -+		 * exists, but given that we don't request any info about the
    -+		 * object this is a lot faster than `oid_object_info()`.
    -+		 */
    -+		if (parse_commit_in_graph_gently(revs->repo, object) < 0) {
    -+			int type = oid_object_info(revs->repo, oid, NULL);
    -+			if (type < 0 || !object_as_type(object, type, 1)) {
    -+				object = NULL;
    -+				goto out;
    -+			}
    -+		} else if (!repo_has_object_file(revs->repo, oid)) {
    - 			object = NULL;
    - 			goto out;
    - 		}
    + 	/*
    +-	 * If the repository has commit graphs, repo_parse_commit() avoids
    +-	 * reading the object buffer, so use it whenever possible.
    ++	 * If the repository has commit graphs, we try to opportunistically
    ++	 * look up the object ID in those graphs. Like this, we can avoid
    ++	 * parsing commit data from disk.
    + 	 */
    +-	if (oid_object_info(revs->repo, oid, NULL) == OBJ_COMMIT) {
    +-		struct commit *c = lookup_commit(revs->repo, oid);
    +-		if (!repo_parse_commit(revs->repo, c))
    +-			object = (struct object *) c;
    +-		else
    +-			object = NULL;
    +-	} else {
    ++	commit = lookup_commit_in_graph(revs->repo, oid);
    ++	if (commit)
    ++		object = &commit->object;
    ++	else
    + 		object = parse_object(revs->repo, oid);
    +-	}
    + 
    + 	if (!object) {
    + 		if (revs->ignore_missing)
-- 
2.32.0


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v5 0/5] Speed up connectivity checks

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 12058 bytes --]

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

On Mon, Aug 09, 2021 at 10:00:39AM +0200, Patrick Steinhardt wrote:
> 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'
>      
>          Signed-off-by: Patrick Steinhardt <ps@pks.im>
>      
>     @@ commit-graph.c: static int find_commit_pos_in_graph(struct commit *item, struct
>       	}
>       }
>       
>     -+int parse_commit_in_graph_gently(struct repository *repo, struct object *object)
>     ++struct commit *lookup_commit_in_graph(struct repository *repo, const struct object_id *id)
>      +{
>      +	struct commit *commit;
>      +	uint32_t pos;
>      +
>     -+	if (object->parsed) {
>     -+		if (object->type != OBJ_COMMIT)
>     -+			return -1;
>     -+		return 0;
>     -+	}
>     -+
>      +	if (!repo->objects->commit_graph)
>     -+		return -1;
>     ++		return NULL;
>     ++	if (!search_commit_pos_in_graph(id, repo->objects->commit_graph, &pos))
>     ++		return NULL;
>     ++	if (!repo_has_object_file(repo, id))
>     ++		return NULL;
>      +
>     -+	if (!search_commit_pos_in_graph(&object->oid, repo->objects->commit_graph, &pos))
>     -+		return -1;
>     -+
>     -+	commit = object_as_type(object, OBJ_COMMIT, 1);
>     ++	commit = lookup_commit(repo, id);
>      +	if (!commit)
>     -+		return -1;
>     -+	if (!fill_commit_in_graph(repo, commit, repo->objects->commit_graph, pos))
>     -+		return -1;
>     ++		return NULL;
>     ++	if (commit->object.parsed)
>     ++		return commit;
>      +
>     -+	return 0;
>     ++	if (!fill_commit_in_graph(repo, commit, repo->objects->commit_graph, pos))
>     ++		return NULL;
>     ++
>     ++	return commit;
>      +}
>      +
>       static int parse_commit_in_graph_one(struct repository *r,
>     @@ commit-graph.h: int open_commit_graph(const char *graph_file, int *fd, struct st
>       int parse_commit_in_graph(struct repository *r, struct commit *item);
>       
>      +/*
>     -+ * Given an object of unknown type, try to fill in the object in case it is a
>     -+ * commit part of the commit-graph. Returns 0 if the object is a parsed commit
>     -+ * or if it could be filled in via the commit graph, otherwise it returns -1.
>     ++ * Look up the given commit ID in the commit-graph. This will only return a
>     ++ * commit if the ID exists both in the graph and in the object database such
>     ++ * that we don't return commits whose object has been pruned. Otherwise, this
>     ++ * function returns `NULL`.
>      + */
>     -+int parse_commit_in_graph_gently(struct repository *repo, struct object *object);
>     ++struct commit *lookup_commit_in_graph(struct repository *repo, const struct object_id *id);
>      +
>       /*
>        * It is possible that we loaded commit contents from the commit buffer,
>     @@ commit-graph.h: int open_commit_graph(const char *graph_file, int *fd, struct st
>      
>       ## revision.c ##
>      @@ revision.c: static struct object *get_reference(struct rev_info *revs, const char *name,
>     - 	struct object *object = lookup_unknown_object(revs->repo, oid);
>     + 				    unsigned int flags)
>     + {
>     + 	struct object *object;
>     ++	struct commit *commit;
>       
>     - 	if (object->type == OBJ_NONE) {
>     --		int type = oid_object_info(revs->repo, oid, NULL);
>     --		if (type < 0 || !object_as_type(object, type, 1)) {
>     -+		/*
>     -+		 * It's likely that the reference points to a commit, so we
>     -+		 * first try to look it up via the commit-graph. If successful,
>     -+		 * then we know it's a commit and don't have to unpack the
>     -+		 * object header. We still need to assert that the object
>     -+		 * exists, but given that we don't request any info about the
>     -+		 * object this is a lot faster than `oid_object_info()`.
>     -+		 */
>     -+		if (parse_commit_in_graph_gently(revs->repo, object) < 0) {
>     -+			int type = oid_object_info(revs->repo, oid, NULL);
>     -+			if (type < 0 || !object_as_type(object, type, 1)) {
>     -+				object = NULL;
>     -+				goto out;
>     -+			}
>     -+		} else if (!repo_has_object_file(revs->repo, oid)) {
>     - 			object = NULL;
>     - 			goto out;
>     - 		}
>     + 	/*
>     +-	 * If the repository has commit graphs, repo_parse_commit() avoids
>     +-	 * reading the object buffer, so use it whenever possible.
>     ++	 * If the repository has commit graphs, we try to opportunistically
>     ++	 * look up the object ID in those graphs. Like this, we can avoid
>     ++	 * parsing commit data from disk.
>     + 	 */
>     +-	if (oid_object_info(revs->repo, oid, NULL) == OBJ_COMMIT) {
>     +-		struct commit *c = lookup_commit(revs->repo, oid);
>     +-		if (!repo_parse_commit(revs->repo, c))
>     +-			object = (struct object *) c;
>     +-		else
>     +-			object = NULL;
>     +-	} else {
>     ++	commit = lookup_commit_in_graph(revs->repo, oid);
>     ++	if (commit)
>     ++		object = &commit->object;
>     ++	else
>     + 		object = parse_object(revs->repo, oid);
>     +-	}
>     + 
>     + 	if (!object) {
>     + 		if (revs->ignore_missing)
> -- 
> 2.32.0
> 



[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v5 0/5] Speed up connectivity checks

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 15551 bytes --]

Hi,

this is the fifth version of my series to speed up connectivity checks
in the context of repos with many refs. While the original goal has been
to speed up connectivity checks only, the series is now optimizing
git-rev-list(1) in general to be able to more efficiently load
references. Like this, `--not --all` is a lot faster in the context of
many refs, but other usecases benefit, too.

Changes compared to v4:

    - I've changed the interface to load commits via the commit-graph.
      Instead of the previous version where you'd had to pass in a
      `struct object`, which forced us to use `lookup_unknown_object()`,
      one now only passes in an object ID. If the object ID is found in
      the commit graph and if the corresponding object exists in the
      ODB, then we return the parsed commit object.

      This also avoids a previous pitfal: we'd have parsed the commit
      via the graph and thus had allocated the object even if the
      corresponding object didn't exist. While we knew to handle this in
      `get_reference()` by asserting object existence, any other caller
      which executes `lookup_commit()` would get the parsed commit and
      assume that it exists. This now cannot happen anymore given that
      we only create the commit object in case we know the ID exists in
      the ODB.

    - With this change, I could now drop the patch which avoided loading
      objects multiple times: we don't need `lookup_unknown_object()`
      anymore and thus don't thave the memory/perf tradeoff. And with
      the new interface to load commits via the graph, the deduplication
      only resulted in a ~1% speedup.

    - `--unsorted-input` and `--no-walk` are now mutually exclusive
      regardless of whether `--no-walk` is sorted or unsorted,
      simplifying the logic.

Patrick

Patrick Steinhardt (5):
  revision: separate walk and unsorted flags
  connected: do not sort input revisions
  revision: stop retrieving reference twice
  commit-graph: split out function to search commit position
  revision: avoid hitting packfiles when commits are in commit-graph

 Documentation/rev-list-options.txt |  8 ++-
 builtin/log.c                      |  2 +-
 builtin/revert.c                   |  3 +-
 commit-graph.c                     | 79 ++++++++++++++++++++----------
 commit-graph.h                     |  8 +++
 connected.c                        |  1 +
 revision.c                         | 38 ++++++++------
 revision.h                         |  7 +--
 t/t6000-rev-list-misc.sh           | 31 ++++++++++++
 9 files changed, 129 insertions(+), 48 deletions(-)

Range-diff against v4:
1:  67232910ac = 1:  67232910ac revision: separate walk and unsorted flags
2:  9d7f484907 ! 2:  d3f498a563 connected: do not sort input revisions
    @@ revision.c: static int handle_revision_opt(struct rev_info *revs, int argc, cons
      		revs->sort_order = REV_SORT_BY_AUTHOR_DATE;
      		revs->topo_order = 1;
     +	} else if (!strcmp(arg, "--unsorted-input")) {
    -+		if (revs->no_walk && !revs->unsorted_input)
    -+			die(_("--unsorted-input is incompatible with --no-walk and --no-walk=sorted"));
    ++		if (revs->no_walk)
    ++			die(_("--unsorted-input is incompatible with --no-walk"));
     +		revs->unsorted_input = 1;
      	} else if (!strcmp(arg, "--early-output")) {
      		revs->early_output = 100;
    @@ revision.c: static int handle_revision_pseudo_opt(const char *submodule,
      	} else if (!strcmp(arg, "--not")) {
      		*flags ^= UNINTERESTING | BOTTOM;
      	} else if (!strcmp(arg, "--no-walk")) {
    -+		if (revs->unsorted_input)
    -+			die(_("--no-walk is incompatible with --no-walk=unsorted and --unsorted-input"));
    ++		if (!revs->no_walk && revs->unsorted_input)
    ++			die(_("--no-walk is incompatible with --unsorted-input"));
      		revs->no_walk = 1;
      	} else if (skip_prefix(arg, "--no-walk=", &optarg)) {
    ++		if (!revs->no_walk && revs->unsorted_input)
    ++			die(_("--no-walk is incompatible with --unsorted-input"));
    ++
      		/*
    -@@ revision.c: static int handle_revision_pseudo_opt(const char *submodule,
    + 		 * Detached form ("--no-walk X" as opposed to "--no-walk=X")
      		 * not allowed, since the argument is optional.
    - 		 */
    - 		revs->no_walk = 1;
    --		if (!strcmp(optarg, "sorted"))
    -+		if (!strcmp(optarg, "sorted")) {
    -+			if (revs->unsorted_input)
    -+				die(_("--no-walk=sorted is incompatible with --no-walk=unsorted "
    -+				    "and --unsorted-input"));
    - 			revs->unsorted_input = 0;
    --		else if (!strcmp(optarg, "unsorted"))
    -+		} else if (!strcmp(optarg, "unsorted"))
    - 			revs->unsorted_input = 1;
    - 		else
    - 			return error("invalid argument to --no-walk");
     
      ## t/t6000-rev-list-misc.sh ##
     @@ t/t6000-rev-list-misc.sh: test_expect_success 'rev-list --count --objects' '
    @@ t/t6000-rev-list-misc.sh: test_expect_success 'rev-list --count --objects' '
     +	test_cmp first.sorted second.sorted
     +'
     +
    -+test_expect_success 'rev-list --unsorted-input compatible with --no-walk=unsorted' '
    -+	git rev-list --unsorted-input --no-walk=unsorted HEAD HEAD~ >actual &&
    -+	git rev-parse HEAD >expect &&
    -+	git rev-parse HEAD~ >>expect &&
    -+	test_cmp expect actual
    -+'
    -+
    -+test_expect_success 'rev-list --unsorted-input incompatible with --no-walk=sorted' '
    ++test_expect_success 'rev-list --unsorted-input incompatible with --no-walk' '
     +	cat >expect <<-EOF &&
    -+		fatal: --no-walk is incompatible with --no-walk=unsorted and --unsorted-input
    ++		fatal: --no-walk is incompatible with --unsorted-input
     +	EOF
     +	test_must_fail git rev-list --unsorted-input --no-walk HEAD 2>error &&
     +	test_cmp expect error &&
    -+
    -+	cat >expect <<-EOF &&
    -+		fatal: --no-walk=sorted is incompatible with --no-walk=unsorted and --unsorted-input
    -+	EOF
     +	test_must_fail git rev-list --unsorted-input --no-walk=sorted HEAD 2>error &&
     +	test_cmp expect error &&
    ++	test_must_fail git rev-list --unsorted-input --no-walk=unsorted HEAD 2>error &&
    ++	test_cmp expect error &&
     +
     +	cat >expect <<-EOF &&
    -+		fatal: --unsorted-input is incompatible with --no-walk and --no-walk=sorted
    ++		fatal: --unsorted-input is incompatible with --no-walk
     +	EOF
     +	test_must_fail git rev-list --no-walk --unsorted-input HEAD 2>error &&
     +	test_cmp expect error &&
     +	test_must_fail git rev-list --no-walk=sorted --unsorted-input HEAD 2>error &&
    ++	test_cmp expect error &&
    ++	test_must_fail git rev-list --no-walk=unsorted --unsorted-input HEAD 2>error &&
     +	test_cmp expect error
     +'
     +
3:  d8e63d0943 = 3:  c9a630927b revision: stop retrieving reference twice
4:  ba8df5cad0 < -:  ---------- revision: avoid loading object headers multiple times
5:  e33cd51ebf = 4:  bc89325fdf commit-graph: split out function to search commit position
6:  900c5a9c60 ! 5:  fdb1fa9d57 revision: avoid hitting packfiles when commits are in commit-graph
    @@ Metadata
      ## Commit message ##
         revision: avoid hitting packfiles when commits are in commit-graph
     
    -    When queueing references in git-rev-list(1), we try to either reuse an
    -    already parsed object or alternatively we load the object header from
    -    disk in order to determine its type. This is inefficient for commits
    -    though in cases where we have a commit graph available: instead of
    -    hitting the real object on disk to determine its type, we may instead
    -    search the object graph for the object ID. In case it's found, we can
    -    directly fill in the commit object, otherwise we can still hit the disk
    -    to determine the object's type.
    +    When queueing references in git-rev-list(1), we try to optimize parsing
    +    of commits via the commit-graph. To do so, we first look up the object's
    +    type, and if it is a commit we call `repo_parse_commit()` instead of
    +    `parse_object()`. This is quite inefficient though given that we're
    +    always uncompressing the object header in order to determine the type.
    +    Instead, we can opportunistically search the commit-graph for the object
    +    ID: in case it's found, we know it's a commit and can directly fill in
    +    the commit object without having to uncompress the object header.
     
    -    Expose a new function `parse_commit_in_graph_gently()`, which fills in
    -    an object of unknown type in case we find its object ID in the graph.
    -    This provides a big performance win in cases where there is a
    -    commit-graph available in the repository in case we load lots of
    -    references. The following has been executed in a real-world repository
    -    with about 2.2 million refs:
    +    Expose a new function `lookup_commit_in_graph()`, which tries to find a
    +    commit in the commit-graph by ID, and convert `get_reference()` to use
    +    this function. This provides a big performance win in cases where we
    +    load references in a repository with lots of references pointing to
    +    commits. The following has been executed in a real-world repository with
    +    about 2.2 million refs:
     
             Benchmark #1: HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev
    -          Time (mean ± σ):      4.508 s ±  0.039 s    [User: 4.131 s, System: 0.377 s]
    -          Range (min … max):    4.455 s …  4.576 s    10 runs
    +          Time (mean ± σ):      4.458 s ±  0.044 s    [User: 4.115 s, System: 0.342 s]
    +          Range (min … max):    4.409 s …  4.534 s    10 runs
     
             Benchmark #2: HEAD: rev-list --unsorted-input --objects --quiet --not --all --not $newrev
    -          Time (mean ± σ):      3.072 s ±  0.031 s    [User: 2.707 s, System: 0.365 s]
    -          Range (min … max):    3.040 s …  3.144 s    10 runs
    +          Time (mean ± σ):      3.089 s ±  0.015 s    [User: 2.768 s, System: 0.321 s]
    +          Range (min … max):    3.061 s …  3.105 s    10 runs
     
             Summary
               'HEAD: rev-list --unsorted-input --objects --quiet --not --all --not $newrev' ran
    -            1.47 ± 0.02 times faster than 'HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev'
    +            1.44 ± 0.02 times faster than 'HEAD~: rev-list --unsorted-input --objects --quiet --not --all --not $newrev'
     
         Signed-off-by: Patrick Steinhardt <ps@pks.im>
     
    @@ commit-graph.c: static int find_commit_pos_in_graph(struct commit *item, struct
      	}
      }
      
    -+int parse_commit_in_graph_gently(struct repository *repo, struct object *object)
    ++struct commit *lookup_commit_in_graph(struct repository *repo, const struct object_id *id)
     +{
     +	struct commit *commit;
     +	uint32_t pos;
     +
    -+	if (object->parsed) {
    -+		if (object->type != OBJ_COMMIT)
    -+			return -1;
    -+		return 0;
    -+	}
    -+
     +	if (!repo->objects->commit_graph)
    -+		return -1;
    ++		return NULL;
    ++	if (!search_commit_pos_in_graph(id, repo->objects->commit_graph, &pos))
    ++		return NULL;
    ++	if (!repo_has_object_file(repo, id))
    ++		return NULL;
     +
    -+	if (!search_commit_pos_in_graph(&object->oid, repo->objects->commit_graph, &pos))
    -+		return -1;
    -+
    -+	commit = object_as_type(object, OBJ_COMMIT, 1);
    ++	commit = lookup_commit(repo, id);
     +	if (!commit)
    -+		return -1;
    -+	if (!fill_commit_in_graph(repo, commit, repo->objects->commit_graph, pos))
    -+		return -1;
    ++		return NULL;
    ++	if (commit->object.parsed)
    ++		return commit;
     +
    -+	return 0;
    ++	if (!fill_commit_in_graph(repo, commit, repo->objects->commit_graph, pos))
    ++		return NULL;
    ++
    ++	return commit;
     +}
     +
      static int parse_commit_in_graph_one(struct repository *r,
    @@ commit-graph.h: int open_commit_graph(const char *graph_file, int *fd, struct st
      int parse_commit_in_graph(struct repository *r, struct commit *item);
      
     +/*
    -+ * Given an object of unknown type, try to fill in the object in case it is a
    -+ * commit part of the commit-graph. Returns 0 if the object is a parsed commit
    -+ * or if it could be filled in via the commit graph, otherwise it returns -1.
    ++ * Look up the given commit ID in the commit-graph. This will only return a
    ++ * commit if the ID exists both in the graph and in the object database such
    ++ * that we don't return commits whose object has been pruned. Otherwise, this
    ++ * function returns `NULL`.
     + */
    -+int parse_commit_in_graph_gently(struct repository *repo, struct object *object);
    ++struct commit *lookup_commit_in_graph(struct repository *repo, const struct object_id *id);
     +
      /*
       * It is possible that we loaded commit contents from the commit buffer,
    @@ commit-graph.h: int open_commit_graph(const char *graph_file, int *fd, struct st
     
      ## revision.c ##
     @@ revision.c: static struct object *get_reference(struct rev_info *revs, const char *name,
    - 	struct object *object = lookup_unknown_object(revs->repo, oid);
    + 				    unsigned int flags)
    + {
    + 	struct object *object;
    ++	struct commit *commit;
      
    - 	if (object->type == OBJ_NONE) {
    --		int type = oid_object_info(revs->repo, oid, NULL);
    --		if (type < 0 || !object_as_type(object, type, 1)) {
    -+		/*
    -+		 * It's likely that the reference points to a commit, so we
    -+		 * first try to look it up via the commit-graph. If successful,
    -+		 * then we know it's a commit and don't have to unpack the
    -+		 * object header. We still need to assert that the object
    -+		 * exists, but given that we don't request any info about the
    -+		 * object this is a lot faster than `oid_object_info()`.
    -+		 */
    -+		if (parse_commit_in_graph_gently(revs->repo, object) < 0) {
    -+			int type = oid_object_info(revs->repo, oid, NULL);
    -+			if (type < 0 || !object_as_type(object, type, 1)) {
    -+				object = NULL;
    -+				goto out;
    -+			}
    -+		} else if (!repo_has_object_file(revs->repo, oid)) {
    - 			object = NULL;
    - 			goto out;
    - 		}
    + 	/*
    +-	 * If the repository has commit graphs, repo_parse_commit() avoids
    +-	 * reading the object buffer, so use it whenever possible.
    ++	 * If the repository has commit graphs, we try to opportunistically
    ++	 * look up the object ID in those graphs. Like this, we can avoid
    ++	 * parsing commit data from disk.
    + 	 */
    +-	if (oid_object_info(revs->repo, oid, NULL) == OBJ_COMMIT) {
    +-		struct commit *c = lookup_commit(revs->repo, oid);
    +-		if (!repo_parse_commit(revs->repo, c))
    +-			object = (struct object *) c;
    +-		else
    +-			object = NULL;
    +-	} else {
    ++	commit = lookup_commit_in_graph(revs->repo, oid);
    ++	if (commit)
    ++		object = &commit->object;
    ++	else
    + 		object = parse_object(revs->repo, oid);
    +-	}
    + 
    + 	if (!object) {
    + 		if (revs->ignore_missing)
-- 
2.32.0


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v5 1/5] revision: separate walk and unsorted flags

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 3681 bytes --]

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.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 builtin/log.c    | 2 +-
 builtin/revert.c | 3 ++-
 revision.c       | 9 +++++----
 revision.h       | 7 ++-----
 4 files changed, 10 insertions(+), 11 deletions(-)

diff --git a/builtin/log.c b/builtin/log.c
index 3d7717ba5c..f75d87e8d7 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -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));
diff --git a/builtin/revert.c b/builtin/revert.c
index 237f2f18d4..2e13660e4b 100644
--- a/builtin/revert.c
+++ b/builtin/revert.c
@@ -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], "-"))
diff --git a/revision.c b/revision.c
index cddd0542a6..86bbcd10d2 100644
--- a/revision.c
+++ b/revision.c
@@ -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;
diff --git a/revision.h b/revision.h
index fbb068da9f..0c65a760ee 100644
--- a/revision.h
+++ b/revision.h
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v5 2/5] connected: do not sort input revisions

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 6655 bytes --]

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.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 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(-)

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 24569b06d1..b7bd27e171 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -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`.
diff --git a/connected.c b/connected.c
index b18299fdf0..b5f9523a5f 100644
--- a/connected.c
+++ b/connected.c
@@ -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;
diff --git a/revision.c b/revision.c
index 86bbcd10d2..47541407d2 100644
--- a/revision.c
+++ b/revision.c
@@ -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.
diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
index 12def7bcbf..ef849e5bc8 100755
--- a/t/t6000-rev-list-misc.sh
+++ b/t/t6000-rev-list-misc.sh
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v5 3/5] revision: stop retrieving reference twice

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 1944 bytes --]

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'

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 revision.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/revision.c b/revision.c
index 47541407d2..80a59896b9 100644
--- a/revision.c
+++ b/revision.c
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v5 4/5] commit-graph: split out function to search commit position

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 4561 bytes --]

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.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 commit-graph.c | 55 +++++++++++++++++++++++++++-----------------------
 1 file changed, 30 insertions(+), 25 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index 3860a0d847..8c4c7262c8 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v5 5/5] revision: avoid hitting packfiles when commits are in commit-graph

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 4772 bytes --]

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'

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 commit-graph.c | 24 ++++++++++++++++++++++++
 commit-graph.h |  8 ++++++++
 revision.c     | 18 ++++++++----------
 3 files changed, 40 insertions(+), 10 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index 8c4c7262c8..00614acd65 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -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)
diff --git a/commit-graph.h b/commit-graph.h
index 96c24fb577..04a94e1830 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -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
diff --git a/revision.c b/revision.c
index 80a59896b9..0dabb5a0bc 100644
--- a/revision.c
+++ b/revision.c
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]