{"thread":{"id":"36945","subject":"[PATCH v11] refs.c: SSE2 optimizations for check_refname_component","startedAt":"2014-06-18T05:54:42Z","lastAt":"2014-06-18T05:54:42Z","messageCount":1,"participants":["David Turner"],"isPatch":true,"patchVersion":11,"patchTotal":null},"messages":[{"id":"244500","messageId":"1403070882-12044-1-git-send-email-dturner@twitter.com","threadId":"36945","inReplyTo":null,"subject":"[PATCH v11] refs.c: SSE2 optimizations for check_refname_component","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-06-18T05:54:42Z","receivedAt":"2014-06-18T05:54:42Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"Optimize check_refname_component using SSE2 on x86_64.\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\nSSE2:          23 ms\n\nThis cuts about 20% off of the runtime.\n\nOndřej Bílka <neleai@seznam.cz> suggested an SSE2 approach to the\nsubstring searches, which netted a speed boost over the SSE4.2 code I\nhad initially written.\n\nSigned-off-by: David Turner <dturner@twitter.com>\n---\n git-compat-util.h           |  11 +++\n refs.c                      | 234 ++++++++++++++++++++++++++++++++++++++++----\n t/t1402-check-ref-format.sh |  15 +++\n t/valgrind/default.supp     |   8 ++\n 4 files changed, 250 insertions(+), 18 deletions(-)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex b6f03b3..96f5554 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -685,6 +685,17 @@ void git_qsort(void *base, size_t nmemb, size_t size,\n #endif\n #endif\n \n+#if defined(__GNUC__) && defined(__x86_64__)\n+#include <emmintrin.h>\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.\n+ */\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 dc45774..20e2bf1 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -7,21 +7,27 @@\n \n /*\n  * How to handle various characters in refnames:\n+ * This table is used by both the SIMD and non-SIMD code.  It has\n+ * some cases that are only useful for the SIMD; these are handled\n+ * equivalently to the listed disposition in the non-SIMD code.\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+ * 1: @, look for a following { to reject @{ in refs (SIMD or = 0)\n+ * 2: \\0: End-of-component and string\n+ * 3: /: End-of-component (SIMD or = 2)\n+ * 4: ., look for a preceding . to reject .. in refs\n+ * 5: {, look for a preceding @ to reject @{ in refs\n+ * 6: *, usually a bad character except, once as a wildcard (SIMD or = 7)\n+ * 7: A bad character except * (see check_refname_component below)\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+\t2, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,\n+\t7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,\n+\t7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 4, 3,\n+\t0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 7,\n+\t1, 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, 7, 7, 0, 7, 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, 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+\t0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 7, 7\n };\n \n /*\n@@ -33,8 +39,9 @@ static unsigned char refname_disposition[256] = {\n  * - any path component of it begins with \".\", or\n  * - it has double dots \"..\", or\n  * - it has ASCII control character, \"~\", \"^\", \":\" or SP, anywhere, or\n- * - it ends with a \"/\".\n- * - it ends with \".lock\"\n+ * - it has pattern-matching notation \"*\", \"?\", \"[\", anywhere, or\n+ * - it ends with a \"/\", or\n+ * - it ends with \".lock\", or\n  * - it contains a \"\\\" (backslash)\n  */\n static int check_refname_component(const char *refname, int flags)\n@@ -46,17 +53,19 @@ static int check_refname_component(const char *refname, int flags)\n \t\tint ch = *cp & 255;\n \t\tunsigned char disp = refname_disposition[ch];\n \t\tswitch (disp) {\n-\t\tcase 1:\n+\t\tcase 2: /* fall-through */\n+\t\tcase 3:\n \t\t\tgoto out;\n-\t\tcase 2:\n+\t\tcase 4:\n \t\t\tif (last == '.')\n \t\t\t\treturn -1; /* Refname contains \"..\". */\n \t\t\tbreak;\n-\t\tcase 3:\n+\t\tcase 5:\n \t\t\tif (last == '@')\n \t\t\t\treturn -1; /* Refname contains \"@{\". */\n \t\t\tbreak;\n-\t\tcase 4:\n+\t\tcase 6: /* fall-through */\n+\t\tcase 7:\n \t\t\treturn -1;\n \t\t}\n \t\tlast = ch;\n@@ -79,7 +88,7 @@ out:\n \treturn cp - refname;\n }\n \n-int check_refname_format(const char *refname, int flags)\n+static int check_refname_format_bytewise(const char *refname, int flags)\n {\n \tint component_len, component_count = 0;\n \n@@ -115,6 +124,195 @@ int check_refname_format(const char *refname, int flags)\n \treturn 0;\n }\n \n+#if defined(__GNUC__) && defined(__x86_64__)\n+#define SSE_VECTOR_BYTES 16\n+\n+/* Vectorized version of check_refname_format. */\n+int check_refname_format(const char *refname, int flags)\n+{\n+\tconst char *cp = refname;\n+\n+\tconst __m128i dot = _mm_set1_epi8('.');\n+\tconst __m128i at = _mm_set1_epi8('@');\n+\tconst __m128i curly = _mm_set1_epi8('{');\n+\tconst __m128i slash = _mm_set1_epi8('/');\n+\tconst __m128i zero = _mm_set1_epi8('\\000');\n+\tconst __m128i el = _mm_set1_epi8('l');\n+\n+\t/* below '*', all characters are forbidden or rare */\n+\tconst __m128i star_ub = _mm_set1_epi8('*' + 1);\n+\n+\tconst __m128i colon = _mm_set1_epi8(':');\n+\tconst __m128i question = _mm_set1_epi8('?');\n+\n+\t/* '['..'^' contains 4 characters: 3 forbidden and 1 rare */\n+\tconst __m128i bracket_lb = _mm_set1_epi8('[' - 1);\n+\tconst __m128i caret_ub = _mm_set1_epi8('^' + 1);\n+\n+\t/* '~' and above are forbidden */\n+\tconst __m128i tilde_lb = _mm_set1_epi8('~' - 1);\n+\n+\tint component_count = 0;\n+\n+\tif (refname[0] == 0 || refname[0] == '/') {\n+\t\t/* entirely empty ref or initial ref component */\n+\t\treturn -1;\n+\t}\n+\n+\t/*\n+\t * Initial ref component of '.'; below we look for /. so we'll\n+\t * miss this.\n+\t */\n+\tif (refname[0] == '.') {\n+\t\tif (refname[1] == '/' || refname[1] == '\\0')\n+\t\t\treturn -1;\n+\t\tif (!(flags & REFNAME_DOT_COMPONENT))\n+\t\t\treturn -1;\n+\t}\n+\twhile(1) {\n+\t\t__m128i tmp, tmp1, result;\n+\t\tuint64_t mask;\n+\n+\t\tif ((uintptr_t) cp % PAGE_SIZE > PAGE_SIZE - SSE_VECTOR_BYTES  - 1)\n+\t\t\t/*\n+\t\t\t * End-of-page; fall back to slow method for\n+\t\t\t * this entire ref.\n+\t\t\t */\n+\t\t\treturn check_refname_format_bytewise(refname, flags);\n+\n+\t\ttmp = _mm_loadu_si128((__m128i *)cp);\n+\t\ttmp1 = _mm_loadu_si128((__m128i *)(cp + 1));\n+\n+\t\t/*\n+\t\t * This range (note the lt) contains some\n+\t\t * permissible-but-rare characters (including all\n+\t\t * characters >= 128), which we handle later.  It also\n+\t\t * includes \\000.\n+\t\t */\n+\t\tresult = _mm_cmplt_epi8(tmp, star_ub);\n+\n+\t\tresult = _mm_or_si128(result, _mm_cmpeq_epi8(tmp, question));\n+\t\tresult = _mm_or_si128(result, _mm_cmpeq_epi8(tmp, colon));\n+\n+\t\t/* This range contains the permissible ] as bycatch */\n+\t\tresult = _mm_or_si128(result, _mm_and_si128(\n+\t\t\t\t\t      _mm_cmpgt_epi8(tmp, bracket_lb),\n+\t\t\t\t\t      _mm_cmplt_epi8(tmp, caret_ub)));\n+\n+\t\tresult = _mm_or_si128(result, _mm_cmpgt_epi8(tmp, tilde_lb));\n+\n+\t\t/* .. */\n+\t\tresult = _mm_or_si128(result, _mm_and_si128(\n+\t\t\t\t\t      _mm_cmpeq_epi8(tmp, dot),\n+\t\t\t\t\t      _mm_cmpeq_epi8(tmp1, dot)));\n+\t\t/* @{ */\n+\t\tresult = _mm_or_si128(result, _mm_and_si128(\n+\t\t\t\t\t      _mm_cmpeq_epi8(tmp, at),\n+\t\t\t\t\t      _mm_cmpeq_epi8(tmp1, curly)));\n+\t\t/* // */\n+\t\tresult = _mm_or_si128(result, _mm_and_si128(\n+\t\t\t\t\t      _mm_cmpeq_epi8(tmp, slash),\n+\t\t\t\t\t      _mm_cmpeq_epi8(tmp1, slash)));\n+\t\t/* trailing / */\n+\t\tresult = _mm_or_si128(result, _mm_and_si128(\n+\t\t\t\t\t      _mm_cmpeq_epi8(tmp, slash),\n+\t\t\t\t\t      _mm_cmpeq_epi8(tmp1, zero)));\n+\t\t/* .l, beginning of .lock */\n+\t\tresult = _mm_or_si128(result, _mm_and_si128(\n+\t\t\t\t\t      _mm_cmpeq_epi8(tmp, dot),\n+\t\t\t\t\t      _mm_cmpeq_epi8(tmp1, el)));\n+\t\t/*\n+\t\t * Even though /. is not necessarily an error, we flag\n+\t\t * it anyway. If we find it, we'll check if it's valid\n+\t\t * and if so we'll advance just past it.\n+\t\t */\n+\t\tresult = _mm_or_si128(result, _mm_and_si128(\n+\t\t\t\t\t      _mm_cmpeq_epi8(tmp, slash),\n+\t\t\t\t\t      _mm_cmpeq_epi8(tmp1, dot)));\n+\n+\t\tmask = _mm_movemask_epi8(result);\n+\t\tif (mask) {\n+\t\t\t/*\n+\t\t\t * We've found either end-of-string, or some\n+\t\t\t * probably-bad character or substring.\n+\t\t\t */\n+\t\t\tint i = __builtin_ctz(mask);\n+\t\t\tswitch (refname_disposition[cp[i] & 255]) {\n+\t\t\tcase 0: /* fall-through */\n+\t\t\tcase 5:\n+\t\t\t\t/*\n+\t\t\t\t * bycatch: a good character that's in\n+\t\t\t\t * one of the ranges of mostly-forbidden\n+\t\t\t\t * characters\n+\t\t\t\t */\n+\t\t\t\tcp += i + 1;\n+\t\t\t\tbreak;\n+\t\t\tcase 1:\n+\t\t\t\tif (cp[i + 1] == '{')\n+\t\t\t\t\treturn -1;\n+\t\t\t\tcp += i + 1;\n+\t\t\t\tbreak;\n+\t\t\tcase 2:\n+\t\t\t\tif (!(flags & REFNAME_ALLOW_ONELEVEL)\n+\t\t\t\t    && !component_count && !strchr(refname, '/'))\n+\t\t\t\t\t/* Refname has only one component. */\n+\t\t\t\t\treturn -1;\n+\t\t\t\treturn 0;\n+\t\t\tcase 3:\n+\t\t\t\tcomponent_count ++;\n+\t\t\t\t/*\n+\t\t\t\t * Even if leading dots are allowed, don't\n+\t\t\t\t * allow \".\" as a component (\"..\" is\n+\t\t\t\t * prevented by case 4 below).\n+\t\t\t\t */\n+\t\t\t\tif (cp[i + 1] == '.') {\n+\t\t\t\t\tif (cp[i + 2] == '\\0')\n+\t\t\t\t\t\treturn -1;\n+\t\t\t\t\tif (flags & REFNAME_DOT_COMPONENT) {\n+\t\t\t\t\t\t/* skip to just after the /. */\n+\t\t\t\t\t\tcp += i + 2;\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\t}\n+\t\t\t\t\treturn -1;\n+\t\t\t\t} else if (cp[i + 1] == '/' || cp[i + 1] == '\\0')\n+\t\t\t\t\treturn -1;\n+\t\t\t\tbreak;\n+\t\t\tcase 4:\n+\t\t\t\tif (cp[i + 1] == '.' || cp[i + 1] == '\\0')\n+\t\t\t\t\treturn -1;\n+\t\t\t\t/* .lock as end-of-component or end-of-string */\n+\t\t\t\tif ((!strncmp(cp + i, \".lock\", 5))\n+\t\t\t\t    && (cp[i + 5] == '/' || cp[i + 5] == 0))\n+\t\t\t\t\treturn -1;\n+\t\t\t\tcp += 1;\n+\t\t\t\tbreak;\n+\t\t\tcase 6:\n+\t\t\t\tif (((cp == refname + i) || cp[i - 1] == '/')\n+\t\t\t\t    && (cp[i + 1] == '/' || cp[i + 1] == 0))\n+\t\t\t\t\tif (flags & REFNAME_REFSPEC_PATTERN) {\n+\t\t\t\t\t\tflags &= ~REFNAME_REFSPEC_PATTERN;\n+\t\t\t\t\t\t/* restart after the * */\n+\t\t\t\t\t\tcp += i + 1;\n+\t\t\t\t\t\tcontinue;\n+\t\t\t\t\t}\n+\t\t\t\t/* fall-through */\n+\t\t\tcase 7:\n+\t\t\t\treturn -1;\n+\t\t\t}\n+\t\t} else\n+\t\t\tcp += SSE_VECTOR_BYTES;\n+\t}\n+}\n+\n+#else\n+\n+int check_refname_format (const char *refname, int flags)\n+{\n+\treturn check_refname_format_bytewise(refname, flags);\n+}\n+\n+#endif\n+\n struct ref_entry;\n \n /*\ndiff --git a/t/t1402-check-ref-format.sh b/t/t1402-check-ref-format.sh\nindex 1a5a5f3..9aeb352 100755\n--- a/t/t1402-check-ref-format.sh\n+++ b/t/t1402-check-ref-format.sh\n@@ -64,6 +64,7 @@ valid_ref \"$(printf 'heads/fu\\303\\237')\"\n invalid_ref 'heads/*foo/bar' --refspec-pattern\n invalid_ref 'heads/foo*/bar' --refspec-pattern\n invalid_ref 'heads/f*o/bar' --refspec-pattern\n+invalid_ref 'heads/foo*//bar' --refspec-pattern\n \n ref='foo'\n invalid_ref \"$ref\"\n@@ -128,6 +129,20 @@ valid_ref NOT_MINGW \"$ref\" '--allow-onelevel --normalize'\n invalid_ref NOT_MINGW \"$ref\" '--refspec-pattern --normalize'\n valid_ref NOT_MINGW \"$ref\" '--refspec-pattern --allow-onelevel --normalize'\n \n+\n+valid_ref 'refs/heads/a-very-long-refname'\n+invalid_ref 'refs/heads/.a-very-long-refname'\n+invalid_ref 'refs/heads/abcdefgh0123..'\n+invalid_ref 'refs/heads/abcdefgh01234..'\n+invalid_ref 'refs/heads/abcdefgh012345..'\n+invalid_ref 'refs/heads/abcdefgh0123456..'\n+invalid_ref 'refs/heads/abcdefgh01234567..'\n+valid_ref 'refs/heads/abcdefgh0123.a'\n+valid_ref 'refs/heads/abcdefgh01234.a'\n+valid_ref 'refs/heads/abcdefgh012345.a'\n+valid_ref 'refs/heads/abcdefgh0123456.a'\n+valid_ref 'refs/heads/abcdefgh01234567.a'\n+\n test_expect_success \"check-ref-format --branch @{-1}\" '\n \tT=$(git write-tree) &&\n \tsha1=$(echo A | git commit-tree $T) &&\ndiff --git a/t/valgrind/default.supp b/t/valgrind/default.supp\nindex 0a6724f..332ab1a 100644\n--- a/t/valgrind/default.supp\n+++ b/t/valgrind/default.supp\n@@ -49,3 +49,11 @@\n \tMemcheck:Addr4\n \tfun:copy_ref\n }\n+{\n+\tignore-sse-check_refname_format\n+\tMemcheck:Addr8\n+\tfun:check_refname_format\n+\tfun:cmd_check_ref_format\n+\tfun:handle_builtin\n+\tfun:main\n+}\n-- \n2.0.0.rc1.24.g9a2fcb5\n"}]}