{"thread":{"id":"36931","subject":"[PATCH v8] refs.c: SSE2 optimizations for check_refname_component","startedAt":"2014-06-16T19:22:46Z","lastAt":"2014-06-17T00:51:57Z","messageCount":3,"participants":["David Turner","Junio C Hamano"],"isPatch":true,"patchVersion":8,"patchTotal":null},"messages":[{"id":"244338","messageId":"1402946566-14923-1-git-send-email-dturner@twitter.com","threadId":"36931","inReplyTo":null,"subject":"[PATCH v8] refs.c: SSE2 optimizations for check_refname_component","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-06-16T19:22:46Z","receivedAt":"2014-06-16T19:22:46Z","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  |  10 +++\n refs.c             | 244 +++++++++++++++++++++++++++++++++++++++++++++--------\n t/t5511-refspec.sh |  19 +++++\n 3 files changed, 239 insertions(+), 34 deletions(-)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex f6d3a46..291d46b 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -668,6 +668,16 @@ 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+/* 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..4c39af7 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -8,22 +8,43 @@\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+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@@ -33,8 +54,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,47 +68,32 @@ 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\treturn check_refname_component_trailer(cp, refname, flags);\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 \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-\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-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 +122,175 @@ 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+\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/* Initial ref component of '.'; below we look for /. so we'll\n+\t * miss this. */\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/* End-of-page; fall back to slow method for\n+\t\t\t * this entire ref. */\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/*\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/* We've found either end-of-string, or some\n+\t\t\t   probably-bad character or substring. */\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\tcontinue;\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\tcontinue;\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\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+\tif (cp - refname >= 5 && !memcmp(cp - 5, \".lock\", 5))\n+\t\treturn -1; /* Refname ends with \".lock\". */\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..ef0f095 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,8 @@ 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+\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 +94,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":"244369","messageId":"xmqqha3ko0vs.fsf@gitster.dls.corp.google.com","threadId":"36931","inReplyTo":"1402946566-14923-1-git-send-email-dturner@twitter.com","subject":"Re: [PATCH v8] refs.c: SSE2 optimizations for check_refname_component","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-06-17T00:06:31Z","receivedAt":"2014-06-17T00:06:31Z","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> The configure.ac changes include code from the GNU C Library written\n> by Joseph S. Myers <joseph at codesourcery dot com>.\n>\n> Ondřej Bílka <neleai@seznam.cz> suggested an SSE2 approach to the\n\nOne e-mail address is obfuscated while the other not; intended?\n\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> diff --git a/git-compat-util.h b/git-compat-util.h\n> index f6d3a46..291d46b 100644\n> --- a/git-compat-util.h\n> +++ b/git-compat-util.h\n> @@ -668,6 +668,16 @@ 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> +/* This is the system memory page size; it's used so that we can read\n\nStyle (there are other instances of the same kind).\n\n/*\n * This is the ...\n\n> + * outside the bounds of an allocation without segfaulting.\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\nThis is merely a moved code that retained the same comment, but it\nis more like \"the current refname component ends with .lock\", I\nsuspect.  In other words, we do not allow \"refs/heads/foo.lock/bar\".\nAm I reading the patch correctly?\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\nStyle (there are other instances of the same kind).  No SP between\nfunction/macro name and opening parenthesis.\n\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\nOK, so we make sure we do not overrun by reading too much near the\nend of the page, as the next page might be unmapped.\n\nI am showing my ignorance but does cp (i.e. refname) upon entry to\nthis function need to be aligned in some way?\n\nThanks.\n"},{"id":"244372","messageId":"1402966317.5629.93.camel@stross","threadId":"36931","inReplyTo":"xmqqha3ko0vs.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH v8] refs.c: SSE2 optimizations for check_refname_component","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-06-17T00:51:57Z","receivedAt":"2014-06-17T00:51:57Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Mon, 2014-06-16 at 17:06 -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> > The configure.ac changes include code from the GNU C Library written\n> > by Joseph S. Myers <joseph at codesourcery dot com>.\n> >\n> > Ondřej Bílka <neleai@seznam.cz> suggested an SSE2 approach to the\n> \n> One e-mail address is obfuscated while the other not; intended?\n\nYes (although I'll happily obfuscate or remove Ondřej's if he prefers);\nJoseph's was obfuscated because that's how I found it in the source\nmaterial.\n\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> > diff --git a/git-compat-util.h b/git-compat-util.h\n> > index f6d3a46..291d46b 100644\n> > --- a/git-compat-util.h\n> > +++ b/git-compat-util.h\n> > @@ -668,6 +668,16 @@ 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> > +/* This is the system memory page size; it's used so that we can read\n> \n> Style (there are other instances of the same kind).\n\nWill fix.\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> \n> This is merely a moved code that retained the same comment, but it\n> is more like \"the current refname component ends with .lock\", I\n> suspect.  In other words, we do not allow \"refs/heads/foo.lock/bar\".\n> Am I reading the patch correctly?\n\nThis code didn't actually need to be moved; I'll move it back.\n\nBut it now occurs to me that the SSE2 code does not actually check\nfor .lock at the end of each component, but only at the end of string.\n\nI don't know why we don't allow refs/heads/foo.lock/bar.  I can\nunderstand not allowing refs/heads/foo.lock, since it might be a lock\nfile.  But I have never heard of a lock directory like this. \n\nI'm happy to replicate what the existing code does, but do you think it\nis correct?\n\n> Style (there are other instances of the same kind).  No SP between\n> function/macro name and opening parenthesis.\n\nWill fix.\n\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> \n> OK, so we make sure we do not overrun by reading too much near the\n> end of the page, as the next page might be unmapped.\n\nExactly.\n\n> I am showing my ignorance but does cp (i.e. refname) upon entry to\n> this function need to be aligned in some way?\n\nNope -- _mm_loadu_si128 does an unaligned load.\n"}]}