{"thread":{"id":"36938","subject":"(unknown)","startedAt":"2014-06-17T17:13:18Z","lastAt":"2014-06-17T18:07:13Z","messageCount":4,"participants":["David Turner","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"244456","messageId":"1403025199-21360-1-git-send-email-dturner@twitter.com","threadId":"36938","inReplyTo":null,"subject":"(unknown)","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-06-17T17:13:18Z","receivedAt":"2014-06-17T17:13:18Z","isPatch":false,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"\nThis version changes only the commit message; there is no longer any\nconfigure.ac code.\n"},{"id":"244457","messageId":"1403025199-21360-2-git-send-email-dturner@twitter.com","threadId":"36938","inReplyTo":"1403025199-21360-1-git-send-email-dturner@twitter.com","subject":"[PATCH v10 1/1] refs.c: SSE2 optimizations for check_refname_component","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-06-17T17:13:19Z","receivedAt":"2014-06-17T17:13:19Z","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             | 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":"244464","messageId":"xmqq8uovmn0d.fsf@gitster.dls.corp.google.com","threadId":"36938","inReplyTo":"1403025199-21360-2-git-send-email-dturner@twitter.com","subject":"Re: [PATCH v10 1/1] refs.c: SSE2 optimizations for check_refname_component","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-06-17T18:03:46Z","receivedAt":"2014-06-17T18:03:46Z","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> Optimize check_refname_component using SSE2 on x86_64.\n>\n> git rev-parse HEAD is a good test-case for this, since it does almost\n> nothing except parse refs.  For one particular repo with about 60k\n> refs, almost all packed, the timings are:\n>\n> Look up table: 29 ms\n> SSE2:          23 ms\n>\n> This cuts about 20% off of the runtime.\n>\n> Ondřej Bílka <neleai@seznam.cz> suggested an SSE2 approach to the\n> substring searches, which netted a speed boost over the SSE4.2 code I\n> had initially written.\n>\n> Signed-off-by: David Turner <dturner@twitter.com>\n> ---\n\nWhen applied on top of your dde8a902 (refs.c: optimize\ncheck_refname_component(), 2014-06-03), this seems to fail t1402 for\nme.\n\nTest Summary Report\n-------------------\nt1402-check-ref-format.sh (Wstat: 256 Tests: 93 Failed: 9)\n  Failed tests:  28, 36, 38, 40, 63, 75, 77, 85-86\n  Non-zero exit status: 1\n\n#28 is the one that runs \"check-ref-format heads/v@{ation\".\n"},{"id":"244465","messageId":"1403028433.5629.94.camel@stross","threadId":"36938","inReplyTo":"xmqq8uovmn0d.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH v10 1/1] refs.c: SSE2 optimizations for check_refname_component","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-06-17T18:07:13Z","receivedAt":"2014-06-17T18:07:13Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Tue, 2014-06-17 at 11:03 -0700, Junio C Hamano wrote:\n> David Turner <dturner@twopensource.com> writes:\n> \n> > Optimize check_refname_component using SSE2 on x86_64.\n> >\n> > git rev-parse HEAD is a good test-case for this, since it does almost\n> > nothing except parse refs.  For one particular repo with about 60k\n> > refs, almost all packed, the timings are:\n> >\n> > Look up table: 29 ms\n> > SSE2:          23 ms\n> >\n> > This cuts about 20% off of the runtime.\n> >\n> > Ondřej Bílka <neleai@seznam.cz> suggested an SSE2 approach to the\n> > substring searches, which netted a speed boost over the SSE4.2 code I\n> > had initially written.\n> >\n> > Signed-off-by: David Turner <dturner@twitter.com>\n> > ---\n> \n> When applied on top of your dde8a902 (refs.c: optimize\n> check_refname_component(), 2014-06-03), this seems to fail t1402 for\n> me.\n> \n> Test Summary Report\n> -------------------\n> t1402-check-ref-format.sh (Wstat: 256 Tests: 93 Failed: 9)\n>   Failed tests:  28, 36, 38, 40, 63, 75, 77, 85-86\n>   Non-zero exit status: 1\n> \n> #28 is the one that runs \"check-ref-format heads/v@{ation\".\n\nOops, I didn't even notice that test!  I was looking only at t5511!\nWill fix.\n"}]}