{"thread":{"id":"36934","subject":"[PATCH v9] refs.c: SSE2 optimizations for check_refname_component","startedAt":"2014-06-17T03:10:42Z","lastAt":"2014-06-17T17:35:43Z","messageCount":2,"participants":["David Turner","Junio C Hamano"],"isPatch":true,"patchVersion":9,"patchTotal":null},"messages":[{"id":"244375","messageId":"1402974642-13808-1-git-send-email-dturner@twitter.com","threadId":"36934","inReplyTo":null,"subject":"[PATCH v9] refs.c: SSE2 optimizations for check_refname_component","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-06-17T03:10:42Z","receivedAt":"2014-06-17T03:10: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\nThe configure.ac changes include code from the GNU C Library written\nby Joseph S. Myers <joseph at codesourcery dot com>.\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             | 223 ++++++++++++++++++++++++++++++++++++++++++++++++-----\n t/t5511-refspec.sh |  20 +++++\n 3 files changed, 236 insertions(+), 18 deletions(-)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex f6d3a46..0aec58e 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -668,6 +668,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 46139d2..5c2f68b 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -8,20 +8,22 @@\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 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: \\0: End-of-component and string\n+ * 2: /: End-of-component\n+ * 3: ., look for a preceding . to reject .. in refs\n+ * 4: {, look for a preceding @ to reject @{ in refs\n+ * 5: *, usually a bad character except, once as a wildcard\n+ * 6: 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+\t1, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,\n+\t6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,\n+\t6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 3, 2,\n+\t0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 6,\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, 6, 6, 0, 6, 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, 4, 0, 0, 6, 6\n };\n \n /*\n@@ -33,8 +35,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 +49,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\t\tgoto out;\n+\t\tcase 1: /* fall-through */\n \t\tcase 2:\n+\t\t\tgoto out;\n+\t\tcase 3:\n \t\t\tif (last == '.')\n \t\t\t\treturn -1; /* Refname contains \"..\". */\n \t\t\tbreak;\n-\t\tcase 3:\n+\t\tcase 4:\n \t\t\tif (last == '@')\n \t\t\t\treturn -1; /* Refname contains \"@{\". */\n \t\t\tbreak;\n-\t\tcase 4:\n+\t\tcase 5: /* fall-through */\n+\t\tcase 6:\n \t\t\treturn -1;\n \t\t}\n \t\tlast = ch;\n@@ -79,14 +84,13 @@ 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 \tif (!strcmp(refname, \"@\"))\n \t\t/* Refname is a single character '@'. */\n \t\treturn -1;\n-\n \twhile (1) {\n \t\t/* We are at the start of a path component. */\n \t\tcomponent_len = check_refname_component(refname, flags);\n@@ -115,6 +119,189 @@ 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+\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:\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\tcp += i;\n+\t\t\t\tgoto success;\n+\t\t\tcase 2:\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 3 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 3:\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 4:\n+\t\t\t\tif (cp[i + 1] == '{')\n+\t\t\t\t\treturn -1;\n+\t\t\t\tbreak;\n+\t\t\tcase 5:\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 6:\n+\t\t\t\treturn -1;\n+\t\t\t}\n+\t\t} else\n+\t\t\tcp += SSE_VECTOR_BYTES;\n+\t}\n+success:\n+\treturn 0;\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/t5511-refspec.sh b/t/t5511-refspec.sh\nindex de6db86..51d23b1 100755\n--- a/t/t5511-refspec.sh\n+++ b/t/t5511-refspec.sh\n@@ -29,6 +29,10 @@ test_refspec push '+:'\n test_refspec fetch ''\n test_refspec fetch ':'\n test_refspec fetch '::'\t\t\t\t\t\tinvalid\n+test_refspec fetch '.'\t\t\t\t\t\tinvalid\n+test_refspec fetch './frotz'\t\t\t\t\tinvalid\n+test_refspec fetch 'refs/.'\t\t\t\t\tinvalid\n+test_refspec push '*//:refs/remotes/frotz/*'\t\t\tinvalid\n \n test_refspec push 'refs/heads/*:refs/remotes/frotz/*'\n test_refspec push 'refs/heads/*:refs/remotes/frotz'\t\tinvalid\n@@ -71,6 +75,9 @@ test_refspec fetch ':refs/remotes/frotz/HEAD-to-me'\n test_refspec push ':refs/remotes/frotz/delete me'\t\tinvalid\n test_refspec fetch ':refs/remotes/frotz/HEAD to me'\t\tinvalid\n \n+test_refspec fetch ':refs/remotes/frotz/something.lock'\t\tinvalid\n+test_refspec fetch ':refs/remotes/frotz/a.lock/b'\t\tinvalid\n+\n test_refspec fetch 'refs/heads/*/for-linus:refs/remotes/mine/*-blah' invalid\n test_refspec push 'refs/heads/*/for-linus:refs/remotes/mine/*-blah' invalid\n \n@@ -88,4 +95,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.24.g0588c94.dirty\n"},{"id":"244460","messageId":"xmqqk38fmob4.fsf@gitster.dls.corp.google.com","threadId":"36934","inReplyTo":"1402974642-13808-1-git-send-email-dturner@twitter.com","subject":"Re: [PATCH v9] refs.c: SSE2 optimizations for check_refname_component","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-06-17T17:35:43Z","receivedAt":"2014-06-17T17:35:43Z","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>  git-compat-util.h  |  11 +++\n>  refs.c             | 223 ++++++++++++++++++++++++++++++++++++++++++++++++-----\n>  t/t5511-refspec.sh |  20 +++++\n>  3 files changed, 236 insertions(+), 18 deletions(-)\n\nHmph, on what branch are you basing your patch?  As a follow-up to\nyour dde8a902 (refs.c: optimize check_refname_component(),\n2014-06-03) I originally tried to apply it on top of it but it does\nnot seem that the patch is based on that version; nor I have a blob\n46139d2 on which the patch claims your refs.c changes are based on.\n\n... goes and looks ...\n\nAhh, I think I know where it is broken.\n\n> diff --git a/refs.c b/refs.c\n> index 46139d2..5c2f68b 100644\n> --- a/refs.c\n> +++ b/refs.c\n> ...\n> @@ -46,17 +49,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\nThere is a stylo here (missing SP after \"switch\"), which I already\nhave locally fixed before pushing it out on 'next'.  I'll fix up\nthis patch and try to apply.\n\nThanks.\n"}]}