{"thread":{"id":"36778","subject":"[PATCH v3] refs.c: optimize check_refname_component()","startedAt":"2014-05-28T23:53:49Z","lastAt":"2014-05-28T23:53:49Z","messageCount":1,"participants":["David Turner"],"isPatch":true,"patchVersion":3,"patchTotal":null},"messages":[{"id":"242923","messageId":"1401321229-11722-1-git-send-email-dturner@twitter.com","threadId":"36778","inReplyTo":null,"subject":"[PATCH v3] refs.c: optimize check_refname_component()","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-05-28T23:53:49Z","receivedAt":"2014-05-28T23:53:49Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"In a repository with many refs, check_refname_component can be a major\ncontributor to the runtime of some git commands.  Provide two\noptimized versions of this function: one for machines with SSE4.2, and\none for machines without.  One such command is\n\ngit rev-parse HEAD\n\nTimings for one particular repo, with about 60k refs, almost all\npacked, are:\n\nOld: 35ms\nNew (no SSE): 29 ms\nNew (SSE): 25 ms\n\nMany other commands which read refs are also sped up.\n\nAdd some tests around 16-byte boundaries to ensure that the SSE\ncode correctly handles edge-cases.\n\nSigned-off-by: David Turner <dturner@twitter.com>\n---\n Makefile           |   6 ++\n configure.ac       |   6 ++\n git-compat-util.h  |  20 +++++++\n refs.c             | 164 +++++++++++++++++++++++++++++++++++++++++++++--------\n t/t5511-refspec.sh |  13 +++++\n 5 files changed, 185 insertions(+), 24 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/git-compat-util.h b/git-compat-util.h\nindex f6d3a46..cb49850 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -668,6 +668,26 @@ void git_qsort(void *base, size_t nmemb, size_t size,\n #endif\n #endif\n \n+#ifndef NO_SSE\n+#include <nmmintrin.h>\n+/* Clang ships with a version of nmmintrin.h that's incomplete; if\n+ * necessary, we define the constants that we're going to use. */\n+#ifndef _SIDD_UBYTE_OPS\n+#define _SIDD_UBYTE_OPS                 0x00\n+#define _SIDD_CMP_EQUAL_ANY             0x00\n+#define _SIDD_CMP_RANGES                0x04\n+#define _SIDD_CMP_EQUAL_ORDERED         0x0c\n+#define _SIDD_NEGATIVE_POLARITY         0x10\n+#endif\n+\n+/* This is the system memory page size; it's used so that we can read\n+ * outside the bounds of an allocation without segfaulting. It is\n+ * assumed to be a power of 2. */\n+#ifndef PAGE_SIZE\n+#define PAGE_SIZE 4096\n+#endif\n+#endif\n+\n #ifdef UNRELIABLE_FSTAT\n #define fstat_is_reliable() 0\n #else\ndiff --git a/refs.c b/refs.c\nindex 28d5eca..61a483a 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -5,9 +5,32 @@\n #include \"dir.h\"\n #include \"string-list.h\"\n \n+/* How to handle various characters in refnames:\n+   0: An acceptable character for refs\n+   1: End-of-component\n+   2: ., look for a following . to reject .. in refs\n+   3: @, look for a following { to reject @{ in refs\n+   9: A bad character, reject ref\n+\n+   See below for the list of illegal characters, from which\n+   this table is derived.\n+ */\n+static unsigned char refname_disposition[] = {\n+\t1, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+\t9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+\t9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 2, 1,\n+\t0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 9,\n+\t0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n+\t0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 9, 0, 9, 0,\n+\t0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n+\t0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 9, 9\n+};\n+\n /*\n- * Make sure \"ref\" is something reasonable to have under \".git/refs/\";\n- * We do not like it if:\n+ * Try to read one refname component from the front of refname.\n+ * Return the length of the component found, or -1 if the component is\n+ * not legal.  It is legal if it is something reasonable to have under\n+ * \".git/refs/\"; We do not like it if:\n  *\n  * - any path component of it begins with \".\", or\n  * - it has double dots \"..\", or\n@@ -15,44 +38,41 @@\n  * - it ends with a \"/\".\n  * - it ends with \".lock\"\n  * - it contains a \"\\\" (backslash)\n- */\n \n-/* Return true iff ch is not allowed in reference names. */\n-static inline int bad_ref_char(int ch)\n-{\n-\tif (((unsigned) ch) <= ' ' || ch == 0x7f ||\n-\t    ch == '~' || ch == '^' || ch == ':' || ch == '\\\\')\n-\t\treturn 1;\n-\t/* 2.13 Pattern Matching Notation */\n-\tif (ch == '*' || ch == '?' || ch == '[') /* Unsupported */\n-\t\treturn 1;\n-\treturn 0;\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\treturn -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\tcase 3:\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\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@@ -68,6 +88,102 @@ static int check_refname_component(const char *refname, int flags)\n \treturn cp - refname;\n }\n \n+#ifdef NO_SSE\n+#define check_refname_component check_refname_component_1\n+#else\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+\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+#endif\n+\n int check_refname_format(const char *refname, int flags)\n {\n \tint component_len, component_count = 0;\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"}]}