{"thread":{"id":"36775","subject":"[PATCH v2 0/1] check_refname_component: Optimize","startedAt":"2014-05-28T21:04:14Z","lastAt":"2014-05-31T11:21:19Z","messageCount":15,"participants":["David Turner","Michael Haggerty","Duy Nguyen","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":2,"patchTotal":1},"messages":[{"id":"242902","messageId":"1401311055-480-1-git-send-email-dturner@twitter.com","threadId":"36775","inReplyTo":null,"subject":"[PATCH v2 0/1] check_refname_component: Optimize","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-05-28T21:04:14Z","receivedAt":"2014-05-28T21:04:14Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"I just tested the previous patch on a Mac with clang and it needed\nsome tweaks.\n\nAlso, I should clarify that this represents a real use-case: we really\ndo have tens of thousands of branches on some repos. It would be nice\nif people would clean up after themselves, but they don't.\n\n(Also, it's probably worth adding a shortcut for HEAD at some point,\nsince that is the most-commonly-used ref, but that's for a later\npatch)\n"},{"id":"242903","messageId":"1401311055-480-2-git-send-email-dturner@twitter.com","threadId":"36775","inReplyTo":"1401311055-480-1-git-send-email-dturner@twitter.com","subject":"[PATCH] check_refname_component: Optimize","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-05-28T21:04:15Z","receivedAt":"2014-05-28T21:04:15Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"In a repository with tens of thousands of refs, the command\n~/git/git-diff-index --cached --quiet --ignore-submodules [revision]\nis a bit slow. check_refname_component is a major contributor to the\nruntime. Provide two optimized versions of this function: one for\nmachines with SSE4.2, and one for machines without. The speedup for\nthis command on one particular repo (with about 60k refs) is about 12%\nfor the SSE version and 8% for the non-SSE version.\n\nSigned-off-by: David Turner \n---\n Makefile | 6 +++\n configure.ac | 6 +++\n refs.c | 152 +++++++++++++++++++++++++++++++++++++++++++++++++++--\n t/t5511-refspec.sh | 13 +++++\n 4 files changed, 172 insertions(+), 5 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex a53f3a8..123e2fc 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_SSE\n+\tBASIC_CFLAGS += -DNO_SSE\n+else\n+\tBASIC_CFLAGS += -msse4\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_SSE=\\''$(subst ','\\'',$(subst ','\\'',$(NO_SSE)))'\\' >>$@\n ifdef TEST_OUTPUT_DIRECTORY\n \t@echo TEST_OUTPUT_DIRECTORY=\\''$(subst ','\\'',$(subst ','\\'',$(TEST_OUTPUT_DIRECTORY)))'\\' >>$@\n endif\ndiff --git a/configure.ac b/configure.ac\nindex b711254..71a9429 100644\n--- a/configure.ac\n+++ b/configure.ac\n@@ -382,6 +382,11 @@ AS_HELP_STRING([],[Tcl/Tk interpreter will be found in a system.]),\n GIT_PARSE_WITH(tcltk))\n #\n \n+# Declare the with-sse/without-sse options.\n+AC_ARG_WITH(sse,\n+AS_HELP_STRING([--with-sse],[use SSE instructions (default is YES)]),\n+GIT_PARSE_WITH(sse))\n+\n \n ## Checks for programs.\n AC_MSG_NOTICE([CHECKS for programs])\n@@ -449,6 +454,7 @@ else\n fi\n fi\n GIT_CONF_SUBST([TCLTK_PATH])\n+GIT_CONF_SUBST([NO_SSE])\n AC_CHECK_PROGS(ASCIIDOC, [asciidoc])\n if test -n \"$ASCIIDOC\"; then\n \tAC_MSG_CHECKING([for asciidoc version])\ndiff --git a/refs.c b/refs.c\nindex 28d5eca..8f0de04 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -5,6 +5,8 @@\n #include \"dir.h\"\n #include \"string-list.h\"\n \n+#include \n+\n /*\n * Make sure \"ref\" is something reasonable to have under \".git/refs/\";\n * We do not like it if:\n@@ -29,30 +31,169 @@ static inline int bad_ref_char(int ch)\n \treturn 0;\n }\n \n+char refname_disposition[] = {\n+ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n+ 0, 9, 9, 9, 9, 9, 9, 9, 9, 9, 0, 9, 9, 9, 2, 1,\n+ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 0, 9, 9, 9, 9, 0,\n+ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 0, 0, 9, 0, 9,\n+ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 3, 9, 9, 0, 0,\n+ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n+ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9\n+};\n+\n /*\n * Try to read one refname component from the front of refname. Return\n * the length of the component found, or -1 if the component is not\n * legal.\n */\n-static int check_refname_component(const char *refname, int flags)\n+static int check_refname_component_1(const char *refname, int flags)\n {\n \tconst char *cp;\n \tchar last = '\\0';\n \n \tfor (cp = refname; ; cp++) {\n-\t\tchar ch = *cp;\n-\t\tif (ch == '\\0' || ch == '/')\n+\t\tunsigned char ch = (unsigned char) *cp;\n+\t\tchar disp = refname_disposition[ch];\n+\t\tswitch(disp) {\n+\t\tcase 0:\n+\t\t return -1;\n+\t\tcase 1:\n+\t\t\tgoto out;\n+\t\tcase 2:\n+\t\t\tif (last == '.')\n+\t\t\t\treturn -1;\n \t\t\tbreak;\n-\t\tif (bad_ref_char(ch))\n-\t\t\treturn -1; /* Illegal character in refname. */\n+\t\tcase 3:\n+\t\t if (last == '@')\n+\t\t\t return -1;\n+\t\t break;\n+\t }\n+\n \t\tif (last == '.' && ch == '.')\n \t\t\treturn -1; /* Refname contains \"..\". */\n \t\tif (last == '@' && ch == '{')\n \t\t\treturn -1; /* Refname contains \"@{\". */\n \t\tlast = ch;\n \t}\n+out:\n+\tif (cp == refname)\n+\t\treturn 0; /* Component has zero length. */\n+\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+#ifdef NO_SSE\n+#define check_refname_component check_refname_component_1\n+#else\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+#ifndef PAGE_SIZE\n+#define PAGE_SIZE 4096\n+#endif\n+#define BLOCK_SIZE 16\n+\n+/* Vectorized version of check_refname_component */\n+static int check_refname_component(const char *refname, int flags)\n+{\n+\tconst __m128i *refname_vec = (__m128i*) refname;\n+\n+\t/* Character ranges for characters forbidden in refs; see\n+\t * 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+\n+\tint dotdotpos = BLOCK_SIZE, atcurlypos = BLOCK_SIZE;\n+\tfor (vp = refname_vec; ; vp++) {\n+\t\t__m128i tmp;\n+\t\tint endpos;\n+\n+\t\t/* Handle case of forbidden substrings .. and @{ crossing\n+\t\t * sixteen-byte boudaries */\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 - 1)) > PAGE_SIZE - BLOCK_SIZE)\n+\t\t\t/* End-of-page; fall back to slow method for\n+\t\t\t * this entire component. */\n+\t\t\treturn check_refname_component_1(refname, flags);\n+\n+\t\ttmp = _mm_lddqu_si128(vp);\n+\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\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, BLOCK_SIZE, 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 < BLOCK_SIZE) {\n+\t\t\tcp = ((const char*) vp) + endpos;\n+\t\t\tbreak;\n+\t\t}\n+\t\tcp = (const char*) vp + BLOCK_SIZE;\n+\t}\n+\n \tif (cp == refname)\n \t\treturn 0; /* Component has zero length. */\n+\n \tif (refname[0] == '.') {\n \t\tif (!(flags & REFNAME_DOT_COMPONENT))\n \t\t\treturn -1; /* Component starts with '.'. */\n@@ -67,6 +208,7 @@ static int check_refname_component(const char *refname, int flags)\n \t\treturn -1; /* Refname ends with \".lock\". */\n \treturn cp - refname;\n }\n+#endif\n \n int check_refname_format(const char *refname, int flags)\n {\ndiff --git a/t/t5511-refspec.sh b/t/t5511-refspec.sh\nindex c289322..0f03f9c 100755\n--- a/t/t5511-refspec.sh\n+++ b/t/t5511-refspec.sh\n@@ -84,4 +84,17 @@ test_refspec push 'refs/heads/*/*/for-linus:refs/remotes/mine/*' invalid\n test_refspec fetch 'refs/heads/*/for-linus:refs/remotes/mine/*'\n test_refspec push 'refs/heads/*/for-linus:refs/remotes/mine/*'\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.18.gf763c0f\n"},{"id":"242906","messageId":"538658C0.8050001@alum.mit.edu","threadId":"36775","inReplyTo":"1401311055-480-2-git-send-email-dturner@twitter.com","subject":"Re: [PATCH] check_refname_component: Optimize","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2014-05-28T21:44:32Z","receivedAt":"2014-05-28T21:44:32Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/28/2014 11:04 PM, David Turner wrote:\n> In a repository with tens of thousands of refs, the command\n> ~/git/git-diff-index --cached --quiet --ignore-submodules [revision]\n> is a bit slow. check_refname_component is a major contributor to the\n> runtime. Provide two optimized versions of this function: one for\n> machines with SSE4.2, and one for machines without. The speedup for\n> this command on one particular repo (with about 60k refs) is about 12%\n> for the SSE version and 8% for the non-SSE version.\n\nInteresting. Thanks for the patch.\n\nWhy do you use \"git diff-index\" to benchmark your change? Is there\nsomething particular about that command that leads to especially bad\nperformance with lots of references?\n\nI assume that most of the time spent in check_refname_component() is\nwhile reading the packed-refs file, right? If so, there are probably\nother git commands that would better measure that time, with less other\nwork. For example, \"git rev-parse refname\" will read the packed-refs\nfile, too (assuming that \"refname\" is not a loose reference). If you\ntest the speedup of a cheaper command like that, it seems to me that you\nwill get a better idea of how much you are speeding up the ref-reading\npart. It would also be interesting to see the difference in\nmilliseconds (rather than a percentage) for some specified number of\nreferences.\n\nI think it's worth using your LUT-based approach to save 8%. I'm less\nsure it's worth the complication and unreadability of using SSE to get\nthe next 4% speedup. But the gains might be proven to be more\nsignificant if you benchmark them differently.\n\nI won't critique the code in detail until we have thrashed out the\nmetaissues, but I made a few comments below about nits that I noticed\nwhen I scanned through.\n\n> Signed-off-by: David Turner \n> ---\n> Makefile | 6 +++\n> configure.ac | 6 +++\n> refs.c | 152 +++++++++++++++++++++++++++++++++++++++++++++++++++--\n> t/t5511-refspec.sh | 13 +++++\n> 4 files changed, 172 insertions(+), 5 deletions(-)\n> \n> diff --git a/Makefile b/Makefile\n> index a53f3a8..123e2fc 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_SSE\n> +\tBASIC_CFLAGS += -DNO_SSE\n> +else\n> +\tBASIC_CFLAGS += -msse4\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_SSE=\\''$(subst ','\\'',$(subst ','\\'',$(NO_SSE)))'\\' >>$@\n> ifdef TEST_OUTPUT_DIRECTORY\n> \t@echo TEST_OUTPUT_DIRECTORY=\\''$(subst ','\\'',$(subst ','\\'',$(TEST_OUTPUT_DIRECTORY)))'\\' >>$@\n> endif\n> diff --git a/configure.ac b/configure.ac\n> index b711254..71a9429 100644\n> --- a/configure.ac\n> +++ b/configure.ac\n> @@ -382,6 +382,11 @@ AS_HELP_STRING([],[Tcl/Tk interpreter will be found in a system.]),\n> GIT_PARSE_WITH(tcltk))\n> #\n> \n> +# Declare the with-sse/without-sse options.\n> +AC_ARG_WITH(sse,\n> +AS_HELP_STRING([--with-sse],[use SSE instructions (default is YES)]),\n> +GIT_PARSE_WITH(sse))\n> +\n> \n> ## Checks for programs.\n> AC_MSG_NOTICE([CHECKS for programs])\n> @@ -449,6 +454,7 @@ else\n> fi\n> fi\n> GIT_CONF_SUBST([TCLTK_PATH])\n> +GIT_CONF_SUBST([NO_SSE])\n> AC_CHECK_PROGS(ASCIIDOC, [asciidoc])\n> if test -n \"$ASCIIDOC\"; then\n> \tAC_MSG_CHECKING([for asciidoc version])\n> diff --git a/refs.c b/refs.c\n> index 28d5eca..8f0de04 100644\n> --- a/refs.c\n> +++ b/refs.c\n> @@ -5,6 +5,8 @@\n> #include \"dir.h\"\n> #include \"string-list.h\"\n> \n> +#include \n> +\n\nYou include this file unconditionally, but I doubt that it is present on\nall platforms. I guess it has to be protected with #ifdef or something\nat a minimum.\n\n> /*\n> * Make sure \"ref\" is something reasonable to have under \".git/refs/\";\n> * We do not like it if:\n> @@ -29,30 +31,169 @@ static inline int bad_ref_char(int ch)\n> \treturn 0;\n> }\n> \n\nPlease add a comment here about what the values in refname_disposition\nsignify. And maybe add some line comments explaining unusual values,\nfor people who haven't memorized the ASCII encoding; e.g., on the third\nline,\n\n/* SP -> 0, '.' -> 2, '-' -> 1 */\n\nAlso, this variable could be static. And if you change your encoding to\nuse 0 instead of 9 for valid characters, then you could define the table\nwith an explicit length of 256 and omit the second half of the\ninitializers, letting those values be initialized to zero automatically.\n\n> +char refname_disposition[] = {\n> + 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n> + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n> + 0, 9, 9, 9, 9, 9, 9, 9, 9, 9, 0, 9, 9, 9, 2, 1,\n> + 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 0, 9, 9, 9, 9, 0,\n> + 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n> + 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 0, 0, 9, 0, 9,\n> + 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n> + 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 3, 9, 9, 0, 0,\n> + 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n> + 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n> + 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n> + 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n> + 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n> + 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n> + 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,\n> + 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9\n> +};\n> +\n> /*\n> * Try to read one refname component from the front of refname. Return\n> * the length of the component found, or -1 if the component is not\n> * legal.\n> */\n> -static int check_refname_component(const char *refname, int flags)\n> +static int check_refname_component_1(const char *refname, int flags)\n> {\n> \tconst char *cp;\n> \tchar last = '\\0';\n> \n> \tfor (cp = refname; ; cp++) {\n> -\t\tchar ch = *cp;\n> -\t\tif (ch == '\\0' || ch == '/')\n> +\t\tunsigned char ch = (unsigned char) *cp;\n> +\t\tchar disp = refname_disposition[ch];\n> +\t\tswitch(disp) {\n> +\t\tcase 0:\n> +\t\t return -1;\n> +\t\tcase 1:\n> +\t\t\tgoto out;\n> +\t\tcase 2:\n> +\t\t\tif (last == '.')\n> +\t\t\t\treturn -1;\n> \t\t\tbreak;\n> -\t\tif (bad_ref_char(ch))\n> -\t\t\treturn -1; /* Illegal character in refname. */\n> +\t\tcase 3:\n> +\t\t if (last == '@')\n> +\t\t\t return -1;\n> +\t\t break;\n> +\t }\n\nYou seem to have some indentation problems. Please always indent with\nTAB characters.\n\n> +\n> \t\tif (last == '.' && ch == '.')\n> \t\t\treturn -1; /* Refname contains \"..\". */\n> \t\tif (last == '@' && ch == '{')\n> \t\t\treturn -1; /* Refname contains \"@{\". */\n> \t\tlast = ch;\n> \t}\n> +out:\n> +\tif (cp == refname)\n> +\t\treturn 0; /* Component has zero length. */\n> +\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> +#ifdef NO_SSE\n> +#define check_refname_component check_refname_component_1\n> +#else\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> +#ifndef PAGE_SIZE\n> +#define PAGE_SIZE 4096\n> +#endif\n> +#define BLOCK_SIZE 16\n> +\n> +/* Vectorized version of check_refname_component */\n> +static int check_refname_component(const char *refname, int flags)\n> +{\n> +\tconst __m128i *refname_vec = (__m128i*) refname;\n> +\n> +\t/* Character ranges for characters forbidden in refs; see\n> +\t * 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> +\n> +\tint dotdotpos = BLOCK_SIZE, atcurlypos = BLOCK_SIZE;\n> +\tfor (vp = refname_vec; ; vp++) {\n> +\t\t__m128i tmp;\n> +\t\tint endpos;\n> +\n> +\t\t/* Handle case of forbidden substrings .. and @{ crossing\n> +\t\t * sixteen-byte boudaries */\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 - 1)) > PAGE_SIZE - BLOCK_SIZE)\n> +\t\t\t/* End-of-page; fall back to slow method for\n> +\t\t\t * this entire component. */\n> +\t\t\treturn check_refname_component_1(refname, flags);\n> +\n> +\t\ttmp = _mm_lddqu_si128(vp);\n> +\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\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, BLOCK_SIZE, 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 < BLOCK_SIZE) {\n> +\t\t\tcp = ((const char*) vp) + endpos;\n> +\t\t\tbreak;\n> +\t\t}\n> +\t\tcp = (const char*) vp + BLOCK_SIZE;\n> +\t}\n> +\n> \tif (cp == refname)\n> \t\treturn 0; /* Component has zero length. */\n> +\n> \tif (refname[0] == '.') {\n> \t\tif (!(flags & REFNAME_DOT_COMPONENT))\n> \t\t\treturn -1; /* Component starts with '.'. */\n> @@ -67,6 +208,7 @@ static int check_refname_component(const char *refname, int flags)\n> \t\treturn -1; /* Refname ends with \".lock\". */\n> \treturn cp - refname;\n> }\n> +#endif\n> \n> int check_refname_format(const char *refname, int flags)\n> {\n> diff --git a/t/t5511-refspec.sh b/t/t5511-refspec.sh\n> index c289322..0f03f9c 100755\n> --- a/t/t5511-refspec.sh\n> +++ b/t/t5511-refspec.sh\n> @@ -84,4 +84,17 @@ test_refspec push 'refs/heads/*/*/for-linus:refs/remotes/mine/*' invalid\n> test_refspec fetch 'refs/heads/*/for-linus:refs/remotes/mine/*'\n> test_refspec push 'refs/heads/*/for-linus:refs/remotes/mine/*'\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> \n\nPlease mention in your commit message why you added these tests. (Are\nthey to test peculiarities around 16-byte boundaries?)\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"242921","messageId":"1401320968.18134.98.camel@stross","threadId":"36775","inReplyTo":"538658C0.8050001@alum.mit.edu","subject":"Re: [PATCH] check_refname_component: Optimize","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-05-28T23:49:28Z","receivedAt":"2014-05-28T23:49:28Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Wed, 2014-05-28 at 23:44 +0200, Michael Haggerty wrote:\n> On 05/28/2014 11:04 PM, David Turner wrote:\n> > In a repository with tens of thousands of refs, the command\n> > ~/git/git-diff-index --cached --quiet --ignore-submodules [revision]\n> > is a bit slow. check_refname_component is a major contributor to the\n> > runtime. Provide two optimized versions of this function: one for\n> > machines with SSE4.2, and one for machines without. The speedup for\n> > this command on one particular repo (with about 60k refs) is about 12%\n> > for the SSE version and 8% for the non-SSE version.\n> \n> Interesting. Thanks for the patch.\n\nThanks for your thoughtful comments.\n\n> Why do you use \"git diff-index\" to benchmark your change? Is there\n> something particular about that command that leads to especially bad\n> performance with lots of references?\n\nBecause a colleague specifically asked me to look at it because he uses\nit as part of the zsh/bash git prompt dirty bit display. But that is not\nactually a good reason to use it in the commit-message. This is also\nthe reason why milliseconds matter, although at present other parts of\ngit are slow enough that the prompt stuff is still somewhat infeasible\nfor large repos.\n\n> I assume that most of the time spent in check_refname_component() is\n> while reading the packed-refs file, right? \n\nYes.\n\n> If so, there are probably\n> other git commands that would better measure that time, with less other\n> work. For example, \"git rev-parse refname\" will read the packed-refs\n> file, too (assuming that \"refname\" is not a loose reference). If you\n> test the speedup of a cheaper command like that, it seems to me that you\n> will get a better idea of how much you are speeding up the ref-reading\n> part. It would also be interesting to see the difference in\n> milliseconds (rather than a percentage) for some specified number of\n> references.\n\nI'll change it to rev-parse and to show the difference in milliseconds.\n\nThe times on rev-parse are 35/29/25ms on one particular computer, for\noriginal, LUT, SSE. So, somewhat larger speedup in percentage terms. I\nshould also note that this represents a real use-case, and I expect that\nthe number of refs will be somewhat larger in the future.\n\n> I think it's worth using your LUT-based approach to save 8%. I'm less\n> sure it's worth the complication and unreadability of using SSE to get\n> the next 4% speedup. But the gains might be proven to be more\n> significant if you benchmark them differently.\n\nI was actually hoping at some point to use SSE to speed up a small few\nof the other slow bits e.g. get_sha1_hex. I have not yet tested if this\nwill actually be faster, but I bet it will. And my watchman branch uses\nit to speed up the hashmap (but it seems CityHash works about as well so\nI might just port that instead).\n\nBut actually speaking of SSE: is there a minimum compiler version for\ngit? Because I have just discovered gcc-4.2 on the Mac has a bug which\ncauses this code to misbehave. Yet again, compiler intrinsics prove\nless portable than straight assembly language. I would be just as happy\nto write it in assembly, but I suspect that nobody would enjoy that. I\ncould also work around the bug with a compiler-specific ifdef, but Apple\nhas been shipping clang for some years now, so I think it's OK to leave\nthe code as-is.\n\n> I won't critique the code in detail until we have thrashed out the\n> metaissues, but I made a few comments below about nits that I noticed\n> when I scanned through.\n\nI'll go ahead and roll a new version with the nits picked.\n\n> Please add a comment here about what the values in refname_disposition\n> signify. And maybe add some line comments explaining unusual values,\n> for people who haven't memorized the ASCII encoding; e.g., on the third\n> line,\n\nI think I'm going to say, \"see below for the list of illegal characters,\nfrom which this table is derived.\", if that's OK with you. \n"},{"id":"242944","messageId":"CACsJy8BcBmuC3KMu+5dhGiOXX=u7WtHWQzQuT=ZPTbSCduJdbw@mail.gmail.com","threadId":"36775","inReplyTo":"1401320968.18134.98.camel@stross","subject":"Re: [PATCH] check_refname_component: Optimize","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2014-05-29T13:41:52Z","receivedAt":"2014-05-29T13:41:52Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, May 29, 2014 at 6:49 AM, David Turner wrote:\n>> I assume that most of the time spent in check_refname_component() is\n>> while reading the packed-refs file, right?\n>\n> Yes.\n\nI wonder if we can get away without SSE code by saving stat info of\nthe packed-refs version that we have verified. When we read pack-refs,\nif stat info matches, skip check_refname_component(). Assuming that\npack-refs does not change often, of course.\n-- \nDuy\n"},{"id":"242966","messageId":"xmqqfvjsbkz2.fsf@gitster.dls.corp.google.com","threadId":"36775","inReplyTo":"CACsJy8BcBmuC3KMu+5dhGiOXX=u7WtHWQzQuT=ZPTbSCduJdbw@mail.gmail.com","subject":"Re: [PATCH] check_refname_component: Optimize","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-05-29T16:36:33Z","receivedAt":"2014-05-29T16:36:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen writes:\n\n> On Thu, May 29, 2014 at 6:49 AM, David Turner wrote:\n>>> I assume that most of the time spent in check_refname_component() is\n>>> while reading the packed-refs file, right?\n>>\n>> Yes.\n>\n> I wonder if we can get away without SSE code by saving stat info of\n> the packed-refs version that we have verified. When we read pack-refs,\n> if stat info matches, skip check_refname_component(). Assuming that\n> pack-refs does not change often, of course.\n\nCan you elaborate a bit more?\n\nRegardless, I think I would prefer to see this patch done as at\nleast a two step series, one that does only the look-up table thing,\nand then the other with arch-specific tweaks as a follow-up on top.\n"},{"id":"242990","messageId":"CACsJy8BS_YhMB9ZZRx4faj=_YWZQrqm7B9AHkTGye=okja=m-Q@mail.gmail.com","threadId":"36775","inReplyTo":"xmqqfvjsbkz2.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] check_refname_component: Optimize","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2014-05-29T23:24:30Z","receivedAt":"2014-05-29T23:24:30Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, May 29, 2014 at 11:36 PM, Junio C Hamano wrote:\n> Duy Nguyen writes:\n>\n>> On Thu, May 29, 2014 at 6:49 AM, David Turner wrote:\n>>>> I assume that most of the time spent in check_refname_component() is\n>>>> while reading the packed-refs file, right?\n>>>\n>>> Yes.\n>>\n>> I wonder if we can get away without SSE code by saving stat info of\n>> the packed-refs version that we have verified. When we read pack-refs,\n>> if stat info matches, skip check_refname_component(). Assuming that\n>> pack-refs does not change often, of course.\n>\n> Can you elaborate a bit more?\n\nThe first time we read packed_refs, check_refname_format() is called\nin read_packed_refs()->create_ref_entry() as usual. If we find no\nproblem, we store packed_refs stat() info in maybe packed_refs.stat.\nNext time we read packed_refs, if packed_refs.stat is there and\nindicates that packed_refs has not changed, we can make\ncreate_ref_entry() ignore check_refname_format() completely. That's\neven cheaper than SSE-enhanced check_refname_component() and easier to\ndo. If packed_refs is updated, we do the whole check_refname_format\ndance again.\n-- \nDuy\n"},{"id":"242992","messageId":"20140529234109.GA28683@sigill.intra.peff.net","threadId":"36775","inReplyTo":"CACsJy8BS_YhMB9ZZRx4faj=_YWZQrqm7B9AHkTGye=okja=m-Q@mail.gmail.com","subject":"Re: [PATCH] check_refname_component: Optimize","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-05-29T23:41:09Z","receivedAt":"2014-05-29T23:41:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, May 30, 2014 at 06:24:30AM +0700, Duy Nguyen wrote:\n\n> >> I wonder if we can get away without SSE code by saving stat info of\n> >> the packed-refs version that we have verified. When we read pack-refs,\n> >> if stat info matches, skip check_refname_component(). Assuming that\n> >> pack-refs does not change often, of course.\n> >\n> > Can you elaborate a bit more?\n> \n> The first time we read packed_refs, check_refname_format() is called\n> in read_packed_refs()->create_ref_entry() as usual. If we find no\n> problem, we store packed_refs stat() info in maybe packed_refs.stat.\n> Next time we read packed_refs, if packed_refs.stat is there and\n> indicates that packed_refs has not changed, we can make\n> create_ref_entry() ignore check_refname_format() completely.\n\nI'm confused. Why would we re-open packed-refs at all if the stat\ninformation hasn't changed?\n\nread_packed_refs is only called from get_packed_ref_cache, and we only\ndo so if !refs->packed. And refs->packed is only NULL if we haven't read\nthe file yet, or it is stat-dirty.\n\nIf that is working as intended, then we should generally only open and\nread packed-refs once per invocation of git.\n\n-Peff\n"},{"id":"242993","messageId":"CACsJy8BgriBBWJ6ZzQS8S7p4SUB=bdZHdnUQsyN03g+vtApbxA@mail.gmail.com","threadId":"36775","inReplyTo":"20140529234109.GA28683@sigill.intra.peff.net","subject":"Re: [PATCH] check_refname_component: Optimize","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2014-05-29T23:43:18Z","receivedAt":"2014-05-29T23:43:18Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, May 30, 2014 at 6:41 AM, Jeff King wrote:\n> On Fri, May 30, 2014 at 06:24:30AM +0700, Duy Nguyen wrote:\n>\n>> >> I wonder if we can get away without SSE code by saving stat info of\n>> >> the packed-refs version that we have verified. When we read pack-refs,\n>> >> if stat info matches, skip check_refname_component(). Assuming that\n>> >> pack-refs does not change often, of course.\n>> >\n>> > Can you elaborate a bit more?\n>>\n>> The first time we read packed_refs, check_refname_format() is called\n>> in read_packed_refs()->create_ref_entry() as usual. If we find no\n>> problem, we store packed_refs stat() info in maybe packed_refs.stat.\n>> Next time we read packed_refs, if packed_refs.stat is there and\n>> indicates that packed_refs has not changed, we can make\n>> create_ref_entry() ignore check_refname_format() completely.\n>\n> I'm confused. Why would we re-open packed-refs at all if the stat\n> information hasn't changed?\n\nNo, not in the same process. In the next run.\n\n>\n> read_packed_refs is only called from get_packed_ref_cache, and we only\n> do so if !refs->packed. And refs->packed is only NULL if we haven't read\n> the file yet, or it is stat-dirty.\n>\n> If that is working as intended, then we should generally only open and\n> read packed-refs once per invocation of git.\n>\n> -Peff\n\n\n\n-- \nDuy\n"},{"id":"242995","messageId":"20140530000728.GC28683@sigill.intra.peff.net","threadId":"36775","inReplyTo":"CACsJy8BgriBBWJ6ZzQS8S7p4SUB=bdZHdnUQsyN03g+vtApbxA@mail.gmail.com","subject":"Re: [PATCH] check_refname_component: Optimize","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-05-30T00:07:28Z","receivedAt":"2014-05-30T00:07:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, May 30, 2014 at 06:43:18AM +0700, Duy Nguyen wrote:\n\n> >> The first time we read packed_refs, check_refname_format() is called\n> >> in read_packed_refs()->create_ref_entry() as usual. If we find no\n> >> problem, we store packed_refs stat() info in maybe packed_refs.stat.\n> >> Next time we read packed_refs, if packed_refs.stat is there and\n> >> indicates that packed_refs has not changed, we can make\n> >> create_ref_entry() ignore check_refname_format() completely.\n> >\n> > I'm confused. Why would we re-open packed-refs at all if the stat\n> > information hasn't changed?\n> \n> No, not in the same process. In the next run.\n\nAh, I thought \"packed_refs.stat\" was a struct member, but I guess you\nmean it as a filename.\n\nBut then we're just trusting that the \"trust me\" flag on disk is\ncorrect. Why not just trust that packed-refs is correct in the first\nplace?\n\nIOW, consider this progression of changes:\n\n 1. Check refname format when we read packed-refs (the current\n behavior).\n\n 2. Keep a separate file \"packed-refs.stat\" with stat information. If\n the packed-refs file matches that stat information, do not bother\n checking refname formats.\n\n 3. Put a flag in \"packed-refs\" that says \"trust me, I'm valid\". Check\n the refnames when it is generated.\n\n 4. Realize that we already check the refnames when we write it out.\n Don't bother writing \"trust me, I'm valid\"; readers can assume that\n it is.\n\nWhat is the scenario that option (2) protects against that options (3)\nand (4) do not?\n\nI could guess something like \"the writer has a different idea of what a\nvalid refname is than we do\". But that applies as well to (2), but just\nas \"the reader who wrote packed-refs.stat has a different idea than we\ndo\".\n\nAs a side note, while it is nice that we might make check_refname_format\nfaster, I think if you _really_ want to make repos with a lot of refs\nfaster, it would make more sense to introduce an on-disk format that\ndoes not need linear parsing (e.g., something we could mmap and binary\nsearch, or even something dbm-ish that could be updated without\nrewriting the whole file (deletions, for example, must rewrite the\nwhole file, giving quadratic performance when deleting all refs one by\none).\n\n-Peff\n"},{"id":"243001","messageId":"CACsJy8CAhGT+dF511cbLZTEre9SKzs2EHfHaskuXh7sMTYL6JQ@mail.gmail.com","threadId":"36775","inReplyTo":"20140530000728.GC28683@sigill.intra.peff.net","subject":"Re: [PATCH] check_refname_component: Optimize","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2014-05-30T02:03:58Z","receivedAt":"2014-05-30T02:03:58Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, May 30, 2014 at 7:07 AM, Jeff King wrote:\n> But then we're just trusting that the \"trust me\" flag on disk is\n> correct. Why not just trust that packed-refs is correct in the first\n> place?\n>\n> IOW, consider this progression of changes:\n>\n> 1. Check refname format when we read packed-refs (the current\n> behavior).\n>\n> 2. Keep a separate file \"packed-refs.stat\" with stat information. If\n> the packed-refs file matches that stat information, do not bother\n> checking refname formats.\n>\n> 3. Put a flag in \"packed-refs\" that says \"trust me, I'm valid\". Check\n> the refnames when it is generated.\n>\n> 4. Realize that we already check the refnames when we write it out.\n> Don't bother writing \"trust me, I'm valid\"; readers can assume that\n> it is.\n>\n> What is the scenario that option (2) protects against that options (3)\n> and (4) do not?\n>\n> I could guess something like \"the writer has a different idea of what a\n> valid refname is than we do\". But that applies as well to (2), but just\n> as \"the reader who wrote packed-refs.stat has a different idea than we\n> do\".\n\nThe reader and the writer have to agree on the same \"valid\" definition\nor it wouldn't work. I don't suppose this packed-refs.stat idea would\nspread out to other implementations than C git, so we're still good.\nIf we could write a flag in packed-refs saying \"trust me\" and other\nimplementations will strip it when they update packed-refs, then we're\ngood too.\n\n>\n> As a side note, while it is nice that we might make check_refname_format\n> faster, I think if you _really_ want to make repos with a lot of refs\n> faster, it would make more sense to introduce an on-disk format that\n> does not need linear parsing (e.g., something we could mmap and binary\n> search, or even something dbm-ish that could be updated without\n> rewriting the whole file (deletions, for example, must rewrite the\n> whole file, giving quadratic performance when deleting all refs one by\n> one).\n\nYeah, I bring up the idea because I think Mike's multiple ref backends\nis the way to go (assuming that it won't take as long as pack v4\ndevelopment). If we assume we'll go with that, then we can keep the\nworkaround to minimum.\n-- \nDuy\n"},{"id":"243009","messageId":"538853B5.1080308@alum.mit.edu","threadId":"36775","inReplyTo":"20140530000728.GC28683@sigill.intra.peff.net","subject":"Re: [PATCH] check_refname_component: Optimize","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2014-05-30T09:47:33Z","receivedAt":"2014-05-30T09:47:33Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/30/2014 02:07 AM, Jeff King wrote:\n> On Fri, May 30, 2014 at 06:43:18AM +0700, Duy Nguyen wrote:\n> \n>>>> The first time we read packed_refs, check_refname_format() is called\n>>>> in read_packed_refs()->create_ref_entry() as usual. If we find no\n>>>> problem, we store packed_refs stat() info in maybe packed_refs.stat.\n>>>> Next time we read packed_refs, if packed_refs.stat is there and\n>>>> indicates that packed_refs has not changed, we can make\n>>>> create_ref_entry() ignore check_refname_format() completely.\n>>>\n>>> I'm confused. Why would we re-open packed-refs at all if the stat\n>>> information hasn't changed?\n>>\n>> No, not in the same process. In the next run.\n> \n> Ah, I thought \"packed_refs.stat\" was a struct member, but I guess you\n> mean it as a filename.\n> \n> But then we're just trusting that the \"trust me\" flag on disk is\n> correct. Why not just trust that packed-refs is correct in the first\n> place?\n> \n> IOW, consider this progression of changes:\n> \n> 1. Check refname format when we read packed-refs (the current\n> behavior).\n> \n> 2. Keep a separate file \"packed-refs.stat\" with stat information. If\n> the packed-refs file matches that stat information, do not bother\n> checking refname formats.\n> \n> 3. Put a flag in \"packed-refs\" that says \"trust me, I'm valid\". Check\n> the refnames when it is generated.\n> \n> 4. Realize that we already check the refnames when we write it out.\n> Don't bother writing \"trust me, I'm valid\"; readers can assume that\n> it is.\n> \n> What is the scenario that option (2) protects against that options (3)\n> and (4) do not?\n> \n> I could guess something like \"the writer has a different idea of what a\n> valid refname is than we do\". But that applies as well to (2), but just\n> as \"the reader who wrote packed-refs.stat has a different idea than we\n> do\".\n\nIf we want to be robust to future changes to refname rules, we could add\na header flag like\n\n # pack-refs with: peeled fully-peeled check-level=1.0\n\nwhich promises that the reference names in the file conform to the\ncurrent (\"version 1.0\") check_refname_format() rules.\n\nIf we ever make the rules stricter (a \"backwards-compatible\" change), we\nwould increment the check-level to 1.1. That way, an old reader, who\nknows about check-level=1.0 but not check-level=1.1, can still trust\nthat the refnames in the file conform to its check_refname_format()\nrules and avoid the verification step. (Of course if that version\nwrites the file again, it would have to set the check-level=1.0 tag, and\nnewer software would be forced to validate on reading to be sure that\nthe refnames still conform to check-level=1.1.)\n\nIf we make the rules looser (a \"backwards-incompatible\" change), we\nwould increment the check-level to 2.0. In that case readers who only\nknow about check-level 1.x would have to turn their verification code\nback on when reading the file to ensure that they can work with the\nrefnames that it contains.\n\nFormat changes should be infrequent enough, and the cost of verification\nis low enough, that sometimes ping-ponging back and forth between\nsoftware versions shouldn't be a problem in practice.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"243020","messageId":"20140530172944.GC25443@sigill.intra.peff.net","threadId":"36775","inReplyTo":"538853B5.1080308@alum.mit.edu","subject":"Re: [PATCH] check_refname_component: Optimize","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-05-30T17:29:44Z","receivedAt":"2014-05-30T17:29:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, May 30, 2014 at 11:47:33AM +0200, Michael Haggerty wrote:\n\n> > I could guess something like \"the writer has a different idea of what a\n> > valid refname is than we do\". But that applies as well to (2), but just\n> > as \"the reader who wrote packed-refs.stat has a different idea than we\n> > do\".\n> \n> If we want to be robust to future changes to refname rules, we could add\n> a header flag like\n> \n> # pack-refs with: peeled fully-peeled check-level=1.0\n> \n> which promises that the reference names in the file conform to the\n> current (\"version 1.0\") check_refname_format() rules.\n\nYeah, I thought about mentioning something like that. But really, this\njust seems like a lot of complexity to solve the problem in a wrong way.\n\nIt's not running check_refname_format that is the real problem. It's the\nfact that we do O(# of refs) work whenever we have to access the\npacked-refs file. check_refname_format is part of that, surely, but so\nis reading the file, creating all of the refname structs in memory, etc.\n\nI'd much rather see a solution that lets us do O(log N) or O(1) work to\naccess a ref, and then we don't have to care about optimizing\ncheck_refname_format specifically.\n\nI don't mind internal code speedups to micro-optimize check_refname_format.\nThey may make the code uglier, but they're fairly contained. But things\nlike check-level are much more invasive, and we'll need to keep\ncompatibility with them in future versions.\n\n-Peff\n"},{"id":"243073","messageId":"5389B35C.8060308@alum.mit.edu","threadId":"36775","inReplyTo":"20140530172944.GC25443@sigill.intra.peff.net","subject":"Re: [PATCH] check_refname_component: Optimize","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2014-05-31T10:47:56Z","receivedAt":"2014-05-31T10:47:56Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/30/2014 07:29 PM, Jeff King wrote:\n> On Fri, May 30, 2014 at 11:47:33AM +0200, Michael Haggerty wrote:\n>> [...]\n>> If we want to be robust to future changes to refname rules, we could add\n>> a header flag like\n>>\n>> # pack-refs with: peeled fully-peeled check-level=1.0\n> [...]\n> Yeah, I thought about mentioning something like that. But really, this\n> just seems like a lot of complexity to solve the problem in a wrong way.\n\nYes, you are right.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"243075","messageId":"CACsJy8BcmT1AKe=EYrYUs9Xyu9YUNbA3YUDafg2rZ9fabVgEiQ@mail.gmail.com","threadId":"36775","inReplyTo":"20140530000728.GC28683@sigill.intra.peff.net","subject":"Re: [PATCH] check_refname_component: Optimize","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2014-05-31T11:21:19Z","receivedAt":"2014-05-31T11:21:19Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, May 30, 2014 at 7:07 AM, Jeff King wrote:\n> But then we're just trusting that the \"trust me\" flag on disk is\n> correct. Why not just trust that packed-refs is correct in the first\n> place?\n\nI missed one thing in the first reply: because packed-refs is a plain\ntext file, the user could be tempted to edit it manually (I know I did\na few times for fast rename) and so it could not be trusted. If we\nignore this (and I think we can, it's not like we encourage people to\nedit files in $GIT_DIR), then #3 and #4 are as good as #2.\n\n>\n> IOW, consider this progression of changes:\n>\n> 1. Check refname format when we read packed-refs (the current\n> behavior).\n>\n> 2. Keep a separate file \"packed-refs.stat\" with stat information. If\n> the packed-refs file matches that stat information, do not bother\n> checking refname formats.\n>\n> 3. Put a flag in \"packed-refs\" that says \"trust me, I'm valid\". Check\n> the refnames when it is generated.\n>\n> 4. Realize that we already check the refnames when we write it out.\n> Don't bother writing \"trust me, I'm valid\"; readers can assume that\n> it is.\n>\n> What is the scenario that option (2) protects against that options (3)\n> and (4) do not?\n-- \nDuy\n"}]}