[PATCH] sha1_name: don't resolve refs when core.warnambiguousrefs is false

[PATCH] sha1_name: don't resolve refs when core.warnambiguousrefs is false

[Brodie Rao]

This change ensures get_sha1_basic() doesn't try to resolve full hashes
as refs when ambiguous ref warnings are disabled.

This provides a substantial performance improvement when passing many
hashes to a command (like "git rev-list --stdin") when
core.warnambiguousrefs is false. The check incurs 6 stat()s for every
hash supplied, which can be costly over NFS.
---
 sha1_name.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/sha1_name.c b/sha1_name.c
index e9c2999..10bd007 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -451,9 +451,9 @@ static int get_sha1_basic(const char *str, int len, unsigned char *sha1)
 	int at, reflog_len, nth_prior = 0;
 
 	if (len == 40 && !get_sha1_hex(str, sha1)) {
-		if (warn_on_object_refname_ambiguity) {
+		if (warn_ambiguous_refs && warn_on_object_refname_ambiguity) {
 			refs_found = dwim_ref(str, len, tmp_sha1, &real_ref);
-			if (refs_found > 0 && warn_ambiguous_refs) {
+			if (refs_found > 0) {
 				warning(warn_msg, len, str);
 				if (advice_object_name_warning)
 					fprintf(stderr, "%s\n", _(object_name_msg));
-- 
1.8.3.4 (Apple Git-47)

Re: [PATCH] sha1_name: don't resolve refs when core.warnambiguousrefs is false

[Brodie Rao]

On Mon, Jan 6, 2014 at 7:32 PM, Brodie Rao <brodie@sf.io> wrote:
> This change ensures get_sha1_basic() doesn't try to resolve full hashes
> as refs when ambiguous ref warnings are disabled.
>
> This provides a substantial performance improvement when passing many
> hashes to a command (like "git rev-list --stdin") when
> core.warnambiguousrefs is false. The check incurs 6 stat()s for every
> hash supplied, which can be costly over NFS.

Forgot to add:

Signed-off-by: Brodie Rao <brodie@sf.io>

> ---
>  sha1_name.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/sha1_name.c b/sha1_name.c
> index e9c2999..10bd007 100644
> --- a/sha1_name.c
> +++ b/sha1_name.c
> @@ -451,9 +451,9 @@ static int get_sha1_basic(const char *str, int len, unsigned char *sha1)
>         int at, reflog_len, nth_prior = 0;
>
>         if (len == 40 && !get_sha1_hex(str, sha1)) {
> -               if (warn_on_object_refname_ambiguity) {
> +               if (warn_ambiguous_refs && warn_on_object_refname_ambiguity) {
>                         refs_found = dwim_ref(str, len, tmp_sha1, &real_ref);
> -                       if (refs_found > 0 && warn_ambiguous_refs) {
> +                       if (refs_found > 0) {
>                                 warning(warn_msg, len, str);
>                                 if (advice_object_name_warning)
>                                         fprintf(stderr, "%s\n", _(object_name_msg));
> --
> 1.8.3.4 (Apple Git-47)
>

Re: [PATCH] sha1_name: don't resolve refs when core.warnambiguousrefs is false

[Duy Nguyen]

On Tue, Jan 7, 2014 at 10:32 AM, Brodie Rao <brodie@sf.io> wrote:
> This change ensures get_sha1_basic() doesn't try to resolve full hashes
> as refs when ambiguous ref warnings are disabled.
>
> This provides a substantial performance improvement when passing many
> hashes to a command (like "git rev-list --stdin") when
> core.warnambiguousrefs is false. The check incurs 6 stat()s for every
> hash supplied, which can be costly over NFS.
> ---
>  sha1_name.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/sha1_name.c b/sha1_name.c
> index e9c2999..10bd007 100644
> --- a/sha1_name.c
> +++ b/sha1_name.c
> @@ -451,9 +451,9 @@ static int get_sha1_basic(const char *str, int len, unsigned char *sha1)
>         int at, reflog_len, nth_prior = 0;
>
>         if (len == 40 && !get_sha1_hex(str, sha1)) {
> -               if (warn_on_object_refname_ambiguity) {
> +               if (warn_ambiguous_refs && warn_on_object_refname_ambiguity) {
>                         refs_found = dwim_ref(str, len, tmp_sha1, &real_ref);
> -                       if (refs_found > 0 && warn_ambiguous_refs) {
> +                       if (refs_found > 0) {
>                                 warning(warn_msg, len, str);
>                                 if (advice_object_name_warning)
>                                         fprintf(stderr, "%s\n", _(object_name_msg));

Looks obviously correct. Thanks.
-- 
Duy

Re: [PATCH] sha1_name: don't resolve refs when core.warnambiguousrefs is false

[Jeff King]

On Mon, Jan 06, 2014 at 07:35:04PM -0800, Brodie Rao wrote:

> On Mon, Jan 6, 2014 at 7:32 PM, Brodie Rao <brodie@sf.io> wrote:
> > This change ensures get_sha1_basic() doesn't try to resolve full hashes
> > as refs when ambiguous ref warnings are disabled.
> >
> > This provides a substantial performance improvement when passing many
> > hashes to a command (like "git rev-list --stdin") when
> > core.warnambiguousrefs is false. The check incurs 6 stat()s for every
> > hash supplied, which can be costly over NFS.
> 
> Forgot to add:
> 
> Signed-off-by: Brodie Rao <brodie@sf.io>

Looks good to me.

I wonder if I should have simply gone this route instead of adding
warn_on_object_refname_ambiguity, and then people who want "cat-file
--batch" to be fast could just turn off core.warnAmbiguousRefs. I wanted
it to happen automatically, though. Alternatively, I guess "cat-file
--batch" could just turn off warn_ambiguous_refs itself.

-Peff

Re: [PATCH] sha1_name: don't resolve refs when core.warnambiguousrefs is false

[Junio C Hamano]

Brodie Rao <brodie@sf.io> writes:

> This change ensures get_sha1_basic() doesn't try to resolve full hashes
> as refs when ambiguous ref warnings are disabled.
>
> This provides a substantial performance improvement when passing many
> hashes to a command (like "git rev-list --stdin") when
> core.warnambiguousrefs is false. The check incurs 6 stat()s for every
> hash supplied, which can be costly over NFS.
> ---

Needs sign-off.  The patch looks good.

Thanks.

>  sha1_name.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/sha1_name.c b/sha1_name.c
> index e9c2999..10bd007 100644
> --- a/sha1_name.c
> +++ b/sha1_name.c
> @@ -451,9 +451,9 @@ static int get_sha1_basic(const char *str, int len, unsigned char *sha1)
>  	int at, reflog_len, nth_prior = 0;
>  
>  	if (len == 40 && !get_sha1_hex(str, sha1)) {
> -		if (warn_on_object_refname_ambiguity) {
> +		if (warn_ambiguous_refs && warn_on_object_refname_ambiguity) {
>  			refs_found = dwim_ref(str, len, tmp_sha1, &real_ref);
> -			if (refs_found > 0 && warn_ambiguous_refs) {
> +			if (refs_found > 0) {
>  				warning(warn_msg, len, str);
>  				if (advice_object_name_warning)
>  					fprintf(stderr, "%s\n", _(object_name_msg));

Re: [PATCH] sha1_name: don't resolve refs when core.warnambiguousrefs is false

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> Alternatively, I guess "cat-file
> --batch" could just turn off warn_ambiguous_refs itself.

Sounds like a sensible way to go, perhaps on top of this change?

Re: [PATCH] sha1_name: don't resolve refs when core.warnambiguousrefs is false

[Jeff King]

On Tue, Jan 07, 2014 at 09:51:07AM -0800, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > Alternatively, I guess "cat-file
> > --batch" could just turn off warn_ambiguous_refs itself.
> 
> Sounds like a sensible way to go, perhaps on top of this change?

The downside is that we would not warn about ambiguous refs anymore,
even if the user was expecting it to. I don't know if that matters much.
I kind of feel in the --batch situation that it is somewhat useless (I
wonder if "rev-list --stdin" should turn it off, too).

-Peff

[PATCH] sha1_name: don't resolve refs when core.warnambiguousrefs is false

[Brodie Rao]

This change ensures get_sha1_basic() doesn't try to resolve full hashes
as refs when ambiguous ref warnings are disabled.

This provides a substantial performance improvement when passing many
hashes to a command (like "git rev-list --stdin") when
core.warnambiguousrefs is false. The check incurs 6 stat()s for every
hash supplied, which can be costly over NFS.

Signed-off-by: Brodie Rao <brodie@sf.io>
---
 sha1_name.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/sha1_name.c b/sha1_name.c
index e9c2999..10bd007 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -451,9 +451,9 @@ static int get_sha1_basic(const char *str, int len, unsigned char *sha1)
 	int at, reflog_len, nth_prior = 0;
 
 	if (len == 40 && !get_sha1_hex(str, sha1)) {
-		if (warn_on_object_refname_ambiguity) {
+		if (warn_ambiguous_refs && warn_on_object_refname_ambiguity) {
 			refs_found = dwim_ref(str, len, tmp_sha1, &real_ref);
-			if (refs_found > 0 && warn_ambiguous_refs) {
+			if (refs_found > 0) {
 				warning(warn_msg, len, str);
 				if (advice_object_name_warning)
 					fprintf(stderr, "%s\n", _(object_name_msg));
-- 
1.8.5.2

Re: [PATCH] sha1_name: don't resolve refs when core.warnambiguousrefs is false

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Tue, Jan 07, 2014 at 09:51:07AM -0800, Junio C Hamano wrote:
>
>> Jeff King <peff@peff.net> writes:
>> 
>> > Alternatively, I guess "cat-file
>> > --batch" could just turn off warn_ambiguous_refs itself.
>> 
>> Sounds like a sensible way to go, perhaps on top of this change?
>
> The downside is that we would not warn about ambiguous refs anymore,
> even if the user was expecting it to. I don't know if that matters much.

That is true already with or without Brodie's change, isn't it?
With warn_on_object_refname_ambiguity, "cat-file --batch" makes us
ignore core.warnambigousrefs setting.  If we redo 25fba78d
(cat-file: disable object/refname ambiguity check for batch mode,
2013-07-12) to unconditionally disable warn_ambiguous_refs in
"cat-file --batch" and get rid of warn_on_object_refname_ambiguity,
the end result would be the same, no?

> I kind of feel in the --batch situation that it is somewhat useless (I
> wonder if "rev-list --stdin" should turn it off, too).

I think doing the same as "cat-file --batch" in "rev-list --stdin"
makes sense.  Both interfaces are designed to grok extended SHA-1s,
and full 40-hex object names could be ambiguous and we are missing
the warning for them.

Or are you wondering if we should revert 25fba78d, apply Brodie's
change to skip the ref resolution whose result is never used, and
tell people who want to use "cat-file --batch" (or "rev-list
--stdin") to disable the ambiguity warning themselves?

Re: [PATCH] sha1_name: don't resolve refs when core.warnambiguousrefs is false

[Jeff King]

On Tue, Jan 07, 2014 at 11:38:15AM -0800, Junio C Hamano wrote:

> >> > Alternatively, I guess "cat-file
> >> > --batch" could just turn off warn_ambiguous_refs itself.
> >> 
> >> Sounds like a sensible way to go, perhaps on top of this change?
> >
> > The downside is that we would not warn about ambiguous refs anymore,
> > even if the user was expecting it to. I don't know if that matters much.
> 
> That is true already with or without Brodie's change, isn't it?
> With warn_on_object_refname_ambiguity, "cat-file --batch" makes us
> ignore core.warnambigousrefs setting.  If we redo 25fba78d
> (cat-file: disable object/refname ambiguity check for batch mode,
> 2013-07-12) to unconditionally disable warn_ambiguous_refs in
> "cat-file --batch" and get rid of warn_on_object_refname_ambiguity,
> the end result would be the same, no?

No, I don't think the end effect is the same (or maybe we are not
talking about the same thing. :) ).

There are two ambiguity situations:

  1. Ambiguous non-fully-qualified refs (e.g., same tag and head name).

  2. 40-hex sha1 object names which might also be unqualified ref names.

Prior to 25ffba78d, cat-file checked both (like all the rest of git).
But checking (2) is very expensive, since otherwise a 40-hex sha1 does
not need to do a ref lookup at all, and something like "rev-list
--objects | cat-file --batch-check" processes a large number of these.

Detecting (1) is not nearly as expensive. You must already be doing a
ref lookup to trigger it (so the relative cost is much closer), and your
query size is bounded by the number of refs, not the number of objects.

Commit 25ffba78d traded off some safety for a lot of performance by
disabling (2), but left (1) in place because the tradeoff is different.

The two options I was musing over earlier today were (all on top of
Brodie's patch):

  a. Revert 25ffba78d. With Brodie's patch, core.warnAmbiguousRefs
     disables _both_ warnings. So we default to safe-but-slow, but
     people who care about performance can turn off ambiguity warnings.
     The downside is that you have to know to turn it off manually (and
     it's a global config flag, so you end up turning it off
     _everywhere_, not just in big queries where it matters).

  b. Revert 25ffba78d, but then on top of it just turn off
     warn_ambiguous_refs unconditionally in "cat-file --batch-check".
     The downside is that we drop the safety from (1). The upside is
     that the code is a little simpler, as we drop the extra flag.

And obviously:

  c. Just leave it at Brodie's patch with nothing else on top.

My thinking in favor of (b) was basically "does anybody actually care
about ambiguous refs in this situation anyway?". If they do, then I
think (c) is my preferred choice.

> > I kind of feel in the --batch situation that it is somewhat useless (I
> > wonder if "rev-list --stdin" should turn it off, too).
> 
> I think doing the same as "cat-file --batch" in "rev-list --stdin"
> makes sense.  Both interfaces are designed to grok extended SHA-1s,
> and full 40-hex object names could be ambiguous and we are missing
> the warning for them.

I'm not sure I understand what you are saying. We _do_ have the warning
for "rev-list --stdin" currently. We do _not_ have the warning for
"cat-file --batch", since my 25ffba78d. I was wondering if rev-list
should go the same way as 25ffba78d, for efficiency reasons (e.g., think
piping to "rev-list --no-walk --stdin").

> Or are you wondering if we should revert 25fba78d, apply Brodie's
> change to skip the ref resolution whose result is never used, and
> tell people who want to use "cat-file --batch" (or "rev-list
> --stdin") to disable the ambiguity warning themselves?

See above. :)

-Peff

Re: [PATCH] sha1_name: don't resolve refs when core.warnambiguousrefs is false

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Tue, Jan 07, 2014 at 11:38:15AM -0800, Junio C Hamano wrote:
>
>> >> > Alternatively, I guess "cat-file
>> >> > --batch" could just turn off warn_ambiguous_refs itself.
>> >> 
>> >> Sounds like a sensible way to go, perhaps on top of this change?
>> >
>> > The downside is that we would not warn about ambiguous refs anymore,
>> > even if the user was expecting it to. I don't know if that matters much.
>> 
>> That is true already with or without Brodie's change, isn't it?
>> With warn_on_object_refname_ambiguity, "cat-file --batch" makes us
>> ignore core.warnambigousrefs setting.  If we redo 25fba78d
>> (cat-file: disable object/refname ambiguity check for batch mode,
>> 2013-07-12) to unconditionally disable warn_ambiguous_refs in
>> "cat-file --batch" and get rid of warn_on_object_refname_ambiguity,
>> the end result would be the same, no?
>
> No, I don't think the end effect is the same (or maybe we are not
> talking about the same thing. :) ).
>
> There are two ambiguity situations:
>
>   1. Ambiguous non-fully-qualified refs (e.g., same tag and head name).
>
>   2. 40-hex sha1 object names which might also be unqualified ref names.
>
> Prior to 25ffba78d, cat-file checked both (like all the rest of git).
> But checking (2) is very expensive,...

Ahh, of course.  Sorry for forgetting about 1.

> The two options I was musing over earlier today were (all on top of
> Brodie's patch):
>
>   a. Revert 25ffba78d. With Brodie's patch, core.warnAmbiguousRefs
>      disables _both_ warnings. So we default to safe-but-slow, but
>      people who care about performance can turn off ambiguity warnings.
>      The downside is that you have to know to turn it off manually (and
>      it's a global config flag, so you end up turning it off
>      _everywhere_, not just in big queries where it matters).

Or "git -c core.warnambiguousrefs=false cat-file --batch", but I
think a more important point is that it is no longer automatic for
known-to-be-heavy operations, and I agree with you that it is a
downside.

>   b. Revert 25ffba78d, but then on top of it just turn off
>      warn_ambiguous_refs unconditionally in "cat-file --batch-check".
>      The downside is that we drop the safety from (1). The upside is
>      that the code is a little simpler, as we drop the extra flag.
>
> And obviously:
>
>   c. Just leave it at Brodie's patch with nothing else on top.
>
> My thinking in favor of (b) was basically "does anybody actually care
> about ambiguous refs in this situation anyway?". If they do, then I
> think (c) is my preferred choice.

OK.  I agree with that line of thinking.  Let's take it one step at
a time, i.e. do c. and also use warn_on_object_refname_ambiguity in
"rev-list --stdin" first and leave the simplification (i.e. b.) for
later.

>> > I kind of feel in the --batch situation that it is somewhat useless (I
>> > wonder if "rev-list --stdin" should turn it off, too).
>> 
>> I think doing the same as "cat-file --batch" in "rev-list --stdin"
>> makes sense.  Both interfaces are designed to grok extended SHA-1s,
>> and full 40-hex object names could be ambiguous and we are missing
>> the warning for them.
>
> I'm not sure I understand what you are saying. We _do_ have the warning
> for "rev-list --stdin" currently. We do _not_ have the warning for
> "cat-file --batch", since my 25ffba78d.

What I wanted to say was that we would be discarding the safety for
"rev-list --stdin" with the same argument as we did for "cat-file
--batch".  If the argument for the earlier "cat-file --batch" were
"this interface only takes raw 40-hex object names", then the
situation would have been different, but that is not the case.

> I was wondering if rev-list should go the same way as 25ffba78d,
> for efficiency reasons (e.g., think piping to "rev-list --no-walk
> --stdin").

Yes, and I was trying to agree with that, but apparently I failed
;-)

Re: [PATCH] sha1_name: don't resolve refs when core.warnambiguousrefs is false

[Jeff King]

On Tue, Jan 07, 2014 at 12:31:57PM -0800, Junio C Hamano wrote:

> >   c. Just leave it at Brodie's patch with nothing else on top.
> >
> > My thinking in favor of (b) was basically "does anybody actually care
> > about ambiguous refs in this situation anyway?". If they do, then I
> > think (c) is my preferred choice.
> 
> OK.  I agree with that line of thinking.  Let's take it one step at
> a time, i.e. do c. and also use warn_on_object_refname_ambiguity in
> "rev-list --stdin" first and leave the simplification (i.e. b.) for
> later.

Here's a series to do that. The first three are just cleanups I noticed
while looking at the problem.

While I was writing the commit messages, though, I had a thought. Maybe
we could simply do the check faster for the common case that most refs
do not look like object names? Right now we blindly call dwim_ref for
each get_sha1 call, which is the expensive part. If we instead just
loaded all of the refnames from the dwim_ref location (basically heads,
tags and the top-level of "refs/"), we could build an index of all of
the entries matching the 40-hex pattern. In 99% of cases, this would be
zero entries, and the check would collapse to a simple integer
comparison (and even if we did have one, it would be a simple binary
search in memory).

Our index is more racy than actually checking the filesystem, but I
don't think it matters here.

Anyway, here is the series I came up with, in the meantime. I can take a
quick peek at just making it faster, too.

  [1/4]: cat-file: refactor error handling of batch_objects
  [2/4]: cat-file: fix a minor memory leak in batch_objects
  [3/4]: cat-file: restore ambiguity warning flag in batch_objects
  [4/4]: revision: turn off object/refname ambiguity check for --stdin

-Peff

[PATCH 1/4] cat-file: refactor error handling of batch_objects

[Jeff King]

This just pulls the return value for the function out of the
inner loop, so we can break out of the loop rather than do
an early return. This will make it easier to put any cleanup
for the function in one place.

Signed-off-by: Jeff King <peff@peff.net>
---
Just making the subsequent diffs less noisy...

 builtin/cat-file.c | 11 +++++------
 1 file changed, 5 insertions(+), 6 deletions(-)

diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index f8288c8..971cdde 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -263,6 +263,7 @@ static int batch_objects(struct batch_options *opt)
 {
 	struct strbuf buf = STRBUF_INIT;
 	struct expand_data data;
+	int retval = 0;
 
 	if (!opt->format)
 		opt->format = "%(objectname) %(objecttype) %(objectsize)";
@@ -294,8 +295,6 @@ static int batch_objects(struct batch_options *opt)
 	warn_on_object_refname_ambiguity = 0;
 
 	while (strbuf_getline(&buf, stdin, '\n') != EOF) {
-		int error;
-
 		if (data.split_on_whitespace) {
 			/*
 			 * Split at first whitespace, tying off the beginning
@@ -310,12 +309,12 @@ static int batch_objects(struct batch_options *opt)
 			data.rest = p;
 		}
 
-		error = batch_one_object(buf.buf, opt, &data);
-		if (error)
-			return error;
+		retval = batch_one_object(buf.buf, opt, &data);
+		if (retval)
+			break;
 	}
 
-	return 0;
+	return retval;
 }
 
 static const char * const cat_file_usage[] = {
-- 
1.8.5.2.500.g8060133

[PATCH 2/4] cat-file: fix a minor memory leak in batch_objects

[Jeff King]

We should always have been freeing our strbuf, but doing so
consistently was annoying until the refactoring in the
previous patch.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/cat-file.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index 971cdde..ce79103 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -314,6 +314,7 @@ static int batch_objects(struct batch_options *opt)
 			break;
 	}
 
+	strbuf_release(&buf);
 	return retval;
 }
 
-- 
1.8.5.2.500.g8060133

[PATCH 3/4] cat-file: restore ambiguity warning flag in batch_objects

[Jeff King]

Since commit 25fba78, we turn off the object/refname
ambiguity warning using a global flag. However, we never
restore it. This doesn't really matter in the current code,
since the program generally exits immediately after the
function is done, but it's good code hygeine to clean up
after ourselves.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/cat-file.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index ce79103..c64e287 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -264,6 +264,7 @@ static int batch_objects(struct batch_options *opt)
 	struct strbuf buf = STRBUF_INIT;
 	struct expand_data data;
 	int retval = 0;
+	int save_warning = warn_on_object_refname_ambiguity;
 
 	if (!opt->format)
 		opt->format = "%(objectname) %(objecttype) %(objectsize)";
@@ -314,6 +315,7 @@ static int batch_objects(struct batch_options *opt)
 			break;
 	}
 
+	warn_on_object_refname_ambiguity = save_warning;
 	strbuf_release(&buf);
 	return retval;
 }
-- 
1.8.5.2.500.g8060133

[PATCH 4/4] revision: turn off object/refname ambiguity check for --stdin

[Jeff King]

We currently check that any 40-hex object name we receive is
not also a refname, and output a warning if this is the
case.  When "rev-list --stdin" is used to receive object
names, we may receive a large number of inputs, and the cost
of checking each name as a ref is relatively high.

Commit 25fba78d already dropped this warning for "cat-file
--batch-check". The same reasoning applies for "rev-list
--stdin". Let's disable the check in that instance.

Here are before and after numbers:

  $ git rev-list --all >commits

  [before]
  $ best-of-five -i commits ./git rev-list --stdin --no-walk --pretty=raw

  real    0m0.675s
  user    0m0.552s
  sys     0m0.120s

  [after]
  $ best-of-five -i commits ./git rev-list --stdin --no-walk --pretty=raw

  real    0m0.415s
  user    0m0.400s
  sys     0m0.012s

Signed-off-by: Jeff King <peff@peff.net>
---
Obviously we drop this one (and revert 25fba78d) if I can just make the
check faster.

 revision.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/revision.c b/revision.c
index a68fde6..87d04dd 100644
--- a/revision.c
+++ b/revision.c
@@ -1576,7 +1576,9 @@ static void read_revisions_from_stdin(struct rev_info *revs,
 {
 	struct strbuf sb;
 	int seen_dashdash = 0;
+	int save_warning = warn_on_object_refname_ambiguity;
 
+	warn_on_object_refname_ambiguity = 0;
 	strbuf_init(&sb, 1000);
 	while (strbuf_getwholeline(&sb, stdin, '\n') != EOF) {
 		int len = sb.len;
@@ -1595,6 +1597,7 @@ static void read_revisions_from_stdin(struct rev_info *revs,
 					REVARG_CANNOT_BE_FILENAME))
 			die("bad revision '%s'", sb.buf);
 	}
+	warn_on_object_refname_ambiguity = save_warning;
 	if (seen_dashdash)
 		read_pathspec_from_stdin(revs, &sb, prune);
 	strbuf_release(&sb);
-- 
1.8.5.2.500.g8060133

[PATCH v2] speeding up 40-hex ambiguity check

[Jeff King]

On Tue, Jan 07, 2014 at 05:08:56PM -0500, Jeff King wrote:

> > OK.  I agree with that line of thinking.  Let's take it one step at
> > a time, i.e. do c. and also use warn_on_object_refname_ambiguity in
> > "rev-list --stdin" first and leave the simplification (i.e. b.) for
> > later.
> 
> Here's a series to do that. The first three are just cleanups I noticed
> while looking at the problem.
> 
> While I was writing the commit messages, though, I had a thought. Maybe
> we could simply do the check faster for the common case that most refs
> do not look like object names? Right now we blindly call dwim_ref for
> each get_sha1 call, which is the expensive part. If we instead just
> loaded all of the refnames from the dwim_ref location (basically heads,
> tags and the top-level of "refs/"), we could build an index of all of
> the entries matching the 40-hex pattern. In 99% of cases, this would be
> zero entries, and the check would collapse to a simple integer
> comparison (and even if we did have one, it would be a simple binary
> search in memory).

That turned out very nicely, and I think we can drop the extra flag
entirely. Brodie's patch still makes sense, for people who do want to
turn off ambiguity warnings entirely (and I built on his patch, which
matters textually for 4 and 5, but it would be easy to rebase).

I'm cc-ing Michael, since it is his ref-traversal code I am butchering
in the 3rd patch. The first two are the unrelated cleanups from v1. They
are not necessary, but I do not see any reason not to include them.

  [1/5]: cat-file: refactor error handling of batch_objects
  [2/5]: cat-file: fix a minor memory leak in batch_objects
  [3/5]: refs: teach for_each_ref a flag to avoid recursion
  [4/5]: get_sha1: speed up ambiguous 40-hex test
  [5/5]: get_sha1: drop object/refname ambiguity flag

-Peff

[PATCH v2 1/5] cat-file: refactor error handling of batch_objects

[Jeff King]

This just pulls the return value for the function out of the
inner loop, so we can break out of the loop rather than do
an early return. This will make it easier to put any cleanup
for the function in one place.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/cat-file.c | 11 +++++------
 1 file changed, 5 insertions(+), 6 deletions(-)

diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index f8288c8..971cdde 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -263,6 +263,7 @@ static int batch_objects(struct batch_options *opt)
 {
 	struct strbuf buf = STRBUF_INIT;
 	struct expand_data data;
+	int retval = 0;
 
 	if (!opt->format)
 		opt->format = "%(objectname) %(objecttype) %(objectsize)";
@@ -294,8 +295,6 @@ static int batch_objects(struct batch_options *opt)
 	warn_on_object_refname_ambiguity = 0;
 
 	while (strbuf_getline(&buf, stdin, '\n') != EOF) {
-		int error;
-
 		if (data.split_on_whitespace) {
 			/*
 			 * Split at first whitespace, tying off the beginning
@@ -310,12 +309,12 @@ static int batch_objects(struct batch_options *opt)
 			data.rest = p;
 		}
 
-		error = batch_one_object(buf.buf, opt, &data);
-		if (error)
-			return error;
+		retval = batch_one_object(buf.buf, opt, &data);
+		if (retval)
+			break;
 	}
 
-	return 0;
+	return retval;
 }
 
 static const char * const cat_file_usage[] = {
-- 
1.8.5.2.500.g8060133

[PATCH v2 2/5] cat-file: fix a minor memory leak in batch_objects

[Jeff King]

We should always have been freeing our strbuf, but doing so
consistently was annoying until the refactoring in the
previous patch.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/cat-file.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index 971cdde..ce79103 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -314,6 +314,7 @@ static int batch_objects(struct batch_options *opt)
 			break;
 	}
 
+	strbuf_release(&buf);
 	return retval;
 }
 
-- 
1.8.5.2.500.g8060133

[PATCH v2 3/5] refs: teach for_each_ref a flag to avoid recursion

[Jeff King]

The normal for_each_ref traversal descends into
subdirectories, returning each ref it finds. However, in
some cases we may want to just iterate over the top-level of
a certain part of the tree.

The introduction of the "flags" option is a little
mysterious. We already have a "flags" option that gets stuck
in a callback struct and ends up interpreted in do_one_ref.
But the traversal itself does not currently have any flags,
and it needs to know about this new flag.

We _could_ introduce this as a completely separate flag
parameter. But instead, we simply put both flag types into a
single namespace, and make it available at both sites. This
is simple, and given that we do not have a proliferation of
flags (we have had exactly one until now), it is probably
sufficient.

Signed-off-by: Jeff King <peff@peff.net>
---
I think the flags thing is OK as explained above, but Michael may have a
different suggestion for refactoring.

 refs.c | 61 ++++++++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 38 insertions(+), 23 deletions(-)

diff --git a/refs.c b/refs.c
index 3926136..ca854d6 100644
--- a/refs.c
+++ b/refs.c
@@ -589,6 +589,8 @@ static void sort_ref_dir(struct ref_dir *dir)
 
 /* Include broken references in a do_for_each_ref*() iteration: */
 #define DO_FOR_EACH_INCLUDE_BROKEN 0x01
+/* Do not recurse into subdirs, just iterate at a single level. */
+#define DO_FOR_EACH_NO_RECURSE     0x02
 
 /*
  * Return true iff the reference described by entry can be resolved to
@@ -661,7 +663,8 @@ static int do_one_ref(struct ref_entry *entry, void *cb_data)
  * called for all references, including broken ones.
  */
 static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
-				    each_ref_entry_fn fn, void *cb_data)
+				    each_ref_entry_fn fn, void *cb_data,
+				    int flags)
 {
 	int i;
 	assert(dir->sorted == dir->nr);
@@ -669,9 +672,13 @@ static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
 		struct ref_entry *entry = dir->entries[i];
 		int retval;
 		if (entry->flag & REF_DIR) {
-			struct ref_dir *subdir = get_ref_dir(entry);
-			sort_ref_dir(subdir);
-			retval = do_for_each_entry_in_dir(subdir, 0, fn, cb_data);
+			if (flags & DO_FOR_EACH_NO_RECURSE) {
+				struct ref_dir *subdir = get_ref_dir(entry);
+				sort_ref_dir(subdir);
+				retval = do_for_each_entry_in_dir(subdir, 0,
+								  fn, cb_data,
+								  flags);
+			}
 		} else {
 			retval = fn(entry, cb_data);
 		}
@@ -691,7 +698,8 @@ static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
  */
 static int do_for_each_entry_in_dirs(struct ref_dir *dir1,
 				     struct ref_dir *dir2,
-				     each_ref_entry_fn fn, void *cb_data)
+				     each_ref_entry_fn fn, void *cb_data,
+				     int flags)
 {
 	int retval;
 	int i1 = 0, i2 = 0;
@@ -702,10 +710,12 @@ static int do_for_each_entry_in_dirs(struct ref_dir *dir1,
 		struct ref_entry *e1, *e2;
 		int cmp;
 		if (i1 == dir1->nr) {
-			return do_for_each_entry_in_dir(dir2, i2, fn, cb_data);
+			return do_for_each_entry_in_dir(dir2, i2, fn, cb_data,
+							flags);
 		}
 		if (i2 == dir2->nr) {
-			return do_for_each_entry_in_dir(dir1, i1, fn, cb_data);
+			return do_for_each_entry_in_dir(dir1, i1, fn, cb_data,
+							flags);
 		}
 		e1 = dir1->entries[i1];
 		e2 = dir2->entries[i2];
@@ -713,12 +723,15 @@ static int do_for_each_entry_in_dirs(struct ref_dir *dir1,
 		if (cmp == 0) {
 			if ((e1->flag & REF_DIR) && (e2->flag & REF_DIR)) {
 				/* Both are directories; descend them in parallel. */
-				struct ref_dir *subdir1 = get_ref_dir(e1);
-				struct ref_dir *subdir2 = get_ref_dir(e2);
-				sort_ref_dir(subdir1);
-				sort_ref_dir(subdir2);
-				retval = do_for_each_entry_in_dirs(
-						subdir1, subdir2, fn, cb_data);
+				if (!(flags & DO_FOR_EACH_NO_RECURSE)) {
+					struct ref_dir *subdir1 = get_ref_dir(e1);
+					struct ref_dir *subdir2 = get_ref_dir(e2);
+					sort_ref_dir(subdir1);
+					sort_ref_dir(subdir2);
+					retval = do_for_each_entry_in_dirs(
+							subdir1, subdir2,
+							fn, cb_data, flags);
+				}
 				i1++;
 				i2++;
 			} else if (!(e1->flag & REF_DIR) && !(e2->flag & REF_DIR)) {
@@ -743,7 +756,7 @@ static int do_for_each_entry_in_dirs(struct ref_dir *dir1,
 				struct ref_dir *subdir = get_ref_dir(e);
 				sort_ref_dir(subdir);
 				retval = do_for_each_entry_in_dir(
-						subdir, 0, fn, cb_data);
+						subdir, 0, fn, cb_data, flags);
 			} else {
 				retval = fn(e, cb_data);
 			}
@@ -817,7 +830,7 @@ static int is_refname_available(const char *refname, const char *oldrefname,
 	data.conflicting_refname = NULL;
 
 	sort_ref_dir(dir);
-	if (do_for_each_entry_in_dir(dir, 0, name_conflict_fn, &data)) {
+	if (do_for_each_entry_in_dir(dir, 0, name_conflict_fn, &data, 0)) {
 		error("'%s' exists; cannot create '%s'",
 		      data.conflicting_refname, refname);
 		return 0;
@@ -1651,7 +1664,8 @@ void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname)
  * 0.
  */
 static int do_for_each_entry(struct ref_cache *refs, const char *base,
-			     each_ref_entry_fn fn, void *cb_data)
+			     each_ref_entry_fn fn, void *cb_data,
+			     int flags)
 {
 	struct packed_ref_cache *packed_ref_cache;
 	struct ref_dir *loose_dir;
@@ -1684,15 +1698,15 @@ static int do_for_each_entry(struct ref_cache *refs, const char *base,
 		sort_ref_dir(packed_dir);
 		sort_ref_dir(loose_dir);
 		retval = do_for_each_entry_in_dirs(
-				packed_dir, loose_dir, fn, cb_data);
+				packed_dir, loose_dir, fn, cb_data, flags);
 	} else if (packed_dir) {
 		sort_ref_dir(packed_dir);
 		retval = do_for_each_entry_in_dir(
-				packed_dir, 0, fn, cb_data);
+				packed_dir, 0, fn, cb_data, flags);
 	} else if (loose_dir) {
 		sort_ref_dir(loose_dir);
 		retval = do_for_each_entry_in_dir(
-				loose_dir, 0, fn, cb_data);
+				loose_dir, 0, fn, cb_data, flags);
 	}
 
 	release_packed_ref_cache(packed_ref_cache);
@@ -1718,7 +1732,7 @@ static int do_for_each_ref(struct ref_cache *refs, const char *base,
 	data.fn = fn;
 	data.cb_data = cb_data;
 
-	return do_for_each_entry(refs, base, do_one_ref, &data);
+	return do_for_each_entry(refs, base, do_one_ref, &data, flags);
 }
 
 static int do_head_ref(const char *submodule, each_ref_fn fn, void *cb_data)
@@ -2200,7 +2214,7 @@ int commit_packed_refs(void)
 
 	do_for_each_entry_in_dir(get_packed_ref_dir(packed_ref_cache),
 				 0, write_packed_entry_fn,
-				 &packed_ref_cache->lock->fd);
+				 &packed_ref_cache->lock->fd, 0);
 	if (commit_lock_file(packed_ref_cache->lock))
 		error = -1;
 	packed_ref_cache->lock = NULL;
@@ -2345,7 +2359,7 @@ int pack_refs(unsigned int flags)
 	cbdata.packed_refs = get_packed_refs(&ref_cache);
 
 	do_for_each_entry_in_dir(get_loose_refs(&ref_cache), 0,
-				 pack_if_possible_fn, &cbdata);
+				 pack_if_possible_fn, &cbdata, 0);
 
 	if (commit_packed_refs())
 		die_errno("unable to overwrite old ref-pack file");
@@ -2447,7 +2461,8 @@ static int repack_without_refs(const char **refnames, int n)
 	}
 
 	/* Remove any other accumulated cruft */
-	do_for_each_entry_in_dir(packed, 0, curate_packed_ref_fn, &refs_to_delete);
+	do_for_each_entry_in_dir(packed, 0, curate_packed_ref_fn,
+				 &refs_to_delete, 0);
 	for_each_string_list_item(ref_to_delete, &refs_to_delete) {
 		if (remove_entry(packed, ref_to_delete->string) == -1)
 			die("internal error");
-- 
1.8.5.2.500.g8060133

[PATCH v2 4/5] get_sha1: speed up ambiguous 40-hex test

[Jeff King]

Since 798c35f (get_sha1: warn about full or short object
names that look like refs, 2013-05-29), a 40-hex sha1 causes
us to call dwim_ref on the result, on the off chance that we
have a matching ref. This can cause a noticeable slow-down
when there are a large number of objects.  E.g., on
linux.git:

  [baseline timing]
  $ best-of-five git rev-list --all --pretty=raw
  real    0m3.996s
  user    0m3.900s
  sys     0m0.100s

  [same thing, but calling get_sha1 on each commit from stdin]
  $ git rev-list --all >commits
  $ best-of-five -i commits git rev-list --stdin --pretty=raw
  real    0m7.862s
  user    0m6.108s
  sys     0m1.760s

The problem is that each call to dwim_ref individually stats
the possible refs in refs/heads, refs/tags, etc. In the
common case, there are no refs that look like sha1s at all.
We can therefore do the same check much faster by loading
all ambiguous-looking candidates once, and then checking our
index for each object.

This is technically more racy (somebody might create such a
ref after we build our index), but that's OK, as it's just a
warning (and we provide no guarantees about whether a
simultaneous process ran before or after the ref was created
anyway).

Here is the time after this patch, which implements the
strategy described above:

  $ best-of-five -i commits git rev-list --stdin --pretty=raw
  real    0m4.966s
  user    0m4.776s
  sys     0m0.192s

We still pay some price to read the commits from stdin, but
notice the system time is much lower, as we are avoiding
hundreds of thousands of stat() calls.

Signed-off-by: Jeff King <peff@peff.net>
---
I wanted to make the ref traversal as cheap as possible, hence the
NO_RECURSE flag I added. I thought INCLUDE_BROKEN used to not open up
the refs at all, but it looks like it does these days. I wonder if that
is worth changing or not.

 refs.c      | 47 +++++++++++++++++++++++++++++++++++++++++++++++
 refs.h      |  2 ++
 sha1_name.c |  4 +---
 3 files changed, 50 insertions(+), 3 deletions(-)

diff --git a/refs.c b/refs.c
index ca854d6..cddd871 100644
--- a/refs.c
+++ b/refs.c
@@ -4,6 +4,7 @@
 #include "tag.h"
 #include "dir.h"
 #include "string-list.h"
+#include "sha1-array.h"
 
 /*
  * Make sure "ref" is something reasonable to have under ".git/refs/";
@@ -2042,6 +2043,52 @@ int dwim_log(const char *str, int len, unsigned char *sha1, char **log)
 	return logs_found;
 }
 
+static int check_ambiguous_sha1_ref(const char *refname,
+				    const unsigned char *sha1,
+				    int flags,
+				    void *data)
+{
+	unsigned char tmp_sha1[20];
+	if (strlen(refname) == 40 && !get_sha1_hex(refname, tmp_sha1))
+		sha1_array_append(data, tmp_sha1);
+	return 0;
+}
+
+static void build_ambiguous_sha1_ref_index(struct sha1_array *idx)
+{
+	const char **rule;
+
+	for (rule = ref_rev_parse_rules; *rule; rule++) {
+		const char *prefix = *rule;
+		const char *end = strstr(prefix, "%.*s");
+		char *buf;
+
+		if (!end)
+			continue;
+
+		buf = xmemdupz(prefix, end - prefix);
+		do_for_each_ref(&ref_cache, buf, check_ambiguous_sha1_ref,
+				end - prefix,
+				DO_FOR_EACH_INCLUDE_BROKEN |
+				DO_FOR_EACH_NO_RECURSE,
+				idx);
+		free(buf);
+	}
+}
+
+int sha1_is_ambiguous_with_ref(const unsigned char *sha1)
+{
+	struct sha1_array idx = SHA1_ARRAY_INIT;
+	static int loaded;
+
+	if (!loaded) {
+		build_ambiguous_sha1_ref_index(&idx);
+		loaded = 1;
+	}
+
+	return sha1_array_lookup(&idx, sha1) >= 0;
+}
+
 static struct ref_lock *lock_ref_sha1_basic(const char *refname,
 					    const unsigned char *old_sha1,
 					    int flags, int *type_p)
diff --git a/refs.h b/refs.h
index 87a1a79..c7d5f89 100644
--- a/refs.h
+++ b/refs.h
@@ -229,4 +229,6 @@ int update_refs(const char *action, const struct ref_update **updates,
 extern int parse_hide_refs_config(const char *var, const char *value, const char *);
 extern int ref_is_hidden(const char *);
 
+int sha1_is_ambiguous_with_ref(const unsigned char *sha1);
+
 #endif /* REFS_H */
diff --git a/sha1_name.c b/sha1_name.c
index a5578f7..f83ecb7 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -452,13 +452,11 @@ static int get_sha1_basic(const char *str, int len, unsigned char *sha1)
 
 	if (len == 40 && !get_sha1_hex(str, sha1)) {
 		if (warn_ambiguous_refs && warn_on_object_refname_ambiguity) {
-			refs_found = dwim_ref(str, len, tmp_sha1, &real_ref);
-			if (refs_found > 0) {
+			if (sha1_is_ambiguous_with_ref(sha1)) {
 				warning(warn_msg, len, str);
 				if (advice_object_name_warning)
 					fprintf(stderr, "%s\n", _(object_name_msg));
 			}
-			free(real_ref);
 		}
 		return 0;
 	}
-- 
1.8.5.2.500.g8060133

[PATCH v2 5/5] get_sha1: drop object/refname ambiguity flag

[Jeff King]

Now that our object/refname ambiguity test is much faster
(thanks to the previous commit), there is no reason for code
like "cat-file --batch-check" to turn it off. Here are
before and after timings with this patch (on git.git):

  $ git rev-list --objects --all | cut -d' ' -f1 >objects

  [with flag]
  $ best-of-five -i objects ./git cat-file --batch-check
  real    0m0.392s
  user    0m0.368s
  sys     0m0.024s

  [without flag, without speedup; i.e., pre-25fba78]
  $ best-of-five -i objects ./git cat-file --batch-check
  real    0m1.652s
  user    0m0.904s
  sys     0m0.748s

  [without flag, with speedup]
  $ best-of-five -i objects ./git cat-file --batch-check
  real    0m0.388s
  user    0m0.356s
  sys     0m0.028s

So the new implementation does just as well as we did with
the flag turning the whole thing off (better actually, but
that is within the noise).

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/cat-file.c | 9 ---------
 cache.h            | 1 -
 environment.c      | 1 -
 sha1_name.c        | 2 +-
 4 files changed, 1 insertion(+), 12 deletions(-)

diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index ce79103..afba21f 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -285,15 +285,6 @@ static int batch_objects(struct batch_options *opt)
 	if (opt->print_contents)
 		data.info.typep = &data.type;
 
-	/*
-	 * We are going to call get_sha1 on a potentially very large number of
-	 * objects. In most large cases, these will be actual object sha1s. The
-	 * cost to double-check that each one is not also a ref (just so we can
-	 * warn) ends up dwarfing the actual cost of the object lookups
-	 * themselves. We can work around it by just turning off the warning.
-	 */
-	warn_on_object_refname_ambiguity = 0;
-
 	while (strbuf_getline(&buf, stdin, '\n') != EOF) {
 		if (data.split_on_whitespace) {
 			/*
diff --git a/cache.h b/cache.h
index ce377e1..73afc38 100644
--- a/cache.h
+++ b/cache.h
@@ -566,7 +566,6 @@ extern int assume_unchanged;
 extern int prefer_symlink_refs;
 extern int log_all_ref_updates;
 extern int warn_ambiguous_refs;
-extern int warn_on_object_refname_ambiguity;
 extern int shared_repository;
 extern const char *apply_default_whitespace;
 extern const char *apply_default_ignorewhitespace;
diff --git a/environment.c b/environment.c
index 3c76905..c59f6d4 100644
--- a/environment.c
+++ b/environment.c
@@ -22,7 +22,6 @@ int prefer_symlink_refs;
 int is_bare_repository_cfg = -1; /* unspecified */
 int log_all_ref_updates = -1; /* unspecified */
 int warn_ambiguous_refs = 1;
-int warn_on_object_refname_ambiguity = 1;
 int repository_format_version;
 const char *git_commit_encoding;
 const char *git_log_output_encoding;
diff --git a/sha1_name.c b/sha1_name.c
index f83ecb7..b9aaf74 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -451,7 +451,7 @@ static int get_sha1_basic(const char *str, int len, unsigned char *sha1)
 	int at, reflog_len, nth_prior = 0;
 
 	if (len == 40 && !get_sha1_hex(str, sha1)) {
-		if (warn_ambiguous_refs && warn_on_object_refname_ambiguity) {
+		if (warn_ambiguous_refs) {
 			if (sha1_is_ambiguous_with_ref(sha1)) {
 				warning(warn_msg, len, str);
 				if (advice_object_name_warning)
-- 
1.8.5.2.500.g8060133

[PATCH v3 3/5] refs: teach for_each_ref a flag to avoid recursion

[Jeff King]

On Tue, Jan 07, 2014 at 06:58:50PM -0500, Jeff King wrote:

> +			if (flags & DO_FOR_EACH_NO_RECURSE) {
> +				struct ref_dir *subdir = get_ref_dir(entry);
> +				sort_ref_dir(subdir);
> +				retval = do_for_each_entry_in_dir(subdir, 0,

Obviously this is totally wrong and inverts the point of the flag. And
causes something like half of the test suite to fail.

Michael was nice enough to point it out to me off-list, but well, I have
to face the brown paper bag at some point. :) In my defense, it was a
last minute refactor before going to dinner. That is what I get for
rushing out the series.

Here's a fixed version of patch 3/5.

-- >8 --
Subject: refs: teach for_each_ref a flag to avoid recursion

The normal for_each_ref traversal descends into
subdirectories, returning each ref it finds. However, in
some cases we may want to just iterate over the top-level of
a certain part of the tree.

The introduction of the "flags" option is a little
mysterious. We already have a "flags" option that gets stuck
in a callback struct and ends up interpreted in do_one_ref.
But the traversal itself does not currently have any flags,
and it needs to know about this new flag.

We _could_ introduce this as a completely separate flag
parameter. But instead, we simply put both flag types into a
single namespace, and make it available at both sites. This
is simple, and given that we do not have a proliferation of
flags (we have had exactly one until now), it is probably
sufficient.

Signed-off-by: Jeff King <peff@peff.net>
---
 refs.c | 61 ++++++++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 38 insertions(+), 23 deletions(-)

diff --git a/refs.c b/refs.c
index 3926136..b70b018 100644
--- a/refs.c
+++ b/refs.c
@@ -589,6 +589,8 @@ static void sort_ref_dir(struct ref_dir *dir)
 
 /* Include broken references in a do_for_each_ref*() iteration: */
 #define DO_FOR_EACH_INCLUDE_BROKEN 0x01
+/* Do not recurse into subdirs, just iterate at a single level. */
+#define DO_FOR_EACH_NO_RECURSE     0x02
 
 /*
  * Return true iff the reference described by entry can be resolved to
@@ -661,7 +663,8 @@ static int do_one_ref(struct ref_entry *entry, void *cb_data)
  * called for all references, including broken ones.
  */
 static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
-				    each_ref_entry_fn fn, void *cb_data)
+				    each_ref_entry_fn fn, void *cb_data,
+				    int flags)
 {
 	int i;
 	assert(dir->sorted == dir->nr);
@@ -669,9 +672,13 @@ static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
 		struct ref_entry *entry = dir->entries[i];
 		int retval;
 		if (entry->flag & REF_DIR) {
-			struct ref_dir *subdir = get_ref_dir(entry);
-			sort_ref_dir(subdir);
-			retval = do_for_each_entry_in_dir(subdir, 0, fn, cb_data);
+			if (!(flags & DO_FOR_EACH_NO_RECURSE)) {
+				struct ref_dir *subdir = get_ref_dir(entry);
+				sort_ref_dir(subdir);
+				retval = do_for_each_entry_in_dir(subdir, 0,
+								  fn, cb_data,
+								  flags);
+			}
 		} else {
 			retval = fn(entry, cb_data);
 		}
@@ -691,7 +698,8 @@ static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
  */
 static int do_for_each_entry_in_dirs(struct ref_dir *dir1,
 				     struct ref_dir *dir2,
-				     each_ref_entry_fn fn, void *cb_data)
+				     each_ref_entry_fn fn, void *cb_data,
+				     int flags)
 {
 	int retval;
 	int i1 = 0, i2 = 0;
@@ -702,10 +710,12 @@ static int do_for_each_entry_in_dirs(struct ref_dir *dir1,
 		struct ref_entry *e1, *e2;
 		int cmp;
 		if (i1 == dir1->nr) {
-			return do_for_each_entry_in_dir(dir2, i2, fn, cb_data);
+			return do_for_each_entry_in_dir(dir2, i2, fn, cb_data,
+							flags);
 		}
 		if (i2 == dir2->nr) {
-			return do_for_each_entry_in_dir(dir1, i1, fn, cb_data);
+			return do_for_each_entry_in_dir(dir1, i1, fn, cb_data,
+							flags);
 		}
 		e1 = dir1->entries[i1];
 		e2 = dir2->entries[i2];
@@ -713,12 +723,15 @@ static int do_for_each_entry_in_dirs(struct ref_dir *dir1,
 		if (cmp == 0) {
 			if ((e1->flag & REF_DIR) && (e2->flag & REF_DIR)) {
 				/* Both are directories; descend them in parallel. */
-				struct ref_dir *subdir1 = get_ref_dir(e1);
-				struct ref_dir *subdir2 = get_ref_dir(e2);
-				sort_ref_dir(subdir1);
-				sort_ref_dir(subdir2);
-				retval = do_for_each_entry_in_dirs(
-						subdir1, subdir2, fn, cb_data);
+				if (!(flags & DO_FOR_EACH_NO_RECURSE)) {
+					struct ref_dir *subdir1 = get_ref_dir(e1);
+					struct ref_dir *subdir2 = get_ref_dir(e2);
+					sort_ref_dir(subdir1);
+					sort_ref_dir(subdir2);
+					retval = do_for_each_entry_in_dirs(
+							subdir1, subdir2,
+							fn, cb_data, flags);
+				}
 				i1++;
 				i2++;
 			} else if (!(e1->flag & REF_DIR) && !(e2->flag & REF_DIR)) {
@@ -743,7 +756,7 @@ static int do_for_each_entry_in_dirs(struct ref_dir *dir1,
 				struct ref_dir *subdir = get_ref_dir(e);
 				sort_ref_dir(subdir);
 				retval = do_for_each_entry_in_dir(
-						subdir, 0, fn, cb_data);
+						subdir, 0, fn, cb_data, flags);
 			} else {
 				retval = fn(e, cb_data);
 			}
@@ -817,7 +830,7 @@ static int is_refname_available(const char *refname, const char *oldrefname,
 	data.conflicting_refname = NULL;
 
 	sort_ref_dir(dir);
-	if (do_for_each_entry_in_dir(dir, 0, name_conflict_fn, &data)) {
+	if (do_for_each_entry_in_dir(dir, 0, name_conflict_fn, &data, 0)) {
 		error("'%s' exists; cannot create '%s'",
 		      data.conflicting_refname, refname);
 		return 0;
@@ -1651,7 +1664,8 @@ void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname)
  * 0.
  */
 static int do_for_each_entry(struct ref_cache *refs, const char *base,
-			     each_ref_entry_fn fn, void *cb_data)
+			     each_ref_entry_fn fn, void *cb_data,
+			     int flags)
 {
 	struct packed_ref_cache *packed_ref_cache;
 	struct ref_dir *loose_dir;
@@ -1684,15 +1698,15 @@ static int do_for_each_entry(struct ref_cache *refs, const char *base,
 		sort_ref_dir(packed_dir);
 		sort_ref_dir(loose_dir);
 		retval = do_for_each_entry_in_dirs(
-				packed_dir, loose_dir, fn, cb_data);
+				packed_dir, loose_dir, fn, cb_data, flags);
 	} else if (packed_dir) {
 		sort_ref_dir(packed_dir);
 		retval = do_for_each_entry_in_dir(
-				packed_dir, 0, fn, cb_data);
+				packed_dir, 0, fn, cb_data, flags);
 	} else if (loose_dir) {
 		sort_ref_dir(loose_dir);
 		retval = do_for_each_entry_in_dir(
-				loose_dir, 0, fn, cb_data);
+				loose_dir, 0, fn, cb_data, flags);
 	}
 
 	release_packed_ref_cache(packed_ref_cache);
@@ -1718,7 +1732,7 @@ static int do_for_each_ref(struct ref_cache *refs, const char *base,
 	data.fn = fn;
 	data.cb_data = cb_data;
 
-	return do_for_each_entry(refs, base, do_one_ref, &data);
+	return do_for_each_entry(refs, base, do_one_ref, &data, flags);
 }
 
 static int do_head_ref(const char *submodule, each_ref_fn fn, void *cb_data)
@@ -2200,7 +2214,7 @@ int commit_packed_refs(void)
 
 	do_for_each_entry_in_dir(get_packed_ref_dir(packed_ref_cache),
 				 0, write_packed_entry_fn,
-				 &packed_ref_cache->lock->fd);
+				 &packed_ref_cache->lock->fd, 0);
 	if (commit_lock_file(packed_ref_cache->lock))
 		error = -1;
 	packed_ref_cache->lock = NULL;
@@ -2345,7 +2359,7 @@ int pack_refs(unsigned int flags)
 	cbdata.packed_refs = get_packed_refs(&ref_cache);
 
 	do_for_each_entry_in_dir(get_loose_refs(&ref_cache), 0,
-				 pack_if_possible_fn, &cbdata);
+				 pack_if_possible_fn, &cbdata, 0);
 
 	if (commit_packed_refs())
 		die_errno("unable to overwrite old ref-pack file");
@@ -2447,7 +2461,8 @@ static int repack_without_refs(const char **refnames, int n)
 	}
 
 	/* Remove any other accumulated cruft */
-	do_for_each_entry_in_dir(packed, 0, curate_packed_ref_fn, &refs_to_delete);
+	do_for_each_entry_in_dir(packed, 0, curate_packed_ref_fn,
+				 &refs_to_delete, 0);
 	for_each_string_list_item(ref_to_delete, &refs_to_delete) {
 		if (remove_entry(packed, ref_to_delete->string) == -1)
 			die("internal error");
-- 
1.8.5.2.500.g8060133

Re: [PATCH v3 3/5] refs: teach for_each_ref a flag to avoid recursion

[Jeff King]

On Tue, Jan 07, 2014 at 10:47:33PM -0500, Jeff King wrote:

> On Tue, Jan 07, 2014 at 06:58:50PM -0500, Jeff King wrote:
> 
> > +			if (flags & DO_FOR_EACH_NO_RECURSE) {
> > +				struct ref_dir *subdir = get_ref_dir(entry);
> > +				sort_ref_dir(subdir);
> > +				retval = do_for_each_entry_in_dir(subdir, 0,
> 
> Obviously this is totally wrong and inverts the point of the flag. And
> causes something like half of the test suite to fail.

And while we're on the subject of my mistakes...

The patch needs the fixup below to ensure that retval is always set,
even when we do not recurse.

I'll hold off on sending a full re-roll of the patch, in the extremely
unlikely event that there are other small errors to be fixed. :)

diff --git a/refs.c b/refs.c
index aafbae9..99c72d0 100644
--- a/refs.c
+++ b/refs.c
@@ -679,7 +679,8 @@ static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
 				retval = do_for_each_entry_in_dir(subdir, 0,
 								  fn, cb_data,
 								  flags);
-			}
+			} else
+				retval = 0;
 		} else {
 			retval = fn(entry, cb_data);
 		}
@@ -732,7 +733,8 @@ static int do_for_each_entry_in_dirs(struct ref_dir *dir1,
 					retval = do_for_each_entry_in_dirs(
 							subdir1, subdir2,
 							fn, cb_data, flags);
-				}
+				} else
+					retval = 0;
 				i1++;
 				i2++;
 			} else if (!(e1->flag & REF_DIR) && !(e2->flag & REF_DIR)) {

Re: [PATCH v3 3/5] refs: teach for_each_ref a flag to avoid recursion

[Michael Haggerty]

On 01/08/2014 04:47 AM, Jeff King wrote:
> On Tue, Jan 07, 2014 at 06:58:50PM -0500, Jeff King wrote:
> 
>> +			if (flags & DO_FOR_EACH_NO_RECURSE) {
>> +				struct ref_dir *subdir = get_ref_dir(entry);
>> +				sort_ref_dir(subdir);
>> +				retval = do_for_each_entry_in_dir(subdir, 0,
> 
> Obviously this is totally wrong and inverts the point of the flag. And
> causes something like half of the test suite to fail.
> 
> Michael was nice enough to point it out to me off-list, but well, I have
> to face the brown paper bag at some point. :) In my defense, it was a
> last minute refactor before going to dinner. That is what I get for
> rushing out the series.
> 
> Here's a fixed version of patch 3/5.

v2 4/5 doesn't apply cleanly on top of v3 3/5.  So I'm basing my review
on the branch you have at GitHub peff/git "jk/cat-file-warn-ambiguous";
I hope it is the same.

> -- >8 --
> Subject: refs: teach for_each_ref a flag to avoid recursion
> 
> The normal for_each_ref traversal descends into

You haven't changed any for_each_ref*() functions; you have only exposed
the DO_FOR_EACH_NO_RECURSE option to the (static) functions
for_each_entry*() and do_for_each_ref().  (This is part and parcel of
your decision not to expose the new functionality in the refs API.)
Please correct the line above.

> subdirectories, returning each ref it finds. However, in
> some cases we may want to just iterate over the top-level of
> a certain part of the tree.
> 
> The introduction of the "flags" option is a little
> mysterious. We already have a "flags" option that gets stuck
> in a callback struct and ends up interpreted in do_one_ref.
> But the traversal itself does not currently have any flags,
> and it needs to know about this new flag.
> 
> We _could_ introduce this as a completely separate flag
> parameter. But instead, we simply put both flag types into a
> single namespace, and make it available at both sites. This
> is simple, and given that we do not have a proliferation of
> flags (we have had exactly one until now), it is probably
> sufficient.
> 
> Signed-off-by: Jeff King <peff@peff.net>
> ---
>  refs.c | 61 ++++++++++++++++++++++++++++++++++++++-----------------------
>  1 file changed, 38 insertions(+), 23 deletions(-)
> 
> diff --git a/refs.c b/refs.c
> index 3926136..b70b018 100644
> --- a/refs.c
> +++ b/refs.c
> @@ -589,6 +589,8 @@ static void sort_ref_dir(struct ref_dir *dir)
>  
>  /* Include broken references in a do_for_each_ref*() iteration: */
>  #define DO_FOR_EACH_INCLUDE_BROKEN 0x01
> +/* Do not recurse into subdirs, just iterate at a single level. */
> +#define DO_FOR_EACH_NO_RECURSE     0x02
>  
>  /*
>   * Return true iff the reference described by entry can be resolved to
> @@ -661,7 +663,8 @@ static int do_one_ref(struct ref_entry *entry, void *cb_data)
>   * called for all references, including broken ones.
>   */
>  static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
> -				    each_ref_entry_fn fn, void *cb_data)
> +				    each_ref_entry_fn fn, void *cb_data,
> +				    int flags)
>  {
>  	int i;
>  	assert(dir->sorted == dir->nr);

Please update the docstring for this function, which still says that it
recurses without mentioning DO_FOR_EACH_NO_RECURSE.

> [...]
> @@ -817,7 +830,7 @@ static int is_refname_available(const char *refname, const char *oldrefname,
>  	data.conflicting_refname = NULL;
>  
>  	sort_ref_dir(dir);
> -	if (do_for_each_entry_in_dir(dir, 0, name_conflict_fn, &data)) {
> +	if (do_for_each_entry_in_dir(dir, 0, name_conflict_fn, &data, 0)) {
>  		error("'%s' exists; cannot create '%s'",
>  		      data.conflicting_refname, refname);
>  		return 0;
> @@ -1651,7 +1664,8 @@ void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname)
>   * 0.
>   */
>  static int do_for_each_entry(struct ref_cache *refs, const char *base,
> -			     each_ref_entry_fn fn, void *cb_data)
> +			     each_ref_entry_fn fn, void *cb_data,
> +			     int flags)
>  {
>  	struct packed_ref_cache *packed_ref_cache;
>  	struct ref_dir *loose_dir;

A few lines after this, do_for_each_entry() calls
prime_ref_dir(loose_dir) to ensure that all of the loose references that
will be iterated over are read before the packed-refs file is checked.
It seems to me that prime_ref_dir() should also get a flags parameter to
prevent it reading more loose references than necessary, something like
this:

====================================================================
diff --git a/refs.c b/refs.c
index b70b018..b8b7354 100644
--- a/refs.c
+++ b/refs.c
@@ -772,13 +772,13 @@ static int do_for_each_entry_in_dirs(struct
ref_dir *dir1,
  * through all of the sub-directories. We do not even need to care about
  * sorting, as traversal order does not matter to us.
  */
-static void prime_ref_dir(struct ref_dir *dir)
+static void prime_ref_dir(struct ref_dir *dir, int flags)
 {
 	int i;
 	for (i = 0; i < dir->nr; i++) {
 		struct ref_entry *entry = dir->entries[i];
-		if (entry->flag & REF_DIR)
-			prime_ref_dir(get_ref_dir(entry));
+		if (entry->flag & REF_DIR && !(flags & DO_FOR_EACH_NO_RECURSE))
+			prime_ref_dir(get_ref_dir(entry), flags);
 	}
 }
 /*
@@ -1685,7 +1685,7 @@ static int do_for_each_entry(struct ref_cache
*refs, const char *base,
 		loose_dir = find_containing_dir(loose_dir, base, 0);
 	}
 	if (loose_dir)
-		prime_ref_dir(loose_dir);
+		prime_ref_dir(loose_dir, flags);

 	packed_ref_cache = get_packed_ref_cache(refs);
 	acquire_packed_ref_cache(packed_ref_cache);

====================================================================

> [...]
> @@ -1718,7 +1732,7 @@ static int do_for_each_ref(struct ref_cache *refs, const char *base,
>  	data.fn = fn;
>  	data.cb_data = cb_data;
>  
> -	return do_for_each_entry(refs, base, do_one_ref, &data);
> +	return do_for_each_entry(refs, base, do_one_ref, &data, flags);
>  }
>  
>  static int do_head_ref(const char *submodule, each_ref_fn fn, void *cb_data)

This change makes the DO_FOR_EACH_NO_RECURSE option usable with
do_for_each_ref() (even though it is never in fact used).  It should
either be mentioned in the docstring or (if there is a reason not to
allow it) explicitly prohibited.

> [...]

The rest looks fine to me.

It would be possible to use your new flag to speed up
is_refname_available(), but it would be a little bit of work and I doubt
that is_refname_available() is ever a bottleneck.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

Re: [PATCH v2 4/5] get_sha1: speed up ambiguous 40-hex test

[Michael Haggerty]

On 01/08/2014 12:59 AM, Jeff King wrote:
> Since 798c35f (get_sha1: warn about full or short object
> names that look like refs, 2013-05-29), a 40-hex sha1 causes
> us to call dwim_ref on the result, on the off chance that we
> have a matching ref. This can cause a noticeable slow-down
> when there are a large number of objects.  E.g., on
> linux.git:
> 
>   [baseline timing]
>   $ best-of-five git rev-list --all --pretty=raw
>   real    0m3.996s
>   user    0m3.900s
>   sys     0m0.100s
> 
>   [same thing, but calling get_sha1 on each commit from stdin]
>   $ git rev-list --all >commits
>   $ best-of-five -i commits git rev-list --stdin --pretty=raw
>   real    0m7.862s
>   user    0m6.108s
>   sys     0m1.760s
> 
> The problem is that each call to dwim_ref individually stats
> the possible refs in refs/heads, refs/tags, etc. In the
> common case, there are no refs that look like sha1s at all.
> We can therefore do the same check much faster by loading
> all ambiguous-looking candidates once, and then checking our
> index for each object.
> 
> This is technically more racy (somebody might create such a
> ref after we build our index), but that's OK, as it's just a
> warning (and we provide no guarantees about whether a
> simultaneous process ran before or after the ref was created
> anyway).

It's not only racy WRT other processes.  If the current git process
would create a new reference, it wouldn't be reflected in the cache.

It's true that the main ref_cache doesn't invalidate itself
automatically either when a new reference is created, so it's not really
a fair complaint.  However, as we add places where the cache is
invalidated, it is easy to overlook this cache that is stuck in static
variables within a function definition and it is impossible to
invalidate it.  Might it not be better to attach the cache to the
ref_cache structure instead, and couple its lifetime to that object?

Alternatively, the cache could be created and managed on the caller
side, since the caller would know when the cache would have to be
invalidated.  Also, different callers are likely to have different
performance characteristics.  It is unlikely that the time to initialize
the cache will be amortized in most cases; in fact, "rev-list --stdin"
might be the *only* plausible use case.

Regarding the overall strategy: you gather all refnames that could be
confused with an SHA-1 into a sha1_array, then later look up SHA-1s in
the array to see if they are ambiguous.  This is a very special-case
optimization for SHA-1s.

I wonder whether another approach would gain almost the same amount of
performance but be more general.  We could change dwim_ref() (or a
version of it?) to read its data out of a ref_cache instead of going to
disk every time.  Then, at the cost of populating the relevant parts of
the ref_cache once, we would have fast dwim_ref() calls for all strings.

It's true that the lookups wouldn't be quite so fast--they would require
a few bisects per refname lookup (one for each level in the refname
hierarchy) and several refname lookups (one for each ref_rev_parse_rule)
for every dwim_ref() call, vs. a single bisect in your current design.
But this approach it would bring us most of the gain, it might
nevertheless be preferable.

> Here is the time after this patch, which implements the
> strategy described above:
> 
>   $ best-of-five -i commits git rev-list --stdin --pretty=raw
>   real    0m4.966s
>   user    0m4.776s
>   sys     0m0.192s
> 
> We still pay some price to read the commits from stdin, but
> notice the system time is much lower, as we are avoiding
> hundreds of thousands of stat() calls.
> 
> Signed-off-by: Jeff King <peff@peff.net>
> ---
> I wanted to make the ref traversal as cheap as possible, hence the
> NO_RECURSE flag I added. I thought INCLUDE_BROKEN used to not open up
> the refs at all, but it looks like it does these days. I wonder if that
> is worth changing or not.

What do you mean by "open up the refs"?  The loose reference files are
read when populating the cache.  (Was that ever different?)  But the
call to ref_resolves_to_object() in do_one_ref() is skipped when the
INCLUDE_BROKEN flag is used.

> 
>  refs.c      | 47 +++++++++++++++++++++++++++++++++++++++++++++++
>  refs.h      |  2 ++
>  sha1_name.c |  4 +---
>  3 files changed, 50 insertions(+), 3 deletions(-)
> 
> diff --git a/refs.c b/refs.c
> index ca854d6..cddd871 100644
> --- a/refs.c
> +++ b/refs.c
> @@ -4,6 +4,7 @@
>  #include "tag.h"
>  #include "dir.h"
>  #include "string-list.h"
> +#include "sha1-array.h"
>  
>  /*
>   * Make sure "ref" is something reasonable to have under ".git/refs/";
> @@ -2042,6 +2043,52 @@ int dwim_log(const char *str, int len, unsigned char *sha1, char **log)
>  	return logs_found;
>  }
>  
> +static int check_ambiguous_sha1_ref(const char *refname,
> +				    const unsigned char *sha1,
> +				    int flags,
> +				    void *data)
> +{
> +	unsigned char tmp_sha1[20];
> +	if (strlen(refname) == 40 && !get_sha1_hex(refname, tmp_sha1))
> +		sha1_array_append(data, tmp_sha1);
> +	return 0;
> +}
> +
> +static void build_ambiguous_sha1_ref_index(struct sha1_array *idx)
> +{
> +	const char **rule;
> +
> +	for (rule = ref_rev_parse_rules; *rule; rule++) {
> +		const char *prefix = *rule;
> +		const char *end = strstr(prefix, "%.*s");
> +		char *buf;
> +
> +		if (!end)
> +			continue;
> +
> +		buf = xmemdupz(prefix, end - prefix);
> +		do_for_each_ref(&ref_cache, buf, check_ambiguous_sha1_ref,
> +				end - prefix,
> +				DO_FOR_EACH_INCLUDE_BROKEN |
> +				DO_FOR_EACH_NO_RECURSE,
> +				idx);

This doesn't correctly handle the rule

	"refs/remotes/%.*s/HEAD"

We might be willing to accept this limitation, but it should at least be
mentioned somewhere.  OTOH if we want to handle this pattern as well, we
could do use a technique like that of shorten_unambiguous_ref().

> +		free(buf);
> +	}
> +}
> +
> +int sha1_is_ambiguous_with_ref(const unsigned char *sha1)
> +{
> +	struct sha1_array idx = SHA1_ARRAY_INIT;
> +	static int loaded;
> +
> +	if (!loaded) {
> +		build_ambiguous_sha1_ref_index(&idx);
> +		loaded = 1;
> +	}
> +
> +	return sha1_array_lookup(&idx, sha1) >= 0;
> +}
> +
>  static struct ref_lock *lock_ref_sha1_basic(const char *refname,
>  					    const unsigned char *old_sha1,
>  					    int flags, int *type_p)
> diff --git a/refs.h b/refs.h
> index 87a1a79..c7d5f89 100644
> --- a/refs.h
> +++ b/refs.h
> @@ -229,4 +229,6 @@ int update_refs(const char *action, const struct ref_update **updates,
>  extern int parse_hide_refs_config(const char *var, const char *value, const char *);
>  extern int ref_is_hidden(const char *);
>  
> +int sha1_is_ambiguous_with_ref(const unsigned char *sha1);
> +
>  #endif /* REFS_H */

Could we have a docstring, please?

> diff --git a/sha1_name.c b/sha1_name.c
> index a5578f7..f83ecb7 100644
> --- a/sha1_name.c
> +++ b/sha1_name.c
> @@ -452,13 +452,11 @@ static int get_sha1_basic(const char *str, int len, unsigned char *sha1)
>  
>  	if (len == 40 && !get_sha1_hex(str, sha1)) {
>  		if (warn_ambiguous_refs && warn_on_object_refname_ambiguity) {
> -			refs_found = dwim_ref(str, len, tmp_sha1, &real_ref);
> -			if (refs_found > 0) {
> +			if (sha1_is_ambiguous_with_ref(sha1)) {
>  				warning(warn_msg, len, str);
>  				if (advice_object_name_warning)
>  					fprintf(stderr, "%s\n", _(object_name_msg));
>  			}
> -			free(real_ref);
>  		}
>  		return 0;
>  	}
> 

Despite all my bellyaching, I think that your optimizing of these
lookups gives a nice speedup and I think that the approach that you took
is also OK.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

Re: [PATCH v2 5/5] get_sha1: drop object/refname ambiguity flag

[Michael Haggerty]

On 01/08/2014 01:00 AM, Jeff King wrote:
> Now that our object/refname ambiguity test is much faster
> (thanks to the previous commit), there is no reason for code
> like "cat-file --batch-check" to turn it off. Here are
> before and after timings with this patch (on git.git):
> 
>   $ git rev-list --objects --all | cut -d' ' -f1 >objects
> 
>   [with flag]
>   $ best-of-five -i objects ./git cat-file --batch-check
>   real    0m0.392s
>   user    0m0.368s
>   sys     0m0.024s
> 
>   [without flag, without speedup; i.e., pre-25fba78]
>   $ best-of-five -i objects ./git cat-file --batch-check
>   real    0m1.652s
>   user    0m0.904s
>   sys     0m0.748s
> 
>   [without flag, with speedup]
>   $ best-of-five -i objects ./git cat-file --batch-check
>   real    0m0.388s
>   user    0m0.356s
>   sys     0m0.028s
> 
> So the new implementation does just as well as we did with
> the flag turning the whole thing off (better actually, but
> that is within the noise).
> 
> Signed-off-by: Jeff King <peff@peff.net>
> [...]

Very nice.  Correctness without a performance hit.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

Re: [PATCH v3 3/5] refs: teach for_each_ref a flag to avoid recursion

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Tue, Jan 07, 2014 at 06:58:50PM -0500, Jeff King wrote:
>
>> +			if (flags & DO_FOR_EACH_NO_RECURSE) {
>> +				struct ref_dir *subdir = get_ref_dir(entry);
>> +				sort_ref_dir(subdir);
>> +				retval = do_for_each_entry_in_dir(subdir, 0,
>
> Obviously this is totally wrong and inverts the point of the flag. And
> causes something like half of the test suite to fail.
>
> Michael was nice enough to point it out to me off-list, but well, I have
> to face the brown paper bag at some point. :) In my defense, it was a
> last minute refactor before going to dinner. That is what I get for
> rushing out the series.

And perhaps a bad naming that calls for double-negation in the
normal cases, which might have been less likely to happen it the new
flag were called "onelevel only" or something, perhaps?

> Here's a fixed version of patch 3/5.
>
> -- >8 --
> Subject: refs: teach for_each_ref a flag to avoid recursion
>
> The normal for_each_ref traversal descends into
> subdirectories, returning each ref it finds. However, in
> some cases we may want to just iterate over the top-level of
> a certain part of the tree.
>
> The introduction of the "flags" option is a little
> mysterious. We already have a "flags" option that gets stuck
> in a callback struct and ends up interpreted in do_one_ref.
> But the traversal itself does not currently have any flags,
> and it needs to know about this new flag.
>
> We _could_ introduce this as a completely separate flag
> parameter. But instead, we simply put both flag types into a
> single namespace, and make it available at both sites. This
> is simple, and given that we do not have a proliferation of
> flags (we have had exactly one until now), it is probably
> sufficient.
>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
>  refs.c | 61 ++++++++++++++++++++++++++++++++++++++-----------------------
>  1 file changed, 38 insertions(+), 23 deletions(-)
>
> diff --git a/refs.c b/refs.c
> index 3926136..b70b018 100644
> --- a/refs.c
> +++ b/refs.c
> @@ -589,6 +589,8 @@ static void sort_ref_dir(struct ref_dir *dir)
>  
>  /* Include broken references in a do_for_each_ref*() iteration: */
>  #define DO_FOR_EACH_INCLUDE_BROKEN 0x01
> +/* Do not recurse into subdirs, just iterate at a single level. */
> +#define DO_FOR_EACH_NO_RECURSE     0x02
>  
>  /*
>   * Return true iff the reference described by entry can be resolved to
> @@ -661,7 +663,8 @@ static int do_one_ref(struct ref_entry *entry, void *cb_data)
>   * called for all references, including broken ones.
>   */
>  static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
> -				    each_ref_entry_fn fn, void *cb_data)
> +				    each_ref_entry_fn fn, void *cb_data,
> +				    int flags)
>  {
>  	int i;
>  	assert(dir->sorted == dir->nr);
> @@ -669,9 +672,13 @@ static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
>  		struct ref_entry *entry = dir->entries[i];
>  		int retval;
>  		if (entry->flag & REF_DIR) {
> -			struct ref_dir *subdir = get_ref_dir(entry);
> -			sort_ref_dir(subdir);
> -			retval = do_for_each_entry_in_dir(subdir, 0, fn, cb_data);
> +			if (!(flags & DO_FOR_EACH_NO_RECURSE)) {
> +				struct ref_dir *subdir = get_ref_dir(entry);
> +				sort_ref_dir(subdir);
> +				retval = do_for_each_entry_in_dir(subdir, 0,
> +								  fn, cb_data,
> +								  flags);
> +			}
>  		} else {
>  			retval = fn(entry, cb_data);
>  		}
> @@ -691,7 +698,8 @@ static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
>   */
>  static int do_for_each_entry_in_dirs(struct ref_dir *dir1,
>  				     struct ref_dir *dir2,
> -				     each_ref_entry_fn fn, void *cb_data)
> +				     each_ref_entry_fn fn, void *cb_data,
> +				     int flags)
>  {
>  	int retval;
>  	int i1 = 0, i2 = 0;
> @@ -702,10 +710,12 @@ static int do_for_each_entry_in_dirs(struct ref_dir *dir1,
>  		struct ref_entry *e1, *e2;
>  		int cmp;
>  		if (i1 == dir1->nr) {
> -			return do_for_each_entry_in_dir(dir2, i2, fn, cb_data);
> +			return do_for_each_entry_in_dir(dir2, i2, fn, cb_data,
> +							flags);
>  		}
>  		if (i2 == dir2->nr) {
> -			return do_for_each_entry_in_dir(dir1, i1, fn, cb_data);
> +			return do_for_each_entry_in_dir(dir1, i1, fn, cb_data,
> +							flags);
>  		}
>  		e1 = dir1->entries[i1];
>  		e2 = dir2->entries[i2];
> @@ -713,12 +723,15 @@ static int do_for_each_entry_in_dirs(struct ref_dir *dir1,
>  		if (cmp == 0) {
>  			if ((e1->flag & REF_DIR) && (e2->flag & REF_DIR)) {
>  				/* Both are directories; descend them in parallel. */
> -				struct ref_dir *subdir1 = get_ref_dir(e1);
> -				struct ref_dir *subdir2 = get_ref_dir(e2);
> -				sort_ref_dir(subdir1);
> -				sort_ref_dir(subdir2);
> -				retval = do_for_each_entry_in_dirs(
> -						subdir1, subdir2, fn, cb_data);
> +				if (!(flags & DO_FOR_EACH_NO_RECURSE)) {
> +					struct ref_dir *subdir1 = get_ref_dir(e1);
> +					struct ref_dir *subdir2 = get_ref_dir(e2);
> +					sort_ref_dir(subdir1);
> +					sort_ref_dir(subdir2);
> +					retval = do_for_each_entry_in_dirs(
> +							subdir1, subdir2,
> +							fn, cb_data, flags);
> +				}
>  				i1++;
>  				i2++;
>  			} else if (!(e1->flag & REF_DIR) && !(e2->flag & REF_DIR)) {
> @@ -743,7 +756,7 @@ static int do_for_each_entry_in_dirs(struct ref_dir *dir1,
>  				struct ref_dir *subdir = get_ref_dir(e);
>  				sort_ref_dir(subdir);
>  				retval = do_for_each_entry_in_dir(
> -						subdir, 0, fn, cb_data);
> +						subdir, 0, fn, cb_data, flags);
>  			} else {
>  				retval = fn(e, cb_data);
>  			}
> @@ -817,7 +830,7 @@ static int is_refname_available(const char *refname, const char *oldrefname,
>  	data.conflicting_refname = NULL;
>  
>  	sort_ref_dir(dir);
> -	if (do_for_each_entry_in_dir(dir, 0, name_conflict_fn, &data)) {
> +	if (do_for_each_entry_in_dir(dir, 0, name_conflict_fn, &data, 0)) {
>  		error("'%s' exists; cannot create '%s'",
>  		      data.conflicting_refname, refname);
>  		return 0;
> @@ -1651,7 +1664,8 @@ void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname)
>   * 0.
>   */
>  static int do_for_each_entry(struct ref_cache *refs, const char *base,
> -			     each_ref_entry_fn fn, void *cb_data)
> +			     each_ref_entry_fn fn, void *cb_data,
> +			     int flags)
>  {
>  	struct packed_ref_cache *packed_ref_cache;
>  	struct ref_dir *loose_dir;
> @@ -1684,15 +1698,15 @@ static int do_for_each_entry(struct ref_cache *refs, const char *base,
>  		sort_ref_dir(packed_dir);
>  		sort_ref_dir(loose_dir);
>  		retval = do_for_each_entry_in_dirs(
> -				packed_dir, loose_dir, fn, cb_data);
> +				packed_dir, loose_dir, fn, cb_data, flags);
>  	} else if (packed_dir) {
>  		sort_ref_dir(packed_dir);
>  		retval = do_for_each_entry_in_dir(
> -				packed_dir, 0, fn, cb_data);
> +				packed_dir, 0, fn, cb_data, flags);
>  	} else if (loose_dir) {
>  		sort_ref_dir(loose_dir);
>  		retval = do_for_each_entry_in_dir(
> -				loose_dir, 0, fn, cb_data);
> +				loose_dir, 0, fn, cb_data, flags);
>  	}
>  
>  	release_packed_ref_cache(packed_ref_cache);
> @@ -1718,7 +1732,7 @@ static int do_for_each_ref(struct ref_cache *refs, const char *base,
>  	data.fn = fn;
>  	data.cb_data = cb_data;
>  
> -	return do_for_each_entry(refs, base, do_one_ref, &data);
> +	return do_for_each_entry(refs, base, do_one_ref, &data, flags);
>  }
>  
>  static int do_head_ref(const char *submodule, each_ref_fn fn, void *cb_data)
> @@ -2200,7 +2214,7 @@ int commit_packed_refs(void)
>  
>  	do_for_each_entry_in_dir(get_packed_ref_dir(packed_ref_cache),
>  				 0, write_packed_entry_fn,
> -				 &packed_ref_cache->lock->fd);
> +				 &packed_ref_cache->lock->fd, 0);
>  	if (commit_lock_file(packed_ref_cache->lock))
>  		error = -1;
>  	packed_ref_cache->lock = NULL;
> @@ -2345,7 +2359,7 @@ int pack_refs(unsigned int flags)
>  	cbdata.packed_refs = get_packed_refs(&ref_cache);
>  
>  	do_for_each_entry_in_dir(get_loose_refs(&ref_cache), 0,
> -				 pack_if_possible_fn, &cbdata);
> +				 pack_if_possible_fn, &cbdata, 0);
>  
>  	if (commit_packed_refs())
>  		die_errno("unable to overwrite old ref-pack file");
> @@ -2447,7 +2461,8 @@ static int repack_without_refs(const char **refnames, int n)
>  	}
>  
>  	/* Remove any other accumulated cruft */
> -	do_for_each_entry_in_dir(packed, 0, curate_packed_ref_fn, &refs_to_delete);
> +	do_for_each_entry_in_dir(packed, 0, curate_packed_ref_fn,
> +				 &refs_to_delete, 0);
>  	for_each_string_list_item(ref_to_delete, &refs_to_delete) {
>  		if (remove_entry(packed, ref_to_delete->string) == -1)
>  			die("internal error");

Re: [PATCH v2 4/5] get_sha1: speed up ambiguous 40-hex test

[Junio C Hamano]

Michael Haggerty <mhagger@alum.mit.edu> writes:

> It's not only racy WRT other processes.  If the current git process
> would create a new reference, it wouldn't be reflected in the cache.
>
> It's true that the main ref_cache doesn't invalidate itself
> automatically either when a new reference is created, so it's not really
> a fair complaint.  However, as we add places where the cache is
> invalidated, it is easy to overlook this cache that is stuck in static
> variables within a function definition and it is impossible to
> invalidate it.  Might it not be better to attach the cache to the
> ref_cache structure instead, and couple its lifetime to that object?
>
> Alternatively, the cache could be created and managed on the caller
> side, since the caller would know when the cache would have to be
> invalidated.  Also, different callers are likely to have different
> performance characteristics.  It is unlikely that the time to initialize
> the cache will be amortized in most cases; in fact, "rev-list --stdin"
> might be the *only* plausible use case.

True.

> Regarding the overall strategy: you gather all refnames that could be
> confused with an SHA-1 into a sha1_array, then later look up SHA-1s in
> the array to see if they are ambiguous.  This is a very special-case
> optimization for SHA-1s.
>
> I wonder whether another approach would gain almost the same amount of
> performance but be more general.  We could change dwim_ref() (or a
> version of it?) to read its data out of a ref_cache instead of going to
> disk every time.  Then, at the cost of populating the relevant parts of
> the ref_cache once, we would have fast dwim_ref() calls for all strings.

If opendir-readdir to grab only the names (but not values) of many
refs is a lot faster than stat-open-read a handful of dwim-ref
locations for a given name, that optimization might be worthwhile,
but I think that requires an update to read_loose_refs() not to
read_ref_full() and the users of refs API to instead lazily resolve
the refs, no?

If I ask for five names (say 'maint', 'master', 'next', 'pu',
'jch'), the current code will do 5 dwim_ref()s, each of which will
consult 6 locations with resolve_ref_unsafe(), totalling 30 calls to
resolve_ref_unsafe(), each of which in turn is essentially an open
followed by either an return on ENOENT or a read.  So 30 opens and 5
reads in total.

With your lazy ref_cache scheme, instead we would enumerate all the
loose ones in the same 6 directories (e.g. refs/tags/, refs/heads),
so 6 opendir()s with as many readdir()s as I have loose refs, plus
we open-read them in read_loose_refs() called from get_ref_dir()
with the current ref_cache code.  For me, "find .git/refs/heads"
gives 500+ lines of output, which suggests that using the ref_cache
mechanism for dwim_ref() may not be a huge win, unless it is updated
to be extremely lazy, and readdir()s turns out to be extremely less
heavier than open-read.  Also it is unlikely that the cost to
initialize the cache is amortized to be a net win unless we are
dealing with tons of dwim_ref()s.

Re: [PATCH v3 3/5] refs: teach for_each_ref a flag to avoid recursion

[Jeff King]

On Wed, Jan 08, 2014 at 12:29:51PM +0100, Michael Haggerty wrote:

> > Here's a fixed version of patch 3/5.
> 
> v2 4/5 doesn't apply cleanly on top of v3 3/5.  So I'm basing my review
> on the branch you have at GitHub peff/git "jk/cat-file-warn-ambiguous";
> I hope it is the same.

Hrmph. I didn't have to do any conflict resolution during the rebase, so
I would think it would apply at least with "am -3".

> > -- >8 --
> > Subject: refs: teach for_each_ref a flag to avoid recursion
> > 
> > The normal for_each_ref traversal descends into
> 
> You haven't changed any for_each_ref*() functions; you have only exposed
> the DO_FOR_EACH_NO_RECURSE option to the (static) functions
> for_each_entry*() and do_for_each_ref().  (This is part and parcel of
> your decision not to expose the new functionality in the refs API.)
> Please correct the line above.

Will do, and I'll add a note on not exposing it (basically because there
is not an existing "flags" parameter in the public API, and nobody needs
it).

> >  static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
> > -				    each_ref_entry_fn fn, void *cb_data)
> > +				    each_ref_entry_fn fn, void *cb_data,
> > +				    int flags)
> >  {
> >  	int i;
> >  	assert(dir->sorted == dir->nr);
> 
> Please update the docstring for this function, which still says that it
> recurses without mentioning DO_FOR_EACH_NO_RECURSE.

Will do (and for the _in_dirs variant).

> >  static int do_for_each_entry(struct ref_cache *refs, const char *base,
> > -			     each_ref_entry_fn fn, void *cb_data)
> > +			     each_ref_entry_fn fn, void *cb_data,
> > +			     int flags)
> >  {
> >  	struct packed_ref_cache *packed_ref_cache;
> >  	struct ref_dir *loose_dir;
> 
> A few lines after this, do_for_each_entry() calls
> prime_ref_dir(loose_dir) to ensure that all of the loose references that
> will be iterated over are read before the packed-refs file is checked.
> It seems to me that prime_ref_dir() should also get a flags parameter to
> prevent it reading more loose references than necessary, something like
> this:

Hmm. I hadn't considered that, but yeah, it definitely nullifies part of
the purpose of the optimization.

However, is it safe to prime only part of the loose ref namespace? The
point of that priming is to avoid the race fixed in 98eeb09, which
depends on us caching the loose refs before the packed refs. But when we
read packed-refs, we will be reading and storing _all_ of it, even if we
do not touch it in this traversal. So it does not affect the race for
this traversal, but have we setup a cache situation where a subsequent
for_each_ref in the same process would be subject to the race?

I'm starting to wonder if this optimization is worth it.

> > [...]
> > @@ -1718,7 +1732,7 @@ static int do_for_each_ref(struct ref_cache *refs, const char *base,
> >  	data.fn = fn;
> >  	data.cb_data = cb_data;
> >  
> > -	return do_for_each_entry(refs, base, do_one_ref, &data);
> > +	return do_for_each_entry(refs, base, do_one_ref, &data, flags);
> >  }
> 
> This change makes the DO_FOR_EACH_NO_RECURSE option usable with
> do_for_each_ref() (even though it is never in fact used).  It should
> either be mentioned in the docstring or (if there is a reason not to
> allow it) explicitly prohibited.

Hrm, yeah. I guess there are no callers, and there is no plan for any.
So we could just pass "0" here, and then "flags" passed to
do_for_each_ref really is _just_ for the callback data that goes to
do_one_ref. That clears up the weird "combined namespace" stuff I
mentioned in the commit message, and is a bit cleaner. I'll take it in
that direction.

> It would be possible to use your new flag to speed up
> is_refname_available(), but it would be a little bit of work and I doubt
> that is_refname_available() is ever a bottleneck.

Yeah, agreed on both counts.

-Peff

Re: [PATCH v3 3/5] refs: teach for_each_ref a flag to avoid recursion

[Jeff King]

On Thu, Jan 09, 2014 at 09:51:24AM -0800, Junio C Hamano wrote:

> > On Tue, Jan 07, 2014 at 06:58:50PM -0500, Jeff King wrote:
> >
> >> +			if (flags & DO_FOR_EACH_NO_RECURSE) {
> >> +				struct ref_dir *subdir = get_ref_dir(entry);
> >> +				sort_ref_dir(subdir);
> >> +				retval = do_for_each_entry_in_dir(subdir, 0,
> >
> > Obviously this is totally wrong and inverts the point of the flag. And
> > causes something like half of the test suite to fail.
> >
> > Michael was nice enough to point it out to me off-list, but well, I have
> > to face the brown paper bag at some point. :) In my defense, it was a
> > last minute refactor before going to dinner. That is what I get for
> > rushing out the series.
> 
> And perhaps a bad naming that calls for double-negation in the
> normal cases, which might have been less likely to happen it the new
> flag were called "onelevel only" or something, perhaps?

That may be a nicer name, but it was not the problem here. The problem
here is that I wrote:

  if (flags & DO_FOR_EACH_NO_RECURSE == 0)

to avoid the extra layer of parentheses, but of course that doesn't
work. And then when I switched it back, I screwed up the reversion.

I think the nicest way to write it would be to avoid negation at all,
as:

  if (flags & DO_FOR_EACH_RECURSE) {
     ... do the recursion ...

but that means flipping the default, requiring us to set the flag
explicitly in the existing callers (though there really aren't that
many).

-Peff

Re: [PATCH v3 3/5] refs: teach for_each_ref a flag to avoid recursion

[Michael Haggerty]

On 01/09/2014 10:49 PM, Jeff King wrote:
> On Wed, Jan 08, 2014 at 12:29:51PM +0100, Michael Haggerty wrote:
> 
>>> Here's a fixed version of patch 3/5.
>>
>> v2 4/5 doesn't apply cleanly on top of v3 3/5.  So I'm basing my review
>> on the branch you have at GitHub peff/git "jk/cat-file-warn-ambiguous";
>> I hope it is the same.
> 
> Hrmph. I didn't have to do any conflict resolution during the rebase, so
> I would think it would apply at least with "am -3".

That may be; I didn't try with "-3".

> [...]
>>>  static int do_for_each_entry(struct ref_cache *refs, const char *base,
>>> -			     each_ref_entry_fn fn, void *cb_data)
>>> +			     each_ref_entry_fn fn, void *cb_data,
>>> +			     int flags)
>>>  {
>>>  	struct packed_ref_cache *packed_ref_cache;
>>>  	struct ref_dir *loose_dir;
>>
>> A few lines after this, do_for_each_entry() calls
>> prime_ref_dir(loose_dir) to ensure that all of the loose references that
>> will be iterated over are read before the packed-refs file is checked.
>> It seems to me that prime_ref_dir() should also get a flags parameter to
>> prevent it reading more loose references than necessary, something like
>> this:
> 
> Hmm. I hadn't considered that, but yeah, it definitely nullifies part of
> the purpose of the optimization.
> 
> However, is it safe to prime only part of the loose ref namespace? The
> point of that priming is to avoid the race fixed in 98eeb09, which
> depends on us caching the loose refs before the packed refs. But when we
> read packed-refs, we will be reading and storing _all_ of it, even if we
> do not touch it in this traversal. So it does not affect the race for
> this traversal, but have we setup a cache situation where a subsequent
> for_each_ref in the same process would be subject to the race?

prime_ref_dir() is called by do_for_each_entry(), which all the
iteration functions pass through.  It is always called before the
iteration starts, and it primes only the subtree of the refs hierarchy
that is being iterated over.  For example, if iterating over
"refs/heads" then it only primes references with that prefix.

This is OK, because if later somebody iterates over a broader part of
the refs hierarchy (say, "refs"), then priming is done again, including
re-checking the packed refs.  If the packed-refs file was changed
between the iterations, then the first iteration (if it is still
running) continues using the old packed-refs cache while the second
iteration uses the new packed-refs cache.  (So the first iteration will
have a stale, but self-consistent, view of the references.)

If do_for_each_entry() gets the DO_FOR_EACH_NO_RECURSE option, then it
knows that it will only traverse one level of the refs hierarchy.  So if
it passes the option to prime_ref_dir(), then the same level will be
primed.  If somebody later iterates over the same part of the hierarchy
without DO_FOR_EACH_NO_RECURSE, they will re-prime without
DO_FOR_EACH_NO_RECURSE then, if the packed-refs file has been changed,
load a new version of it.  So they will also get a self-consistent view
of the references and I think everything will be OK.

> I'm starting to wonder if this optimization is worth it.

It's true that this is quite a special-case optimization.

I think reference handling will have to move in the direction of
transactions, to remove one or two known race conditions.  That is why I
described the alternative of having the DWIM function do its lookups in
a ref cache.  It would move in the direction of consciously taking a
snapshot of the ref tree and using it for a whole "transaction", which I
think is a style that we will want to use in more places.  It's just
hard to judge whether this alternative would actually solve the
performance problem that you were originally trying to address--a point
that Junio discussed elsewhere in this thread.

(This is something I would be willing to work on if you feel like I am
pushing you to enlarge the scope of your work beyond what you are
interested in.)

>>> [...]
>>> @@ -1718,7 +1732,7 @@ static int do_for_each_ref(struct ref_cache *refs, const char *base,
>>>  	data.fn = fn;
>>>  	data.cb_data = cb_data;
>>>  
>>> -	return do_for_each_entry(refs, base, do_one_ref, &data);
>>> +	return do_for_each_entry(refs, base, do_one_ref, &data, flags);
>>>  }
>>
>> This change makes the DO_FOR_EACH_NO_RECURSE option usable with
>> do_for_each_ref() (even though it is never in fact used).  It should
>> either be mentioned in the docstring or (if there is a reason not to
>> allow it) explicitly prohibited.
> 
> Hrm, yeah. I guess there are no callers, and there is no plan for any.
> So we could just pass "0" here, and then "flags" passed to
> do_for_each_ref really is _just_ for the callback data that goes to
> do_one_ref. That clears up the weird "combined namespace" stuff I
> mentioned in the commit message, and is a bit cleaner. I'll take it in
> that direction.

It would also be possible to swing in the other direction.  I don't
remember a particular reason why I left the DO_FOR_EACH_INCLUDE_BROKEN
handling at the do_for_each_ref() level rather than handling it at the
do_for_each_entry() level.  But now that you are passing the flags
parameter all the way down the call stack, it wouldn't cost anything to
support both of the DO_FOR_EACH flags everywhere and just document it
that way.

> [...]

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

Re: [PATCH v3 3/5] refs: teach for_each_ref a flag to avoid recursion

[Jeff King]

On Fri, Jan 10, 2014 at 09:59:25AM +0100, Michael Haggerty wrote:

> > However, is it safe to prime only part of the loose ref namespace?
> [...]
> 
> prime_ref_dir() is called by do_for_each_entry(), which all the
> iteration functions pass through.  It is always called before the
> iteration starts, and it primes only the subtree of the refs hierarchy
> that is being iterated over.  For example, if iterating over
> "refs/heads" then it only primes references with that prefix.
> 
> This is OK, because if later somebody iterates over a broader part of
> the refs hierarchy (say, "refs"), then priming is done again, including
> re-checking the packed refs.

Ah, right. This is the part I was forgetting: the next for_each_ref will
re-prime with the expanded view. Thanks for a dose of sanity.

I'll fix that in my re-roll.

> It would also be possible to swing in the other direction.  I don't
> remember a particular reason why I left the DO_FOR_EACH_INCLUDE_BROKEN
> handling at the do_for_each_ref() level rather than handling it at the
> do_for_each_entry() level.  But now that you are passing the flags
> parameter all the way down the call stack, it wouldn't cost anything to
> support both of the DO_FOR_EACH flags everywhere and just document it
> that way.

I think it was simply that it was an option that the traversal did not
need to know about (just like the "trim" option), so you kept it as
encapsulated as possible. I think I'll introduce it as a separate flag
namespace, as discussed in the previous email. It is the same amount of
refactoring work to merge them later as it is now, if we so choose.

-Peff

Re: [PATCH v2 4/5] get_sha1: speed up ambiguous 40-hex test

[Jeff King]

On Wed, Jan 08, 2014 at 05:09:25PM +0100, Michael Haggerty wrote:

> It's not only racy WRT other processes.  If the current git process
> would create a new reference, it wouldn't be reflected in the cache.
> 
> It's true that the main ref_cache doesn't invalidate itself
> automatically either when a new reference is created, so it's not really
> a fair complaint.  However, as we add places where the cache is
> invalidated, it is easy to overlook this cache that is stuck in static
> variables within a function definition and it is impossible to
> invalidate it.  Might it not be better to attach the cache to the
> ref_cache structure instead, and couple its lifetime to that object?

Yeah, I noticed that we don't ever invalidate the loose ref cache. I
think that's mostly fine, as we rely on resolve_ref to cover the cases
that need to be ordered properly. And in this particular case, it's
"only" a warning (and a rather obscure one, at that), so I think the
stakes are low.

That being said, it should not be hard at all to attach the cache to the
ref_cache. Since we are generated from that cache, the lifetimes should
be the same.

> Alternatively, the cache could be created and managed on the caller
> side, since the caller would know when the cache would have to be
> invalidated.  Also, different callers are likely to have different
> performance characteristics.  It is unlikely that the time to initialize
> the cache will be amortized in most cases; in fact, "rev-list --stdin"
> might be the *only* plausible use case.

The two I know of are "rev-list --stdin" and "cat-file --batch-check".

> Regarding the overall strategy: you gather all refnames that could be
> confused with an SHA-1 into a sha1_array, then later look up SHA-1s in
> the array to see if they are ambiguous.  This is a very special-case
> optimization for SHA-1s.

Yes, it is very sha1-specific. Part of my goal was that in the common
case, the check would collapse to O(# of ambiguous refs), which is
typically 0.

That may be premature optimization, though. As you note below, doing a
few binary searches through the in-memory ref cache is _probably_ fine,
too. And we can do that without a separate index.

> I wonder whether another approach would gain almost the same amount of
> performance but be more general.  We could change dwim_ref() (or a
> version of it?) to read its data out of a ref_cache instead of going to
> disk every time.  Then, at the cost of populating the relevant parts of
> the ref_cache once, we would have fast dwim_ref() calls for all strings.

I'm very nervous about turning dwim_ref into a cache. As we noted above,
we never invalidate the cache, so any write-then-read operations could
get stale data. That is not as risky as caching, say, resolve_ref, but
it still makes me nervous. Caching just the warning has much lower
stakes.

> It's true that the lookups wouldn't be quite so fast--they would require
> a few bisects per refname lookup (one for each level in the refname
> hierarchy) and several refname lookups (one for each ref_rev_parse_rule)
> for every dwim_ref() call, vs. a single bisect in your current design.
> But this approach it would bring us most of the gain, it might
> nevertheless be preferable.

I don't think this would be all that hard to measure. I'll see what I
can do.

> > I wanted to make the ref traversal as cheap as possible, hence the
> > NO_RECURSE flag I added. I thought INCLUDE_BROKEN used to not open up
> > the refs at all, but it looks like it does these days. I wonder if that
> > is worth changing or not.
> 
> What do you mean by "open up the refs"?  The loose reference files are
> read when populating the cache.  (Was that ever different?)

I meant actually open the ref files and read the sha1. But that is me
being dumb. We have always done that, as we must provide the sha1 via
to the for_each_ref callback.

That being said, we could further optimize this by not opening the files
at all (and make that the responsibility of do_one_ref, which we are
avoiding here). I am slightly worried about the open() cost of my
solution. It's amortized away in a big call, but it is probably
noticeable for something like `git rev-parse <40-hex>`.

> This doesn't correctly handle the rule
> 
> 	"refs/remotes/%.*s/HEAD"
>
> We might be willing to accept this limitation, but it should at least be
> mentioned somewhere.  OTOH if we want to handle this pattern as well, we
> could do use a technique like that of shorten_unambiguous_ref().

Yes, you're right. I considered this, but for some reason convinced
myself that it would be OK to just look for "refs/remotes/<40-hex>" in
this case (which is what my patch does). But obviously that's wrong.
The ref traversal won't find a _directory_ with that name.

I'll see how painful it is to make it work. I have to say I was tempted
to simply manually write the rules. It's a duplication that could go out
of sync with the ref_rev_parse rules, and that's nasty. But that list does
not change often, and the reverse-parsing of the rules is error-prone
and hard to understand itself.

-Peff

Re: [PATCH v2 4/5] get_sha1: speed up ambiguous 40-hex test

[Jeff King]

On Fri, Jan 10, 2014 at 04:41:20AM -0500, Jeff King wrote:

> That being said, we could further optimize this by not opening the files
> at all (and make that the responsibility of do_one_ref, which we are
> avoiding here). I am slightly worried about the open() cost of my
> solution. It's amortized away in a big call, but it is probably
> noticeable for something like `git rev-parse <40-hex>`.

I took a look at this. It gets a bit hairy. My strategy is to add a flag
to ask read_loose_refs to create REF_INCOMPLETE values. We currently use
this flag for loose REF_DIRs to mean "we haven't opendir()'d the
subdirectory yet". This would extend it to the non-REF_DIR case to mean
"we haven't opened the loose ref file yet". We'd check REF_INCOMPLETE
before handing the ref_entry to a callback, and complete it if
necessary.

It gets ugly, though, because we need to pass that flag through quite a
bit of callstack. get_ref_dir() needs to know it, which means all of
find_containing_dir, etc need it, meaning it pollutes all of the
packed-refs code paths too.

I have a half-done patch in this direction if that doesn't sound too
nasty.

> > This doesn't correctly handle the rule
> > 
> > 	"refs/remotes/%.*s/HEAD"
> [...]

> I'll see how painful it is to make it work.

It's actually reasonably painful. I thought at first we could get away
with more cleverly parsing the rule, find the prefix (up to the
placeholder), and then look for the suffix ("/HEAD") inside there. But
it can never work with the current do_for_each_* code. That code only
triggers a callback when we see a concrete ref. It _never_ lets the
callbacks see an intermediate directory.

So a NO_RECURSE flag is not sufficient to handle this case. I'd need to
teach do_for_each_ref to recurse based on pathspecs, or a custom
callback function. And that is getting quite complicated.

I think it might be simpler to just do my own custom traversal. What I
need is much simpler than what do_for_each_entry provides. I don't need
recursion, and I don't actually need to look at the loose and packed
refs together. It's OK for me to do them one at a time because I don't
care about the actual value; I just want to know about which refs exist.

-Peff

Re: [PATCH v2 4/5] get_sha1: speed up ambiguous 40-hex test

[Michael Haggerty]

On 01/14/2014 10:50 AM, Jeff King wrote:
> On Fri, Jan 10, 2014 at 04:41:20AM -0500, Jeff King wrote:
> 
>> That being said, we could further optimize this by not opening the files
>> at all (and make that the responsibility of do_one_ref, which we are
>> avoiding here). I am slightly worried about the open() cost of my
>> solution. It's amortized away in a big call, but it is probably
>> noticeable for something like `git rev-parse <40-hex>`.
> 
> I took a look at this. It gets a bit hairy. My strategy is to add a flag
> to ask read_loose_refs to create REF_INCOMPLETE values. We currently use
> this flag for loose REF_DIRs to mean "we haven't opendir()'d the
> subdirectory yet". This would extend it to the non-REF_DIR case to mean
> "we haven't opened the loose ref file yet". We'd check REF_INCOMPLETE
> before handing the ref_entry to a callback, and complete it if
> necessary.
> 
> It gets ugly, though, because we need to pass that flag through quite a
> bit of callstack. get_ref_dir() needs to know it, which means all of
> find_containing_dir, etc need it, meaning it pollutes all of the
> packed-refs code paths too.
> 
> I have a half-done patch in this direction if that doesn't sound too
> nasty.

A long time ago I write a patch series to allow incomplete reading of
references, but my version *always* read them lazily, so it was much
simpler (no need to pass a new option down the call stack).  It didn't
seem to speed things up in general, so I never submitted it.

Reading lazily only from particular callers is more complicated, and I
can see how it would get messy.

Given the race avoidance needed between packed/loose references, lazy
reading would mean that after each reference is read, the packed-refs
file would need to be stat()ted again to make sure that it hasn't been
changed since the last check.  I know this isn't an issue for your use
case, because you plan *never* to read the file contents.  But it does
increase the price of lazy reference reading to most callers.

On the other hand, if we ever go in the direction of routing *all*
reference lookups--including lookups of single references--through the
cache, then lazy reading of references probably becomes essential to
avoid populating more of the cache than necessary.

>>> This doesn't correctly handle the rule
>>>
>>> 	"refs/remotes/%.*s/HEAD"
>> [...]
> 
>> I'll see how painful it is to make it work.
> 
> It's actually reasonably painful. I thought at first we could get away
> with more cleverly parsing the rule, find the prefix (up to the
> placeholder), and then look for the suffix ("/HEAD") inside there. But
> it can never work with the current do_for_each_* code. That code only
> triggers a callback when we see a concrete ref. It _never_ lets the
> callbacks see an intermediate directory.
> 
> So a NO_RECURSE flag is not sufficient to handle this case. I'd need to
> teach do_for_each_ref to recurse based on pathspecs, or a custom
> callback function. And that is getting quite complicated.

Another possibility would be to have an "int recurse" parameter rather
than "bool recurse", telling how many levels to recurse.  Then one could
do a

    do_for_each_ref(..., "refs/remotes", ..., recurse=2)

to get all of the refs/remotes/*/HEAD references.  Though since all of
the heads for a remote are also siblings of "refs/remotes/foo/HEAD", it
could still involve a lot of superfluous file reading.  And the integer
wouldn't fit conveniently in the flags parameter.

> I think it might be simpler to just do my own custom traversal. What I
> need is much simpler than what do_for_each_entry provides. I don't need
> recursion, and I don't actually need to look at the loose and packed
> refs together. It's OK for me to do them one at a time because I don't
> care about the actual value; I just want to know about which refs exist.

Yes.  Still, the code is really piling up for this one warning for the
contrived eventuality that somebody wants to pass SHA-1s and branch
names together in a single cat-file invocation *and* wants to pass lots
of inputs at once and so is worried about performance *and* has
reference names that look like SHA-1s.  Otherwise we could just leave
the warning disabled in this case, as now.  Or we could add a new
"--hashes-only" option that tells cat-file to treat all of its
arguments/inputs as SHA-1s; such an option would permit an even faster
code path for bulk callers.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/