{"thread":{"id":"30630","subject":"[PATCH WIP 0/3] top-level gitignore considered less harmful","startedAt":"2012-05-26T12:31:11Z","lastAt":"2012-05-29T18:21:37Z","messageCount":14,"participants":["Nguyễn Thái Ngọc Duy","Nguyen Thai Ngoc Duy","Jeff King","Junio C Hamano","Thiago Farina"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"192235","messageId":"1338035474-4346-1-git-send-email-pclouds@gmail.com","threadId":"30630","inReplyTo":null,"subject":"[PATCH WIP 0/3] top-level gitignore considered less harmful","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-26T12:31:11Z","receivedAt":"2012-05-26T12:31:11Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"While my mind is still fresh on exclude stuff, let's do something\nto improve the big top-level gitignore situation [1].\n\nThe last patch is the real meat, where it assumes caller calls it on a\nseries of pathnames of the same dirname. It'll cache strcmp result of\nthe dirname part so we only pay the cost once per pattern for all\nentries in the same directory.\n\nThe result is not so impressive (i'm on -O0 though). Old webkit.git,\nbefore:\n\nreal 0m6.418s\nuser 0m5.561s\nsys 0m0.827s\n\nafter:\n\nreal 0m5.262s\nuser 0m4.407s\nsys 0m0.850s\n\nWe could approach the problem a different way instead: push back as\nmuch dirname as possible back to \"(struct exclude*)->base\", but I'm\nafraid that may mess thing up with all the pushing/popping in\nprep_exclude.\n\nAlso about that, we should not need to call prep_exclude() on every\npathname, at least when the caller is {fill,read}_directory().\n\nThere's another optimaztion we could do to pay even less. If users\nsort the exclude patterns, if we check dirname of one pattern and the\nnext pattern shares the same dirname, skip comparing what we have\ncompared again.\n\nThe same can be done on \"base\" (even easier because we can just\ncompare base pointer to know if they are the same) but \"base\" is for\nnon-top-level gitignore.\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/194294\n\nNguyễn Thái Ngọc Duy (3):\n Unindent excluded_from_list()\n exclude: do strcmp as much as possible before fnmatch\n exclude: reduce computation cost on checking dirname in patterns\n\n dir.c | 166 ++++++++++++++++++++++++++++++++++++++++++++++--------------------\n dir.h | 5 +-\n 2 files changed, 120 insertions(+), 51 deletions(-)\n\n-- \n1.7.10.2.549.g9354186\n"},{"id":"192236","messageId":"1338035474-4346-2-git-send-email-pclouds@gmail.com","threadId":"30630","inReplyTo":"1338035474-4346-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 1/3] Unindent excluded_from_list()","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-26T12:31:12Z","receivedAt":"2012-05-26T12:31:12Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Return early if el->nr == 0. Unindent one more level for FNM_PATHNAME\ncode block as this block is getting complex and may need more\nindentation.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n dir.c | 96 +++++++++++++++++++++++++++++++++----------------------------------\n 1 file changed, 48 insertions(+), 48 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex b65d37c..8535cf2 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -508,56 +508,56 @@ int excluded_from_list(const char *pathname,\n {\n \tint i;\n \n-\tif (el->nr) {\n-\t\tfor (i = el->nr - 1; 0 <= i; i--) {\n-\t\t\tstruct exclude *x = el->excludes[i];\n-\t\t\tconst char *exclude = x->pattern;\n-\t\t\tint to_exclude = x->to_exclude;\n-\n-\t\t\tif (x->flags & EXC_FLAG_MUSTBEDIR) {\n-\t\t\t\tif (*dtype == DT_UNKNOWN)\n-\t\t\t\t\t*dtype = get_dtype(NULL, pathname, pathlen);\n-\t\t\t\tif (*dtype != DT_DIR)\n-\t\t\t\t\tcontinue;\n-\t\t\t}\n+\tif (!el->nr)\n+\t\treturn -1;\t/* undefined */\n+\n+\tfor (i = el->nr - 1; 0 <= i; i--) {\n+\t\tstruct exclude *x = el->excludes[i];\n+\t\tconst char *exclude = x->pattern;\n+\t\tint to_exclude = x->to_exclude;\n+\n+\t\tif (x->flags & EXC_FLAG_MUSTBEDIR) {\n+\t\t\tif (*dtype == DT_UNKNOWN)\n+\t\t\t\t*dtype = get_dtype(NULL, pathname, pathlen);\n+\t\t\tif (*dtype != DT_DIR)\n+\t\t\t\tcontinue;\n+\t\t}\n \n-\t\t\tif (x->flags & EXC_FLAG_NODIR) {\n-\t\t\t\t/* match basename */\n-\t\t\t\tif (x->flags & EXC_FLAG_NOWILDCARD) {\n-\t\t\t\t\tif (!strcmp_icase(exclude, basename))\n-\t\t\t\t\t\treturn to_exclude;\n-\t\t\t\t} else if (x->flags & EXC_FLAG_ENDSWITH) {\n-\t\t\t\t\tif (x->patternlen - 1 <= pathlen &&\n-\t\t\t\t\t !strcmp_icase(exclude + 1, pathname + pathlen - x->patternlen + 1))\n-\t\t\t\t\t\treturn to_exclude;\n-\t\t\t\t} else {\n-\t\t\t\t\tif (fnmatch_icase(exclude, basename, 0) == 0)\n-\t\t\t\t\t\treturn to_exclude;\n-\t\t\t\t}\n-\t\t\t}\n-\t\t\telse {\n-\t\t\t\t/* match with FNM_PATHNAME:\n-\t\t\t\t * exclude has base (baselen long) implicitly\n-\t\t\t\t * in front of it.\n-\t\t\t\t */\n-\t\t\t\tint baselen = x->baselen;\n-\t\t\t\tif (*exclude == '/')\n-\t\t\t\t\texclude++;\n-\n-\t\t\t\tif (pathlen < baselen ||\n-\t\t\t\t (baselen && pathname[baselen-1] != '/') ||\n-\t\t\t\t strncmp_icase(pathname, x->base, baselen))\n-\t\t\t\t continue;\n-\n-\t\t\t\tif (x->flags & EXC_FLAG_NOWILDCARD) {\n-\t\t\t\t\tif (!strcmp_icase(exclude, pathname + baselen))\n-\t\t\t\t\t\treturn to_exclude;\n-\t\t\t\t} else {\n-\t\t\t\t\tif (fnmatch_icase(exclude, pathname+baselen,\n-\t\t\t\t\t\t FNM_PATHNAME) == 0)\n-\t\t\t\t\t return to_exclude;\n-\t\t\t\t}\n+\t\tif (x->flags & EXC_FLAG_NODIR) {\n+\t\t\t/* match basename */\n+\t\t\tif (x->flags & EXC_FLAG_NOWILDCARD) {\n+\t\t\t\tif (!strcmp_icase(exclude, basename))\n+\t\t\t\t\treturn to_exclude;\n+\t\t\t} else if (x->flags & EXC_FLAG_ENDSWITH) {\n+\t\t\t\tif (x->patternlen - 1 <= pathlen &&\n+\t\t\t\t !strcmp_icase(exclude + 1, pathname + pathlen - x->patternlen + 1))\n+\t\t\t\t\treturn to_exclude;\n+\t\t\t} else {\n+\t\t\t\tif (fnmatch_icase(exclude, basename, 0) == 0)\n+\t\t\t\t\treturn to_exclude;\n \t\t\t}\n+\t\t\tcontinue;\n+\t\t}\n+\n+\n+\t\t/* match with FNM_PATHNAME:\n+\t\t * exclude has base (baselen long) implicitly in front of it.\n+\t\t */\n+\t\tif (*exclude == '/')\n+\t\t\texclude++;\n+\n+\t\tif (pathlen < x->baselen ||\n+\t\t (x->baselen && pathname[x->baselen-1] != '/') ||\n+\t\t strncmp_icase(pathname, x->base, x->baselen))\n+\t\t\tcontinue;\n+\n+\t\tif (x->flags & EXC_FLAG_NOWILDCARD) {\n+\t\t\tif (!strcmp_icase(exclude, pathname + x->baselen))\n+\t\t\t\treturn to_exclude;\n+\t\t} else {\n+\t\t\tif (fnmatch_icase(exclude, pathname+x->baselen,\n+\t\t\t\t\t FNM_PATHNAME) == 0)\n+\t\t\t\treturn to_exclude;\n \t\t}\n \t}\n \treturn -1; /* undecided */\n-- \n1.7.10.2.549.g9354186\n"},{"id":"192237","messageId":"1338035474-4346-3-git-send-email-pclouds@gmail.com","threadId":"30630","inReplyTo":"1338035474-4346-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 2/3] exclude: do strcmp as much as possible before fnmatch","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-26T12:31:13Z","receivedAt":"2012-05-26T12:31:13Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"this also avoids calling fnmatch() if the non-wildcard prefix is\nlonger than basename\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n dir.c | 41 +++++++++++++++++++++++++++--------------\n dir.h | 2 +-\n 2 files changed, 28 insertions(+), 15 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 8535cf2..50d744f 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -295,9 +295,11 @@ int match_pathspec_depth(const struct pathspec *ps,\n \treturn retval;\n }\n \n+const char *wildcards = \"*?[{\\\\\";\n+\n static int no_wildcard(const char *string)\n {\n-\treturn string[strcspn(string, \"*?[{\\\\\")] == '\\0';\n+\treturn string[strcspn(string, wildcards)] == '\\0';\n }\n \n void add_exclude(const char *string, const char *base,\n@@ -336,8 +338,7 @@ void add_exclude(const char *string, const char *base,\n \tx->flags = flags;\n \tif (!strchr(string, '/'))\n \t\tx->flags |= EXC_FLAG_NODIR;\n-\tif (no_wildcard(string))\n-\t\tx->flags |= EXC_FLAG_NOWILDCARD;\n+\tx->nowildcardlen = strcspn(string, wildcards);\n \tif (*string == '*' && no_wildcard(string+1))\n \t\tx->flags |= EXC_FLAG_ENDSWITH;\n \tALLOC_GROW(which->excludes, which->nr + 1, which->alloc);\n@@ -513,8 +514,9 @@ int excluded_from_list(const char *pathname,\n \n \tfor (i = el->nr - 1; 0 <= i; i--) {\n \t\tstruct exclude *x = el->excludes[i];\n-\t\tconst char *exclude = x->pattern;\n+\t\tconst char *name, *exclude = x->pattern;\n \t\tint to_exclude = x->to_exclude;\n+\t\tint namelen, prefix = x->nowildcardlen;\n \n \t\tif (x->flags & EXC_FLAG_MUSTBEDIR) {\n \t\t\tif (*dtype == DT_UNKNOWN)\n@@ -525,7 +527,7 @@ int excluded_from_list(const char *pathname,\n \n \t\tif (x->flags & EXC_FLAG_NODIR) {\n \t\t\t/* match basename */\n-\t\t\tif (x->flags & EXC_FLAG_NOWILDCARD) {\n+\t\t\tif (prefix == x->patternlen) {\n \t\t\t\tif (!strcmp_icase(exclude, basename))\n \t\t\t\t\treturn to_exclude;\n \t\t\t} else if (x->flags & EXC_FLAG_ENDSWITH) {\n@@ -539,26 +541,37 @@ int excluded_from_list(const char *pathname,\n \t\t\tcontinue;\n \t\t}\n \n-\n \t\t/* match with FNM_PATHNAME:\n \t\t * exclude has base (baselen long) implicitly in front of it.\n \t\t */\n-\t\tif (*exclude == '/')\n+\t\tif (*exclude == '/') {\n \t\t\texclude++;\n+\t\t\tprefix--;\n+\t\t}\n \n \t\tif (pathlen < x->baselen ||\n \t\t (x->baselen && pathname[x->baselen-1] != '/') ||\n \t\t strncmp_icase(pathname, x->base, x->baselen))\n \t\t\tcontinue;\n \n-\t\tif (x->flags & EXC_FLAG_NOWILDCARD) {\n-\t\t\tif (!strcmp_icase(exclude, pathname + x->baselen))\n-\t\t\t\treturn to_exclude;\n-\t\t} else {\n-\t\t\tif (fnmatch_icase(exclude, pathname+x->baselen,\n-\t\t\t\t\t FNM_PATHNAME) == 0)\n-\t\t\t\treturn to_exclude;\n+\t\tnamelen = x->baselen ? pathlen - x->baselen : pathlen;\n+\t\tname = pathname + pathlen - namelen;\n+\n+\t\t/* if the non-wildcard part is longer than the\n+\t\t remaining pathname, surely it cannot match */\n+\t\tif (prefix > namelen)\n+\t\t\tcontinue;\n+\n+\t\tif (prefix) {\n+\t\t\tif (strncmp_icase(exclude, name, prefix))\n+\t\t\t\tcontinue;\n+\t\t\texclude += prefix;\n+\t\t\tname += prefix;\n+\t\t\tnamelen -= prefix;\n \t\t}\n+\n+\t\tif (!namelen || !fnmatch_icase(exclude, name, FNM_PATHNAME))\n+\t\t\treturn to_exclude;\n \t}\n \treturn -1; /* undecided */\n }\ndiff --git a/dir.h b/dir.h\nindex 58b6fc7..39fc145 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -7,7 +7,6 @@ struct dir_entry {\n };\n \n #define EXC_FLAG_NODIR 1\n-#define EXC_FLAG_NOWILDCARD 2\n #define EXC_FLAG_ENDSWITH 4\n #define EXC_FLAG_MUSTBEDIR 8\n \n@@ -17,6 +16,7 @@ struct exclude_list {\n \tstruct exclude {\n \t\tconst char *pattern;\n \t\tint patternlen;\n+\t\tint nowildcardlen;\n \t\tconst char *base;\n \t\tint baselen;\n \t\tint to_exclude;\n-- \n1.7.10.2.549.g9354186\n"},{"id":"192238","messageId":"1338035474-4346-4-git-send-email-pclouds@gmail.com","threadId":"30630","inReplyTo":"1338035474-4346-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 3/3] exclude: reduce computation cost on checking dirname in patterns","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-26T12:31:14Z","receivedAt":"2012-05-26T12:31:14Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n dir.c | 55 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-\n dir.h | 3 +++\n 2 files changed, 57 insertions(+), 1 deletion(-)\n\ndiff --git a/dir.c b/dir.c\nindex 50d744f..ff5e2d9 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -507,7 +507,7 @@ int excluded_from_list(const char *pathname,\n \t\t int pathlen, const char *basename, int *dtype,\n \t\t struct exclude_list *el)\n {\n-\tint i;\n+\tint i, baselen = pathlen - (basename - pathname);\n \n \tif (!el->nr)\n \t\treturn -1;\t/* undefined */\n@@ -562,6 +562,35 @@ int excluded_from_list(const char *pathname,\n \t\tif (prefix > namelen)\n \t\t\tcontinue;\n \n+\t\t/*\n+\t\t * it's supposed that the caller throws a series of pathnames of\n+\t\t * the same dirname to this function when el->pruning != 0.\n+\t\t *\n+\t\t * If we could check whether a pattern matches dirname, we could\n+\t\t * save the result and reuse for next pathnames. The caller\n+\t\t * must reset pruned/dir_matched bits when it moves to a\n+\t\t * different directory.\n+\t\t */\n+\t\tif (el->samedir && prefix >= namelen - baselen) {\n+\t\t\tint matched;\n+\t\t\tif (x->flags & EXC_FLAG_DIR_MATCH_VALID)\n+\t\t\t\tmatched = x->flags & EXC_FLAG_DIR_MATCHED;\n+\t\t\telse {\n+\t\t\t\tmatched = !strncmp_icase(exclude, name, namelen - baselen);\n+\t\t\t\tif (matched)\n+\t\t\t\t\tx->flags |= EXC_FLAG_DIR_MATCHED;\n+\t\t\t\tx->flags |= EXC_FLAG_DIR_MATCH_VALID;\n+\t\t\t}\n+\n+\t\t\tif (!matched)\n+\t\t\t\tcontinue;\n+\n+\t\t\tprefix -= namelen - baselen;\n+\t\t\texclude += namelen - baselen;\n+\t\t\tname = basename;\n+\t\t\tnamelen = baselen;\n+\t\t}\n+\n \t\tif (prefix) {\n \t\t\tif (strncmp_icase(exclude, name, prefix))\n \t\t\t\tcontinue;\n@@ -576,6 +605,28 @@ int excluded_from_list(const char *pathname,\n \treturn -1; /* undecided */\n }\n \n+static void prep_exclude_read_directory(struct dir_struct *dir,\n+\t\t\t\t\tconst struct strbuf *path)\n+{\n+\tint i, st;\n+\tprep_exclude(dir, path->buf, path->len);\n+\tfor (st = EXC_CMDL; st <= EXC_FILE; st++) {\n+\t\tstruct exclude_list *el = dir->exclude_list + st;\n+\t\tel->samedir = 1;\n+\t\tfor (i = 0; i < el->nr; i++)\n+\t\t\tel->excludes[i]->flags &= ~EXC_FLAG_DIR_MATCH_VALID;\n+\t}\n+}\n+\n+static void cleanup_exclude_read_directory(struct dir_struct *dir)\n+{\n+\tint st;\n+\tfor (st = EXC_CMDL; st <= EXC_FILE; st++) {\n+\t\tstruct exclude_list *el = dir->exclude_list + st;\n+\t\tel->samedir = 0;\n+\t}\n+}\n+\n int excluded(struct dir_struct *dir, const char *pathname, int *dtype_p)\n {\n \tint pathlen = strlen(pathname);\n@@ -985,6 +1036,7 @@ static int read_directory_recursive(struct dir_struct *dir,\n \t\treturn 0;\n \n \tstrbuf_add(&path, base, baselen);\n+\tprep_exclude_read_directory(dir, &path);\n \n \twhile ((de = readdir(fdir)) != NULL) {\n \t\tswitch (treat_path(dir, de, &path, baselen, simplify)) {\n@@ -1005,6 +1057,7 @@ static int read_directory_recursive(struct dir_struct *dir,\n \t\t\tdir_add_name(dir, path.buf, path.len);\n \t}\n exit_early:\n+\tcleanup_exclude_read_directory(dir);\n \tclosedir(fdir);\n \tstrbuf_release(&path);\n \ndiff --git a/dir.h b/dir.h\nindex 39fc145..003daf4 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -7,12 +7,15 @@ struct dir_entry {\n };\n \n #define EXC_FLAG_NODIR 1\n+#define EXC_FLAG_DIR_MATCH_VALID 2\n #define EXC_FLAG_ENDSWITH 4\n #define EXC_FLAG_MUSTBEDIR 8\n+#define EXC_FLAG_DIR_MATCHED 16\n \n struct exclude_list {\n \tint nr;\n \tint alloc;\n+\tint samedir;\n \tstruct exclude {\n \t\tconst char *pattern;\n \t\tint patternlen;\n-- \n1.7.10.2.549.g9354186\n"},{"id":"192243","messageId":"CACsJy8Bbn3hSDC_LmFtOXfJZhV9SqStwSSXFwcQLjDyUUAjOpQ@mail.gmail.com","threadId":"30630","inReplyTo":"1338035474-4346-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH WIP 0/3] top-level gitignore considered less harmful","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-26T13:25:54Z","receivedAt":"2012-05-26T13:25:54Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, May 26, 2012 at 7:31 PM, Nguyễn Thái Ngọc Duy wrote:\n> The result is not so impressive (i'm on -O0 though). Old webkit.git,\n> before:\n\n(it's \"git status\" by the way)\n\n>\n> real    0m6.418s\n> user    0m5.561s\n> sys     0m0.827s\n>\n> after:\n>\n> real    0m5.262s\n> user    0m4.407s\n> sys     0m0.850s\n\nand with your patch to redistribute .gitignore in webkit, so top-level\nis small again:\n\nreal 0m4.185s\nuser 0m3.271s\nsys 0m0.905s\n\nso my numbers look \"ok\".\n-- \nDuy\n"},{"id":"192250","messageId":"20120526214529.GA29463@sigill.intra.peff.net","threadId":"30630","inReplyTo":"CACsJy8Bbn3hSDC_LmFtOXfJZhV9SqStwSSXFwcQLjDyUUAjOpQ@mail.gmail.com","subject":"Re: [PATCH WIP 0/3] top-level gitignore considered less harmful","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-26T21:45:29Z","receivedAt":"2012-05-26T21:45:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, May 26, 2012 at 08:25:54PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> On Sat, May 26, 2012 at 7:31 PM, Nguyễn Thái Ngọc Duy wrote:\n> > The result is not so impressive (i'm on -O0 though). Old webkit.git,\n> > before:\n> \n> (it's \"git status\" by the way)\n> \n> >\n> > real    0m6.418s\n> > user    0m5.561s\n> > sys     0m0.827s\n> >\n> > after:\n> >\n> > real    0m5.262s\n> > user    0m4.407s\n> > sys     0m0.850s\n> \n> and with your patch to redistribute .gitignore in webkit, so top-level\n> is small again:\n> \n> real 0m4.185s\n> user 0m3.271s\n> sys 0m0.905s\n> \n> so my numbers look \"ok\".\n\nIs that last number just with the redistribution, or with the\nredistribution _and_ your patch? I'd like to see both to see whether it\nis the case that the two optimizations work together for combined\nbenefit, or if doing one makes the other one pointless.\n\n-Peff\n"},{"id":"192256","messageId":"CACsJy8AAqQ-VBhuEwH01ym16T2sMUMBJJhXpqBMD72B8tU7=2Q@mail.gmail.com","threadId":"30630","inReplyTo":"20120526214529.GA29463@sigill.intra.peff.net","subject":"Re: [PATCH WIP 0/3] top-level gitignore considered less harmful","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-27T03:45:44Z","receivedAt":"2012-05-27T03:45:44Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, May 27, 2012 at 4:45 AM, Jeff King wrote:\n> On Sat, May 26, 2012 at 08:25:54PM +0700, Nguyen Thai Ngoc Duy wrote:\n>\n>> On Sat, May 26, 2012 at 7:31 PM, Nguyễn Thái Ngọc Duy wrote:\n>> > The result is not so impressive (i'm on -O0 though). Old webkit.git,\n>> > before:\n>>\n>> (it's \"git status\" by the way)\n>>\n>> >\n>> > real    0m6.418s\n>> > user    0m5.561s\n>> > sys     0m0.827s\n>> >\n>> > after:\n>> >\n>> > real    0m5.262s\n>> > user    0m4.407s\n>> > sys     0m0.850s\n>>\n>> and with your patch to redistribute .gitignore in webkit, so top-level\n>> is small again:\n>>\n>> real    0m4.185s\n>> user    0m3.271s\n>> sys     0m0.905s\n>>\n>> so my numbers look \"ok\".\n>\n> Is that last number just with the redistribution, or with the\n> redistribution _and_ your patch? I'd like to see both to see whether it\n> is the case that the two optimizations work together for combined\n> benefit, or if doing one makes the other one pointless.\n\nwithout my patch. redistribution with my patch is:\n\nreal 0m4.284s\nuser 0m3.407s\nsys 0m0.864s\n-- \nDuy\n"},{"id":"192260","messageId":"7vk3zyp14i.fsf@alter.siamese.dyndns.org","threadId":"30630","inReplyTo":"1338035474-4346-3-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH 2/3] exclude: do strcmp as much as possible before fnmatch","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-27T06:51:57Z","receivedAt":"2012-05-27T06:51:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy writes:\n\n> this also avoids calling fnmatch() if the non-wildcard prefix is\n> longer than basename\n>\n> Signed-off-by: Nguyễn Thái Ngọc Duy \n> ---\n\nI have been wondering if you can take a different approach based on the\nsame observation this patch is based on. If you see an entry /foo/bar/*.c\nin the top-level .gitignore, perhaps you can set it aside in a different\npart of \"struct exclude\" for the top-level directory (because the pattern\nwill never match outside foo/bar directory), so that it is not even used\nfor matching, and only when you descend to foo/bar directory, add \"/*.c\"\nto the \"struct exclude\" you create for that directory.\n\nThat way, instead of \"strcmp is faster than fnmatch, but we always compare\nall elements in the huge pattern list given at the toplevel\", you would be\ndoing \"we do not even bother to compare with the elements we know do not\nmatter\", which would be far more efficient, no?\n"},{"id":"192265","messageId":"CACsJy8DOz30GD_zv9yO7KD55+=H0t=+q_5qRtt51nOoYXwOBBQ@mail.gmail.com","threadId":"30630","inReplyTo":"7vk3zyp14i.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/3] exclude: do strcmp as much as possible before fnmatch","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-27T12:06:14Z","receivedAt":"2012-05-27T12:06:14Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, May 27, 2012 at 1:51 PM, Junio C Hamano wrote:\n> Nguyễn Thái Ngọc Duy   writes:\n>\n>> this also avoids calling fnmatch() if the non-wildcard prefix is\n>> longer than basename\n>>\n>> Signed-off-by: Nguyễn Thái Ngọc Duy \n>> ---\n>\n> I have been wondering if you can take a different approach based on the\n> same observation this patch is based on.  If you see an entry /foo/bar/*.c\n> in the top-level .gitignore, perhaps you can set it aside in a different\n> part of \"struct exclude\" for the top-level directory (because the pattern\n> will never match outside foo/bar directory), so that it is not even used\n> for matching, and only when you descend to foo/bar directory, add \"/*.c\"\n> to the \"struct exclude\" you create for that directory.\n\nthat part is \"base\" field in \"struct exclude\", I believe.\n\n> That way, instead of \"strcmp is faster than fnmatch, but we always compare\n> all elements in the huge pattern list given at the toplevel\", you would be\n> doing \"we do not even bother to compare with the elements we know do not\n> matter\", which would be far more efficient, no?\n\nYou still have to do at least one strncmp on \"base\" though to know if\na pattern is applicable to the given directory. So it's not really\ncheaper than what is done in 3/3.\n-- \nDuy\n"},{"id":"192295","messageId":"7v8vgd7ap9.fsf@alter.siamese.dyndns.org","threadId":"30630","inReplyTo":"CACsJy8DOz30GD_zv9yO7KD55+=H0t=+q_5qRtt51nOoYXwOBBQ@mail.gmail.com","subject":"Re: [PATCH 2/3] exclude: do strcmp as much as possible before fnmatch","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-27T18:14:42Z","receivedAt":"2012-05-27T18:14:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyen Thai Ngoc Duy writes:\n\n>> I have been wondering if you can take a different approach based on the\n>> same observation this patch is based on.  If you see an entry /foo/bar/*.c\n>> in the top-level .gitignore, perhaps you can set it aside in a different\n>> part of \"struct exclude\" for the top-level directory (because the pattern\n>> will never match outside foo/bar directory), so that it is not even used\n>> for matching, and only when you descend to foo/bar directory, add \"/*.c\"\n>> to the \"struct exclude\" you create for that directory.\n>\n> that part is \"base\" field in \"struct exclude\", I believe.\n\nSorry, I misspoke; it is not about struct exclude at all.\n\n>> That way, instead of \"strcmp is faster than fnmatch, but we always compare\n>> all elements in the huge pattern list given at the toplevel\", you would be\n>> doing \"we do not even bother to compare with the elements we know do not\n>> matter\", which would be far more efficient, no?\n>\n> You still have to do at least one strncmp on \"base\" though to know if\n> a pattern is applicable to the given directory. So it's not really\n> cheaper than what is done in 3/3.\n\nActually I was referring to the exclude_stack.\n\nSuppose you have .gitignore file at the top that lists /foo/bar/*.c\n(among other millions of patterns anchored to specific directory),\nand another in the foo/bar directory. When you are looking at a\npath in the top-level, currently the exclude_stack would have one\nelement, per-directory one for .gitignore at the top, that has\nmillions of patterns that would never match. And then when you\ndescend into foo/bar directory, prep_exclude would link two elements\n(one for foo/ directory which may be empty, another for foo/bar\ndirectory) to this, and then you check paths you see in foo/bar\ndirectory using all the elements that appear in the exclude_stack.\n\nWhat I was suggesting was that you could choose not to add\n/foo/bar/*.c entry in the exclude_stack element for the top-level\n(but remember you did so), and then inside prep_exclude() when you\nlook at different directory, e.g. foo/bar, notice that higher level\n(i.e. toplevel in this example) has such a deferred patterns that\napplies to the new directory. Then instead of adding /foo/bar/*.c\nat the top-level, you can pretend as if /*.c appeared in .gitignore\nfile in the deeper level in the hierarchy.\n\nAnd this does not happen per path you check; exclude_stack used by\nexcluded() is designed to take advantage of the access pattern that\nwe tend to check paths from the same directory together, so such an\nadjustment will be per directory switching (i.e. it will be part of\nthe prep_exclude() overhead that is amortized over paths you walk).\n"},{"id":"192301","messageId":"CACsJy8ApRn65_Okeg+T41+fLv_Z4tMMUGrGMZN979q=JaYmogg@mail.gmail.com","threadId":"30630","inReplyTo":"7v8vgd7ap9.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/3] exclude: do strcmp as much as possible before fnmatch","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-28T01:03:42Z","receivedAt":"2012-05-28T01:03:42Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, May 28, 2012 at 1:14 AM, Junio C Hamano wrote:\n> Actually I was referring to the exclude_stack.\n>\n> Suppose you have .gitignore file at the top that lists /foo/bar/*.c\n> (among other millions of patterns anchored to specific directory),\n> and another in the foo/bar directory.  When you are looking at a\n> path in the top-level, currently the exclude_stack would have one\n> element, per-directory one for .gitignore at the top, that has\n> millions of patterns that would never match.  And then when you\n> descend into foo/bar directory, prep_exclude would link two elements\n> (one for foo/ directory which may be empty, another for foo/bar\n> directory) to this, and then you check paths you see in foo/bar\n> directory using all the elements that appear in the exclude_stack.\n>\n> What I was suggesting was that you could choose not to add\n> /foo/bar/*.c entry in the exclude_stack element for the top-level\n> (but remember you did so), and then inside prep_exclude() when you\n> look at different directory, e.g. foo/bar, notice that higher level\n> (i.e. toplevel in this example) has such a deferred patterns that\n> applies to the new directory.  Then instead of adding /foo/bar/*.c\n> at the top-level, you can pretend as if /*.c appeared in .gitignore\n> file in the deeper level in the hierarchy.\n>\n> And this does not happen per path you check; exclude_stack used by\n> excluded() is designed to take advantage of the access pattern that\n> we tend to check paths from the same directory together, so such an\n> adjustment will be per directory switching (i.e. it will be part of\n> the prep_exclude() overhead that is amortized over paths you walk).\n\nThat's perhaps a better approach. Two points (for myself to think\nagain after work):\n\n - that involves reordering the stack to make sure we always have\ngitignore \"files\" in root dir first, then 1st level... after we split\nsome patterns from top-level file to deeper level, so that popping\nworks without major change\n - the implication due to pattern reordering (probably keep the order\nas we currently have. Suppose we checking in \"sub\", then sub/...\npatterns from top-level go first, then from sub/.gitignore)\n-- \nDuy\n"},{"id":"192304","messageId":"7vwr3w6gqd.fsf@alter.siamese.dyndns.org","threadId":"30630","inReplyTo":"7v8vgd7ap9.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/3] exclude: do strcmp as much as possible before fnmatch","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-28T05:02:02Z","receivedAt":"2012-05-28T05:02:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> And this does not happen per path you check; exclude_stack used by\n> excluded() is designed to take advantage of the access pattern that\n> we tend to check paths from the same directory together, so such an\n> adjustment will be per directory switching (i.e. it will be part of\n> the prep_exclude() overhead that is amortized over paths you walk).\n\nJust in case it wasn't clear, I didn't mean to say \"mine is the\nright way to do so; I will reject your patch that doesn't do so\".\n"},{"id":"192420","messageId":"7v8vga6f1a.fsf@alter.siamese.dyndns.org","threadId":"30630","inReplyTo":"1338035474-4346-3-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH 2/3] exclude: do strcmp as much as possible before fnmatch","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-29T18:03:13Z","receivedAt":"2012-05-29T18:03:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy writes:\n\n> this also avoids calling fnmatch() if the non-wildcard prefix is\n> longer than basename\n>\n> Signed-off-by: Nguyễn Thái Ngọc Duy \n> ---\n> dir.c | 41 +++++++++++++++++++++++++++--------------\n> dir.h | 2 +-\n> 2 files changed, 28 insertions(+), 15 deletions(-)\n>\n> diff --git a/dir.c b/dir.c\n> index 8535cf2..50d744f 100644\n> --- a/dir.c\n> +++ b/dir.c\n> @@ -295,9 +295,11 @@ int match_pathspec_depth(const struct pathspec *ps,\n> \treturn retval;\n> }\n> \n> +const char *wildcards = \"*?[{\\\\\";\n\nElsewhere in this file, the logic to notice the non-wildcard part of\nthe pathspec uses is_glob_special(). Shouldn't the new code that\nuse this do the same?\n"},{"id":"192421","messageId":"CACnwZYeB2Da5mEtw9xX9pPnCa=Ld4WoePsJytn90L9XwO2+WxQ@mail.gmail.com","threadId":"30630","inReplyTo":"7v8vga6f1a.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/3] exclude: do strcmp as much as possible before fnmatch","fromName":"Thiago Farina","fromEmail":"tfransosi@gmail.com","sentAt":"2012-05-29T18:21:37Z","receivedAt":"2012-05-29T18:21:37Z","isPatch":true,"sender":{"key":"tfransosi@gmail.com","avatar":"https://avatars.githubusercontent.com/u/970071?v=4"},"body":"On Tue, May 29, 2012 at 3:03 PM, Junio C Hamano wrote:\n> Nguyễn Thái Ngọc Duy   writes:\n>\n>> this also avoids calling fnmatch() if the non-wildcard prefix is\n>> longer than basename\n>>\n>> Signed-off-by: Nguyễn Thái Ngọc Duy \n>> ---\n>>  dir.c | 41 +++++++++++++++++++++++++++--------------\n>>  dir.h |  2 +-\n>>  2 files changed, 28 insertions(+), 15 deletions(-)\n>>\n>> diff --git a/dir.c b/dir.c\n>> index 8535cf2..50d744f 100644\n>> --- a/dir.c\n>> +++ b/dir.c\n>> @@ -295,9 +295,11 @@ int match_pathspec_depth(const struct pathspec *ps,\n>>       return retval;\n>>  }\n>>\n>> +const char *wildcards = \"*?[{\\\\\";\n>\nnit: can this be const char wildcards[] = \"...\"; ?\n\nalso an unrelated question, is there a style guide for naming\nconstants like this? In chromium project we write them like kFoo.\n"}]}