[PATCH] refs: remove lookup cache for reference-transaction hook

[PATCH] refs: remove lookup cache for reference-transaction hook

[Patrick Steinhardt]

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

When adding the reference-transaction hook, there were concerns about
the performance impact it may have on setups which do not make use of
the new hook at all. After all, it gets executed every time a reftx is
prepared, committed or aborted, which linearly scales with the number of
reference-transactions created per session. And as there are code paths
like `git push` which create a new transaction for each reference to be
updated, this may translate to calling `find_hook()` quite a lot.

To address this concern, a cache was added with the intention to not
repeatedly do negative hook lookups. Turns out this cache caused a
regression, which was fixed via e5256c82e5 (refs: fix interleaving hook
calls with reference-transaction hook, 2020-08-07). In the process of
discussing the fix, we realized that the cache doesn't really help even
in the negative-lookup case. While performance tests added to benchmark
this did show a slight improvement in the 1% range, this really doesn't
warrent having a cache. Furthermore, it's quite flaky, too. E.g. running
it twice in succession produces the following results:

Test                         master            pks-reftx-hook-remove-cache
--------------------------------------------------------------------------
1400.2: update-ref           2.79(2.16+0.74)   2.73(2.12+0.71) -2.2%
1400.3: update-ref --stdin   0.22(0.08+0.14)   0.21(0.08+0.12) -4.5%

Test                         master            pks-reftx-hook-remove-cache
--------------------------------------------------------------------------
1400.2: update-ref           2.70(2.09+0.72)   2.74(2.13+0.71) +1.5%
1400.3: update-ref --stdin   0.21(0.10+0.10)   0.21(0.08+0.13) +0.0%

One case notably absent from those benchmarks is a single executable
searching for the hook hundreds of times, which is exactly the case for
which the negative cache was added. p1400.2 will spawn a new update-ref
for each transaction and p1400.3 only has a single reference-transaction
for all reference updates. So this commit adds a third benchmark, which
performs an non-atomic push of a thousand references. This will create a
new reference transaction per reference. But even for this case, the
negative cache doesn't consistently improve performance:

Test                         master            pks-reftx-hook-remove-cache
--------------------------------------------------------------------------
1400.4: nonatomic push       6.63(6.50+0.13)   6.81(6.67+0.14) +2.7%
1400.4: nonatomic push       6.35(6.21+0.14)   6.39(6.23+0.16) +0.6%
1400.4: nonatomic push       6.43(6.31+0.13)   6.42(6.28+0.15) -0.2%

So let's just remove the cache altogether to simplify the code.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 refs.c                     | 11 ++---------
 t/perf/p1400-update-ref.sh |  9 ++++++++-
 2 files changed, 10 insertions(+), 10 deletions(-)

diff --git a/refs.c b/refs.c
index cf91711968..cb9bfc5c5c 100644
--- a/refs.c
+++ b/refs.c
@@ -1924,24 +1924,17 @@ int ref_update_reject_duplicates(struct string_list *refnames,
 	return 0;
 }
 
-static const char hook_not_found;
-static const char *hook;
-
 static int run_transaction_hook(struct ref_transaction *transaction,
 				const char *state)
 {
 	struct child_process proc = CHILD_PROCESS_INIT;
 	struct strbuf buf = STRBUF_INIT;
+	const char *hook;
 	int ret = 0, i;
 
-	if (hook == &hook_not_found)
-		return ret;
+	hook = find_hook("reference-transaction");
 	if (!hook)
-		hook = xstrdup_or_null(find_hook("reference-transaction"));
-	if (!hook) {
-		hook = &hook_not_found;
 		return ret;
-	}
 
 	strvec_pushl(&proc.args, hook, state, NULL);
 	proc.in = -1;
diff --git a/t/perf/p1400-update-ref.sh b/t/perf/p1400-update-ref.sh
index d275a81248..5d6da3cb70 100755
--- a/t/perf/p1400-update-ref.sh
+++ b/t/perf/p1400-update-ref.sh
@@ -7,11 +7,13 @@ test_description="Tests performance of update-ref"
 test_perf_fresh_repo
 
 test_expect_success "setup" '
+	git init --bare target-repo.git &&
 	test_commit PRE &&
 	test_commit POST &&
 	printf "create refs/heads/%d PRE\n" $(test_seq 1000) >create &&
 	printf "update refs/heads/%d POST PRE\n" $(test_seq 1000) >update &&
-	printf "delete refs/heads/%d POST\n" $(test_seq 1000) >delete
+	printf "delete refs/heads/%d POST\n" $(test_seq 1000) >delete &&
+	printf "create refs/heads/branch-%d PRE\n" $(test_seq 1000) | git update-ref --stdin
 '
 
 test_perf "update-ref" '
@@ -29,4 +31,9 @@ test_perf "update-ref --stdin" '
 	git update-ref --stdin <delete
 '
 
+test_perf "nonatomic push" '
+	git push ./target-repo.git branch-{1..1000} &&
+	git push --delete ./target-repo.git branch-{1..1000}
+'
+
 test_done
-- 
2.28.0


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

Re: [PATCH] refs: remove lookup cache for reference-transaction hook

[Jeff King]

On Fri, Aug 21, 2020 at 10:29:18AM +0200, Patrick Steinhardt wrote:

> One case notably absent from those benchmarks is a single executable
> searching for the hook hundreds of times, which is exactly the case for
> which the negative cache was added. p1400.2 will spawn a new update-ref
> for each transaction and p1400.3 only has a single reference-transaction
> for all reference updates. So this commit adds a third benchmark, which
> performs an non-atomic push of a thousand references. This will create a
> new reference transaction per reference. But even for this case, the
> negative cache doesn't consistently improve performance:

Ah, right, I forgot that update-ref would use one single transaction. So
what we were testing in our earlier discussion was not even useful. :)

>  test_expect_success "setup" '
> +	git init --bare target-repo.git &&
>  	test_commit PRE &&
>  	test_commit POST &&
>  	printf "create refs/heads/%d PRE\n" $(test_seq 1000) >create &&
>  	printf "update refs/heads/%d POST PRE\n" $(test_seq 1000) >update &&
> -	printf "delete refs/heads/%d POST\n" $(test_seq 1000) >delete
> +	printf "delete refs/heads/%d POST\n" $(test_seq 1000) >delete &&
> +	printf "create refs/heads/branch-%d PRE\n" $(test_seq 1000) | git update-ref --stdin
>  '

OK, we need these new branches to have something to push into and delete
from the remote. They might impact the timings of the other tests,
though (since we now have 1000 entries in .git/refs/heads/, which might
affect filesystem performance). But it should do so uniformly, so I
don't think it invalidates their results.

However, I wondered...

> +test_perf "nonatomic push" '
> +	git push ./target-repo.git branch-{1..1000} &&
> +	git push --delete ./target-repo.git branch-{1..1000}
> +'

...if it might make the test more consistent (not to mention isolated
from the cost of other parts of the push) if we used update-ref here, as
well. You added the code necessary to control individual transactions,
so I thought that:

  printf 'start\ncreate refs/heads/%d PRE\ncommit\n' \
    $(test_seq 1000) >create-transaction

might work. But it doesn't, because after the first transaction is
closed, we refuse to accept any other commands. That makes sense for
"prepare", etc, but there's no reason we couldn't start a new one.

Is that worth supporting? It would allow a caller to use a single
update-ref to make a series of non-atomic updates, which is something
that can't currently be done. And we're so close.

Even if it is, though, that's definitely outside the scope of this
patch, and I think we should take it as-is with "push".

-Peff

Re: [PATCH] refs: remove lookup cache for reference-transaction hook

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> However, I wondered...
>
>> +test_perf "nonatomic push" '
>> +	git push ./target-repo.git branch-{1..1000} &&
>> +	git push --delete ./target-repo.git branch-{1..1000}
>> +'

Is this a bash-and-ksh-only test?  At least, the above would not try
to push 1000 branches with the version of dash I have.

Re: [PATCH] refs: remove lookup cache for reference-transaction hook

[Jeff King]

On Fri, Aug 21, 2020 at 09:42:45AM -0700, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > However, I wondered...
> >
> >> +test_perf "nonatomic push" '
> >> +	git push ./target-repo.git branch-{1..1000} &&
> >> +	git push --delete ./target-repo.git branch-{1..1000}
> >> +'
> 
> Is this a bash-and-ksh-only test?  At least, the above would not try
> to push 1000 branches with the version of dash I have.

Heh, I was so focused on the "push" part of it that I didn't even look
carefully at the second half of the command-line. ;)

I think pushing "refs/heads/branch-*" would work for pushing. For
deletion, though, I don't think we allow wildcards in the refspecs.
You could abuse pruning:

  git push --prune ../dst.git refs/heads/does-not-exist/*:refs/heads/*

It also may be OK to just omit that half of the test. I think the
initial push exercises the case we care about. Though I guess we do run
the test repeatedly, so we might have to do:

  rm -rf dst.git &&
  git init dst.git &&
  git push dst.git refs/heads/branch-*

-Peff

Re: [PATCH] refs: remove lookup cache for reference-transaction hook

[Patrick Steinhardt]

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

On Fri, Aug 21, 2020 at 01:21:37PM -0400, Jeff King wrote:
> On Fri, Aug 21, 2020 at 09:42:45AM -0700, Junio C Hamano wrote:
> 
> > Jeff King <peff@peff.net> writes:
> > 
> > > However, I wondered...
> > >
> > >> +test_perf "nonatomic push" '
> > >> +	git push ./target-repo.git branch-{1..1000} &&
> > >> +	git push --delete ./target-repo.git branch-{1..1000}
> > >> +'
> > 
> > Is this a bash-and-ksh-only test?  At least, the above would not try
> > to push 1000 branches with the version of dash I have.

I didn't realize it's shell-specific behaviour, thanks for highlighting.

> Heh, I was so focused on the "push" part of it that I didn't even look
> carefully at the second half of the command-line. ;)
> 
> I think pushing "refs/heads/branch-*" would work for pushing. For
> deletion, though, I don't think we allow wildcards in the refspecs.
> You could abuse pruning:
> 
>   git push --prune ../dst.git refs/heads/does-not-exist/*:refs/heads/*
> 
> It also may be OK to just omit that half of the test. I think the
> initial push exercises the case we care about. Though I guess we do run
> the test repeatedly, so we might have to do:
> 
>   rm -rf dst.git &&
>   git init dst.git &&
>   git push dst.git refs/heads/branch-*

I'm not too keen to use `rm -rf && git init` as it muddies the subject
under test a bit. I'll try to come up with a non-shell-specific version
of this on Monday.

Patrick

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

Re: [PATCH] refs: remove lookup cache for reference-transaction hook

[Patrick Steinhardt]

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

On Fri, Aug 21, 2020 at 10:37:27AM -0400, Jeff King wrote:
> On Fri, Aug 21, 2020 at 10:29:18AM +0200, Patrick Steinhardt wrote:
> 
> > One case notably absent from those benchmarks is a single executable
> > searching for the hook hundreds of times, which is exactly the case for
> > which the negative cache was added. p1400.2 will spawn a new update-ref
> > for each transaction and p1400.3 only has a single reference-transaction
> > for all reference updates. So this commit adds a third benchmark, which
> > performs an non-atomic push of a thousand references. This will create a
> > new reference transaction per reference. But even for this case, the
> > negative cache doesn't consistently improve performance:
> 
> Ah, right, I forgot that update-ref would use one single transaction. So
> what we were testing in our earlier discussion was not even useful. :)
> 
> >  test_expect_success "setup" '
> > +	git init --bare target-repo.git &&
> >  	test_commit PRE &&
> >  	test_commit POST &&
> >  	printf "create refs/heads/%d PRE\n" $(test_seq 1000) >create &&
> >  	printf "update refs/heads/%d POST PRE\n" $(test_seq 1000) >update &&
> > -	printf "delete refs/heads/%d POST\n" $(test_seq 1000) >delete
> > +	printf "delete refs/heads/%d POST\n" $(test_seq 1000) >delete &&
> > +	printf "create refs/heads/branch-%d PRE\n" $(test_seq 1000) | git update-ref --stdin
> >  '
> 
> OK, we need these new branches to have something to push into and delete
> from the remote. They might impact the timings of the other tests,
> though (since we now have 1000 entries in .git/refs/heads/, which might
> affect filesystem performance). But it should do so uniformly, so I
> don't think it invalidates their results.
> 
> However, I wondered...
> 
> > +test_perf "nonatomic push" '
> > +	git push ./target-repo.git branch-{1..1000} &&
> > +	git push --delete ./target-repo.git branch-{1..1000}
> > +'
> 
> ...if it might make the test more consistent (not to mention isolated
> from the cost of other parts of the push) if we used update-ref here, as
> well. You added the code necessary to control individual transactions,
> so I thought that:
> 
>   printf 'start\ncreate refs/heads/%d PRE\ncommit\n' \
>     $(test_seq 1000) >create-transaction
> 
> might work. But it doesn't, because after the first transaction is
> closed, we refuse to accept any other commands. That makes sense for
> "prepare", etc, but there's no reason we couldn't start a new one.
> 
> Is that worth supporting? It would allow a caller to use a single
> update-ref to make a series of non-atomic updates, which is something
> that can't currently be done. And we're so close.

Yeah, I had the exact same thought and I do think it's useful to be able
to create multiple reference transactions per git-update-ref(1) session.
I might whip something up as soon as I find the time to do so, it really
shouldn't be a lot of work.

Patrick

> Even if it is, though, that's definitely outside the scope of this
> patch, and I think we should take it as-is with "push".
> 
> -Peff

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

[PATCH v2] refs: remove lookup cache for reference-transaction hook

[Patrick Steinhardt]

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

When adding the reference-transaction hook, there were concerns about
the performance impact it may have on setups which do not make use of
the new hook at all. After all, it gets executed every time a reftx is
prepared, committed or aborted, which linearly scales with the number of
reference-transactions created per session. And as there are code paths
like `git push` which create a new transaction for each reference to be
updated, this may translate to calling `find_hook()` quite a lot.

To address this concern, a cache was added with the intention to not
repeatedly do negative hook lookups. Turns out this cache caused a
regression, which was fixed via e5256c82e5 (refs: fix interleaving hook
calls with reference-transaction hook, 2020-08-07). In the process of
discussing the fix, we realized that the cache doesn't really help even
in the negative-lookup case. While performance tests added to benchmark
this did show a slight improvement in the 1% range, this really doesn't
warrent having a cache. Furthermore, it's quite flaky, too. E.g. running
it twice in succession produces the following results:

Test                         master            pks-reftx-hook-remove-cache
--------------------------------------------------------------------------
1400.2: update-ref           2.79(2.16+0.74)   2.73(2.12+0.71) -2.2%
1400.3: update-ref --stdin   0.22(0.08+0.14)   0.21(0.08+0.12) -4.5%

Test                         master            pks-reftx-hook-remove-cache
--------------------------------------------------------------------------
1400.2: update-ref           2.70(2.09+0.72)   2.74(2.13+0.71) +1.5%
1400.3: update-ref --stdin   0.21(0.10+0.10)   0.21(0.08+0.13) +0.0%

One case notably absent from those benchmarks is a single executable
searching for the hook hundreds of times, which is exactly the case for
which the negative cache was added. p1400.2 will spawn a new update-ref
for each transaction and p1400.3 only has a single reference-transaction
for all reference updates. So this commit adds a third benchmark, which
performs an non-atomic push of a thousand references. This will create a
new reference transaction per reference. But even for this case, the
negative cache doesn't consistently improve performance:

Test                         master            pks-reftx-hook-remove-cache
--------------------------------------------------------------------------
1400.4: nonatomic push       6.63(6.50+0.13)   6.81(6.67+0.14) +2.7%
1400.4: nonatomic push       6.35(6.21+0.14)   6.39(6.23+0.16) +0.6%
1400.4: nonatomic push       6.43(6.31+0.13)   6.42(6.28+0.15) -0.2%

So let's just remove the cache altogether to simplify the code.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---

The only change compared to v1 is that I've addressed the unportable
`branch-{1..1000}` syntax in favor of `test_seq`. I had to setup refs as
part of the setup and change the ordering for "update-ref --stdin" from
create/update/delete to update/delete/create, but I don't think that's
too bad. At least timings didn't seem to really change because of that.

 refs.c                     | 11 ++---------
 t/perf/p1400-update-ref.sh | 13 ++++++++++---
 2 files changed, 12 insertions(+), 12 deletions(-)

diff --git a/refs.c b/refs.c
index cf91711968..cb9bfc5c5c 100644
--- a/refs.c
+++ b/refs.c
@@ -1924,24 +1924,17 @@ int ref_update_reject_duplicates(struct string_list *refnames,
 	return 0;
 }
 
-static const char hook_not_found;
-static const char *hook;
-
 static int run_transaction_hook(struct ref_transaction *transaction,
 				const char *state)
 {
 	struct child_process proc = CHILD_PROCESS_INIT;
 	struct strbuf buf = STRBUF_INIT;
+	const char *hook;
 	int ret = 0, i;
 
-	if (hook == &hook_not_found)
-		return ret;
+	hook = find_hook("reference-transaction");
 	if (!hook)
-		hook = xstrdup_or_null(find_hook("reference-transaction"));
-	if (!hook) {
-		hook = &hook_not_found;
 		return ret;
-	}
 
 	strvec_pushl(&proc.args, hook, state, NULL);
 	proc.in = -1;
diff --git a/t/perf/p1400-update-ref.sh b/t/perf/p1400-update-ref.sh
index d275a81248..ce5ac3ed85 100755
--- a/t/perf/p1400-update-ref.sh
+++ b/t/perf/p1400-update-ref.sh
@@ -7,11 +7,13 @@ test_description="Tests performance of update-ref"
 test_perf_fresh_repo
 
 test_expect_success "setup" '
+	git init --bare target-repo.git &&
 	test_commit PRE &&
 	test_commit POST &&
 	printf "create refs/heads/%d PRE\n" $(test_seq 1000) >create &&
 	printf "update refs/heads/%d POST PRE\n" $(test_seq 1000) >update &&
-	printf "delete refs/heads/%d POST\n" $(test_seq 1000) >delete
+	printf "delete refs/heads/%d POST\n" $(test_seq 1000) >delete &&
+	git update-ref --stdin <create
 '
 
 test_perf "update-ref" '
@@ -24,9 +26,14 @@ test_perf "update-ref" '
 '
 
 test_perf "update-ref --stdin" '
-	git update-ref --stdin <create &&
 	git update-ref --stdin <update &&
-	git update-ref --stdin <delete
+	git update-ref --stdin <delete &&
+	git update-ref --stdin <create
+'
+
+test_perf "nonatomic push" '
+	git push ./target-repo.git $(test_seq 1000) &&
+	git push --delete ./target-repo.git $(test_seq 1000)
 '
 
 test_done
-- 
2.28.0


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

Re: [PATCH v2] refs: remove lookup cache for reference-transaction hook

[Jeff King]

On Tue, Aug 25, 2020 at 12:35:24PM +0200, Patrick Steinhardt wrote:

> The only change compared to v1 is that I've addressed the unportable
> `branch-{1..1000}` syntax in favor of `test_seq`. I had to setup refs as
> part of the setup and change the ordering for "update-ref --stdin" from
> create/update/delete to update/delete/create, but I don't think that's
> too bad. At least timings didn't seem to really change because of that.

Another option instead of changing the order in the other tests is to do
another untimed setup step before the push test. I'm OK either way,
though.

> +test_perf "nonatomic push" '
> +	git push ./target-repo.git $(test_seq 1000) &&
> +	git push --delete ./target-repo.git $(test_seq 1000)
>  '

This works as far as Git is concerned, but "seq 1000" output with NULs
is 3893 bytes. I wonder if some platforms might run into command-line
limits there. I guess we will see when Windows CI runs. :)

-Peff

Re: [PATCH v2] refs: remove lookup cache for reference-transaction hook

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Tue, Aug 25, 2020 at 12:35:24PM +0200, Patrick Steinhardt wrote:
>
>> The only change compared to v1 is that I've addressed the unportable
>> `branch-{1..1000}` syntax in favor of `test_seq`. I had to setup refs as
>> part of the setup and change the ordering for "update-ref --stdin" from
>> create/update/delete to update/delete/create, but I don't think that's
>> too bad. At least timings didn't seem to really change because of that.
>
> Another option instead of changing the order in the other tests is to do
> another untimed setup step before the push test. I'm OK either way,
> though.
>
>> +test_perf "nonatomic push" '
>> +	git push ./target-repo.git $(test_seq 1000) &&
>> +	git push --delete ./target-repo.git $(test_seq 1000)
>>  '
>
> This works as far as Git is concerned, but "seq 1000" output with NULs
> is 3893 bytes. I wonder if some platforms might run into command-line
> limits there.

That was my thought when I saw the above as well.  In addition, I do
not think it is a good idea to encourage digit-only refnames.

Re: [PATCH v2] refs: remove lookup cache for reference-transaction hook

[Jeff King]

On Tue, Aug 25, 2020 at 11:09:54AM -0700, Junio C Hamano wrote:

> >> +test_perf "nonatomic push" '
> >> +	git push ./target-repo.git $(test_seq 1000) &&
> >> +	git push --delete ./target-repo.git $(test_seq 1000)
> >>  '
> >
> > This works as far as Git is concerned, but "seq 1000" output with NULs
> > is 3893 bytes. I wonder if some platforms might run into command-line
> > limits there.
> 
> That was my thought when I saw the above as well.  In addition, I do
> not think it is a good idea to encourage digit-only refnames.

Good point. It gets hairy at four digits:

  $ git show 1000
  error: short SHA1 1000 is ambiguous
  hint: The candidates are:
  hint:   10000434d2 tree
  hint:   10007bcb9e tree
  hint:   10008a0e22 tree
  hint:   1000bdf512 tree
  hint:   1000dc2368 blob
  fatal: ambiguous argument '1000': unknown revision or path not in the working tree.

So I think if the test works it may be relying on the exact object ids
that happen to be generated (which fortunately are at least
deterministic these days, but it may be a trap waiting to spring for
somebody later).

-Peff