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

[Michael Haggerty <mhagger@alum.mit.edu>]

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/