{"thread":{"id":"36774","subject":"[PATCH] check_refname_component: Optimize","startedAt":"2014-05-28T19:57:35Z","lastAt":"2014-05-29T12:19:26Z","messageCount":3,"participants":["David Turner","Junio C Hamano","brian m. carlson"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"242899","messageId":"1401307055-11603-1-git-send-email-dturner@twitter.com","threadId":"36774","inReplyTo":null,"subject":"[PATCH] check_refname_component: Optimize","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-05-28T19:57:35Z","receivedAt":"2014-05-28T19:57:35Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"In a repository with tens of thousands of refs, the command\n~/git/git-diff-index --cached --quiet --ignore-submodules [revision]\nis a bit slow.  check_refname_component is a major contributor to the\nruntime.  Provide two optimized versions of this function: one for\nmachines with SSE4.2, and one for machines without.  The speedup for\nthis command on one particular repo (with about 60k refs) is about 12%\nfor the SSE version and 8% for the non-SSE version.\n\nSigned-off-by: David Turner <dturner@twitter.com>\n---\n Makefile           |   6 +++\n configure.ac       |   6 +++\n refs.c             | 143 +++++++++++++++++++++++++++++++++++++++++++++++++++--\n t/t5511-refspec.sh |  13 +++++\n 4 files changed, 163 insertions(+), 5 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex a53f3a8..123e2fc 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1326,6 +1326,11 @@ else\n \t\tCOMPAT_OBJS += compat/win32mmap.o\n \tendif\n endif\n+ifdef NO_SSE\n+\tBASIC_CFLAGS += -DNO_SSE\n+else\n+\tBASIC_CFLAGS += -msse4\n+endif\n ifdef OBJECT_CREATION_USES_RENAMES\n \tCOMPAT_CFLAGS += -DOBJECT_CREATION_MODE=1\n endif\n@@ -2199,6 +2204,7 @@ GIT-BUILD-OPTIONS: FORCE\n \t@echo NO_PERL=\\''$(subst ','\\'',$(subst ','\\'',$(NO_PERL)))'\\' >>$@\n \t@echo NO_PYTHON=\\''$(subst ','\\'',$(subst ','\\'',$(NO_PYTHON)))'\\' >>$@\n \t@echo NO_UNIX_SOCKETS=\\''$(subst ','\\'',$(subst ','\\'',$(NO_UNIX_SOCKETS)))'\\' >>$@\n+\t@echo NO_SSE=\\''$(subst ','\\'',$(subst ','\\'',$(NO_SSE)))'\\' >>$@\n ifdef TEST_OUTPUT_DIRECTORY\n \t@echo TEST_OUTPUT_DIRECTORY=\\''$(subst ','\\'',$(subst ','\\'',$(TEST_OUTPUT_DIRECTORY)))'\\' >>$@\n endif\ndiff --git a/configure.ac b/configure.ac\nindex b711254..71a9429 100644\n--- a/configure.ac\n+++ b/configure.ac\n@@ -382,6 +382,11 @@ AS_HELP_STRING([],[Tcl/Tk interpreter will be found in a system.]),\n GIT_PARSE_WITH(tcltk))\n #\n \n+# Declare the with-sse/without-sse options.\n+AC_ARG_WITH(sse,\n+AS_HELP_STRING([--with-sse],[use SSE instructions (default is YES)]),\n+GIT_PARSE_WITH(sse))\n+\n \n ## Checks for programs.\n AC_MSG_NOTICE([CHECKS for programs])\n@@ -449,6 +454,7 @@ else\n   fi\n fi\n GIT_CONF_SUBST([TCLTK_PATH])\n+GIT_CONF_SUBST([NO_SSE])\n AC_CHECK_PROGS(ASCIIDOC, [asciidoc])\n if test -n \"$ASCIIDOC\"; then\n \tAC_MSG_CHECKING([for asciidoc version])\ndiff --git a/refs.c b/refs.c\nindex 28d5eca..8ca124c 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -5,6 +5,8 @@\n #include \"dir.h\"\n #include \"string-list.h\"\n \n+#include <nmmintrin.h>\n+\n /*\n  * Make sure \"ref\" is something reasonable to have under \".git/refs/\";\n  * We do not like it if:\n@@ -29,30 +31,160 @@ static inline int bad_ref_char(int ch)\n \treturn 0;\n }\n \n+char refname_disposition[] = {\n+       1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n+       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n+       0, 9, 9, 9, 9, 9, 9, 9, 9, 9, 0, 9, 9, 9, 2, 1,\n+       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 0, 9, 9, 9, 9, 0,\n+       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 0, 0, 9, 0, 9,\n+       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 3, 9, 9, 0, 0,\n+       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9\n+};\n+\n /*\n  * Try to read one refname component from the front of refname.  Return\n  * the length of the component found, or -1 if the component is not\n  * legal.\n  */\n-static int check_refname_component(const char *refname, int flags)\n+static int check_refname_component_1(const char *refname, int flags)\n {\n \tconst char *cp;\n \tchar last = '\\0';\n \n \tfor (cp = refname; ; cp++) {\n-\t\tchar ch = *cp;\n-\t\tif (ch == '\\0' || ch == '/')\n+\t\tunsigned char ch = (unsigned char) *cp;\n+\t\tchar disp = refname_disposition[ch];\n+\t\tswitch(disp) {\n+\t\tcase 0:\n+\t\t       return -1;\n+\t\tcase 1:\n+\t\t\tgoto out;\n+\t\tcase 2:\n+\t\t\tif (last == '.')\n+\t\t\t\treturn -1;\n \t\t\tbreak;\n-\t\tif (bad_ref_char(ch))\n-\t\t\treturn -1; /* Illegal character in refname. */\n+\t\tcase 3:\n+\t\t       if (last == '@')\n+\t\t\t       return -1;\n+\t\t       break;\n+\t       }\n+\n \t\tif (last == '.' && ch == '.')\n \t\t\treturn -1; /* Refname contains \"..\". */\n \t\tif (last == '@' && ch == '{')\n \t\t\treturn -1; /* Refname contains \"@{\". */\n \t\tlast = ch;\n \t}\n+out:\n+\tif (cp == refname)\n+\t\treturn 0; /* Component has zero length. */\n+\n+\tif (refname[0] == '.') {\n+\t\tif (!(flags & REFNAME_DOT_COMPONENT))\n+\t\t\treturn -1; /* Component starts with '.'. */\n+\t\t/*\n+\t\t * Even if leading dots are allowed, don't allow \".\"\n+\t\t * as a component (\"..\" is prevented by a rule above).\n+\t\t */\n+\t\tif (refname[1] == '\\0')\n+\t\t\treturn -1; /* Component equals \".\". */\n+\t}\n+\tif (cp - refname >= 5 && !memcmp(cp - 5, \".lock\", 5))\n+\t\treturn -1; /* Refname ends with \".lock\". */\n+\treturn cp - refname;\n+}\n+\n+#ifdef NO_SSE\n+#define check_refname_component check_refname_component_1\n+#else\n+\n+#define PAGE_SIZE 4096\n+#define BLOCK_SIZE 16\n+\n+/* Vectorized version of check_refname_component */\n+static int check_refname_component(const char *refname, int flags)\n+{\n+\tconst __m128i *refname_vec = (__m128i*) refname;\n+\n+\t/* Character ranges for characters forbidden in refs; see\n+\t * above */\n+\tstatic const __v16qi bad = {\n+\t\t0x01, 0x20,  0x7e, 0x7f,  0x5e, 0x5e,  0x3a, 0x3a,\n+\t\t0x5b, 0x5c,  0x2a, 0x2a,  0x3f, 0x3f,  0x3f, 0x3f};\n+\n+\tstatic const __v16qi nonslashes = {\n+\t\t'\\001', '/' -1, '/' + 1, 0xff,\n+\t};\n+\n+\tstatic const __v16qi dotdot = {'.','.',0};\n+\tstatic const __v16qi atcurly = {'@','{',0};\n+\n+\tconst __m128i *vp;\n+\tconst char *cp = (const char *)refname_vec;\n+\n+\n+\tint dotdotpos = BLOCK_SIZE, atcurlypos = BLOCK_SIZE;\n+\tfor (vp = refname_vec; ; vp++) {\n+\t\t__m128i tmp;\n+\t\tint endpos;\n+\n+\t\t/* Handle case of forbidden substrings .. and @{ crossing\n+\t\t * sixteen-byte boudaries */\n+\t\tif (dotdotpos == 15 && *cp == '.')\n+\t\t\treturn -1;\n+\n+\t\tif (atcurlypos == 15 && *cp == '{')\n+\t\t\treturn -1;\n+\n+\t\tif (((uintptr_t) vp & (PAGE_SIZE - 1)) > PAGE_SIZE - BLOCK_SIZE)\n+\t\t\t/* End-of-page; fall back to slow method for\n+\t\t\t * this entire component. */\n+\t\t\treturn check_refname_component_1(refname, flags);\n+\n+\t\ttmp = _mm_lddqu_si128(vp);\n+\n+\t\t/* Find slashes or end-of-string. The double-negative\n+\t\t * (negative-polarity search for non-slashes) is\n+\t\t * necessary so that \\0 will also be counted.  */\n+\t\tendpos = _mm_cmpistri((__m128i) nonslashes, tmp,\n+\t\t\t\t      _SIDD_UBYTE_OPS | _SIDD_CMP_RANGES |\n+\t\t\t\t      _SIDD_NEGATIVE_POLARITY);\n+\n+\t\tif (_mm_cmpestrc((__m128i) bad, BLOCK_SIZE, tmp, endpos,\n+\t\t\t\t _SIDD_UBYTE_OPS | _SIDD_CMP_RANGES))\n+\t\t\treturn -1;\n+\n+\t\tdotdotpos = _mm_cmpestri((__m128i) dotdot, 2, tmp, endpos,\n+\t\t\t\t\t _SIDD_UBYTE_OPS |\n+\t\t\t\t\t _SIDD_CMP_EQUAL_ORDERED);\n+\t\tif (dotdotpos < 15)\n+\t\t\treturn -1;\n+\n+\t\tatcurlypos = _mm_cmpestri((__m128i) atcurly, 2, tmp, endpos,\n+\t\t\t\t\t  _SIDD_UBYTE_OPS |\n+\t\t\t\t\t  _SIDD_CMP_EQUAL_ORDERED);\n+\t\tif (atcurlypos < 15)\n+\t\t\treturn -1;\n+\n+\t\tif (endpos < BLOCK_SIZE) {\n+\t\t\tcp = ((const char*) vp) + endpos;\n+\t\t\tbreak;\n+\t\t}\n+\t\tcp = (const char*) vp + BLOCK_SIZE;\n+\t}\n+\n \tif (cp == refname)\n \t\treturn 0; /* Component has zero length. */\n+\n \tif (refname[0] == '.') {\n \t\tif (!(flags & REFNAME_DOT_COMPONENT))\n \t\t\treturn -1; /* Component starts with '.'. */\n@@ -67,6 +199,7 @@ static int check_refname_component(const char *refname, int flags)\n \t\treturn -1; /* Refname ends with \".lock\". */\n \treturn cp - refname;\n }\n+#endif\n \n int check_refname_format(const char *refname, int flags)\n {\ndiff --git a/t/t5511-refspec.sh b/t/t5511-refspec.sh\nindex c289322..0f03f9c 100755\n--- a/t/t5511-refspec.sh\n+++ b/t/t5511-refspec.sh\n@@ -84,4 +84,17 @@ test_refspec push 'refs/heads/*/*/for-linus:refs/remotes/mine/*' invalid\n test_refspec fetch 'refs/heads/*/for-linus:refs/remotes/mine/*'\n test_refspec push 'refs/heads/*/for-linus:refs/remotes/mine/*'\n \n+test_refspec fetch 'refs/heads/a-very-long-refname'\n+test_refspec fetch 'refs/heads/.a-very-long-refname'\t\tinvalid\n+test_refspec fetch 'refs/heads/abcdefgh0123..'\t\t\tinvalid\n+test_refspec fetch 'refs/heads/abcdefgh01234..'\t\t\tinvalid\n+test_refspec fetch 'refs/heads/abcdefgh012345..'\t\tinvalid\n+test_refspec fetch 'refs/heads/abcdefgh0123456..'\t\tinvalid\n+test_refspec fetch 'refs/heads/abcdefgh01234567..'\t\tinvalid\n+test_refspec fetch 'refs/heads/abcdefgh0123.a'\n+test_refspec fetch 'refs/heads/abcdefgh01234.a'\n+test_refspec fetch 'refs/heads/abcdefgh012345.a'\n+test_refspec fetch 'refs/heads/abcdefgh0123456.a'\n+test_refspec fetch 'refs/heads/abcdefgh01234567.a'\n+\n test_done\n-- \n2.0.0.rc1.18.gf763c0f\n"},{"id":"242905","messageId":"xmqq38ftd2bs.fsf@gitster.dls.corp.google.com","threadId":"36774","inReplyTo":"1401307055-11603-1-git-send-email-dturner@twitter.com","subject":"Re: [PATCH] check_refname_component: Optimize","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-05-28T21:24:07Z","receivedAt":"2014-05-28T21:24:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Turner <dturner@twopensource.com> writes:\n\n> In a repository with tens of thousands of refs, the command\n> ~/git/git-diff-index --cached --quiet --ignore-submodules [revision]\n> is a bit slow.  check_refname_component is a major contributor to the\n> runtime.  Provide two optimized versions of this function: one for\n> machines with SSE4.2, and one for machines without.  The speedup for\n> this command on one particular repo (with about 60k refs) is about 12%\n> for the SSE version and 8% for the non-SSE version.\n>\n> Signed-off-by: David Turner <dturner@twitter.com>\n\nJust a few quick impressions (I do not have time today to look at\nnew patches).\n\n - The title seems a bit strange.\n   Perhaps \"refs.c: optimize check_refname_component()\" or something?\n\n - \"~/git/git-diff-index\" looks doubly strange in that the issue you\n   are addressing would not depend on your compiled Git being\n   installed in your $HOME/git at all.  For that matter, from the\n   command line and the patch, I am not sure if this is specific to\n   \"git diff-index\", or the same issue exists for anything that\n   takes revs and pathspecs from the command line.\n\n\n\n\n\n> ---\n>  Makefile           |   6 +++\n>  configure.ac       |   6 +++\n>  refs.c             | 143 +++++++++++++++++++++++++++++++++++++++++++++++++++--\n>  t/t5511-refspec.sh |  13 +++++\n>  4 files changed, 163 insertions(+), 5 deletions(-)\n>\n> diff --git a/Makefile b/Makefile\n> index a53f3a8..123e2fc 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -1326,6 +1326,11 @@ else\n>  \t\tCOMPAT_OBJS += compat/win32mmap.o\n>  \tendif\n>  endif\n> +ifdef NO_SSE\n> +\tBASIC_CFLAGS += -DNO_SSE\n> +else\n> +\tBASIC_CFLAGS += -msse4\n> +endif\n>  ifdef OBJECT_CREATION_USES_RENAMES\n>  \tCOMPAT_CFLAGS += -DOBJECT_CREATION_MODE=1\n>  endif\n> @@ -2199,6 +2204,7 @@ GIT-BUILD-OPTIONS: FORCE\n>  \t@echo NO_PERL=\\''$(subst ','\\'',$(subst ','\\'',$(NO_PERL)))'\\' >>$@\n>  \t@echo NO_PYTHON=\\''$(subst ','\\'',$(subst ','\\'',$(NO_PYTHON)))'\\' >>$@\n>  \t@echo NO_UNIX_SOCKETS=\\''$(subst ','\\'',$(subst ','\\'',$(NO_UNIX_SOCKETS)))'\\' >>$@\n> +\t@echo NO_SSE=\\''$(subst ','\\'',$(subst ','\\'',$(NO_SSE)))'\\' >>$@\n>  ifdef TEST_OUTPUT_DIRECTORY\n>  \t@echo TEST_OUTPUT_DIRECTORY=\\''$(subst ','\\'',$(subst ','\\'',$(TEST_OUTPUT_DIRECTORY)))'\\' >>$@\n>  endif\n> diff --git a/configure.ac b/configure.ac\n> index b711254..71a9429 100644\n> --- a/configure.ac\n> +++ b/configure.ac\n> @@ -382,6 +382,11 @@ AS_HELP_STRING([],[Tcl/Tk interpreter will be found in a system.]),\n>  GIT_PARSE_WITH(tcltk))\n>  #\n>  \n> +# Declare the with-sse/without-sse options.\n> +AC_ARG_WITH(sse,\n> +AS_HELP_STRING([--with-sse],[use SSE instructions (default is YES)]),\n> +GIT_PARSE_WITH(sse))\n> +\n>  \n>  ## Checks for programs.\n>  AC_MSG_NOTICE([CHECKS for programs])\n> @@ -449,6 +454,7 @@ else\n>    fi\n>  fi\n>  GIT_CONF_SUBST([TCLTK_PATH])\n> +GIT_CONF_SUBST([NO_SSE])\n>  AC_CHECK_PROGS(ASCIIDOC, [asciidoc])\n>  if test -n \"$ASCIIDOC\"; then\n>  \tAC_MSG_CHECKING([for asciidoc version])\n> diff --git a/refs.c b/refs.c\n> index 28d5eca..8ca124c 100644\n> --- a/refs.c\n> +++ b/refs.c\n> @@ -5,6 +5,8 @@\n>  #include \"dir.h\"\n>  #include \"string-list.h\"\n>  \n> +#include <nmmintrin.h>\n> +\n\nWe would prefer not to add inclusion of any system header files in\nrandom *.c files, as there often are system dependencies (order of\ninclusion, definition of feature macros, etc.) we would rather want\nto encapsulate in one place, that is git-compat-util.h.\n\n>  /*\n>   * Make sure \"ref\" is something reasonable to have under \".git/refs/\";\n>   * We do not like it if:\n> @@ -29,30 +31,160 @@ static inline int bad_ref_char(int ch)\n>  \treturn 0;\n>  }\n>  \n> +char refname_disposition[] = {\n> +       1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n> +       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n> ...\n> +       9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9\n> +};\n> +\n\nDoes this array need to be extern?\n\nIs this table designed to take both positive and negative values?\nIf the answer is \"I expect we add only positive\", then please make\nit explicitly \"unsigned char\".\n\nWhat do these magic numbers in the array mean?\n\nHow were the values derived?  What are you doing in this commit to\nhelp others who later need to debug, fix and enhance this table?\n"},{"id":"242937","messageId":"20140529121926.GA47385@vauxhall.crustytoothpaste.net","threadId":"36774","inReplyTo":"1401307055-11603-1-git-send-email-dturner@twitter.com","subject":"Re: [PATCH] check_refname_component: Optimize","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2014-05-29T12:19:26Z","receivedAt":"2014-05-29T12:19:26Z","isPatch":true,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On Wed, May 28, 2014 at 03:57:35PM -0400, David Turner wrote:\n> +ifdef NO_SSE\n> +\tBASIC_CFLAGS += -DNO_SSE\n\nThis is not a great name.  This implies the system does not have SSE\n(SSE 1), but in fact what you're concerned about is SSE 4.  This will be\nconfusing for users of older x86-64 processors, where SSE and SSE 2 are\narchitecturally guaranteed even though SSE 4 is not present.\n\n> +else\n> +\tBASIC_CFLAGS += -msse4\n> +endif\n\nYou probably also want to autodetect when the system is not x86(-64)?\nand turn this off.  I doubt PowerPC/SPARC/ARM users are going to want to\nhave to disable it manually.\n\n-- \nbrian m. carlson / brian with sandals: Houston, Texas, US\n+1 832 623 2791 | http://www.crustytoothpaste.net/~bmc | My opinion only\nOpenPGP: RSA v4 4096b: 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187\n"}]}