{"thread":{"id":"36824","subject":"[PATCH v5 1/2] refs.c: optimize check_refname_component()","startedAt":"2014-06-03T18:21:24Z","lastAt":"2014-06-03T18:21:25Z","messageCount":2,"participants":["David Turner"],"isPatch":true,"patchVersion":5,"patchTotal":2},"messages":[{"id":"243198","messageId":"1401819685-17064-1-git-send-email-dturner@twitter.com","threadId":"36824","inReplyTo":null,"subject":"[PATCH v5 1/2] refs.c: optimize check_refname_component()","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-06-03T18:21:24Z","receivedAt":"2014-06-03T18:21:24Z","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. 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: 35 ms\nNew: 29 ms\n\nMany other commands which read refs are also sped up.\n\nSigned-off-by: David Turner <dturner@twitter.com>\n---\n refs.c             | 67 +++++++++++++++++++++++++++++++-----------------------\n t/t5511-refspec.sh |  6 ++++-\n 2 files changed, 44 insertions(+), 29 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 28d5eca..46139d2 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -6,8 +6,29 @@\n #include \"string-list.h\"\n \n /*\n- * Make sure \"ref\" is something reasonable to have under \".git/refs/\";\n- * We do not like it if:\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 preceding . to reject .. in refs\n+ * 3: {, look for a preceding @ to reject @{ in refs\n+ * 4: A bad character: ASCII control characters, \"~\", \"^\", \":\" or SP\n+ */\n+static unsigned char refname_disposition[256] = {\n+\t1, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,\n+\t4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,\n+\t4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 2, 1,\n+\t0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 4,\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, 4, 4, 0, 4, 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, 4, 4\n+};\n+\n+/*\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@@ -16,41 +37,31 @@\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 {\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\tint ch = *cp & 255;\n+\t\tunsigned char disp = refname_disposition[ch];\n+\t\tswitch(disp) {\n+\t\tcase 1:\n+\t\t\tgoto out;\n+\t\tcase 2:\n+\t\t\tif (last == '.')\n+\t\t\t\treturn -1; /* Refname contains \"..\". */\n+\t\t\tbreak;\n+\t\tcase 3:\n+\t\t\tif (last == '@')\n+\t\t\t\treturn -1; /* Refname contains \"@{\". */\n \t\t\tbreak;\n-\t\tif (bad_ref_char(ch))\n-\t\t\treturn -1; /* Illegal character in refname. */\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\tcase 4:\n+\t\t\treturn -1;\n+\t\t}\n \t\tlast = ch;\n \t}\n+out:\n \tif (cp == refname)\n \t\treturn 0; /* Component has zero length. */\n \tif (refname[0] == '.') {\ndiff --git a/t/t5511-refspec.sh b/t/t5511-refspec.sh\nindex c289322..de6db86 100755\n--- a/t/t5511-refspec.sh\n+++ b/t/t5511-refspec.sh\n@@ -5,7 +5,6 @@ test_description='refspec parsing'\n . ./test-lib.sh\n \n test_refspec () {\n-\n \tkind=$1 refspec=$2 expect=$3\n \tgit config remote.frotz.url \".\" &&\n \tgit config --remove-section remote.frotz &&\n@@ -84,4 +83,9 @@ 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+good=$(printf '\\303\\204')\n+test_refspec fetch \"refs/heads/${good}\"\n+bad=$(printf '\\011tab')\n+test_refspec fetch \"refs/heads/${bad}\"\t\t\t\tinvalid\n+\n test_done\n-- \n2.0.0.rc1.18.gf763c0f\n"},{"id":"243199","messageId":"1401819685-17064-2-git-send-email-dturner@twitter.com","threadId":"36824","inReplyTo":"1401819685-17064-1-git-send-email-dturner@twitter.com","subject":"[PATCH v5 2/2] refs.c: SSE4.2 optimizations for check_refname_component","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-06-03T18:21:25Z","receivedAt":"2014-06-03T18:21:25Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"Optimize check_refname_component using SSE4.2, where available.\n\ngit rev-parse HEAD is a good test-case for this, since it does almost\nnothing except parse refs.  For one particular repo with about 60k\nrefs, almost all packed, the timings are:\n\nLook up table: 29 ms\nSSE4.2:        25 ms\n\nThis is about a 15% improvement.\n\nThe configure.ac changes include code from the GNU C Library written\nby Joseph S. Myers <joseph at codesourcery dot com>.\n\nSigned-off-by: David Turner <dturner@twitter.com>\n---\n Makefile           |   6 +++\n aclocal.m4         |   6 +++\n configure.ac       |  17 ++++++++\n git-compat-util.h  |  20 +++++++++\n refs.c             | 116 +++++++++++++++++++++++++++++++++++++++++++++--------\n t/t5511-refspec.sh |  13 ++++++\n 6 files changed, 161 insertions(+), 17 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex a53f3a8..dd2127a 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_SSE42\n+\tBASIC_CFLAGS += -DNO_SSE42\n+else\n+\tBASIC_CFLAGS += -msse4.2\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_SSE42=\\''$(subst ','\\'',$(subst ','\\'',$(NO_SSE42)))'\\' >>$@\n ifdef TEST_OUTPUT_DIRECTORY\n \t@echo TEST_OUTPUT_DIRECTORY=\\''$(subst ','\\'',$(subst ','\\'',$(TEST_OUTPUT_DIRECTORY)))'\\' >>$@\n endif\ndiff --git a/aclocal.m4 b/aclocal.m4\nindex f11bc7e..d9f3f19 100644\n--- a/aclocal.m4\n+++ b/aclocal.m4\n@@ -38,3 +38,9 @@ AC_DEFUN([TYPE_SOCKLEN_T],\n       [#include <sys/types.h>\n #include <sys/socket.h>])\n ])\n+\n+dnl Test a compiler option or options with an empty input file.\n+dnl LIBC_TRY_CC_OPTION([options], [action-if-true], [action-if-false])\n+AC_DEFUN([LIBC_TRY_CC_OPTION],\n+[AS_IF([AC_TRY_COMMAND([${CC-cc} $1 -xc /dev/null -S -o /dev/null])],\n+\t[$2], [$3])])\ndiff --git a/configure.ac b/configure.ac\nindex b711254..3a5bda9 100644\n--- a/configure.ac\n+++ b/configure.ac\n@@ -382,6 +382,23 @@ AS_HELP_STRING([],[Tcl/Tk interpreter will be found in a system.]),\n GIT_PARSE_WITH(tcltk))\n #\n \n+# Declare the with-sse42/without-sse42 options.\n+AC_ARG_WITH(sse42,\n+AS_HELP_STRING([--with-sse42],[use SSE4.2 instructions])\n+AS_HELP_STRING([],[(default is YES if your compiler supports -msse4.2)]),\n+GIT_PARSE_WITH(sse42))\n+\n+if test \"$NO_SSE42\" != \"YesPlease\"; then\n+   dnl Check if -msse4.2 works.\n+   AC_CACHE_CHECK(for SSE4.2 support, cc_cv_sse42, [dnl\n+   LIBC_TRY_CC_OPTION([-msse4.2], [cc_cv_sse42=yes], [cc_cv_sse42=no])\n+   ])\n+   if test $cc_cv_sse42 = no; then\n+     NO_SSE42=1\n+   fi\n+fi\n+\n+GIT_CONF_SUBST([NO_SSE42])\n \n ## Checks for programs.\n AC_MSG_NOTICE([CHECKS for programs])\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex f6d3a46..254487a 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_SSE42\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 46139d2..532aaf4 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -24,6 +24,25 @@ static unsigned char refname_disposition[256] = {\n \t0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 4, 4\n };\n \n+static int check_refname_component_trailer(const char *cp, const char *refname, int flags)\n+{\n+\tif (cp == refname)\n+\t\treturn 0; /* Component has zero length. */\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 /*\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@@ -37,7 +56,7 @@ static unsigned char refname_disposition[256] = {\n  * - it ends with \".lock\"\n  * - it contains a \"\\\" (backslash)\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@@ -47,7 +66,7 @@ static int check_refname_component(const char *refname, int flags)\n \t\tunsigned char disp = refname_disposition[ch];\n \t\tswitch(disp) {\n \t\tcase 1:\n-\t\t\tgoto out;\n+\t\t\treturn check_refname_component_trailer(cp, refname, flags);\n \t\tcase 2:\n \t\t\tif (last == '.')\n \t\t\t\treturn -1; /* Refname contains \"..\". */\n@@ -61,23 +80,86 @@ static int check_refname_component(const char *refname, int flags)\n \t\t}\n \t\tlast = ch;\n \t}\n-out:\n-\tif (cp == refname)\n-\t\treturn 0; /* Component has zero length. */\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+}\n+\n+#ifdef NO_SSE42\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+\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 boundaries */\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-\tif (cp - refname >= 5 && !memcmp(cp - 5, \".lock\", 5))\n-\t\treturn -1; /* Refname ends with \".lock\". */\n-\treturn cp - refname;\n+\treturn check_refname_component_trailer(cp, refname, flags);\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 de6db86..7f1bd74 100755\n--- a/t/t5511-refspec.sh\n+++ b/t/t5511-refspec.sh\n@@ -88,4 +88,17 @@ test_refspec fetch \"refs/heads/${good}\"\n bad=$(printf '\\011tab')\n test_refspec fetch \"refs/heads/${bad}\"\t\t\t\tinvalid\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"}]}