{"thread":{"id":"36851","subject":"[PATCH v7 0/1] refs.c: SSE4.2 optimizations for check_refname_component","startedAt":"2014-06-05T23:56:14Z","lastAt":"2014-06-15T05:53:40Z","messageCount":12,"participants":["David Turner","Junio C Hamano","Johannes Sixt","Torsten Bögershausen","Philip Oakley","Ondřej Bílka"],"isPatch":true,"patchVersion":7,"patchTotal":1},"messages":[{"id":"243438","messageId":"1402012575-16546-1-git-send-email-dturner@twitter.com","threadId":"36851","inReplyTo":null,"subject":"[PATCH v7 0/1] refs.c: SSE4.2 optimizations for check_refname_component","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-06-05T23:56:14Z","receivedAt":"2014-06-05T23:56:14Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"Since Junio has picked up the first patch from previous versions of\nthis series, I'm just going to send the second (SSE) one. I decided\nnot to s/NO_SSE42/!HAVE_SSE42/ because it looks like git mostly uses\nthe former convention (for instance, that's what GIT_PARSE_WITH\ngenerates).\n\nThanks for all of the comments so far.\n"},{"id":"243439","messageId":"1402012575-16546-2-git-send-email-dturner@twitter.com","threadId":"36851","inReplyTo":"1402012575-16546-1-git-send-email-dturner@twitter.com","subject":"[PATCH v7 1/1] refs.c: SSE4.2 optimizations for check_refname_component","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-06-05T23:56:15Z","receivedAt":"2014-06-05T23:56:15Z","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 .\n\nOnly supports GCC and Clang at present, because C interfaces to the\ncpuid instruction are not well-standardized.\n\nSigned-off-by: David Turner \n---\n Makefile | 6 +++\n aclocal.m4 | 6 +++\n compat/cpuid.h | 25 +++++++++\n configure.ac | 17 ++++++\n git-compat-util.h | 23 ++++++++\n refs.c | 150 +++++++++++++++++++++++++++++++++++++++++++++++------\n t/t5511-refspec.sh | 13 +++++\n 7 files changed, 225 insertions(+), 15 deletions(-)\n create mode 100644 compat/cpuid.h\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 \n #include ])\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/compat/cpuid.h b/compat/cpuid.h\nnew file mode 100644\nindex 0000000..7709e35\n--- /dev/null\n+++ b/compat/cpuid.h\n@@ -0,0 +1,25 @@\n+#ifndef COMPAT_CPUID_H\n+#define COMPAT_CPUID_H\n+\n+#if (defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__)))\n+#include \n+#define CPUID_SSE42_BIT (1 << 20)\n+\n+static int processor_supports_sse42(void)\n+{\n+\tunsigned eax, ebx, ecx, edx;\n+\t__cpuid(1, eax, ebx, ecx, edx);\n+\treturn ecx & CPUID_SSE42_BIT;\n+}\n+\n+#else\n+\n+static int processor_supports_sse42(void)\n+{\n+\t/* TODO: handle CPUID on non-GCC compilers */\n+\treturn 0;\n+}\n+\n+#endif\n+\n+#endif /* COMPAT_CPUID_H */\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..2c66d6d 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -668,6 +668,29 @@ void git_qsort(void *base, size_t nmemb, size_t size,\n #endif\n #endif\n \n+#ifndef NO_SSE42\n+#include \n+#include \"compat/cpuid.h\"\n+/*\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+ */\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.\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..b3bd333 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_bytewise(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,24 +80,125 @@ 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+}\n+\n+#if defined(NO_SSE42) || !(defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__)))\n+#define check_refname_component check_refname_component_bytewise\n+#else\n+#define SSE_VECTOR_BYTES 16\n+\n+/* Vectorized version of check_refname_component */\n+static int check_refname_component_sse42(const char *refname, int flags)\n+{\n+\tconst __m128i *refname_vec = (__m128i*) refname;\n+\n+\t/* Character ranges for characters forbidden in refs; see 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 = SSE_VECTOR_BYTES, atcurlypos = SSE_VECTOR_BYTES;\n+\tfor (vp = refname_vec; ; vp++) {\n+\t\t__m128i tmp;\n+\t\tint endpos;\n+\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 * Handle case of forbidden substrings .. and @{ crossing\n+\t\t * sixteen-byte boundaries\n \t\t */\n-\t\tif (refname[1] == '\\0')\n-\t\t\treturn -1; /* Component equals \".\". */\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) > PAGE_SIZE - SSE_VECTOR_BYTES)\n+\t\t\t/*\n+\t\t\t * End-of-page; fall back to slow method for\n+\t\t\t * this entire component.\n+\t\t\t */\n+\t\t\treturn check_refname_component_bytewise(refname, flags);\n+\n+\t\ttmp = _mm_lddqu_si128(vp);\n+\n+\t\t/*\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\t */\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, SSE_VECTOR_BYTES, 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 < SSE_VECTOR_BYTES) {\n+\t\t\tcp = ((const char*) vp) + endpos;\n+\t\t\tbreak;\n+\t\t}\n+\t\tcp = (const char*) vp + SSE_VECTOR_BYTES;\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+\n+static void* find_check_refname_component(void)\n+{\n+\tif (processor_supports_sse42())\n+\t\treturn check_refname_component_sse42;\n+\telse\n+\t\treturn check_refname_component_bytewise;\n }\n \n+#ifdef __clang__\n+\n+static int check_refname_component_autodetect(const char *refname, int flags);\n+\n+static int (*check_refname_component)(const char *, int) = check_refname_component_autodetect;\n+\n+/*\n+ * On the first run of check_refname_component, autodetect the correct\n+ * version for this CPU. This is necessary because Clang doesn't support\n+ * ifunc.\n+ */\n+static int check_refname_component_autodetect(const char *refname, int flags)\n+{\n+\tcheck_refname_component = find_check_refname_component();\n+\treturn check_refname_component(refname, flags);\n+}\n+\n+#else\n+\n+static int check_refname_component(const char *refname, int flags)\n+\t__attribute__ ((ifunc (\"find_check_refname_component\")));\n+\n+#endif /* __clang__ */\n+\n+#endif /* NO_SSE42 */\n+\n int check_refname_format(const char *refname, int flags)\n {\n \tint component_len, component_count = 0;\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.24.g0588c94.dirty\n"},{"id":"243650","messageId":"xmqqfvjdenk5.fsf@gitster.dls.corp.google.com","threadId":"36851","inReplyTo":"1402012575-16546-1-git-send-email-dturner@twitter.com","subject":"Re: [PATCH v7 0/1] refs.c: SSE4.2 optimizations for check_refname_component","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-06-09T22:16:26Z","receivedAt":"2014-06-09T22:16:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Turner writes:\n\n> Since Junio has picked up the first patch from previous versions of\n> this series, I'm just going to send the second (SSE) one. I decided\n> not to s/NO_SSE42/!HAVE_SSE42/ because it looks like git mostly uses\n> the former convention (for instance, that's what GIT_PARSE_WITH\n> generates).\n\nYeah but NO_FROTZ is used only when FROTZ is something everybody is\nexpected to have (e.g. it's in posix, people ought to have it, but\nwe do support those who don't), isn't it? For a very arch specific\nstuff like sse42, I'd feel better to make it purely opt-in by\nforcing people to explicitly say HAVE_SSE42 to enable it.\n"},{"id":"243671","messageId":"1402353543.18134.203.camel@stross","threadId":"36851","inReplyTo":"xmqqfvjdenk5.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH v7 0/1] refs.c: SSE4.2 optimizations for check_refname_component","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-06-09T22:39:03Z","receivedAt":"2014-06-09T22:39:03Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Mon, 2014-06-09 at 15:16 -0700, Junio C Hamano wrote:\n> David Turner writes:\n> \n> > Since Junio has picked up the first patch from previous versions of\n> > this series, I'm just going to send the second (SSE) one. I decided\n> > not to s/NO_SSE42/!HAVE_SSE42/ because it looks like git mostly uses\n> > the former convention (for instance, that's what GIT_PARSE_WITH\n> > generates).\n> \n> Yeah but NO_FROTZ is used only when FROTZ is something everybody is\n> expected to have (e.g. it's in posix, people ought to have it, but\n> we do support those who don't), isn't it? For a very arch specific\n> stuff like sse42, I'd feel better to make it purely opt-in by\n> forcing people to explicitly say HAVE_SSE42 to enable it.\n\nThe patch now has two kinds of autodetection:\n\n1. At build-time, we check for the compiler supporting -msse4.2. If it\ndoes, and if the user has not explicitly done --without-sse, then we\nbuild with SSE support. This does not mean that the SSE code will\nnecessarily be used because:\n2. At run-time, if we have built with SSE support, we check cpuid to\nchoose a version of the function that will run on the current CPU.\n\nSo I think we never hit a case where we try to use SSE and fail, which\nis the major reason I see to make it non-default.\n\nTo me, this means that we should not require people to explicitly\nrequest SSE, because we generally want to try to provide the\nmost-efficient version of git that will work everywhere. In fact, I am\nnot sure we need a --without-sse option at all, since all it saves is a\ncpuid instruction. But I don't need to remove the option, in case\nthere's a use for it I'm not thinking of.\n"},{"id":"243673","messageId":"xmqqvbs9d6qn.fsf@gitster.dls.corp.google.com","threadId":"36851","inReplyTo":"xmqqfvjdenk5.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH v7 0/1] refs.c: SSE4.2 optimizations for check_refname_component","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-06-09T23:05:04Z","receivedAt":"2014-06-09T23:05:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> David Turner writes:\n>\n>> Since Junio has picked up the first patch from previous versions of\n>> this series, I'm just going to send the second (SSE) one. I decided\n>> not to s/NO_SSE42/!HAVE_SSE42/ because it looks like git mostly uses\n>> the former convention (for instance, that's what GIT_PARSE_WITH\n>> generates).\n>\n> Yeah but NO_FROTZ is used only when FROTZ is something everybody is\n> expected to have (e.g. it's in posix, people ought to have it, but\n> we do support those who don't), isn't it? For a very arch specific\n> stuff like sse42, I'd feel better to make it purely opt-in by\n> forcing people to explicitly say HAVE_SSE42 to enable it.\n\nJust FYI: I am getting\n\ncompat/cpuid.h:8:12: error: 'processor_supports_sse42' defined but\nnot used [-Werror=unused-function]\ncc1: all warnings being treated as errors\n\nwhile building 'pu'; I'll have to rebuild 'pu' without this patch\nbefore I can push the day's result out.\n"},{"id":"243707","messageId":"53969FDF.3050506@viscovery.net","threadId":"36851","inReplyTo":"xmqqvbs9d6qn.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH v7 0/1] refs.c: SSE4.2 optimizations for check_refname_component","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2014-06-10T06:04:15Z","receivedAt":"2014-06-10T06:04:15Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 6/10/2014 1:05, schrieb Junio C Hamano:\n> Junio C Hamano writes:\n> \n>> David Turner writes:\n>>\n>>> Since Junio has picked up the first patch from previous versions of\n>>> this series, I'm just going to send the second (SSE) one. I decided\n>>> not to s/NO_SSE42/!HAVE_SSE42/ because it looks like git mostly uses\n>>> the former convention (for instance, that's what GIT_PARSE_WITH\n>>> generates).\n>>\n>> Yeah but NO_FROTZ is used only when FROTZ is something everybody is\n>> expected to have (e.g. it's in posix, people ought to have it, but\n>> we do support those who don't), isn't it? For a very arch specific\n>> stuff like sse42, I'd feel better to make it purely opt-in by\n>> forcing people to explicitly say HAVE_SSE42 to enable it.\n> \n> Just FYI: I am getting\n> \n> compat/cpuid.h:8:12: error: 'processor_supports_sse42' defined but\n> not used [-Werror=unused-function]\n> cc1: all warnings being treated as errors\n> \n> while building 'pu'; I'll have to rebuild 'pu' without this patch\n> before I can push the day's result out.\n\nAnd I get this when I compile on Windows with msysgit:\n\n CC abspath.o\nIn file included from git-compat-util.h:694,\n from cache.h:4,\n from abspath.c:1:\ncompat/cpuid.h: In function 'processor_supports_sse42':\ncompat/cpuid.h:11: warning: implicit declaration of function '__cpuid'\nabspath.c: At top level:\ncompat/cpuid.h:8: warning: 'processor_supports_sse42' defined but not used\nabspath.c: In function 'processor_supports_sse42':\ncompat/cpuid.h:11: warning: 'eax' is used uninitialized in this function\ncompat/cpuid.h:11: warning: 'ebx' is used uninitialized in this function\ncompat/cpuid.h:11: warning: 'ecx' is used uninitialized in this function\ncompat/cpuid.h:11: warning: 'edx' is used uninitialized in this function\n\nPerhaps our gcc is too old?\n\n-- Hannes\n"},{"id":"243710","messageId":"xmqqfvjdb6en.fsf@gitster.dls.corp.google.com","threadId":"36851","inReplyTo":"53969FDF.3050506@viscovery.net","subject":"Re: [PATCH v7 0/1] refs.c: SSE4.2 optimizations for check_refname_component","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-06-10T06:55:12Z","receivedAt":"2014-06-10T06:55:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Sixt writes:\n\n> And I get this when I compile on Windows with msysgit:\n>\n> CC abspath.o\n> In file included from git-compat-util.h:694,\n> from cache.h:4,\n> from abspath.c:1:\n> compat/cpuid.h: In function 'processor_supports_sse42':\n> compat/cpuid.h:11: warning: implicit declaration of function '__cpuid'\n> abspath.c: At top level:\n> compat/cpuid.h:8: warning: 'processor_supports_sse42' defined but not used\n> abspath.c: In function 'processor_supports_sse42':\n> compat/cpuid.h:11: warning: 'eax' is used uninitialized in this function\n> compat/cpuid.h:11: warning: 'ebx' is used uninitialized in this function\n> compat/cpuid.h:11: warning: 'ecx' is used uninitialized in this function\n> compat/cpuid.h:11: warning: 'edx' is used uninitialized in this function\n>\n> Perhaps our gcc is too old?\n\nMaybe.\n\nIn any case, it is a good indication that it probably is a good idea\nto start with an optional USE_SSE42 (not !NO_SSE42 or HAVE_SSE42) so\nthat it is clear to anybody that those with SSE42 does not have to\nuse this compilation option. Once the code proves itself, we can\nconsider turning it on by default when able, but it seems that it is\na bit too premature for that (not that the code itself is premature\nin the original author's environment, but its portability has not\nbeen quite ready for everybody yet, it seems).\n"},{"id":"244048","messageId":"1402622313.5629.45.camel@stross","threadId":"36851","inReplyTo":"53969FDF.3050506@viscovery.net","subject":"Re: [PATCH v7 0/1] refs.c: SSE4.2 optimizations for check_refname_component","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-06-13T01:18:33Z","receivedAt":"2014-06-13T01:18:33Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Tue, 2014-06-10 at 08:04 +0200, Johannes Sixt wrote:\n> Am 6/10/2014 1:05, schrieb Junio C Hamano:\n> > Junio C Hamano writes:\n> > \n> >> David Turner writes:\n> >>\n> >>> Since Junio has picked up the first patch from previous versions of\n> >>> this series, I'm just going to send the second (SSE) one. I decided\n> >>> not to s/NO_SSE42/!HAVE_SSE42/ because it looks like git mostly uses\n> >>> the former convention (for instance, that's what GIT_PARSE_WITH\n> >>> generates).\n> >>\n> >> Yeah but NO_FROTZ is used only when FROTZ is something everybody is\n> >> expected to have (e.g. it's in posix, people ought to have it, but\n> >> we do support those who don't), isn't it? For a very arch specific\n> >> stuff like sse42, I'd feel better to make it purely opt-in by\n> >> forcing people to explicitly say HAVE_SSE42 to enable it.\n> > \n> > Just FYI: I am getting\n> > \n> > compat/cpuid.h:8:12: error: 'processor_supports_sse42' defined but\n> > not used [-Werror=unused-function]\n> > cc1: all warnings being treated as errors\n> > \n> > while building 'pu'; I'll have to rebuild 'pu' without this patch\n> > before I can push the day's result out.\n> \n> And I get this when I compile on Windows with msysgit:\n> \n> CC abspath.o\n> In file included from git-compat-util.h:694,\n> from cache.h:4,\n> from abspath.c:1:\n> compat/cpuid.h: In function 'processor_supports_sse42':\n> compat/cpuid.h:11: warning: implicit declaration of function '__cpuid'\n> abspath.c: At top level:\n> compat/cpuid.h:8: warning: 'processor_supports_sse42' defined but not used\n> abspath.c: In function 'processor_supports_sse42':\n> compat/cpuid.h:11: warning: 'eax' is used uninitialized in this function\n> compat/cpuid.h:11: warning: 'ebx' is used uninitialized in this function\n> compat/cpuid.h:11: warning: 'ecx' is used uninitialized in this function\n> compat/cpuid.h:11: warning: 'edx' is used uninitialized in this function\n> \n> Perhaps our gcc is too old?\n\nIt is too old for my patch because it doesn't support ifunc (and I\nsuspect that no version of GCC for Windows supports ifunc). But that\ndoes not seem to be what is going on in your error message. Instead,\nwhen we #include , we get compat/cpuid.h rather than the\nsystem's cpuid.h. When I rename compat/cpuid.h to something else (and\nadjust the code accordingly), and add a check for gcc 4.5+ and for\nWindows before using ifunc, then everything works.\n\nSo tomorrow, I'm going to send a new patch (which also fixes the\nwarnings Junio reported) which I've tested on Windows, GNU/Linux, and\nMac OS X. \n\nI'm testing on a Windows 8 VM from modern.ie with msysgit's\n\"netinstaller\" -- is that a reasonable test environment?\n"},{"id":"244052","messageId":"539A79F6.9020905@web.de","threadId":"36851","inReplyTo":"1402622313.5629.45.camel@stross","subject":"Re: [PATCH v7 0/1] refs.c: SSE4.2 optimizations for check_refname_component","fromName":"Torsten Bögershausen","fromEmail":"tboegi@web.de","sentAt":"2014-06-13T04:11:34Z","receivedAt":"2014-06-13T04:11:34Z","isPatch":true,"sender":{"key":"tboegi@web.de","avatar":"https://avatars.githubusercontent.com/u/7138363?v=4"},"body":"On 2014-06-13 03.18, David Turner wrote:\n[]\n> \n> It is too old for my patch because it doesn't support ifunc (and I\n> suspect that no version of GCC for Windows supports ifunc). But that\n> does not seem to be what is going on in your error message. Instead,\n> when we #include , we get compat/cpuid.h rather than the\n> system's cpuid.h. When I rename compat/cpuid.h to something else \ncompat/git_cpuid.h ?\n\n> I'm testing on a Windows 8 VM from modern.ie with msysgit's\n> \"netinstaller\" -- is that a reasonable test environment?\n\nMany people are using Windows 7,\nand we shouldn't break for things for Windows XP.\n"},{"id":"244192","messageId":"01A8C25BF47246C7AB925EFA1C07D26C@PhilipOakley","threadId":"36851","inReplyTo":"539A79F6.9020905@web.de","subject":"Re: [PATCH v7 0/1] refs.c: SSE4.2 optimizations for check_refname_component","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.org","sentAt":"2014-06-14T10:24:33Z","receivedAt":"2014-06-14T10:24:33Z","isPatch":true,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"From: \"Torsten Bögershausen\" \n> On 2014-06-13 03.18, David Turner wrote:\n> []\n>>\n>> It is too old for my patch because it doesn't support ifunc (and I\n>> suspect that no version of GCC for Windows supports ifunc). But that\n>> does not seem to be what is going on in your error message. Instead,\n>> when we #include , we get compat/cpuid.h rather than the\n>> system's cpuid.h. When I rename compat/cpuid.h to something else\n> compat/git_cpuid.h ?\n>\n>> I'm testing on a Windows 8 VM from modern.ie with msysgit's\n>> \"netinstaller\" -- is that a reasonable test environment?\n>\n> Many people are using Windows 7,\n> and we shouldn't break for things for Windows XP.\n>\nI'd like that.\n--\nPhilip\nsent from my XP netbook;-)\n"},{"id":"244193","messageId":"20140614152209.GA14125@domone.podge","threadId":"36851","inReplyTo":"1402012575-16546-2-git-send-email-dturner@twitter.com","subject":"Re: [PATCH v7 1/1] refs.c: SSE4.2 optimizations for check_refname_component","fromName":"Ondřej Bílka","fromEmail":"neleai@seznam.cz","sentAt":"2014-06-14T15:22:09Z","receivedAt":"2014-06-14T15:22:09Z","isPatch":true,"sender":{"key":"neleai@seznam.cz","avatar":"https://avatars.githubusercontent.com/u/48067?v=4"},"body":"On Thu, Jun 05, 2014 at 07:56:15PM -0400, David Turner wrote:\n> Optimize check_refname_component using SSE4.2, where available.\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> SSE4.2: 25 ms\n> \n> This is about a 15% improvement.\n> \n> The configure.ac changes include code from the GNU C Library written\n> by Joseph S. Myers .\n> \n> Only supports GCC and Clang at present, because C interfaces to the\n> cpuid instruction are not well-standardized.\n>\nStill a SSE4.2 is not that useful, in most cases SSE2 is faster. Here I\nthink that difference will not be that big when correctly implemented.\nThat will avoid a runtime checks.\n\nFor parallelisation you need to take extra step and paralelize whole\ncheck than going component-by-component.\n\nFor detecting sequences a faster way is construct bitmasks with SSE2 so\nyou could combine these. It avoids needing special casing on 16-byte\nboundaries. \n\nBelow is untested implementation where you could add a bad character\ncheck with SSE4.2 which would speed it up. Are refs mostly\nalphanumerical? If so we could speed this up by paralelized alnum check\nand handling other characters in slower path.\n\n\n#include \n#include \n\nchar bad_table[256]; // TODO\nint bad_characters(unsigned char *x)\n{\n\twhile (*x)\n\tif (bad_table[*x++])\n\t\treturn -1;\n\n\treturn 0;\n}\n\nint check_refname_skeleton(char *x)\n{\n\tif (bad_characters(x))\n\t\treturn -1;\n\n\t__m128i slash = _mm_set1_epi8 ('/');\n\t__m128i dot = _mm_set1_epi8 ('.');\n\t__m128i char_l = _mm_set1_epi8 ('l');\n\t__m128i at = _mm_set1_epi8 ('@');\n\t__m128i brace = _mm_set1_epi8 ('{');\n\n\twhile (1) {\n\t\tif (((uint64_t) x) & 4095 < 4096 - 17)\n\t\t\t{\n\t\t\t\tif (bytewise_check(x) != -2);\n\t\t\t\t\treturn bytewise_check(x);\n\t\n\t\t\t\tx += 16;\n\t\t\t}\n\n\t\t__m128i v0 = _mm_loadu_si128 ((__m128i *)(x));\n\t\t__m128i v1 = _mm_loadu_si128 ((__m128i *)(x + 1));\n\n\t\t__m128i result;\n\n\t\t// terminating 0\n\t\tresult = _mm_cmpeq_epi8(v0, _mm_set1_epi8('\\000'));\n\n\t\t// sequence ..\n\t\tresult = _mm_or_si128(result, _mm_and_si128 (_mm_cmpeq_epi8(v0, dot),\n \t\t \t\t _mm_cmpeq_epi8(v1, dot)));\n\n\t\t// sequence /.\n\t\tresult = _mm_or_si128(result, _mm_and_si128 (_mm_cmpeq_epi8(v0, slash),\n \t\t \t\t _mm_cmpeq_epi8(v1, dot)));\n\n\t\t// sequence //\n\t\tresult = _mm_or_si128(result, _mm_and_si128 (_mm_cmpeq_epi8(v0, slash),\n \t\t \t\t _mm_cmpeq_epi8(v1, slash)));\n\n \n\t\t// sequence .l \n\t\tresult = _mm_or_si128(result, _mm_and_si128 (_mm_cmpeq_epi8(v0, dot),\n \t\t \t\t _mm_cmpeq_epi8(v1, char_l)));\n \n\t\t// sequence @{ \n \n\t\tresult = _mm_or_si128(result, _mm_and_si128 (_mm_cmpeq_epi8(v0, at),\n \t\t _mm_cmpeq_epi8(v1, brace)));\n\n\t\tuint64_t mask = _mm_movemask_epi8(result);\n\t\tif (mask) {\n\t\t char *p = x + __builtin_ctzl(mask);\n\n\t\t if (!*p)\n \t\treturn 0;\n\t\t else if (p[0] == '.' && p[1] == 'l')\n \t\tif (bytewise_check(x) != -2)\n\t\t\t\t\treturn bytewise_check(x);\n\t\t else\n \t\treturn -1;\n\t\t}\n\t\tx += 16;\n\t}\n}\n"},{"id":"244204","messageId":"1402811620.5629.77.camel@stross","threadId":"36851","inReplyTo":"20140614152209.GA14125@domone.podge","subject":"Re: [PATCH v7 1/1] refs.c: SSE4.2 optimizations for check_refname_component","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-06-15T05:53:40Z","receivedAt":"2014-06-15T05:53:40Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Sat, 2014-06-14 at 17:22 +0200, Ondřej Bílka wrote:\n> On Thu, Jun 05, 2014 at 07:56:15PM -0400, David Turner wrote:\n> > Optimize check_refname_component using SSE4.2, where available.\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> > SSE4.2: 25 ms\n> > \n> > This is about a 15% improvement.\n> > \n> > The configure.ac changes include code from the GNU C Library written\n> > by Joseph S. Myers .\n> > \n> > Only supports GCC and Clang at present, because C interfaces to the\n> > cpuid instruction are not well-standardized.\n> >\n> Still a SSE4.2 is not that useful, in most cases SSE2 is faster. Here I\n> think that difference will not be that big when correctly implemented.\n> That will avoid a runtime checks.\n\nSurprisingly to me, this is true! At least, on my machine. Sadly, the\nonly way to make it avoid a runtime check is to exclude 32-bit machines\n(or to make the option non-default, which I would prefer not to do). \n\n> For parallelisation you need to take extra step and paralelize whole\n> check than going component-by-component.\n\nGood idea.\n\n> For detecting sequences a faster way is construct bitmasks with SSE2 so\n> you could combine these. It avoids needing special casing on 16-byte\n> boundaries.\n\nThat does seem to be faster.\n\n> Below is untested implementation where you could add a bad character\n> check with SSE4.2 which would speed it up. Are refs mostly\n> alphanumerical? If so we could speed this up by paralelized alnum check\n> and handling other characters in slower path.\n\nTwitter's are almost entirely in [-._/a-zA-Z0-9] -- there are only a\nhandful of exceptions. So, a method that has some bycatch outside of\nthis range is just as fast as the SSE4.2 bad character check (but\nsomewhat more code).\n"}]}