v2check_refname_component: Optimize

> In a repository with tens of thousands of refs, the command
> ~/git/git-diff-index --cached --quiet --ignore-submodules [revision]
> is a bit slow.  check_refname_component is a major contributor to the
> runtime.  Provide two optimized versions of this function: one for
> machines with SSE4.2, and one for machines without.  The speedup for
> this command on one particular repo (with about 60k refs) is about 12%
> for the SSE version and 8% for the non-SSE version.

> Signed-off-by: David Turner <dturner@twitter.com>
> ---
>  Makefile           |   6 +++
>  configure.ac       |   6 +++
>  refs.c             | 152 +++++++++++++++++++++++++++++++++++++++++++++++++++--
>  t/t5511-refspec.sh |  13 +++++
>  4 files changed, 172 insertions(+), 5 deletions(-)
> 
> diff --git a/Makefile b/Makefile
> index a53f3a8..123e2fc 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -1326,6 +1326,11 @@ else
>  		COMPAT_OBJS += compat/win32mmap.o
>  	endif
>  endif
> +ifdef NO_SSE
> +	BASIC_CFLAGS += -DNO_SSE
> +else
> +	BASIC_CFLAGS += -msse4
> +endif
>  ifdef OBJECT_CREATION_USES_RENAMES
>  	COMPAT_CFLAGS += -DOBJECT_CREATION_MODE=1
>  endif
> @@ -2199,6 +2204,7 @@ GIT-BUILD-OPTIONS: FORCE
>  	@echo NO_PERL=\''$(subst ','\'',$(subst ','\'',$(NO_PERL)))'\' >>$@
>  	@echo NO_PYTHON=\''$(subst ','\'',$(subst ','\'',$(NO_PYTHON)))'\' >>$@
>  	@echo NO_UNIX_SOCKETS=\''$(subst ','\'',$(subst ','\'',$(NO_UNIX_SOCKETS)))'\' >>$@
> +	@echo NO_SSE=\''$(subst ','\'',$(subst ','\'',$(NO_SSE)))'\' >>$@
>  ifdef TEST_OUTPUT_DIRECTORY
>  	@echo TEST_OUTPUT_DIRECTORY=\''$(subst ','\'',$(subst ','\'',$(TEST_OUTPUT_DIRECTORY)))'\' >>$@
>  endif
> diff --git a/configure.ac b/configure.ac
> index b711254..71a9429 100644
> --- a/configure.ac
> +++ b/configure.ac
> @@ -382,6 +382,11 @@ AS_HELP_STRING([],[Tcl/Tk interpreter will be found in a system.]),
>  GIT_PARSE_WITH(tcltk))
>  #
>  
> +# Declare the with-sse/without-sse options.
> +AC_ARG_WITH(sse,
> +AS_HELP_STRING([--with-sse],[use SSE instructions (default is YES)]),
> +GIT_PARSE_WITH(sse))
> +
>  
>  ## Checks for programs.
>  AC_MSG_NOTICE([CHECKS for programs])
> @@ -449,6 +454,7 @@ else
>    fi
>  fi
>  GIT_CONF_SUBST([TCLTK_PATH])
> +GIT_CONF_SUBST([NO_SSE])
>  AC_CHECK_PROGS(ASCIIDOC, [asciidoc])
>  if test -n "$ASCIIDOC"; then
>  	AC_MSG_CHECKING([for asciidoc version])
> diff --git a/refs.c b/refs.c
> index 28d5eca..8f0de04 100644
> --- a/refs.c
> +++ b/refs.c
> @@ -5,6 +5,8 @@
>  #include "dir.h"
>  #include "string-list.h"
>  
> +#include <nmmintrin.h>
> +

>  /*
>   * Make sure "ref" is something reasonable to have under ".git/refs/";
>   * We do not like it if:
> @@ -29,30 +31,169 @@ static inline int bad_ref_char(int ch)
>  	return 0;
>  }
>  

> +char refname_disposition[] = {
> +       1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
> +       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
> +       0, 9, 9, 9, 9, 9, 9, 9, 9, 9, 0, 9, 9, 9, 2, 1,
> +       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 0, 9, 9, 9, 9, 0,
> +       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
> +       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 0, 0, 9, 0, 9,
> +       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
> +       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 3, 9, 9, 0, 0,
> +       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
> +       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
> +       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
> +       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
> +       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
> +       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
> +       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
> +       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9
> +};
> +
>  /*
>   * Try to read one refname component from the front of refname.  Return
>   * the length of the component found, or -1 if the component is not
>   * legal.
>   */
> -static int check_refname_component(const char *refname, int flags)
> +static int check_refname_component_1(const char *refname, int flags)
>  {
>  	const char *cp;
>  	char last = '\0';
>  
>  	for (cp = refname; ; cp++) {
> -		char ch = *cp;
> -		if (ch == '\0' || ch == '/')
> +		unsigned char ch = (unsigned char) *cp;
> +		char disp = refname_disposition[ch];
> +		switch(disp) {
> +		case 0:
> +		       return -1;
> +		case 1:
> +			goto out;
> +		case 2:
> +			if (last == '.')
> +				return -1;
>  			break;
> -		if (bad_ref_char(ch))
> -			return -1; /* Illegal character in refname. */
> +		case 3:
> +		       if (last == '@')
> +			       return -1;
> +		       break;
> +	       }

> +
>  		if (last == '.' && ch == '.')
>  			return -1; /* Refname contains "..". */
>  		if (last == '@' && ch == '{')
>  			return -1; /* Refname contains "@{". */
>  		last = ch;
>  	}
> +out:
> +	if (cp == refname)
> +		return 0; /* Component has zero length. */
> +
> +	if (refname[0] == '.') {
> +		if (!(flags & REFNAME_DOT_COMPONENT))
> +			return -1; /* Component starts with '.'. */
> +		/*
> +		 * Even if leading dots are allowed, don't allow "."
> +		 * as a component (".." is prevented by a rule above).
> +		 */
> +		if (refname[1] == '\0')
> +			return -1; /* Component equals ".". */
> +	}
> +	if (cp - refname >= 5 && !memcmp(cp - 5, ".lock", 5))
> +		return -1; /* Refname ends with ".lock". */
> +	return cp - refname;
> +}
> +
> +#ifdef NO_SSE
> +#define check_refname_component check_refname_component_1
> +#else
> +
> +#ifndef _SIDD_UBYTE_OPS
> +#define _SIDD_UBYTE_OPS                 0x00
> +#define _SIDD_CMP_EQUAL_ANY             0x00
> +#define _SIDD_CMP_RANGES                0x04
> +#define _SIDD_CMP_EQUAL_ORDERED         0x0c
> +#define _SIDD_NEGATIVE_POLARITY         0x10
> +#endif
> +#ifndef PAGE_SIZE
> +#define PAGE_SIZE 4096
> +#endif
> +#define BLOCK_SIZE 16
> +
> +/* Vectorized version of check_refname_component */
> +static int check_refname_component(const char *refname, int flags)
> +{
> +	const __m128i *refname_vec = (__m128i*) refname;
> +
> +	/* Character ranges for characters forbidden in refs; see
> +	 * above */
> +	static const __v16qi bad = {
> +		0x01, 0x20,  0x7e, 0x7f,  0x5e, 0x5e,  0x3a, 0x3a,
> +		0x5b, 0x5c,  0x2a, 0x2a,  0x3f, 0x3f,  0x3f, 0x3f};
> +
> +	static const __v16qi nonslashes = {
> +		'\001', '/' -1, '/' + 1, 0xff,
> +	};
> +
> +	static const __v16qi dotdot = {'.','.',0};
> +	static const __v16qi atcurly = {'@','{',0};
> +
> +	const __m128i *vp;
> +	const char *cp = (const char *)refname_vec;
> +
> +
> +	int dotdotpos = BLOCK_SIZE, atcurlypos = BLOCK_SIZE;
> +	for (vp = refname_vec; ; vp++) {
> +		__m128i tmp;
> +		int endpos;
> +
> +		/* Handle case of forbidden substrings .. and @{ crossing
> +		 * sixteen-byte boudaries */
> +		if (dotdotpos == 15 && *cp == '.')
> +			return -1;
> +
> +		if (atcurlypos == 15 && *cp == '{')
> +			return -1;
> +
> +		if (((uintptr_t) vp & (PAGE_SIZE - 1)) > PAGE_SIZE - BLOCK_SIZE)
> +			/* End-of-page; fall back to slow method for
> +			 * this entire component. */
> +			return check_refname_component_1(refname, flags);
> +
> +		tmp = _mm_lddqu_si128(vp);
> +
> +		/* Find slashes or end-of-string. The double-negative
> +		 * (negative-polarity search for non-slashes) is
> +		 * necessary so that \0 will also be counted.  */
> +		endpos = _mm_cmpistri((__m128i) nonslashes, tmp,
> +				      _SIDD_UBYTE_OPS | _SIDD_CMP_RANGES |
> +				      _SIDD_NEGATIVE_POLARITY);
> +
> +		if (_mm_cmpestrc((__m128i) bad, BLOCK_SIZE, tmp, endpos,
> +				 _SIDD_UBYTE_OPS | _SIDD_CMP_RANGES))
> +			return -1;
> +
> +		dotdotpos = _mm_cmpestri((__m128i) dotdot, 2, tmp, endpos,
> +					 _SIDD_UBYTE_OPS |
> +					 _SIDD_CMP_EQUAL_ORDERED);
> +		if (dotdotpos < 15)
> +			return -1;
> +
> +		atcurlypos = _mm_cmpestri((__m128i) atcurly, 2, tmp, endpos,
> +					  _SIDD_UBYTE_OPS |
> +					  _SIDD_CMP_EQUAL_ORDERED);
> +		if (atcurlypos < 15)
> +			return -1;
> +
> +		if (endpos < BLOCK_SIZE) {
> +			cp = ((const char*) vp) + endpos;
> +			break;
> +		}
> +		cp = (const char*) vp + BLOCK_SIZE;
> +	}
> +
>  	if (cp == refname)
>  		return 0; /* Component has zero length. */
> +
>  	if (refname[0] == '.') {
>  		if (!(flags & REFNAME_DOT_COMPONENT))
>  			return -1; /* Component starts with '.'. */
> @@ -67,6 +208,7 @@ static int check_refname_component(const char *refname, int flags)
>  		return -1; /* Refname ends with ".lock". */
>  	return cp - refname;
>  }
> +#endif
>  
>  int check_refname_format(const char *refname, int flags)
>  {
> diff --git a/t/t5511-refspec.sh b/t/t5511-refspec.sh
> index c289322..0f03f9c 100755
> --- a/t/t5511-refspec.sh
> +++ b/t/t5511-refspec.sh
> @@ -84,4 +84,17 @@ test_refspec push 'refs/heads/*/*/for-linus:refs/remotes/mine/*' invalid
>  test_refspec fetch 'refs/heads/*/for-linus:refs/remotes/mine/*'
>  test_refspec push 'refs/heads/*/for-linus:refs/remotes/mine/*'
>  
> +test_refspec fetch 'refs/heads/a-very-long-refname'
> +test_refspec fetch 'refs/heads/.a-very-long-refname'		invalid
> +test_refspec fetch 'refs/heads/abcdefgh0123..'			invalid
> +test_refspec fetch 'refs/heads/abcdefgh01234..'			invalid
> +test_refspec fetch 'refs/heads/abcdefgh012345..'		invalid
> +test_refspec fetch 'refs/heads/abcdefgh0123456..'		invalid
> +test_refspec fetch 'refs/heads/abcdefgh01234567..'		invalid
> +test_refspec fetch 'refs/heads/abcdefgh0123.a'
> +test_refspec fetch 'refs/heads/abcdefgh01234.a'
> +test_refspec fetch 'refs/heads/abcdefgh012345.a'
> +test_refspec fetch 'refs/heads/abcdefgh0123456.a'
> +test_refspec fetch 'refs/heads/abcdefgh01234567.a'
> +
>  test_done
> 

> On 05/28/2014 11:04 PM, David Turner wrote:
> > In a repository with tens of thousands of refs, the command
> > ~/git/git-diff-index --cached --quiet --ignore-submodules [revision]
> > is a bit slow.  check_refname_component is a major contributor to the
> > runtime.  Provide two optimized versions of this function: one for
> > machines with SSE4.2, and one for machines without.  The speedup for
> > this command on one particular repo (with about 60k refs) is about 12%
> > for the SSE version and 8% for the non-SSE version.
> 
> Interesting.  Thanks for the patch.

> If so, there are probably
> other git commands that would better measure that time, with less other
> work.  For example, "git rev-parse refname" will read the packed-refs
> file, too (assuming that "refname" is not a loose reference).  If you
> test the speedup of a cheaper command like that, it seems to me that you
> will get a better idea of how much you are speeding up the ref-reading
> part.  It would also be interesting to see the difference in
> milliseconds (rather than a percentage) for some specified number of
> references.

> On Thu, May 29, 2014 at 6:49 AM, David Turner <dturner@twopensource.com> wrote:
>>> I assume that most of the time spent in check_refname_component() is
>>> while reading the packed-refs file, right?
>>
>> Yes.
>
> I wonder if we can get away without SSE code by saving stat info of
> the packed-refs version that we have verified. When we read pack-refs,
> if stat info matches, skip check_refname_component(). Assuming that
> pack-refs does not change often, of course.

> Duy Nguyen <pclouds@gmail.com> writes:
>
>> On Thu, May 29, 2014 at 6:49 AM, David Turner <dturner@twopensource.com> wrote:
>>>> I assume that most of the time spent in check_refname_component() is
>>>> while reading the packed-refs file, right?
>>>
>>> Yes.
>>
>> I wonder if we can get away without SSE code by saving stat info of
>> the packed-refs version that we have verified. When we read pack-refs,
>> if stat info matches, skip check_refname_component(). Assuming that
>> pack-refs does not change often, of course.
>
> Can you elaborate a bit more?

> >> I wonder if we can get away without SSE code by saving stat info of
> >> the packed-refs version that we have verified. When we read pack-refs,
> >> if stat info matches, skip check_refname_component(). Assuming that
> >> pack-refs does not change often, of course.
> >
> > Can you elaborate a bit more?
> 
> The first time we read packed_refs, check_refname_format() is called
> in read_packed_refs()->create_ref_entry() as usual. If we find no
> problem, we store packed_refs stat() info in maybe packed_refs.stat.
> Next time we read packed_refs, if packed_refs.stat is there and
> indicates that packed_refs has not changed, we can make
> create_ref_entry() ignore check_refname_format() completely.

> On Fri, May 30, 2014 at 06:24:30AM +0700, Duy Nguyen wrote:
>
>> >> I wonder if we can get away without SSE code by saving stat info of
>> >> the packed-refs version that we have verified. When we read pack-refs,
>> >> if stat info matches, skip check_refname_component(). Assuming that
>> >> pack-refs does not change often, of course.
>> >
>> > Can you elaborate a bit more?
>>
>> The first time we read packed_refs, check_refname_format() is called
>> in read_packed_refs()->create_ref_entry() as usual. If we find no
>> problem, we store packed_refs stat() info in maybe packed_refs.stat.
>> Next time we read packed_refs, if packed_refs.stat is there and
>> indicates that packed_refs has not changed, we can make
>> create_ref_entry() ignore check_refname_format() completely.
>
> I'm confused. Why would we re-open packed-refs at all if the stat
> information hasn't changed?

>
> read_packed_refs is only called from get_packed_ref_cache, and we only
> do so if !refs->packed. And refs->packed is only NULL if we haven't read
> the file yet, or it is stat-dirty.
>
> If that is working as intended, then we should generally only open and
> read packed-refs once per invocation of git.
>
> -Peff

> >> The first time we read packed_refs, check_refname_format() is called
> >> in read_packed_refs()->create_ref_entry() as usual. If we find no
> >> problem, we store packed_refs stat() info in maybe packed_refs.stat.
> >> Next time we read packed_refs, if packed_refs.stat is there and
> >> indicates that packed_refs has not changed, we can make
> >> create_ref_entry() ignore check_refname_format() completely.
> >
> > I'm confused. Why would we re-open packed-refs at all if the stat
> > information hasn't changed?
> 
> No, not in the same process. In the next run.

> But then we're just trusting that the "trust me" flag on disk is
> correct. Why not just trust that packed-refs is correct in the first
> place?
>
> IOW, consider this progression of changes:
>
>   1. Check refname format when we read packed-refs (the current
>      behavior).
>
>   2. Keep a separate file "packed-refs.stat" with stat information. If
>      the packed-refs file matches that stat information, do not bother
>      checking refname formats.
>
>   3. Put a flag in "packed-refs" that says "trust me, I'm valid". Check
>      the refnames when it is generated.
>
>   4. Realize that we already check the refnames when we write it out.
>      Don't bother writing "trust me, I'm valid"; readers can assume that
>      it is.
>
> What is the scenario that option (2) protects against that options (3)
> and (4) do not?
>
> I could guess something like "the writer has a different idea of what a
> valid refname is than we do". But that applies as well to (2), but just
> as "the reader who wrote packed-refs.stat has a different idea than we
> do".

>
> As a side note, while it is nice that we might make check_refname_format
> faster, I think if you _really_ want to make repos with a lot of refs
> faster, it would make more sense to introduce an on-disk format that
> does not need linear parsing (e.g., something we could mmap and binary
> search, or even something dbm-ish that could be updated without
> rewriting the whole file (deletions, for example, must rewrite the
> whole file, giving quadratic performance when deleting all refs one by
> one).

> On Fri, May 30, 2014 at 06:43:18AM +0700, Duy Nguyen wrote:
> 
>>>> The first time we read packed_refs, check_refname_format() is called
>>>> in read_packed_refs()->create_ref_entry() as usual. If we find no
>>>> problem, we store packed_refs stat() info in maybe packed_refs.stat.
>>>> Next time we read packed_refs, if packed_refs.stat is there and
>>>> indicates that packed_refs has not changed, we can make
>>>> create_ref_entry() ignore check_refname_format() completely.
>>>
>>> I'm confused. Why would we re-open packed-refs at all if the stat
>>> information hasn't changed?
>>
>> No, not in the same process. In the next run.
> 
> Ah, I thought "packed_refs.stat" was a struct member, but I guess you
> mean it as a filename.
> 
> But then we're just trusting that the "trust me" flag on disk is
> correct. Why not just trust that packed-refs is correct in the first
> place?
> 
> IOW, consider this progression of changes:
> 
>   1. Check refname format when we read packed-refs (the current
>      behavior).
> 
>   2. Keep a separate file "packed-refs.stat" with stat information. If
>      the packed-refs file matches that stat information, do not bother
>      checking refname formats.
> 
>   3. Put a flag in "packed-refs" that says "trust me, I'm valid". Check
>      the refnames when it is generated.
> 
>   4. Realize that we already check the refnames when we write it out.
>      Don't bother writing "trust me, I'm valid"; readers can assume that
>      it is.
> 
> What is the scenario that option (2) protects against that options (3)
> and (4) do not?
> 
> I could guess something like "the writer has a different idea of what a
> valid refname is than we do". But that applies as well to (2), but just
> as "the reader who wrote packed-refs.stat has a different idea than we
> do".

> > I could guess something like "the writer has a different idea of what a
> > valid refname is than we do". But that applies as well to (2), but just
> > as "the reader who wrote packed-refs.stat has a different idea than we
> > do".
> 
> If we want to be robust to future changes to refname rules, we could add
> a header flag like
> 
>     # pack-refs with: peeled fully-peeled check-level=1.0
> 
> which promises that the reference names in the file conform to the
> current ("version 1.0") check_refname_format() rules.

> On Fri, May 30, 2014 at 11:47:33AM +0200, Michael Haggerty wrote:
>> [...]
>> If we want to be robust to future changes to refname rules, we could add
>> a header flag like
>>
>>     # pack-refs with: peeled fully-peeled check-level=1.0
> [...]
> Yeah, I thought about mentioning something like that. But really, this
> just seems like a lot of complexity to solve the problem in a wrong way.

>
> IOW, consider this progression of changes:
>
>   1. Check refname format when we read packed-refs (the current
>      behavior).
>
>   2. Keep a separate file "packed-refs.stat" with stat information. If
>      the packed-refs file matches that stat information, do not bother
>      checking refname formats.
>
>   3. Put a flag in "packed-refs" that says "trust me, I'm valid". Check
>      the refnames when it is generated.
>
>   4. Realize that we already check the refnames when we write it out.
>      Don't bother writing "trust me, I'm valid"; readers can assume that
>      it is.
>
> What is the scenario that option (2) protects against that options (3)
> and (4) do not?