{"thread":{"id":"33112","subject":"[PATCH 1/3] match_pathname: avoid calling strncmp if baselen is 0","startedAt":"2013-03-09T04:09:47Z","lastAt":"2013-03-14T13:05:57Z","messageCount":48,"participants":["Nguyễn Thái Ngọc Duy","Junio C Hamano","Fredrik Gustafsson","Antoine Pelisse","Duy Nguyen","Eric Sunshine"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"210867","messageId":"1362802190-7331-1-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":null,"subject":"[PATCH 0/3] Trivial (and small) exclude optimizations","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-09T04:09:47Z","receivedAt":"2013-03-09T04:09:47Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"I've been examining how and where str*cmp are called by\nread_directory(). They are presumably where most of the time is spent.\nThe gain is not big, but still worth it, I think.\n\nThese are tested without nd/read-directory-recursive-optim. The saving\nis probably smaller as nd/read... cuts down a big number of entries to\nbe processed by exclude machinery.\n\nThere is another optimization window, which a simple hack suggests it\nmay shave 100ms out of 500ms ls-files time on my machine. Say you have\n\"/INSTALL\" in your root .gitignore. The pattern will be tested for\n_all_ pathnames including \"path/deep/down/here\". By limiting the\npattern to pathnames of the same directory level, the number of\napplicable pathnames to the pattern will be usually small and limited\n(otherwise as the repository grows with more pathnames, we pay more\nfor exclude). Haven't figured out how to save directory level yet\nthough.\n\nNguyễn Thái Ngọc Duy (3):\n match_pathname: avoid calling strncmp if baselen is 0\n dir.c: inline convenient *_icase helpers\n match_basename: use strncmp instead of strcmp\n\n attr.c | 2 ++\n dir.c | 26 ++++++--------------------\n dir.h | 18 +++++++++++++++---\n 3 files changed, 23 insertions(+), 23 deletions(-)\n\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"210866","messageId":"1362802190-7331-2-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1362802190-7331-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 1/3] match_pathname: avoid calling strncmp if baselen is 0","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-09T04:09:48Z","receivedAt":"2013-03-09T04:09:48Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This reduces \"git status\" user time by a little bit. This is the\nsorted results of 10 consecutive runs of \"git ls-files\n--exclude-standard -o\" on webkit.git, compiled with gcc -O2:\n\n before after\nuser 0m0.580s 0m0.546s\nuser 0m0.581s 0m0.549s\nuser 0m0.582s 0m0.550s\nuser 0m0.584s 0m0.558s\nuser 0m0.586s 0m0.560s\nuser 0m0.587s 0m0.561s\nuser 0m0.587s 0m0.562s\nuser 0m0.593s 0m0.566s\nuser 0m0.597s 0m0.568s\nuser 0m0.601s 0m0.573s\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n dir.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/dir.c b/dir.c\nindex 57394e4..669cf80 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -663,7 +663,7 @@ int match_pathname(const char *pathname, int pathlen,\n \t */\n \tif (pathlen < baselen + 1 ||\n \t (baselen && pathname[baselen] != '/') ||\n-\t strncmp_icase(pathname, base, baselen))\n+\t (baselen && strncmp_icase(pathname, base, baselen)))\n \t\treturn 0;\n \n \tnamelen = baselen ? pathlen - baselen - 1 : pathlen;\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"210868","messageId":"1362802190-7331-3-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1362802190-7331-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 2/3] dir.c: inline convenient *_icase helpers","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-09T04:09:49Z","receivedAt":"2013-03-09T04:09:49Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Like the previous patch, this cuts down the number of str*cmp calls in\nread_directory (which does _a lot_). Again sorted results on webkit.git:\n\n before after\nuser 0m0.546s 0m0.519s\nuser 0m0.549s 0m0.521s\nuser 0m0.550s 0m0.523s\nuser 0m0.558s 0m0.532s\nuser 0m0.560s 0m0.534s\nuser 0m0.561s 0m0.536s\nuser 0m0.562s 0m0.537s\nuser 0m0.566s 0m0.545s\nuser 0m0.568s 0m0.546s\nuser 0m0.573s 0m0.548s\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n dir.c | 16 ----------------\n dir.h | 18 +++++++++++++++---\n 2 files changed, 15 insertions(+), 19 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 669cf80..f58320d 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -21,22 +21,6 @@ static int read_directory_recursive(struct dir_struct *dir, const char *path, in\n \tint check_only, const struct path_simplify *simplify);\n static int get_dtype(struct dirent *de, const char *path, int len);\n \n-/* helper string functions with support for the ignore_case flag */\n-int strcmp_icase(const char *a, const char *b)\n-{\n-\treturn ignore_case ? strcasecmp(a, b) : strcmp(a, b);\n-}\n-\n-int strncmp_icase(const char *a, const char *b, size_t count)\n-{\n-\treturn ignore_case ? strncasecmp(a, b, count) : strncmp(a, b, count);\n-}\n-\n-int fnmatch_icase(const char *pattern, const char *string, int flags)\n-{\n-\treturn fnmatch(pattern, string, flags | (ignore_case ? FNM_CASEFOLD : 0));\n-}\n-\n inline int git_fnmatch(const char *pattern, const char *string,\n \t\t int flags, int prefix)\n {\ndiff --git a/dir.h b/dir.h\nindex c3eb4b5..560ade4 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -200,9 +200,21 @@ extern int remove_dir_recursively(struct strbuf *path, int flag);\n /* tries to remove the path with empty directories along it, ignores ENOENT */\n extern int remove_path(const char *path);\n \n-extern int strcmp_icase(const char *a, const char *b);\n-extern int strncmp_icase(const char *a, const char *b, size_t count);\n-extern int fnmatch_icase(const char *pattern, const char *string, int flags);\n+/* helper string functions with support for the ignore_case flag */\n+static inline int strcmp_icase(const char *a, const char *b)\n+{\n+\treturn ignore_case ? strcasecmp(a, b) : strcmp(a, b);\n+}\n+\n+static inline int strncmp_icase(const char *a, const char *b, size_t count)\n+{\n+\treturn ignore_case ? strncasecmp(a, b, count) : strncmp(a, b, count);\n+}\n+\n+static inline int fnmatch_icase(const char *pattern, const char *string, int flags)\n+{\n+\treturn fnmatch(pattern, string, flags | (ignore_case ? FNM_CASEFOLD : 0));\n+}\n \n /*\n * The prefix part of pattern must not contains wildcards.\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"210869","messageId":"1362802190-7331-4-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1362802190-7331-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 3/3] match_basename: use strncmp instead of strcmp","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-09T04:09:50Z","receivedAt":"2013-03-09T04:09:50Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"strncmp provides length information, compared to strcmp, which could\nbe taken advantage by the implementation. Even better, we could check\nif the lengths are equal before calling strncmp, eliminating a bit of\nstrncmp calls.\n\n before after\nuser 0m0.519s 0m0.489s\nuser 0m0.521s 0m0.504s\nuser 0m0.523s 0m0.507s\nuser 0m0.532s 0m0.510s\nuser 0m0.534s 0m0.513s\nuser 0m0.536s 0m0.514s\nuser 0m0.537s 0m0.522s\nuser 0m0.545s 0m0.523s\nuser 0m0.546s 0m0.527s\nuser 0m0.548s 0m0.529s\n\nWhile at there, fix an inconsistency about pattern/patternlen in how\nattr handles EXC_FLAG_MUSTBEDIR. When parse_exclude_pattern detects\nthis flag, it sets patternlen _not_ to include the trailing slash and\nexpects the caller to trim it. add_exclude does, parse_attr_line does\nnot.\n\nIn attr.c, the pattern could be \"foo/\" while patternlen tells us it\nonly has 3 chars. Some functions do not care about patternlen and will\nsee the pattern as \"foo/\" while others may see it as \"foo\". This patch\nmakes patternlen 4 in this case. (Although for a piece of mind,\nperhaps we should trim it to \"foo\" like exclude, and never pass a\npathname like \"abc/\" to match_{base,path}name)\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n attr.c | 2 ++\n dir.c | 8 +++++---\n 2 files changed, 7 insertions(+), 3 deletions(-)\n\ndiff --git a/attr.c b/attr.c\nindex e2f9377..1818ba5 100644\n--- a/attr.c\n+++ b/attr.c\n@@ -255,6 +255,8 @@ static struct match_attr *parse_attr_line(const char *line, const char *src,\n \t\t\t\t &res->u.pat.patternlen,\n \t\t\t\t &res->u.pat.flags,\n \t\t\t\t &res->u.pat.nowildcardlen);\n+\t\tif (res->u.pat.flags & EXC_FLAG_MUSTBEDIR)\n+\t\t\tres->u.pat.patternlen++;\n \t\tif (res->u.pat.flags & EXC_FLAG_NEGATIVE) {\n \t\t\twarning(_(\"Negative patterns are ignored in git attributes\\n\"\n \t\t\t\t \"Use '\\\\!' for literal leading exclamation.\"));\ndiff --git a/dir.c b/dir.c\nindex f58320d..2a91d14 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -610,12 +610,14 @@ int match_basename(const char *basename, int basenamelen,\n \t\t int flags)\n {\n \tif (prefix == patternlen) {\n-\t\tif (!strcmp_icase(pattern, basename))\n+\t\tif (patternlen == basenamelen &&\n+\t\t !strncmp_icase(pattern, basename, patternlen))\n \t\t\treturn 1;\n \t} else if (flags & EXC_FLAG_ENDSWITH) {\n \t\tif (patternlen - 1 <= basenamelen &&\n-\t\t !strcmp_icase(pattern + 1,\n-\t\t\t\t basename + basenamelen - patternlen + 1))\n+\t\t !strncmp_icase(pattern + 1,\n+\t\t\t\t basename + basenamelen - patternlen + 1,\n+\t\t\t\t patternlen - 1))\n \t\t\treturn 1;\n \t} else {\n \t\tif (fnmatch_icase(pattern, basename, 0) == 0)\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"210874","messageId":"7v4nglf1w3.fsf@alter.siamese.dyndns.org","threadId":"33112","inReplyTo":"1362802190-7331-4-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH 3/3] match_basename: use strncmp instead of strcmp","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-09T07:50:04Z","receivedAt":"2013-03-09T07:50:04Z","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> strncmp provides length information, compared to strcmp, which could\n> be taken advantage by the implementation. Even better, we could check\n> if the lengths are equal before calling strncmp, eliminating a bit of\n> strncmp calls.\n\nI think I am a bit slower than my usual self tonight, but I am\nutterly confused by the above.\n\nstrncmp() compares _only_ up to the first n bytes, so when you are\nusing it for equality, it is not \"we could check length\", but is \"we\nMUST check they match to the length of the shorter string\", if you\nwant to obtain not just faster but correct result.\n\nAm I mistaken?\n\nEven if you are using strcmp() that yields ordering not just\nequality, it can return a correct result as soon as it hits the\nfirst bytes that are different; I doubt using strncmp() contributes\nto the performance very much. Comparing lengths before doing\nbyte-for-byte comparison could help because you can reject two\nstrings with different lengths without looking at them.\n\nAt the same time, I wonder if we can take advantage of the fact that\nthese call sites only care about equality and not ordering.\n"},{"id":"210883","messageId":"20130309084759.GA8688@paksenarrion.iveqy.com","threadId":"33112","inReplyTo":"7v4nglf1w3.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/3] match_basename: use strncmp instead of strcmp","fromName":"Fredrik Gustafsson","fromEmail":"iveqy@iveqy.com","sentAt":"2013-03-09T08:47:59Z","receivedAt":"2013-03-09T08:47:59Z","isPatch":true,"sender":{"key":"iveqy@iveqy.com","avatar":"https://avatars.githubusercontent.com/u/761743?v=4"},"body":"On Fri, Mar 08, 2013 at 11:50:04PM -0800, Junio C Hamano wrote:\n> At the same time, I wonder if we can take advantage of the fact that\n> these call sites only care about equality and not ordering.\n\nI did an RFC-patch for that (that I mistakenly didn't sent as a reply to\nthis e-mail). And I believe that you're correct. My solution is inspired\nof curl's strequal.\n\nIs the reason for git not to care about lower/upper-case for beeing able\nto support windows? Or is there any other smart reason?\n\nI was also thinking about discarding files by looking at their\nmodification date. If the modification timestamp is older than/or equal to\nthe latest commit, there's probably no reason for examine that file any\nfurther. I'm not sure about the side effects this may imply though. I\nthink they can be quite nasty. Is this something worth digging more in\nor am I already on the wrong path?\n\n-- \nMed vänliga hälsningar\nFredrik Gustafsson\n\ntel: 0733-608274\ne-post: iveqy@iveqy.com\n"},{"id":"210885","messageId":"CALWbr2xJfgba9_nyy609mhMOY3vq_ckZwb5C2nSsZJNNFRCLTA@mail.gmail.com","threadId":"33112","inReplyTo":"1362802190-7331-2-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH 1/3] match_pathname: avoid calling strncmp if baselen is 0","fromName":"Antoine Pelisse","fromEmail":"apelisse@gmail.com","sentAt":"2013-03-09T09:06:29Z","receivedAt":"2013-03-09T09:06:29Z","isPatch":true,"sender":{"key":"apelisse@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1929644?v=4"},"body":"> diff --git a/dir.c b/dir.c\n> index 57394e4..669cf80 100644\n> --- a/dir.c\n> +++ b/dir.c\n> @@ -663,7 +663,7 @@ int match_pathname(const char *pathname, int pathlen,\n> */\n> if (pathlen < baselen + 1 ||\n> (baselen && pathname[baselen] != '/') ||\n> - strncmp_icase(pathname, base, baselen))\n> + (baselen && strncmp_icase(pathname, base, baselen)))\n\nShouldn't you factorize by baselen here ? For readability reasons, not\nperformance of course.\n\n> return 0;\n>\n> namelen = baselen ? pathlen - baselen - 1 : pathlen;\n"},{"id":"210886","messageId":"CACsJy8D-ZJrC7n5ky9sc_UoenOLTg0h6tEczp=-U9ppn820P-g@mail.gmail.com","threadId":"33112","inReplyTo":"7v4nglf1w3.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/3] match_basename: use strncmp instead of strcmp","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-09T09:58:39Z","receivedAt":"2013-03-09T09:58:39Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Mar 9, 2013 at 2:50 PM, Junio C Hamano wrote:\n> Nguyễn Thái Ngọc Duy writes:\n>\n>> strncmp provides length information, compared to strcmp, which could\n>> be taken advantage by the implementation. Even better, we could check\n>> if the lengths are equal before calling strncmp, eliminating a bit of\n>> strncmp calls.\n>\n> I think I am a bit slower than my usual self tonight, but I am\n> utterly confused by the above.\n>\n> strncmp() compares _only_ up to the first n bytes, so when you are\n> using it for equality, it is not \"we could check length\", but is \"we\n> MUST check they match to the length of the shorter string\", if you\n> want to obtain not just faster but correct result.\n>\n> Am I mistaken?\n\nYeap, the description is a bit misleading. Although you could get away\nwith length check by doing !strncmp(a, b, strlen(a)+1).\n\n> Even if you are using strcmp() that yields ordering not just\n> equality, it can return a correct result as soon as it hits the\n> first bytes that are different; I doubt using strncmp() contributes\n> to the performance very much. Comparing lengths before doing\n> byte-for-byte comparison could help because you can reject two\n> strings with different lengths without looking at them.\n>\n> At the same time, I wonder if we can take advantage of the fact that\n> these call sites only care about equality and not ordering.\n\nI tried to push it further and compare hash before do the actual\nstring comparison. It slowed things down (hopefully because the cost\nof hashing, the same one from name-hash.c, not because I did it\nwrong).\n-- \nDuy\n"},{"id":"210950","messageId":"1362896070-17456-1-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1362802190-7331-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v2 0/6] Exclude optimizations","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-10T06:14:24Z","receivedAt":"2013-03-10T06:14:24Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"v2 includes strncmp_equal and directory level pattern filter. user\ntime of \"git ls-files --exclude-standard -o\" on webkit.git below.\nLooking pretty good.\n\n before after\nuser 0m0.607s 0m0.365s\nuser 0m0.613s 0m0.366s\nuser 0m0.613s 0m0.374s\nuser 0m0.621s 0m0.374s\nuser 0m0.621s 0m0.377s\nuser 0m0.622s 0m0.381s\nuser 0m0.624s 0m0.381s\nuser 0m0.626s 0m0.383s\nuser 0m0.628s 0m0.384s\nuser 0m0.638s 0m0.384s\n\n\nNguyễn Thái Ngọc Duy (6):\n match_pathname: avoid calling strncmp if baselen is 0\n dir.c: inline convenient *_icase helpers\n match_basename: use strncmp instead of strcmp\n match_{base,path}name: replace strncmp_icase with strnequal_icase\n dir.c: pass pathname length to last_exclude_matching\n exclude: filter patterns by directory level\n\n attr.c | 5 ++-\n dir.c | 114 ++++++++++++++++++++++++++++++++++++++++++++---------------------\n dir.h | 27 +++++++++++++---\n 3 files changed, 104 insertions(+), 42 deletions(-)\n\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"210951","messageId":"1362896070-17456-2-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1362896070-17456-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v2 1/6] match_pathname: avoid calling strncmp if baselen is 0","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-10T06:14:25Z","receivedAt":"2013-03-10T06:14:25Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This reduces \"git status\" user time by a little bit. This is the\nsorted results of 10 consecutive runs of \"git ls-files\n--exclude-standard -o\" on webkit.git, compiled with gcc -O2:\n\n before after\nuser 0m0.607s 0m0.554s\nuser 0m0.613s 0m0.564s\nuser 0m0.613s 0m0.571s\nuser 0m0.621s 0m0.576s\nuser 0m0.621s 0m0.578s\nuser 0m0.622s 0m0.579s\nuser 0m0.624s 0m0.583s\nuser 0m0.626s 0m0.584s\nuser 0m0.628s 0m0.586s\nuser 0m0.638s 0m0.592s\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n dir.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 57394e4..b3cd66c 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -662,8 +662,8 @@ int match_pathname(const char *pathname, int pathlen,\n \t * may not end with a trailing slash though.\n \t */\n \tif (pathlen < baselen + 1 ||\n-\t (baselen && pathname[baselen] != '/') ||\n-\t strncmp_icase(pathname, base, baselen))\n+\t (baselen && (pathname[baselen] != '/' ||\n+\t\t\t strncmp_icase(pathname, base, baselen))))\n \t\treturn 0;\n \n \tnamelen = baselen ? pathlen - baselen - 1 : pathlen;\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"210953","messageId":"1362896070-17456-3-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1362896070-17456-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v2 2/6] dir.c: inline convenient *_icase helpers","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-10T06:14:26Z","receivedAt":"2013-03-10T06:14:26Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Like the previous patch, this cuts down the number of str*cmp calls in\nread_directory (which does _a lot_). Again sorted results on webkit.git:\n\n before after\nuser 0m0.554s 0m0.548s\nuser 0m0.564s 0m0.549s\nuser 0m0.571s 0m0.554s\nuser 0m0.576s 0m0.557s\nuser 0m0.578s 0m0.558s\nuser 0m0.579s 0m0.559s\nuser 0m0.583s 0m0.562s\nuser 0m0.584s 0m0.564s\nuser 0m0.586s 0m0.566s\nuser 0m0.592s 0m0.569s\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n dir.c | 16 ----------------\n dir.h | 18 +++++++++++++++---\n 2 files changed, 15 insertions(+), 19 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex b3cd66c..9960a37 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -21,22 +21,6 @@ static int read_directory_recursive(struct dir_struct *dir, const char *path, in\n \tint check_only, const struct path_simplify *simplify);\n static int get_dtype(struct dirent *de, const char *path, int len);\n \n-/* helper string functions with support for the ignore_case flag */\n-int strcmp_icase(const char *a, const char *b)\n-{\n-\treturn ignore_case ? strcasecmp(a, b) : strcmp(a, b);\n-}\n-\n-int strncmp_icase(const char *a, const char *b, size_t count)\n-{\n-\treturn ignore_case ? strncasecmp(a, b, count) : strncmp(a, b, count);\n-}\n-\n-int fnmatch_icase(const char *pattern, const char *string, int flags)\n-{\n-\treturn fnmatch(pattern, string, flags | (ignore_case ? FNM_CASEFOLD : 0));\n-}\n-\n inline int git_fnmatch(const char *pattern, const char *string,\n \t\t int flags, int prefix)\n {\ndiff --git a/dir.h b/dir.h\nindex c3eb4b5..560ade4 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -200,9 +200,21 @@ extern int remove_dir_recursively(struct strbuf *path, int flag);\n /* tries to remove the path with empty directories along it, ignores ENOENT */\n extern int remove_path(const char *path);\n \n-extern int strcmp_icase(const char *a, const char *b);\n-extern int strncmp_icase(const char *a, const char *b, size_t count);\n-extern int fnmatch_icase(const char *pattern, const char *string, int flags);\n+/* helper string functions with support for the ignore_case flag */\n+static inline int strcmp_icase(const char *a, const char *b)\n+{\n+\treturn ignore_case ? strcasecmp(a, b) : strcmp(a, b);\n+}\n+\n+static inline int strncmp_icase(const char *a, const char *b, size_t count)\n+{\n+\treturn ignore_case ? strncasecmp(a, b, count) : strncmp(a, b, count);\n+}\n+\n+static inline int fnmatch_icase(const char *pattern, const char *string, int flags)\n+{\n+\treturn fnmatch(pattern, string, flags | (ignore_case ? FNM_CASEFOLD : 0));\n+}\n \n /*\n * The prefix part of pattern must not contains wildcards.\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"210952","messageId":"1362896070-17456-4-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1362896070-17456-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v2 3/6] match_basename: use strncmp instead of strcmp","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-10T06:14:27Z","receivedAt":"2013-03-10T06:14:27Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"strncmp is provided length information which could be taken advantage\nby the underlying implementation. Even better, we need to check if the\nlengths are equal before calling strncmp, eliminating a bit of strncmp\ncalls.\n\n before after\nuser 0m0.548s 0m0.516s\nuser 0m0.549s 0m0.523s\nuser 0m0.554s 0m0.532s\nuser 0m0.557s 0m0.533s\nuser 0m0.558s 0m0.535s\nuser 0m0.559s 0m0.542s\nuser 0m0.562s 0m0.546s\nuser 0m0.564s 0m0.551s\nuser 0m0.566s 0m0.556s\nuser 0m0.569s 0m0.561s\n\nWhile at there, fix an inconsistency about pattern/patternlen in how\nattr handles EXC_FLAG_MUSTBEDIR. When parse_exclude_pattern detects\nthis flag, it sets patternlen _not_ to include the trailing slash and\nexpects the caller to trim it. add_exclude does, parse_attr_line does\nnot.\n\nIn attr.c, the pattern could be \"foo/\" while patternlen tells us it\nonly has 3 chars. Some functions do not care about patternlen and will\nsee the pattern as \"foo/\" while others may see it as \"foo\". This patch\nmakes patternlen 4 in this case. (Although for a piece of mind,\nperhaps we should trim it to \"foo\" like exclude, and never pass a\npathname like \"abc/\" to match_{base,path}name)\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n attr.c | 2 ++\n dir.c | 8 +++++---\n 2 files changed, 7 insertions(+), 3 deletions(-)\n\ndiff --git a/attr.c b/attr.c\nindex e2f9377..1818ba5 100644\n--- a/attr.c\n+++ b/attr.c\n@@ -255,6 +255,8 @@ static struct match_attr *parse_attr_line(const char *line, const char *src,\n \t\t\t\t &res->u.pat.patternlen,\n \t\t\t\t &res->u.pat.flags,\n \t\t\t\t &res->u.pat.nowildcardlen);\n+\t\tif (res->u.pat.flags & EXC_FLAG_MUSTBEDIR)\n+\t\t\tres->u.pat.patternlen++;\n \t\tif (res->u.pat.flags & EXC_FLAG_NEGATIVE) {\n \t\t\twarning(_(\"Negative patterns are ignored in git attributes\\n\"\n \t\t\t\t \"Use '\\\\!' for literal leading exclamation.\"));\ndiff --git a/dir.c b/dir.c\nindex 9960a37..46b24db 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -610,12 +610,14 @@ int match_basename(const char *basename, int basenamelen,\n \t\t int flags)\n {\n \tif (prefix == patternlen) {\n-\t\tif (!strcmp_icase(pattern, basename))\n+\t\tif (patternlen == basenamelen &&\n+\t\t !strncmp_icase(pattern, basename, patternlen))\n \t\t\treturn 1;\n \t} else if (flags & EXC_FLAG_ENDSWITH) {\n \t\tif (patternlen - 1 <= basenamelen &&\n-\t\t !strcmp_icase(pattern + 1,\n-\t\t\t\t basename + basenamelen - patternlen + 1))\n+\t\t !strncmp_icase(pattern + 1,\n+\t\t\t\t basename + basenamelen - patternlen + 1,\n+\t\t\t\t patternlen - 1))\n \t\t\treturn 1;\n \t} else {\n \t\tif (fnmatch_icase(pattern, basename, 0) == 0)\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"210954","messageId":"1362896070-17456-5-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1362896070-17456-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v2 4/6] match_{base,path}name: replace strncmp_icase with strnequal_icase","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-10T06:14:28Z","receivedAt":"2013-03-10T06:14:28Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"We could also optimize for ignore_case, assuming that non-ascii\ncharacters are not used in most repositories. We could check that all\npatterns and pathnames are ascii-only, then use git's toupper()\n\n before after\nuser 0m0.516s 0m0.433s\nuser 0m0.523s 0m0.437s\nuser 0m0.532s 0m0.443s\nuser 0m0.533s 0m0.448s\nuser 0m0.535s 0m0.449s\nuser 0m0.542s 0m0.452s\nuser 0m0.546s 0m0.453s\nuser 0m0.551s 0m0.458s\nuser 0m0.556s 0m0.459s\nuser 0m0.561s 0m0.462s\n\nSuggested-by: Fredrik Gustafsson \nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n dir.c | 27 +++++++++++++++++++++++----\n 1 file changed, 23 insertions(+), 4 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 46b24db..7b6a625 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -21,6 +21,25 @@ static int read_directory_recursive(struct dir_struct *dir, const char *path, in\n \tint check_only, const struct path_simplify *simplify);\n static int get_dtype(struct dirent *de, const char *path, int len);\n \n+/*\n+ * This function is more like memequal_icase than strnequal_icase as\n+ * it does not check for NUL. The caller is not supposed to pass a\n+ * length longer than both input strings\n+ */\n+static inline strnequal_icase(const char *a, const char *b, int n)\n+{\n+\tif (!ignore_case) {\n+\t\twhile (n && *a == *b) {\n+\t\t\ta++;\n+\t\t\tb++;\n+\t\t\tn--;\n+\t\t}\n+\t\treturn n == 0;\n+\t}\n+\n+\treturn !strncmp_icase(a, b, n);\n+}\n+\n inline int git_fnmatch(const char *pattern, const char *string,\n \t\t int flags, int prefix)\n {\n@@ -611,11 +630,11 @@ int match_basename(const char *basename, int basenamelen,\n {\n \tif (prefix == patternlen) {\n \t\tif (patternlen == basenamelen &&\n-\t\t !strncmp_icase(pattern, basename, patternlen))\n+\t\t strnequal_icase(pattern, basename, patternlen))\n \t\t\treturn 1;\n \t} else if (flags & EXC_FLAG_ENDSWITH) {\n \t\tif (patternlen - 1 <= basenamelen &&\n-\t\t !strncmp_icase(pattern + 1,\n+\t\t strnequal_icase(pattern + 1,\n \t\t\t\t basename + basenamelen - patternlen + 1,\n \t\t\t\t patternlen - 1))\n \t\t\treturn 1;\n@@ -649,7 +668,7 @@ int match_pathname(const char *pathname, int pathlen,\n \t */\n \tif (pathlen < baselen + 1 ||\n \t (baselen && (pathname[baselen] != '/' ||\n-\t\t\t strncmp_icase(pathname, base, baselen))))\n+\t\t\t !strnequal_icase(pathname, base, baselen))))\n \t\treturn 0;\n \n \tnamelen = baselen ? pathlen - baselen - 1 : pathlen;\n@@ -663,7 +682,7 @@ int match_pathname(const char *pathname, int pathlen,\n \t\tif (prefix > namelen)\n \t\t\treturn 0;\n \n-\t\tif (strncmp_icase(pattern, name, prefix))\n+\t\tif (!strnequal_icase(pattern, name, prefix))\n \t\t\treturn 0;\n \t\tpattern += prefix;\n \t\tname += prefix;\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"210955","messageId":"1362896070-17456-6-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1362896070-17456-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v2 5/6] dir.c: pass pathname length to last_exclude_matching","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-10T06:14:29Z","receivedAt":"2013-03-10T06:14:29Z","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 | 15 +++++++++------\n 1 file changed, 9 insertions(+), 6 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 7b6a625..880b5e6 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -764,9 +764,9 @@ int is_excluded_from_list(const char *pathname,\n */\n static struct exclude *last_exclude_matching(struct dir_struct *dir,\n \t\t\t\t\t const char *pathname,\n+\t\t\t\t\t int pathlen,\n \t\t\t\t\t int *dtype_p)\n {\n-\tint pathlen = strlen(pathname);\n \tint i, j;\n \tstruct exclude_list_group *group;\n \tstruct exclude *exclude;\n@@ -793,10 +793,12 @@ static struct exclude *last_exclude_matching(struct dir_struct *dir,\n * scans all exclude lists to determine whether pathname is excluded.\n * Returns 1 if true, otherwise 0.\n */\n-static int is_excluded(struct dir_struct *dir, const char *pathname, int *dtype_p)\n+static int is_excluded(struct dir_struct *dir,\n+\t\t const char *pathname, int pathlen,\n+\t\t int *dtype_p)\n {\n \tstruct exclude *exclude =\n-\t\tlast_exclude_matching(dir, pathname, dtype_p);\n+\t\tlast_exclude_matching(dir, pathname, pathlen, dtype_p);\n \tif (exclude)\n \t\treturn exclude->flags & EXC_FLAG_NEGATIVE ? 0 : 1;\n \treturn 0;\n@@ -859,7 +861,8 @@ struct exclude *last_exclude_matching_path(struct path_exclude_check *check,\n \t\tif (ch == '/') {\n \t\t\tint dt = DT_DIR;\n \t\t\texclude = last_exclude_matching(check->dir,\n-\t\t\t\t\t\t\tpath->buf, &dt);\n+\t\t\t\t\t\t\tpath->buf, path->len,\n+\t\t\t\t\t\t\t&dt);\n \t\t\tif (exclude) {\n \t\t\t\tcheck->exclude = exclude;\n \t\t\t\treturn exclude;\n@@ -871,7 +874,7 @@ struct exclude *last_exclude_matching_path(struct path_exclude_check *check,\n \t/* An entry in the index; cannot be a directory with subentries */\n \tstrbuf_setlen(path, 0);\n \n-\treturn last_exclude_matching(check->dir, name, dtype);\n+\treturn last_exclude_matching(check->dir, name, namelen, dtype);\n }\n \n /*\n@@ -1249,7 +1252,7 @@ static enum path_treatment treat_one_path(struct dir_struct *dir,\n \t\t\t\t\t const struct path_simplify *simplify,\n \t\t\t\t\t int dtype, struct dirent *de)\n {\n-\tint exclude = is_excluded(dir, path->buf, &dtype);\n+\tint exclude = is_excluded(dir, path->buf, path->len, &dtype);\n \tif (exclude && (dir->flags & DIR_COLLECT_IGNORED)\n \t && exclude_matches_pathspec(path->buf, path->len, simplify))\n \t\tdir_add_ignored(dir, path->buf, path->len);\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"210956","messageId":"1362896070-17456-7-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1362896070-17456-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v2 6/6] exclude: filter patterns by directory level","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-10T06:14:30Z","receivedAt":"2013-03-10T06:14:30Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"A non-basename pattern that does not contain /**/ can't match anything\noutside the attached directory. Record its directory level and avoid\nmatching unless the pathname is also at the same directory level.\n\nThis optimization shines when there are a lot of non-basename patterns\nare the root .gitignore and big/deep worktree. Due to the cascading\nrule of .gitignore, patterns in the root .gitignore are checked for\n_all_ entries in the worktree.\n\n before after\nuser 0m0.424s 0m0.365s\nuser 0m0.427s 0m0.366s\nuser 0m0.432s 0m0.374s\nuser 0m0.435s 0m0.374s\nuser 0m0.435s 0m0.377s\nuser 0m0.437s 0m0.381s\nuser 0m0.439s 0m0.381s\nuser 0m0.440s 0m0.383s\nuser 0m0.450s 0m0.384s\nuser 0m0.454s 0m0.384s\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n attr.c | 3 ++-\n dir.c | 68 ++++++++++++++++++++++++++++++++++++++++++++++++------------------\n dir.h | 9 ++++++++-\n 3 files changed, 60 insertions(+), 20 deletions(-)\n\ndiff --git a/attr.c b/attr.c\nindex 1818ba5..7764ddd 100644\n--- a/attr.c\n+++ b/attr.c\n@@ -254,7 +254,8 @@ static struct match_attr *parse_attr_line(const char *line, const char *src,\n \t\tparse_exclude_pattern(&res->u.pat.pattern,\n \t\t\t\t &res->u.pat.patternlen,\n \t\t\t\t &res->u.pat.flags,\n-\t\t\t\t &res->u.pat.nowildcardlen);\n+\t\t\t\t &res->u.pat.nowildcardlen,\n+\t\t\t\t NULL);\n \t\tif (res->u.pat.flags & EXC_FLAG_MUSTBEDIR)\n \t\t\tres->u.pat.patternlen++;\n \t\tif (res->u.pat.flags & EXC_FLAG_NEGATIVE) {\ndiff --git a/dir.c b/dir.c\nindex 880b5e6..de7a6ba 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -360,10 +360,12 @@ static int no_wildcard(const char *string)\n void parse_exclude_pattern(const char **pattern,\n \t\t\t int *patternlen,\n \t\t\t int *flags,\n-\t\t\t int *nowildcardlen)\n+\t\t\t int *nowildcardlen,\n+\t\t\t int *dirs_p)\n {\n \tconst char *p = *pattern;\n \tsize_t i, len;\n+\tint dirs;\n \n \t*flags = 0;\n \tif (*p == '!') {\n@@ -375,12 +377,15 @@ void parse_exclude_pattern(const char **pattern,\n \t\tlen--;\n \t\t*flags |= EXC_FLAG_MUSTBEDIR;\n \t}\n-\tfor (i = 0; i < len; i++) {\n+\tfor (i = 0, dirs = 0; i < len; i++) {\n \t\tif (p[i] == '/')\n-\t\t\tbreak;\n+\t\t\tdirs++;\n \t}\n-\tif (i == len)\n+\tif (!dirs)\n \t\t*flags |= EXC_FLAG_NODIR;\n+\telse if (*p == '/')\n+\t\tdirs--;\n+\n \t*nowildcardlen = simple_length(p);\n \t/*\n \t * we should have excluded the trailing slash from 'p' too,\n@@ -393,6 +398,8 @@ void parse_exclude_pattern(const char **pattern,\n \t\t*flags |= EXC_FLAG_ENDSWITH;\n \t*pattern = p;\n \t*patternlen = len;\n+\tif (dirs_p)\n+\t\t*dirs_p = dirs;\n }\n \n void add_exclude(const char *string, const char *base,\n@@ -402,8 +409,9 @@ void add_exclude(const char *string, const char *base,\n \tint patternlen;\n \tint flags;\n \tint nowildcardlen;\n+\tint dirs;\n \n-\tparse_exclude_pattern(&string, &patternlen, &flags, &nowildcardlen);\n+\tparse_exclude_pattern(&string, &patternlen, &flags, &nowildcardlen, &dirs);\n \tif (flags & EXC_FLAG_MUSTBEDIR) {\n \t\tchar *s;\n \t\tx = xmalloc(sizeof(*x) + patternlen + 1);\n@@ -415,11 +423,26 @@ void add_exclude(const char *string, const char *base,\n \t\tx = xmalloc(sizeof(*x));\n \t\tx->pattern = string;\n \t}\n+\t/*\n+\t * TODO: nowildcardlen < patternlen is a stricter than\n+\t * necessary mainly to exclude \"**\" that breaks directory\n+\t * boundary. Patterns like \"/foo-*\" should be fine.\n+\t */\n+\tif ((flags & EXC_FLAG_NODIR) || nowildcardlen < patternlen)\n+\t\tdirs = -1;\n+\telse {\n+\t\tint i;\n+\t\tfor (i = 0; i < baselen; i++) {\n+\t\t\tif (base[i] == '/')\n+\t\t\t\tdirs++;\n+\t\t}\n+\t}\n \tx->patternlen = patternlen;\n \tx->nowildcardlen = nowildcardlen;\n \tx->base = base;\n \tx->baselen = baselen;\n \tx->flags = flags;\n+\tx->dirs = dirs;\n \tx->srcpos = srcpos;\n \tALLOC_GROW(el->excludes, el->nr + 1, el->alloc);\n \tel->excludes[el->nr++] = x;\n@@ -701,7 +724,7 @@ int match_pathname(const char *pathname, int pathlen,\n * matched, or NULL for undecided.\n */\n static struct exclude *last_exclude_matching_from_list(const char *pathname,\n-\t\t\t\t\t\t int pathlen,\n+\t\t\t\t\t\t int pathlen, int dirs,\n \t\t\t\t\t\t const char *basename,\n \t\t\t\t\t\t int *dtype,\n \t\t\t\t\t\t struct exclude_list *el)\n@@ -732,6 +755,9 @@ static struct exclude *last_exclude_matching_from_list(const char *pathname,\n \t\t\tcontinue;\n \t\t}\n \n+\t\tif (dirs >= 0 && x->dirs >= 0 && x->dirs != dirs)\n+\t\t\tcontinue;\n+\n \t\tassert(x->baselen == 0 || x->base[x->baselen - 1] == '/');\n \t\tif (match_pathname(pathname, pathlen,\n \t\t\t\t x->base, x->baselen ? x->baselen - 1 : 0,\n@@ -750,7 +776,8 @@ int is_excluded_from_list(const char *pathname,\n \t\t\t struct exclude_list *el)\n {\n \tstruct exclude *exclude;\n-\texclude = last_exclude_matching_from_list(pathname, pathlen, basename, dtype, el);\n+\texclude = last_exclude_matching_from_list(pathname, pathlen, -1,\n+\t\t\t\t\t\t basename, dtype, el);\n \tif (exclude)\n \t\treturn exclude->flags & EXC_FLAG_NEGATIVE ? 0 : 1;\n \treturn -1; /* undecided */\n@@ -765,6 +792,7 @@ int is_excluded_from_list(const char *pathname,\n static struct exclude *last_exclude_matching(struct dir_struct *dir,\n \t\t\t\t\t const char *pathname,\n \t\t\t\t\t int pathlen,\n+\t\t\t\t\t int dirs,\n \t\t\t\t\t int *dtype_p)\n {\n \tint i, j;\n@@ -779,8 +807,8 @@ static struct exclude *last_exclude_matching(struct dir_struct *dir,\n \t\tgroup = &dir->exclude_list_group[i];\n \t\tfor (j = group->nr - 1; j >= 0; j--) {\n \t\t\texclude = last_exclude_matching_from_list(\n-\t\t\t\tpathname, pathlen, basename, dtype_p,\n-\t\t\t\t&group->el[j]);\n+\t\t\t\tpathname, pathlen, dir->dir_level,\n+\t\t\t\tbasename, dtype_p, &group->el[j]);\n \t\t\tif (exclude)\n \t\t\t\treturn exclude;\n \t\t}\n@@ -794,11 +822,11 @@ static struct exclude *last_exclude_matching(struct dir_struct *dir,\n * Returns 1 if true, otherwise 0.\n */\n static int is_excluded(struct dir_struct *dir,\n-\t\t const char *pathname, int pathlen,\n+\t\t const char *pathname, int pathlen, int dirs,\n \t\t int *dtype_p)\n {\n \tstruct exclude *exclude =\n-\t\tlast_exclude_matching(dir, pathname, pathlen, dtype_p);\n+\t\tlast_exclude_matching(dir, pathname, pathlen, dirs, dtype_p);\n \tif (exclude)\n \t\treturn exclude->flags & EXC_FLAG_NEGATIVE ? 0 : 1;\n \treturn 0;\n@@ -862,7 +890,7 @@ struct exclude *last_exclude_matching_path(struct path_exclude_check *check,\n \t\t\tint dt = DT_DIR;\n \t\t\texclude = last_exclude_matching(check->dir,\n \t\t\t\t\t\t\tpath->buf, path->len,\n-\t\t\t\t\t\t\t&dt);\n+\t\t\t\t\t\t\t-1, &dt);\n \t\t\tif (exclude) {\n \t\t\t\tcheck->exclude = exclude;\n \t\t\t\treturn exclude;\n@@ -874,7 +902,7 @@ struct exclude *last_exclude_matching_path(struct path_exclude_check *check,\n \t/* An entry in the index; cannot be a directory with subentries */\n \tstrbuf_setlen(path, 0);\n \n-\treturn last_exclude_matching(check->dir, name, namelen, dtype);\n+\treturn last_exclude_matching(check->dir, name, namelen, -1, dtype);\n }\n \n /*\n@@ -1248,11 +1276,11 @@ enum path_treatment {\n };\n \n static enum path_treatment treat_one_path(struct dir_struct *dir,\n-\t\t\t\t\t struct strbuf *path,\n+\t\t\t\t\t struct strbuf *path, int dirs,\n \t\t\t\t\t const struct path_simplify *simplify,\n \t\t\t\t\t int dtype, struct dirent *de)\n {\n-\tint exclude = is_excluded(dir, path->buf, path->len, &dtype);\n+\tint exclude = is_excluded(dir, path->buf, path->len, dirs, &dtype);\n \tif (exclude && (dir->flags & DIR_COLLECT_IGNORED)\n \t && exclude_matches_pathspec(path->buf, path->len, simplify))\n \t\tdir_add_ignored(dir, path->buf, path->len);\n@@ -1310,7 +1338,7 @@ static enum path_treatment treat_path(struct dir_struct *dir,\n \t\treturn path_ignored;\n \n \tdtype = DTYPE(de);\n-\treturn treat_one_path(dir, path, simplify, dtype, de);\n+\treturn treat_one_path(dir, path, -1, simplify, dtype, de);\n }\n \n /*\n@@ -1338,6 +1366,7 @@ static int read_directory_recursive(struct dir_struct *dir,\n \tif (!fdir)\n \t\tgoto out;\n \n+\tdir->dir_level++;\n \twhile ((de = readdir(fdir)) != NULL) {\n \t\tswitch (treat_path(dir, de, &path, baselen, simplify)) {\n \t\tcase path_recurse:\n@@ -1357,6 +1386,7 @@ static int read_directory_recursive(struct dir_struct *dir,\n \t}\n \tclosedir(fdir);\n out:\n+\tdir->dir_level--;\n \tstrbuf_release(&path);\n \n \treturn contents;\n@@ -1427,7 +1457,7 @@ static int treat_leading_path(struct dir_struct *dir,\n \t\t\tbreak;\n \t\tif (simplify_away(sb.buf, sb.len, simplify))\n \t\t\tbreak;\n-\t\tif (treat_one_path(dir, &sb, simplify,\n+\t\tif (treat_one_path(dir, &sb, -1, simplify,\n \t\t\t\t DT_DIR, NULL) == path_ignored)\n \t\t\tbreak; /* do not recurse into it */\n \t\tif (len <= baselen) {\n@@ -1447,8 +1477,10 @@ int read_directory(struct dir_struct *dir, const char *path, int len, const char\n \t\treturn dir->nr;\n \n \tsimplify = create_simplify(pathspec);\n-\tif (!len || treat_leading_path(dir, path, len, simplify))\n+\tif (!len || treat_leading_path(dir, path, len, simplify)) {\n+\t\tdir->dir_level = -1;\n \t\tread_directory_recursive(dir, path, len, 0, simplify);\n+\t}\n \tfree_simplify(simplify);\n \tqsort(dir->entries, dir->nr, sizeof(struct dir_entry *), cmp_name);\n \tqsort(dir->ignored, dir->ignored_nr, sizeof(struct dir_entry *), cmp_name);\ndiff --git a/dir.h b/dir.h\nindex 560ade4..c434f1c 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -45,6 +45,7 @@ struct exclude_list {\n \t\tconst char *base;\n \t\tint baselen;\n \t\tint flags;\n+\t\tint dirs;\n \n \t\t/*\n \t\t * Counting starts from 1 for line numbers in ignore files,\n@@ -87,6 +88,8 @@ struct dir_struct {\n \t/* Exclude info */\n \tconst char *exclude_per_dir;\n \n+\tint dir_level;\n+\n \t/*\n \t * We maintain three groups of exclude pattern lists:\n \t *\n@@ -171,7 +174,11 @@ extern struct exclude_list *add_exclude_list(struct dir_struct *dir,\n extern int add_excludes_from_file_to_list(const char *fname, const char *base, int baselen,\n \t\t\t\t\t struct exclude_list *el, int check_index);\n extern void add_excludes_from_file(struct dir_struct *, const char *fname);\n-extern void parse_exclude_pattern(const char **string, int *patternlen, int *flags, int *nowildcardlen);\n+extern void parse_exclude_pattern(const char **string,\n+\t\t\t\t int *patternlen,\n+\t\t\t\t int *flags,\n+\t\t\t\t int *nowildcardlen,\n+\t\t\t\t int *dirs);\n extern void add_exclude(const char *string, const char *base,\n \t\t\tint baselen, struct exclude_list *el, int srcpos);\n extern void clear_exclude_list(struct exclude_list *el);\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"210959","messageId":"7vy5dvd7yq.fsf@alter.siamese.dyndns.org","threadId":"33112","inReplyTo":"1362896070-17456-4-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH v2 3/6] match_basename: use strncmp instead of strcmp","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-10T07:34:05Z","receivedAt":"2013-03-10T07:34:05Z","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> strncmp is provided length information which could be taken advantage\n> by the underlying implementation.\n\nI may be missing something fundamental, but I somehow find the above\ndoes not make any sense.\n\nstrcmp(a, b) has to pay attention to NUL in these strings and stop\ncomparison. strncmp(a, b, n) not only has to pay the same attention\nto NUL in the strings, but also needs to stop comparing at n bytes.\n\nIn what situation can the latter take advantage of that extra thing\nthat it needs to keep track of and operate faster, when n is the\nlength of shorter of the two strings?\n\n> diff --git a/dir.c b/dir.c\n> index 9960a37..46b24db 100644\n> --- a/dir.c\n> +++ b/dir.c\n> @@ -610,12 +610,14 @@ int match_basename(const char *basename, int basenamelen,\n> \t\t int flags)\n> {\n> \tif (prefix == patternlen) {\n> -\t\tif (!strcmp_icase(pattern, basename))\n> +\t\tif (patternlen == basenamelen &&\n> +\t\t !strncmp_icase(pattern, basename, patternlen))\n> \t\t\treturn 1;\n\nWhat happens if you replace this with\n\n\t\tif (patternlen == baselen &&\n !strcmp_icase(pattern, basename, patternlen))\n\nand drop the other hunk and run the benchmark again?\n\n> \t} else if (flags & EXC_FLAG_ENDSWITH) {\n> \t\tif (patternlen - 1 <= basenamelen &&\n> -\t\t !strcmp_icase(pattern + 1,\n> -\t\t\t\t basename + basenamelen - patternlen + 1))\n> +\t\t !strncmp_icase(pattern + 1,\n> +\t\t\t\t basename + basenamelen - patternlen + 1,\n> +\t\t\t\t patternlen - 1))\n> \t\t\treturn 1;\n> \t} else {\n> \t\tif (fnmatch_icase(pattern, basename, 0) == 0)\n"},{"id":"210960","messageId":"7vtxojd5u7.fsf@alter.siamese.dyndns.org","threadId":"33112","inReplyTo":"1362896070-17456-7-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH v2 6/6] exclude: filter patterns by directory level","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-10T08:20:00Z","receivedAt":"2013-03-10T08:20:00Z","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> A non-basename pattern that does not contain /**/ can't match anything\n> outside the attached directory. Record its directory level and avoid\n> matching unless the pathname is also at the same directory level.\n\nWithout defining what a \"directory level\" is, the above is a bit\nhard to grok, but I think you mean an entry \"b/c/*.c\" that appears\nin \"a/.gitignore\" file will want to match a path that is directly\nin \"a/b/c\" directory (and not in its subdirectories),\n\"a/b/x.c\" at the two levels deep subdirectory or \"a/b/c/d/x.c\" that is\nfour levels deep will never match the pattern.\n\nThe logic feels sound.\n\n> diff --git a/dir.c b/dir.c\n> index 880b5e6..de7a6ba 100644\n> --- a/dir.c\n> +++ b/dir.c\n> @@ -360,10 +360,12 @@ static int no_wildcard(const char *string)\n> void parse_exclude_pattern(const char **pattern,\n> \t\t\t int *patternlen,\n> \t\t\t int *flags,\n> -\t\t\t int *nowildcardlen)\n> +\t\t\t int *nowildcardlen,\n> +\t\t\t int *dirs_p)\n> {\n> \tconst char *p = *pattern;\n> \tsize_t i, len;\n> +\tint dirs;\n> \n> \t*flags = 0;\n> \tif (*p == '!') {\n> @@ -375,12 +377,15 @@ void parse_exclude_pattern(const char **pattern,\n> \t\tlen--;\n> \t\t*flags |= EXC_FLAG_MUSTBEDIR;\n> \t}\n> -\tfor (i = 0; i < len; i++) {\n> +\tfor (i = 0, dirs = 0; i < len; i++) {\n> \t\tif (p[i] == '/')\n> -\t\t\tbreak;\n> +\t\t\tdirs++;\n> \t}\n> -\tif (i == len)\n> +\tif (!dirs)\n> \t\t*flags |= EXC_FLAG_NODIR;\n> +\telse if (*p == '/')\n> +\t\tdirs--;\n\nI presume this is to compensate for a pattern like \"/pat\" whose\nleading slash is only to anchor the pattern at the level. Correct?\n\n> @@ -415,11 +423,26 @@ void add_exclude(const char *string, const char *base,\n> \t\tx = xmalloc(sizeof(*x));\n> \t\tx->pattern = string;\n> \t}\n> +\t/*\n> +\t * TODO: nowildcardlen < patternlen is a stricter than\n> +\t * necessary mainly to exclude \"**\" that breaks directory\n> +\t * boundary. Patterns like \"/foo-*\" should be fine.\n> +\t */\n> +\tif ((flags & EXC_FLAG_NODIR) || nowildcardlen < patternlen)\n> +\t\tdirs = -1;\n\nOK, so an entry \"README\" to match README in any subdirectory will\nbecomes (dirs < 0) and the matcher below will not short-circuit the\ncomparison. Good.\n\n> +\telse {\n> +\t\tint i;\n> +\t\tfor (i = 0; i < baselen; i++) {\n> +\t\t\tif (base[i] == '/')\n> +\t\t\t\tdirs++;\n> +\t\t}\n> +\t}\n> \tx->patternlen = patternlen;\n> \tx->nowildcardlen = nowildcardlen;\n> \tx->base = base;\n> \tx->baselen = baselen;\n> \tx->flags = flags;\n> +\tx->dirs = dirs;\n> \tx->srcpos = srcpos;\n> \tALLOC_GROW(el->excludes, el->nr + 1, el->alloc);\n> \tel->excludes[el->nr++] = x;\n> @@ -701,7 +724,7 @@ int match_pathname(const char *pathname, int pathlen,\n> * matched, or NULL for undecided.\n> */\n> static struct exclude *last_exclude_matching_from_list(const char *pathname,\n> -\t\t\t\t\t\t int pathlen,\n> +\t\t\t\t\t\t int pathlen, int dirs,\n> \t\t\t\t\t\t const char *basename,\n> \t\t\t\t\t\t int *dtype,\n> \t\t\t\t\t\t struct exclude_list *el)\n> @@ -732,6 +755,9 @@ static struct exclude *last_exclude_matching_from_list(const char *pathname,\n> \t\t\tcontinue;\n> \t\t}\n> \n> +\t\tif (dirs >= 0 && x->dirs >= 0 && x->dirs != dirs)\n> +\t\t\tcontinue;\n"},{"id":"210964","messageId":"CACsJy8DwfYL80Zwxufv7Uz7-H_c8VTs=DNQkeDz2bh4K1tTtcw@mail.gmail.com","threadId":"33112","inReplyTo":"7vtxojd5u7.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2 6/6] exclude: filter patterns by directory level","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-10T10:18:34Z","receivedAt":"2013-03-10T10:18:34Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Mar 10, 2013 at 3:20 PM, Junio C Hamano wrote:\n>> + else if (*p == '/')\n>> + dirs--;\n>\n> I presume this is to compensate for a pattern like \"/pat\" whose\n> leading slash is only to anchor the pattern at the level. Correct?\n\nYes.\n\nAlso for the record, we could cut down the number of prep_exclude\ncalls significantly by only calling it when we switch directories\n(i.e. when read_directory_recursive begins or exits), not calling it\nfor all entries of the same directory. For instance, path/, path/a,\npath/b, path/c/, path/c/d, path/e should only call prep_exclude 3\ntimes when we enter \"path\", \"path/c\" and leave \"path/c\" (rather than 6\ntimes currently). Unfortunately, I see no real time savings by this\ncall reduction. So no patch. Maybe I'll try it again on my slower\nlaptop and see if it makes any difference.\n-- \nDuy\n"},{"id":"210965","messageId":"CACsJy8A_4SqLu5L6P0PJ78Lwy12fjL7T2p-KbVEVLJmKNqhyRw@mail.gmail.com","threadId":"33112","inReplyTo":"7vy5dvd7yq.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2 3/6] match_basename: use strncmp instead of strcmp","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-10T10:38:37Z","receivedAt":"2013-03-10T10:38:37Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Mar 10, 2013 at 2:34 PM, Junio C Hamano wrote:\n> Nguyễn Thái Ngọc Duy writes:\n>\n>> strncmp is provided length information which could be taken advantage\n>> by the underlying implementation.\n>\n> I may be missing something fundamental, but I somehow find the above\n> does not make any sense.\n>\n> strcmp(a, b) has to pay attention to NUL in these strings and stop\n> comparison. strncmp(a, b, n) not only has to pay the same attention\n> to NUL in the strings, but also needs to stop comparing at n bytes.\n>\n> In what situation can the latter take advantage of that extra thing\n> that it needs to keep track of and operate faster, when n is the\n> length of shorter of the two strings?\n\nglibc's C strncmp version does 4-byte comparison at a time when n >=4,\nthen fall back to 1-byte for the rest. I don't know if it's faster\nthan a plain always 1-byte comparison though. There's also the hand\nwritten assembly version that compares n from 1..16, not exactly sure\nhow this version works yet.\n\n>> diff --git a/dir.c b/dir.c\n>> index 9960a37..46b24db 100644\n>> --- a/dir.c\n>> +++ b/dir.c\n>> @@ -610,12 +610,14 @@ int match_basename(const char *basename, int basenamelen,\n>> int flags)\n>> {\n>> if (prefix == patternlen) {\n>> - if (!strcmp_icase(pattern, basename))\n>> + if (patternlen == basenamelen &&\n>> + !strncmp_icase(pattern, basename, patternlen))\n>> return 1;\n>\n> What happens if you replace this with\n>\n> if (patternlen == baselen &&\n> !strcmp_icase(pattern, basename, patternlen))\n>\n> and drop the other hunk and run the benchmark again?\n>\n\n before after\nuser 0m0.533s 0m0.522s\nuser 0m0.549s 0m0.530s\nuser 0m0.550s 0m0.534s\nuser 0m0.551s 0m0.545s\nuser 0m0.556s 0m0.550s\nuser 0m0.557s 0m0.552s\nuser 0m0.559s 0m0.554s\nuser 0m0.564s 0m0.561s\nuser 0m0.567s 0m0.565s\nuser 0m0.567s 0m0.565s\n-- \nDuy\n"},{"id":"210967","messageId":"7vmwubcyii.fsf@alter.siamese.dyndns.org","threadId":"33112","inReplyTo":"7vtxojd5u7.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2 6/6] exclude: filter patterns by directory level","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-10T10:58:13Z","receivedAt":"2013-03-10T10:58:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Nguyễn Thái Ngọc Duy writes:\n>\n>> A non-basename pattern that does not contain /**/ can't match anything\n>> outside the attached directory. Record its directory level and avoid\n>> matching unless the pathname is also at the same directory level.\n>\n> Without defining what a \"directory level\" is, the above is a bit\n> hard to grok, but I think you mean an entry \"b/c/*.c\" that appears\n> in \"a/.gitignore\" file will want to match a path that is directly\n> in \"a/b/c\" directory (and not in its subdirectories),\n> \"a/b/x.c\" at the two levels deep subdirectory or \"a/b/c/d/x.c\" that is\n> four levels deep will never match the pattern.\n>\n> The logic feels sound.\n\nActually, I think you may be able to do a lot more with a simpler\nchange. If your top-level .gitignore has \"a/b/c/*.c\" in it, you\ncertainly want to mark it not to be applied when you are looking at\npaths directly in directory a/b/ because they will never match, but\nyou also know that nothing will match when you are inside a/b/d/,\neven though the pattern and the path you are checking are at the\nsame levels. Your dirlen approach will fail for that case, no?\n\nThe idea behind prep_exclude() that organizes the exclode patterns\ninto a stack structure and update the groups near the leaves by\npopping those for the old directory we were in and pushing those for\nthe new directory we are going into is to give us a place to tweak\nthe elements on the whole stack for optimization when we notice that\nwe are looking at paths in different directories. Instead of giving\na \"dirlen\" member to each element, you could give a \"do not look at\nme\" flag to it, and when you notice that you were in a/b/c/ and now\nyou are going to look at paths in a/b/d/, you can look at the group\nthat was read from the .gitignore from the top-level, and mark\nentries that cannot be relevant (e.g. \"a/b/c/*.c\") as such.\n\nThe mark does not have to be a boolean. \"a/b/*.c\" when you are in\n\"a/b/c/\" can be marked as \"This never matches, and I do not have to\nre-check until I pop one level\". When digging deeper to \"a/b/c/d\",\nyou add one to that. When switching to \"a/b/e\", you would first pop\ntwice (\"d\" and then \"c\"), each time decrementing the \"I do not have\nto re-check\" counter by one, and then when pushing \"e\" down, you\nnotice that you need to re-check, and mark it again as \"no need to\nre-check for one pop\". So it is not like you have to re-scan all\nentries textually every time you switch directories. Most entries\nthat are level-limited you would increment or decrement its counter\nand only the ones at the level boundary need to be re-checked.\n\nHmm?\n"},{"id":"210969","messageId":"CACsJy8Bufcoe1ERMSx3uwUrQD88-kUPMHs5Oe_KMY7942eqMYg@mail.gmail.com","threadId":"33112","inReplyTo":"7vmwubcyii.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2 6/6] exclude: filter patterns by directory level","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-10T11:14:25Z","receivedAt":"2013-03-10T11:14:25Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Mar 10, 2013 at 5:58 PM, Junio C Hamano wrote:\n> Junio C Hamano writes:\n>\n>> Nguyễn Thái Ngọc Duy writes:\n>>\n>>> A non-basename pattern that does not contain /**/ can't match anything\n>>> outside the attached directory. Record its directory level and avoid\n>>> matching unless the pathname is also at the same directory level.\n>>\n>> Without defining what a \"directory level\" is, the above is a bit\n>> hard to grok, but I think you mean an entry \"b/c/*.c\" that appears\n>> in \"a/.gitignore\" file will want to match a path that is directly\n>> in \"a/b/c\" directory (and not in its subdirectories),\n>> \"a/b/x.c\" at the two levels deep subdirectory or \"a/b/c/d/x.c\" that is\n>> four levels deep will never match the pattern.\n>>\n>> The logic feels sound.\n>\n> Actually, I think you may be able to do a lot more with a simpler\n> change. If your top-level .gitignore has \"a/b/c/*.c\" in it, you\n> certainly want to mark it not to be applied when you are looking at\n> paths directly in directory a/b/ because they will never match, but\n> you also know that nothing will match when you are inside a/b/d/,\n> even though the pattern and the path you are checking are at the\n> same levels. Your dirlen approach will fail for that case, no?\n>\n> The idea behind prep_exclude() that organizes the exclode patterns\n> into a stack structure and update the groups near the leaves by\n> popping those for the old directory we were in and pushing those for\n> the new directory we are going into is to give us a place to tweak\n> the elements on the whole stack for optimization when we notice that\n> we are looking at paths in different directories. Instead of giving\n> a \"dirlen\" member to each element, you could give a \"do not look at\n> me\" flag to it, and when you notice that you were in a/b/c/ and now\n> you are going to look at paths in a/b/d/, you can look at the group\n> that was read from the .gitignore from the top-level, and mark\n> entries that cannot be relevant (e.g. \"a/b/c/*.c\") as such.\n>\n> The mark does not have to be a boolean. \"a/b/*.c\" when you are in\n> \"a/b/c/\" can be marked as \"This never matches, and I do not have to\n> re-check until I pop one level\". When digging deeper to \"a/b/c/d\",\n> you add one to that. When switching to \"a/b/e\", you would first pop\n> twice (\"d\" and then \"c\"), each time decrementing the \"I do not have\n> to re-check\" counter by one, and then when pushing \"e\" down, you\n> notice that you need to re-check, and mark it again as \"no need to\n> re-check for one pop\". So it is not like you have to re-scan all\n> entries textually every time you switch directories. Most entries\n> that are level-limited you would increment or decrement its counter\n> and only the ones at the level boundary need to be re-checked.\n\nA bit confused by \"dirlen\" (what is it?). I think what you're trying\nto say is \"mark whether a pattern is applicable for entries in this\ndirectory in prep_exclude, update the marks as we push and pop\ndirectories\". It does not sound simpler (and it's actually more\npowerful, as you said it could avoid checking \"a/b/c/*.c\" when\nstanding in a/b/d). I'll give it a try.\n-- \nDuy\n"},{"id":"210970","messageId":"CALWbr2wEJy0p2hcFK_rLtA98koeacE8rS2T=9P130GUFjWKc0Q@mail.gmail.com","threadId":"33112","inReplyTo":"CACsJy8A_4SqLu5L6P0PJ78Lwy12fjL7T2p-KbVEVLJmKNqhyRw@mail.gmail.com","subject":"Re: [PATCH v2 3/6] match_basename: use strncmp instead of strcmp","fromName":"Antoine Pelisse","fromEmail":"apelisse@gmail.com","sentAt":"2013-03-10T11:43:02Z","receivedAt":"2013-03-10T11:43:02Z","isPatch":true,"sender":{"key":"apelisse@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1929644?v=4"},"body":"On Sun, Mar 10, 2013 at 11:38 AM, Duy Nguyen wrote:\n> glibc's C strncmp version does 4-byte comparison at a time when n >=4,\n> then fall back to 1-byte for the rest.\n\nLooking at this\n(http://fossies.org/dox/glibc-2.17/strncmp_8c_source.html), it's not\nexactly true.\n\nIt would rather be while (n >= 4), manually unroll the loop.\n"},{"id":"210972","messageId":"CALWbr2x6V6TB9g_nQCgG2r9L__a2wxG28Qi5KTXChHxj5JSQ8w@mail.gmail.com","threadId":"33112","inReplyTo":"CALWbr2wEJy0p2hcFK_rLtA98koeacE8rS2T=9P130GUFjWKc0Q@mail.gmail.com","subject":"Re: [PATCH v2 3/6] match_basename: use strncmp instead of strcmp","fromName":"Antoine Pelisse","fromEmail":"apelisse@gmail.com","sentAt":"2013-03-10T11:54:18Z","receivedAt":"2013-03-10T11:54:18Z","isPatch":true,"sender":{"key":"apelisse@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1929644?v=4"},"body":"On Sun, Mar 10, 2013 at 12:43 PM, Antoine Pelisse wrote:\n> On Sun, Mar 10, 2013 at 11:38 AM, Duy Nguyen wrote:\n>> glibc's C strncmp version does 4-byte comparison at a time when n >=4,\n>> then fall back to 1-byte for the rest.\n>\n> Looking at this\n> (http://fossies.org/dox/glibc-2.17/strncmp_8c_source.html), it's not\n> exactly true.\n>\n> It would rather be while (n >= 4), manually unroll the loop.\n\nBy the way, if we know the length of the string, we could use memcmp.\nThis one is allowed to compare 4-bytes at a time (he doesn't care\nabout end of string). This is true because the value of the length\nparameter is no longer \"at most\".\n"},{"id":"210973","messageId":"CACsJy8A4+2t=PMJ+iSFFz-fafkAHYGvm6G4M-qpiO9674sanEQ@mail.gmail.com","threadId":"33112","inReplyTo":"CALWbr2x6V6TB9g_nQCgG2r9L__a2wxG28Qi5KTXChHxj5JSQ8w@mail.gmail.com","subject":"Re: [PATCH v2 3/6] match_basename: use strncmp instead of strcmp","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-10T12:06:34Z","receivedAt":"2013-03-10T12:06:34Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Mar 10, 2013 at 6:54 PM, Antoine Pelisse wrote:\n> On Sun, Mar 10, 2013 at 12:43 PM, Antoine Pelisse wrote:\n>> On Sun, Mar 10, 2013 at 11:38 AM, Duy Nguyen wrote:\n>>> glibc's C strncmp version does 4-byte comparison at a time when n >=4,\n>>> then fall back to 1-byte for the rest.\n>>\n>> Looking at this\n>> (http://fossies.org/dox/glibc-2.17/strncmp_8c_source.html), it's not\n>> exactly true.\n>>\n>> It would rather be while (n >= 4), manually unroll the loop.\n>\n> By the way, if we know the length of the string, we could use memcmp.\n> This one is allowed to compare 4-bytes at a time (he doesn't care\n> about end of string). This is true because the value of the length\n> parameter is no longer \"at most\".\n\nWe still need to worry about access violation after NUL when two\nstrings have different lengths. That could be avoided in this\nparticular case, but I think it's too fragile.\n-- \nDuy\n"},{"id":"210974","messageId":"CALWbr2w+HdsOJAXF3974=vx+BtxgCC=bKHetE=ptXTwv7_L0pg@mail.gmail.com","threadId":"33112","inReplyTo":"CACsJy8A4+2t=PMJ+iSFFz-fafkAHYGvm6G4M-qpiO9674sanEQ@mail.gmail.com","subject":"Re: [PATCH v2 3/6] match_basename: use strncmp instead of strcmp","fromName":"Antoine Pelisse","fromEmail":"apelisse@gmail.com","sentAt":"2013-03-10T12:11:06Z","receivedAt":"2013-03-10T12:11:06Z","isPatch":true,"sender":{"key":"apelisse@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1929644?v=4"},"body":">> By the way, if we know the length of the string, we could use memcmp.\n>> This one is allowed to compare 4-bytes at a time (he doesn't care\n>> about end of string). This is true because the value of the length\n>> parameter is no longer \"at most\".\n>\n> We still need to worry about access violation after NUL when two\n> strings have different lengths. That could be avoided in this\n> particular case, but I think it's too fragile.\n\nWhy would we need to compare if the strings don't have the same length\n? We already do that in combine-diff.c:append_lost().\n"},{"id":"210975","messageId":"CACsJy8C+29ebL37kFC21S-b670-ct2yCOjghLPErjwXz1BoQBA@mail.gmail.com","threadId":"33112","inReplyTo":"CALWbr2w+HdsOJAXF3974=vx+BtxgCC=bKHetE=ptXTwv7_L0pg@mail.gmail.com","subject":"Re: [PATCH v2 3/6] match_basename: use strncmp instead of strcmp","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-10T12:14:25Z","receivedAt":"2013-03-10T12:14:25Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Mar 10, 2013 at 7:11 PM, Antoine Pelisse wrote:\n>>> By the way, if we know the length of the string, we could use memcmp.\n>>> This one is allowed to compare 4-bytes at a time (he doesn't care\n>>> about end of string). This is true because the value of the length\n>>> parameter is no longer \"at most\".\n>>\n>> We still need to worry about access violation after NUL when two\n>> strings have different lengths. That could be avoided in this\n>> particular case, but I think it's too fragile.\n>\n> Why would we need to compare if the strings don't have the same length\n> ? We already do that in combine-diff.c:append_lost().\n\nWatching movie and replying to git@ don't mix. You're right we don't\nneed to compare if lengths are different. What was I thinking..\n-- \nDuy\n"},{"id":"211046","messageId":"CACsJy8D=P0Fyg5MoVry8JnsxsKsrQZXqWsvi_Yrb-G_VfCtDRg@mail.gmail.com","threadId":"33112","inReplyTo":"1362896070-17456-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH v2 0/6] Exclude optimizations","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-11T15:11:21Z","receivedAt":"2013-03-11T15:11:21Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"The hunt continues.. (and thanks everyone for suggestions). Now\nis_excluded() (and exclude machinery) is no longer the hot spot in\nread_directory. index_name_exists is the new star:\n\nfunction time (in seconds)\ntreat_leading_path: 0.000\nread_directory: 0.289\n+treat_one_path: 0.147\n++is_excluded: 0.013\n+++prep_exclude: 0.006\n+++matching: 0.004\n++dir_exists_in_index: 0.008\n++index_name_exists: 0.117 <--\n+++lazy_init_name_hash: 0.060\n+simplify_away: 0.004\n+dir_add_name: 0.000\n\nreal 0m0.372s\nuser 0m0.256s\nsys 0m0.114s <-- can't kill this one (*) until we get inotify support\n\nI think if we save the hash in index, we could nearly cut\nlazy_init_name_hash out (or not, perf reported insert_hash near the\ntop, not hash_name). Any ideas to further reduce iname_name_exists\ncost are welcome. 0.117s on 2.50GHz turns to 0.549s on my Atom 1.6GHz,\nso I think it's worth doing something about it.\n\n(*) I tried breadth-first search, checking for .gitignore existence\nbefore opening, chdir() to shorten pathnames. Nothing worked.\n-- \nDuy\n"},{"id":"211117","messageId":"1363093500-16796-1-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1362896070-17456-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v3 00/13] Exclude optimizations","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-12T13:04:47Z","receivedAt":"2013-03-12T13:04:47Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Result of today. I cherry-picked nd/read-directory-recursive-optim to\nsee how far I can get after pulling all the tricks. This is a slower\nmachine so time is longer. Anyway, read_directory time is reduced\nabout 70% in the end.\n\nfunction before after\n----------------------------------\ntreat_leading_path: 0.000 0.000\nread_directory: 4.102 1.235\n+treat_one_path: 2.843 0.531\n++is_excluded: 2.632 0.102\n+++prep_exclude: 0.225 0.040\n+++matching: 2.054 0.035\n++dir_exist: 0.035 0.035\n++index_name_exists: 0.292 0.225\nlazy_init_name_hash: 0.258 0.155\n+simplify_away: 0.085 0.083\n+dir_add_name: 0.446 0.000\n\nI don't expect all these patches to go in. The meat is\nnd/read-directory-recursive-optim (or 10/13) and 09/13. Some other\npatches are safe even if they do not contribute much to the gain. The\nlast two are probably not worth the trouble.\n\n\nNguyễn Thái Ngọc Duy (13):\n dir.c: add MEASURE_EXCLUDE code for tracking exclude performance\n match_pathname: avoid calling strncmp if baselen is 0\n dir.c: inline convenient *_icase helpers\n match_basename: use strncmp instead of strcmp\n match_{base,path}name: replace strncmp_icase with memequal_icase\n dir: pass pathname length to last_exclude_matching\n exclude: avoid calling prep_exclude on entries of the same directory\n exclude: record baselen in the pattern\n exclude: filter out patterns not applicable to the current directory\n read_directory: avoid invoking exclude machinery on tracked files\n Preallocate hash tables when the number of inserts are known in advance\n name-hash: allow to lookup a name with precalculated base hash\n read_directory: calculate name hashes incrementally\n\n Makefile | 1 +\n attr.c | 6 +-\n cache.h | 2 -\n diffcore-rename.c | 1 +\n dir.c | 392 ++++++++++++++++++++++++++++++++++++++++++++----------\n dir.h | 26 +++-\n hash.h | 7 +\n name-hash.c | 49 ++++---\n name-hash.h (new) | 45 +++++++\n read-cache.c | 1 +\n unpack-trees.c | 1 +\n 11 files changed, 431 insertions(+), 100 deletions(-)\n create mode 100644 name-hash.h\n\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"211116","messageId":"1363093500-16796-2-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1363093500-16796-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v3 01/13] dir.c: add MEASURE_EXCLUDE code for tracking exclude performance","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-12T13:04:48Z","receivedAt":"2013-03-12T13:04:48Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Hot read_directory() codepaths are tracked. This could be helpful to\nsee how changes affect read_directory() performance.\n\nResults are printed when environment variable GIT_MEASURE_EXCLUDE is set.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n dir.c | 109 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------\n 1 file changed, 100 insertions(+), 9 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 57394e4..69c045b 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -12,6 +12,32 @@\n #include \"refs.h\"\n #include \"wildmatch.h\"\n \n+#ifdef MEASURE_EXCLUDE\n+static uint32_t tv_treat_leading_path;\n+static uint32_t tv_read_directory;\n+static uint32_t tv_treat_one_path;\n+static uint32_t tv_is_excluded;\n+static uint32_t tv_prep_exclude;\n+static uint32_t tv_last_exclude_matching;\n+static uint32_t tv_dir_add_name;\n+static uint32_t tv_directory_exists_in_index;\n+static uint32_t tv_simplify_away;\n+static uint32_t tv_index_name_exists;\n+static uint32_t tv_lazy_init_name_hash;\n+#define START_CLOCK() \\\n+\t{ \\\n+\t\tstruct timeval tv1, tv2; \\\n+\t\tgettimeofday(&tv1, NULL);\n+#define STOP_CLOCK(v) \\\n+\t\tgettimeofday(&tv2, NULL); \\\n+\t\tv += (uint64_t)tv2.tv_sec * 1000000 + tv2.tv_usec - \\\n+\t\t\t(uint64_t)tv1.tv_sec * 1000000 - tv1.tv_usec; \\\n+\t}\n+#else\n+#define START_CLOCK()\n+#define STOP_CLOCK(v)\n+#endif\n+\n struct path_simplify {\n \tint len;\n \tconst char *path;\n@@ -768,8 +794,11 @@ static struct exclude *last_exclude_matching(struct dir_struct *dir,\n \tconst char *basename = strrchr(pathname, '/');\n \tbasename = (basename) ? basename+1 : pathname;\n \n+\tSTART_CLOCK();\n \tprep_exclude(dir, pathname, basename-pathname);\n+\tSTOP_CLOCK(tv_prep_exclude);\n \n+\tSTART_CLOCK();\n \tfor (i = EXC_CMDL; i <= EXC_FILE; i++) {\n \t\tgroup = &dir->exclude_list_group[i];\n \t\tfor (j = group->nr - 1; j >= 0; j--) {\n@@ -780,6 +809,7 @@ static struct exclude *last_exclude_matching(struct dir_struct *dir,\n \t\t\t\treturn exclude;\n \t\t}\n \t}\n+\tSTOP_CLOCK(tv_last_exclude_matching);\n \treturn NULL;\n }\n \n@@ -897,9 +927,14 @@ static struct dir_entry *dir_entry_new(const char *pathname, int len)\n \n static struct dir_entry *dir_add_name(struct dir_struct *dir, const char *pathname, int len)\n {\n-\tif (!(dir->flags & DIR_SHOW_IGNORED) &&\n-\t cache_name_exists(pathname, len, ignore_case))\n-\t\treturn NULL;\n+\tif (!(dir->flags & DIR_SHOW_IGNORED)) {\n+\t\tstruct cache_entry *ce;\n+\t\tSTART_CLOCK();\n+\t\tce = cache_name_exists(pathname, len, ignore_case);\n+\t\tSTOP_CLOCK(tv_index_name_exists);\n+\t\tif (ce)\n+\t\t\treturn NULL;\n+\t}\n \n \tALLOC_GROW(dir->entries, dir->nr+1, dir->alloc);\n \treturn dir->entries[dir->nr++] = dir_entry_new(pathname, len);\n@@ -1034,8 +1069,12 @@ static enum directory_treatment treat_directory(struct dir_struct *dir,\n \tconst char *dirname, int len, int exclude,\n \tconst struct path_simplify *simplify)\n {\n+\tint ret;\n+\tSTART_CLOCK();\n \t/* The \"len-1\" is to strip the final '/' */\n-\tswitch (directory_exists_in_index(dirname, len-1)) {\n+\tret = directory_exists_in_index(dirname, len-1);\n+\tSTOP_CLOCK(tv_directory_exists_in_index);\n+\tswitch (ret) {\n \tcase index_directory:\n \t\tif ((dir->flags & DIR_SHOW_OTHER_DIRECTORIES) && exclude)\n \t\t\tbreak;\n@@ -1179,7 +1218,9 @@ static int get_index_dtype(const char *path, int len)\n \tint pos;\n \tstruct cache_entry *ce;\n \n+\tSTART_CLOCK();\n \tce = cache_name_exists(path, len, 0);\n+\tSTOP_CLOCK(tv_index_name_exists);\n \tif (ce) {\n \t\tif (!ce_uptodate(ce))\n \t\t\treturn DT_UNKNOWN;\n@@ -1244,7 +1285,12 @@ static enum path_treatment treat_one_path(struct dir_struct *dir,\n \t\t\t\t\t const struct path_simplify *simplify,\n \t\t\t\t\t int dtype, struct dirent *de)\n {\n-\tint exclude = is_excluded(dir, path->buf, &dtype);\n+\tint exclude;\n+\n+\tSTART_CLOCK();\n+\texclude = is_excluded(dir, path->buf, &dtype);\n+\tSTOP_CLOCK(tv_is_excluded);\n+\n \tif (exclude && (dir->flags & DIR_COLLECT_IGNORED)\n \t && exclude_matches_pathspec(path->buf, path->len, simplify))\n \t\tdir_add_ignored(dir, path->buf, path->len);\n@@ -1292,17 +1338,23 @@ static enum path_treatment treat_path(struct dir_struct *dir,\n \t\t\t\t int baselen,\n \t\t\t\t const struct path_simplify *simplify)\n {\n-\tint dtype;\n+\tint dtype, ret;\n \n \tif (is_dot_or_dotdot(de->d_name) || !strcmp(de->d_name, \".git\"))\n \t\treturn path_ignored;\n \tstrbuf_setlen(path, baselen);\n \tstrbuf_addstr(path, de->d_name);\n-\tif (simplify_away(path->buf, path->len, simplify))\n+\tSTART_CLOCK();\n+\tret = simplify_away(path->buf, path->len, simplify);\n+\tSTOP_CLOCK(tv_simplify_away);\n+\tif (ret)\n \t\treturn path_ignored;\n \n \tdtype = DTYPE(de);\n-\treturn treat_one_path(dir, path, simplify, dtype, de);\n+\tSTART_CLOCK();\n+\tret = treat_one_path(dir, path, simplify, dtype, de);\n+\tSTOP_CLOCK(tv_treat_one_path);\n+\treturn ret;\n }\n \n /*\n@@ -1345,7 +1397,9 @@ static int read_directory_recursive(struct dir_struct *dir,\n \t\tcontents++;\n \t\tif (check_only)\n \t\t\tbreak;\n+\t\tSTART_CLOCK();\n \t\tdir_add_name(dir, path.buf, path.len);\n+\t\tSTOP_CLOCK(tv_dir_add_name);\n \t}\n \tclosedir(fdir);\n out:\n@@ -1405,6 +1459,7 @@ static int treat_leading_path(struct dir_struct *dir,\n \t\tlen--;\n \tif (!len)\n \t\treturn 1;\n+\tSTART_CLOCK();\n \tbaselen = 0;\n \twhile (1) {\n \t\tcp = path + baselen + !!baselen;\n@@ -1428,6 +1483,7 @@ static int treat_leading_path(struct dir_struct *dir,\n \t\t}\n \t}\n \tstrbuf_release(&sb);\n+\tSTOP_CLOCK(tv_treat_leading_path);\n \treturn rc;\n }\n \n@@ -1439,8 +1495,43 @@ int read_directory(struct dir_struct *dir, const char *path, int len, const char\n \t\treturn dir->nr;\n \n \tsimplify = create_simplify(pathspec);\n-\tif (!len || treat_leading_path(dir, path, len, simplify))\n+\tif (!len || treat_leading_path(dir, path, len, simplify)) {\n+#ifdef MEASURE_EXCLUDE\n+\t\t/* The first call triggers lazy_init_name_hash() */\n+\t\tSTART_CLOCK();\n+\t\tindex_name_exists(&the_index, \"\", 0, ignore_case);\n+\t\tSTOP_CLOCK(tv_lazy_init_name_hash);\n+#endif\n+\t\tSTART_CLOCK();\n \t\tread_directory_recursive(dir, path, len, 0, simplify);\n+\t\tSTOP_CLOCK(tv_read_directory);\n+\t}\n+#ifdef MEASURE_EXCLUDE\n+\tif (getenv(\"GIT_MEASURE_EXCLUDE\")) {\n+\t\tfprintf(stderr, \"treat_leading_path: %10.3f\\n\",\n+\t\t\t(float)tv_treat_leading_path / 1000000);\n+\t\tfprintf(stderr, \"read_directory: %10.3f\\n\",\n+\t\t\t(float)tv_read_directory / 1000000);\n+\t\tfprintf(stderr, \"+treat_one_path: %10.3f\\n\",\n+\t\t\t(float)tv_treat_one_path / 1000000);\n+\t\tfprintf(stderr, \"++is_excluded: %10.3f\\n\",\n+\t\t\t(float)tv_is_excluded / 1000000);\n+\t\tfprintf(stderr, \"+++prep_exclude: %10.3f\\n\",\n+\t\t\t(float)tv_prep_exclude / 1000000);\n+\t\tfprintf(stderr, \"+++matching: %10.3f\\n\",\n+\t\t\t(float)tv_last_exclude_matching / 1000000);\n+\t\tfprintf(stderr, \"++dir_exist: %10.3f\\n\",\n+\t\t\t(float)tv_directory_exists_in_index / 1000000);\n+\t\tfprintf(stderr, \"++index_name_exists: %10.3f\\n\",\n+\t\t\t(float)tv_index_name_exists / 1000000);\n+\t\tfprintf(stderr, \"lazy_init_name_hash: %10.3f\\n\",\n+\t\t\t(float)tv_lazy_init_name_hash / 1000000);\n+\t\tfprintf(stderr, \"+simplify_away: %10.3f\\n\",\n+\t\t\t(float)tv_simplify_away / 1000000);\n+\t\tfprintf(stderr, \"+dir_add_name: %10.3f\\n\",\n+\t\t\t(float)tv_dir_add_name / 1000000);\n+\t}\n+#endif\n \tfree_simplify(simplify);\n \tqsort(dir->entries, dir->nr, sizeof(struct dir_entry *), cmp_name);\n \tqsort(dir->ignored, dir->ignored_nr, sizeof(struct dir_entry *), cmp_name);\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"211119","messageId":"1363093500-16796-3-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1363093500-16796-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v3 02/13] match_pathname: avoid calling strncmp if baselen is 0","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-12T13:04:49Z","receivedAt":"2013-03-12T13:04:49Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This reduces \"git status\" user time by a little bit. This is the\nsorted results of 10 consecutive runs of \"git ls-files\n--exclude-standard -o\" on webkit.git, compiled with gcc -O2:\n\ntreat_leading_path: 0.000 0.000\nread_directory: 4.102 3.674\n+treat_one_path: 2.843 2.427\n++is_excluded: 2.632 2.221\n+++prep_exclude: 0.225 0.224\n+++matching: 2.054 1.650\n++dir_exist: 0.035 0.035\n++index_name_exists: 0.292 0.288\nlazy_init_name_hash: 0.258 0.257\n+simplify_away: 0.085 0.085\n+dir_add_name: 0.446 0.441\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n dir.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 69c045b..32a3adb 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -688,8 +688,8 @@ int match_pathname(const char *pathname, int pathlen,\n \t * may not end with a trailing slash though.\n \t */\n \tif (pathlen < baselen + 1 ||\n-\t (baselen && pathname[baselen] != '/') ||\n-\t strncmp_icase(pathname, base, baselen))\n+\t (baselen && (pathname[baselen] != '/' ||\n+\t\t\t strncmp_icase(pathname, base, baselen))))\n \t\treturn 0;\n \n \tnamelen = baselen ? pathlen - baselen - 1 : pathlen;\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"211120","messageId":"1363093500-16796-4-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1363093500-16796-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v3 03/13] dir.c: inline convenient *_icase helpers","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-12T13:04:50Z","receivedAt":"2013-03-12T13:04:50Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Like the previous patch, this cuts down the number of str*cmp calls in\nread_directory (which does _a lot_). Again sorted results on webkit.git:\n\ntreat_leading_path: 0.000 0.000\nread_directory: 3.674 3.558\n+treat_one_path: 2.427 2.305\n++is_excluded: 2.221 2.098\n+++prep_exclude: 0.224 0.223\n+++matching: 1.650 1.529\n++dir_exist: 0.035 0.035\n++index_name_exists: 0.288 0.291\nlazy_init_name_hash: 0.257 0.257\n+simplify_away: 0.085 0.086\n+dir_add_name: 0.441 0.445\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n dir.c | 16 ----------------\n dir.h | 18 +++++++++++++++---\n 2 files changed, 15 insertions(+), 19 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 32a3adb..a69c8ac 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -47,22 +47,6 @@ static int read_directory_recursive(struct dir_struct *dir, const char *path, in\n \tint check_only, const struct path_simplify *simplify);\n static int get_dtype(struct dirent *de, const char *path, int len);\n \n-/* helper string functions with support for the ignore_case flag */\n-int strcmp_icase(const char *a, const char *b)\n-{\n-\treturn ignore_case ? strcasecmp(a, b) : strcmp(a, b);\n-}\n-\n-int strncmp_icase(const char *a, const char *b, size_t count)\n-{\n-\treturn ignore_case ? strncasecmp(a, b, count) : strncmp(a, b, count);\n-}\n-\n-int fnmatch_icase(const char *pattern, const char *string, int flags)\n-{\n-\treturn fnmatch(pattern, string, flags | (ignore_case ? FNM_CASEFOLD : 0));\n-}\n-\n inline int git_fnmatch(const char *pattern, const char *string,\n \t\t int flags, int prefix)\n {\ndiff --git a/dir.h b/dir.h\nindex c3eb4b5..560ade4 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -200,9 +200,21 @@ extern int remove_dir_recursively(struct strbuf *path, int flag);\n /* tries to remove the path with empty directories along it, ignores ENOENT */\n extern int remove_path(const char *path);\n \n-extern int strcmp_icase(const char *a, const char *b);\n-extern int strncmp_icase(const char *a, const char *b, size_t count);\n-extern int fnmatch_icase(const char *pattern, const char *string, int flags);\n+/* helper string functions with support for the ignore_case flag */\n+static inline int strcmp_icase(const char *a, const char *b)\n+{\n+\treturn ignore_case ? strcasecmp(a, b) : strcmp(a, b);\n+}\n+\n+static inline int strncmp_icase(const char *a, const char *b, size_t count)\n+{\n+\treturn ignore_case ? strncasecmp(a, b, count) : strncmp(a, b, count);\n+}\n+\n+static inline int fnmatch_icase(const char *pattern, const char *string, int flags)\n+{\n+\treturn fnmatch(pattern, string, flags | (ignore_case ? FNM_CASEFOLD : 0));\n+}\n \n /*\n * The prefix part of pattern must not contains wildcards.\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"211118","messageId":"1363093500-16796-5-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1363093500-16796-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v3 04/13] match_basename: use strncmp instead of strcmp","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-12T13:04:51Z","receivedAt":"2013-03-12T13:04:51Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"strncmp provides length information, compared to strcmp, which could\nbe taken advantage by the implementation. Even better, we could check\nif the lengths are equal before calling strncmp, eliminating a bit of\nstrncmp calls.\n\ntreat_leading_path: 0.000 0.000\nread_directory: 3.558 3.578\n+treat_one_path: 2.305 2.323\n++is_excluded: 2.098 2.117\n+++prep_exclude: 0.223 0.224\n+++matching: 1.529 1.544\n++dir_exist: 0.035 0.035\n++index_name_exists: 0.291 0.290\nlazy_init_name_hash: 0.257 0.258\n+simplify_away: 0.086 0.087\n+dir_add_name: 0.445 0.445\n\nWhile at there, fix an inconsistency about pattern/patternlen in how\nattr handles EXC_FLAG_MUSTBEDIR. When parse_exclude_pattern detects\nthis flag, it sets patternlen _not_ to include the trailing slash and\nexpects the caller to trim it. add_exclude does, parse_attr_line does\nnot.\n\nIn attr.c, the pattern could be \"foo/\" while patternlen tells us it\nonly has 3 chars. Some functions do not care about patternlen and will\nsee the pattern as \"foo/\" while others may see it as \"foo\". This patch\nmakes patternlen 4 in this case. (Although for a piece of mind,\nperhaps we should trim it to \"foo\" like exclude, and never pass a\npathname like \"abc/\" to match_{base,path}name)\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n attr.c | 2 ++\n dir.c | 8 +++++---\n 2 files changed, 7 insertions(+), 3 deletions(-)\n\ndiff --git a/attr.c b/attr.c\nindex e2f9377..1818ba5 100644\n--- a/attr.c\n+++ b/attr.c\n@@ -255,6 +255,8 @@ static struct match_attr *parse_attr_line(const char *line, const char *src,\n \t\t\t\t &res->u.pat.patternlen,\n \t\t\t\t &res->u.pat.flags,\n \t\t\t\t &res->u.pat.nowildcardlen);\n+\t\tif (res->u.pat.flags & EXC_FLAG_MUSTBEDIR)\n+\t\t\tres->u.pat.patternlen++;\n \t\tif (res->u.pat.flags & EXC_FLAG_NEGATIVE) {\n \t\t\twarning(_(\"Negative patterns are ignored in git attributes\\n\"\n \t\t\t\t \"Use '\\\\!' for literal leading exclamation.\"));\ndiff --git a/dir.c b/dir.c\nindex a69c8ac..a2ab200 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -636,12 +636,14 @@ int match_basename(const char *basename, int basenamelen,\n \t\t int flags)\n {\n \tif (prefix == patternlen) {\n-\t\tif (!strcmp_icase(pattern, basename))\n+\t\tif (patternlen == basenamelen &&\n+\t\t !strncmp_icase(pattern, basename, patternlen))\n \t\t\treturn 1;\n \t} else if (flags & EXC_FLAG_ENDSWITH) {\n \t\tif (patternlen - 1 <= basenamelen &&\n-\t\t !strcmp_icase(pattern + 1,\n-\t\t\t\t basename + basenamelen - patternlen + 1))\n+\t\t !strncmp_icase(pattern + 1,\n+\t\t\t\t basename + basenamelen - patternlen + 1,\n+\t\t\t\t patternlen - 1))\n \t\t\treturn 1;\n \t} else {\n \t\tif (fnmatch_icase(pattern, basename, 0) == 0)\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"211122","messageId":"1363093500-16796-6-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1363093500-16796-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v3 05/13] match_{base,path}name: replace strncmp_icase with memequal_icase","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-12T13:04:52Z","receivedAt":"2013-03-12T13:04:52Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"treat_leading_path: 0.000 0.000\nread_directory: 3.578 3.501\n+treat_one_path: 2.323 2.257\n++is_excluded: 2.117 2.056\n+++prep_exclude: 0.224 0.216\n+++matching: 1.544 1.493\n++dir_exist: 0.035 0.035\n++index_name_exists: 0.290 0.292\nlazy_init_name_hash: 0.258 0.256\n+simplify_away: 0.087 0.084\n+dir_add_name: 0.445 0.447\n\nSuggested-by: Fredrik Gustafsson \nSuggested-by: Antoine Pelisse \nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n dir.c | 31 +++++++++++++++++++++++++++----\n 1 file changed, 27 insertions(+), 4 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex a2ab200..26c3b3a 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -47,6 +47,29 @@ static int read_directory_recursive(struct dir_struct *dir, const char *path, in\n \tint check_only, const struct path_simplify *simplify);\n static int get_dtype(struct dirent *de, const char *path, int len);\n \n+static inline int memequal_icase(const char *a, const char *b, int n)\n+{\n+\tif (!memcmp(a, b, n))\n+\t\treturn 1;\n+\n+\tif (!ignore_case)\n+\t\treturn 0;\n+\n+\t/*\n+\t * This assumes that ASCII is used in most repositories. We\n+\t * try the ascii-only version first (i.e. Git's\n+\t * toupper). Failing that, fall back to normal strncasecmp.\n+\t */\n+\twhile (n && toupper(*a) == toupper(*b)) {\n+\t\ta++;\n+\t\tb++;\n+\t\tn--;\n+\t}\n+\tif (!n)\n+\t\treturn 1;\n+\treturn !strncasecmp(a, b, n);\n+}\n+\n inline int git_fnmatch(const char *pattern, const char *string,\n \t\t int flags, int prefix)\n {\n@@ -637,11 +660,11 @@ int match_basename(const char *basename, int basenamelen,\n {\n \tif (prefix == patternlen) {\n \t\tif (patternlen == basenamelen &&\n-\t\t !strncmp_icase(pattern, basename, patternlen))\n+\t\t memequal_icase(pattern, basename, patternlen))\n \t\t\treturn 1;\n \t} else if (flags & EXC_FLAG_ENDSWITH) {\n \t\tif (patternlen - 1 <= basenamelen &&\n-\t\t !strncmp_icase(pattern + 1,\n+\t\t memequal_icase(pattern + 1,\n \t\t\t\t basename + basenamelen - patternlen + 1,\n \t\t\t\t patternlen - 1))\n \t\t\treturn 1;\n@@ -675,7 +698,7 @@ int match_pathname(const char *pathname, int pathlen,\n \t */\n \tif (pathlen < baselen + 1 ||\n \t (baselen && (pathname[baselen] != '/' ||\n-\t\t\t strncmp_icase(pathname, base, baselen))))\n+\t\t\t !memequal_icase(pathname, base, baselen))))\n \t\treturn 0;\n \n \tnamelen = baselen ? pathlen - baselen - 1 : pathlen;\n@@ -689,7 +712,7 @@ int match_pathname(const char *pathname, int pathlen,\n \t\tif (prefix > namelen)\n \t\t\treturn 0;\n \n-\t\tif (strncmp_icase(pattern, name, prefix))\n+\t\tif (!memequal_icase(pattern, name, prefix))\n \t\t\treturn 0;\n \t\tpattern += prefix;\n \t\tname += prefix;\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"211121","messageId":"1363093500-16796-7-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1363093500-16796-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v3 06/13] dir: pass pathname length to last_exclude_matching","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-12T13:04:53Z","receivedAt":"2013-03-12T13:04:53Z","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 | 15 +++++++++------\n 1 file changed, 9 insertions(+), 6 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 26c3b3a..58739f3 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -794,9 +794,9 @@ int is_excluded_from_list(const char *pathname,\n */\n static struct exclude *last_exclude_matching(struct dir_struct *dir,\n \t\t\t\t\t const char *pathname,\n+\t\t\t\t\t int pathlen,\n \t\t\t\t\t int *dtype_p)\n {\n-\tint pathlen = strlen(pathname);\n \tint i, j;\n \tstruct exclude_list_group *group;\n \tstruct exclude *exclude;\n@@ -827,10 +827,12 @@ static struct exclude *last_exclude_matching(struct dir_struct *dir,\n * scans all exclude lists to determine whether pathname is excluded.\n * Returns 1 if true, otherwise 0.\n */\n-static int is_excluded(struct dir_struct *dir, const char *pathname, int *dtype_p)\n+static int is_excluded(struct dir_struct *dir,\n+\t\t const char *pathname, int pathlen,\n+\t\t int *dtype_p)\n {\n \tstruct exclude *exclude =\n-\t\tlast_exclude_matching(dir, pathname, dtype_p);\n+\t\tlast_exclude_matching(dir, pathname, pathlen, dtype_p);\n \tif (exclude)\n \t\treturn exclude->flags & EXC_FLAG_NEGATIVE ? 0 : 1;\n \treturn 0;\n@@ -893,7 +895,8 @@ struct exclude *last_exclude_matching_path(struct path_exclude_check *check,\n \t\tif (ch == '/') {\n \t\t\tint dt = DT_DIR;\n \t\t\texclude = last_exclude_matching(check->dir,\n-\t\t\t\t\t\t\tpath->buf, &dt);\n+\t\t\t\t\t\t\tpath->buf, path->len,\n+\t\t\t\t\t\t\t&dt);\n \t\t\tif (exclude) {\n \t\t\t\tcheck->exclude = exclude;\n \t\t\t\treturn exclude;\n@@ -905,7 +908,7 @@ struct exclude *last_exclude_matching_path(struct path_exclude_check *check,\n \t/* An entry in the index; cannot be a directory with subentries */\n \tstrbuf_setlen(path, 0);\n \n-\treturn last_exclude_matching(check->dir, name, dtype);\n+\treturn last_exclude_matching(check->dir, name, namelen, dtype);\n }\n \n /*\n@@ -1297,7 +1300,7 @@ static enum path_treatment treat_one_path(struct dir_struct *dir,\n \tint exclude;\n \n \tSTART_CLOCK();\n-\texclude = is_excluded(dir, path->buf, &dtype);\n+\texclude = is_excluded(dir, path->buf, path->len, &dtype);\n \tSTOP_CLOCK(tv_is_excluded);\n \n \tif (exclude && (dir->flags & DIR_COLLECT_IGNORED)\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"211123","messageId":"1363093500-16796-8-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1363093500-16796-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v3 07/13] exclude: avoid calling prep_exclude on entries of the same directory","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-12T13:04:54Z","receivedAt":"2013-03-12T13:04:54Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"prep_exclude is only necessary when we enter or leave a directory. Now\nit's called for every entry in a directory. With this patch, the\nnumber of prep_exclude calls in webkit.git goes from 188k down to\n11k. This patch does not make exclude any faster, but it prepares for\nmaking prep_exclude heavier in terms of computation, where a large\nnumber of calls may have bigger impacts.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n dir.c | 10 +++++++++-\n dir.h | 1 +\n 2 files changed, 10 insertions(+), 1 deletion(-)\n\ndiff --git a/dir.c b/dir.c\nindex 58739f3..f8f7a7e 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -804,7 +804,10 @@ static struct exclude *last_exclude_matching(struct dir_struct *dir,\n \tbasename = (basename) ? basename+1 : pathname;\n \n \tSTART_CLOCK();\n-\tprep_exclude(dir, pathname, basename-pathname);\n+\tif (!dir->exclude_prepared) {\n+\t\tprep_exclude(dir, pathname, basename-pathname);\n+\t\tdir->exclude_prepared = 1;\n+\t}\n \tSTOP_CLOCK(tv_prep_exclude);\n \n \tSTART_CLOCK();\n@@ -894,6 +897,7 @@ struct exclude *last_exclude_matching_path(struct path_exclude_check *check,\n \n \t\tif (ch == '/') {\n \t\t\tint dt = DT_DIR;\n+\t\t\tcheck->dir->exclude_prepared = 0;\n \t\t\texclude = last_exclude_matching(check->dir,\n \t\t\t\t\t\t\tpath->buf, path->len,\n \t\t\t\t\t\t\t&dt);\n@@ -908,6 +912,7 @@ struct exclude *last_exclude_matching_path(struct path_exclude_check *check,\n \t/* An entry in the index; cannot be a directory with subentries */\n \tstrbuf_setlen(path, 0);\n \n+\tcheck->dir->exclude_prepared = 0;\n \treturn last_exclude_matching(check->dir, name, namelen, dtype);\n }\n \n@@ -1394,6 +1399,7 @@ static int read_directory_recursive(struct dir_struct *dir,\n \tif (!fdir)\n \t\tgoto out;\n \n+\tdir->exclude_prepared = 0;\n \twhile ((de = readdir(fdir)) != NULL) {\n \t\tswitch (treat_path(dir, de, &path, baselen, simplify)) {\n \t\tcase path_recurse:\n@@ -1415,6 +1421,7 @@ static int read_directory_recursive(struct dir_struct *dir,\n \t}\n \tclosedir(fdir);\n out:\n+\tdir->exclude_prepared = 0;\n \tstrbuf_release(&path);\n \n \treturn contents;\n@@ -1486,6 +1493,7 @@ static int treat_leading_path(struct dir_struct *dir,\n \t\t\tbreak;\n \t\tif (simplify_away(sb.buf, sb.len, simplify))\n \t\t\tbreak;\n+\t\tdir->exclude_prepared = 0;\n \t\tif (treat_one_path(dir, &sb, simplify,\n \t\t\t\t DT_DIR, NULL) == path_ignored)\n \t\t\tbreak; /* do not recurse into it */\ndiff --git a/dir.h b/dir.h\nindex 560ade4..0748407 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -86,6 +86,7 @@ struct dir_struct {\n \n \t/* Exclude info */\n \tconst char *exclude_per_dir;\n+\tint exclude_prepared;\n \n \t/*\n \t * We maintain three groups of exclude pattern lists:\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"211124","messageId":"1363093500-16796-9-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1363093500-16796-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v3 08/13] exclude: record baselen in the pattern","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-12T13:04:55Z","receivedAt":"2013-03-12T13:04:55Z","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 attr.c | 4 +++-\n dir.c | 19 ++++++++++++++-----\n dir.h | 6 +++++-\n 3 files changed, 22 insertions(+), 7 deletions(-)\n\ndiff --git a/attr.c b/attr.c\nindex 1818ba5..b89da33 100644\n--- a/attr.c\n+++ b/attr.c\n@@ -249,12 +249,14 @@ static struct match_attr *parse_attr_line(const char *line, const char *src,\n \t\tres->u.attr = git_attr_internal(name, namelen);\n \telse {\n \t\tchar *p = (char *)&(res->state[num_attr]);\n+\t\tint pattern_baselen;\n \t\tmemcpy(p, name, namelen);\n \t\tres->u.pat.pattern = p;\n \t\tparse_exclude_pattern(&res->u.pat.pattern,\n \t\t\t\t &res->u.pat.patternlen,\n \t\t\t\t &res->u.pat.flags,\n-\t\t\t\t &res->u.pat.nowildcardlen);\n+\t\t\t\t &res->u.pat.nowildcardlen,\n+\t\t\t\t &pattern_baselen);\n \t\tif (res->u.pat.flags & EXC_FLAG_MUSTBEDIR)\n \t\t\tres->u.pat.patternlen++;\n \t\tif (res->u.pat.flags & EXC_FLAG_NEGATIVE) {\ndiff --git a/dir.c b/dir.c\nindex f8f7a7e..932fd2f 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -390,10 +390,11 @@ static int no_wildcard(const char *string)\n void parse_exclude_pattern(const char **pattern,\n \t\t\t int *patternlen,\n \t\t\t int *flags,\n-\t\t\t int *nowildcardlen)\n+\t\t\t int *nowildcardlen,\n+\t\t\t int *pattern_baselen)\n {\n \tconst char *p = *pattern;\n-\tsize_t i, len;\n+\tint i, len;\n \n \t*flags = 0;\n \tif (*p == '!') {\n@@ -405,12 +406,15 @@ void parse_exclude_pattern(const char **pattern,\n \t\tlen--;\n \t\t*flags |= EXC_FLAG_MUSTBEDIR;\n \t}\n-\tfor (i = 0; i < len; i++) {\n+\tfor (i = len - 1; i >= 0; i--) {\n \t\tif (p[i] == '/')\n \t\t\tbreak;\n \t}\n-\tif (i == len)\n+\tif (i < 0) {\n \t\t*flags |= EXC_FLAG_NODIR;\n+\t\t*pattern_baselen = -1;\n+\t} else\n+\t\t*pattern_baselen = i;\n \t*nowildcardlen = simple_length(p);\n \t/*\n \t * we should have excluded the trailing slash from 'p' too,\n@@ -421,6 +425,8 @@ void parse_exclude_pattern(const char **pattern,\n \t\t*nowildcardlen = len;\n \tif (*p == '*' && no_wildcard(p + 1))\n \t\t*flags |= EXC_FLAG_ENDSWITH;\n+\telse if (*nowildcardlen != len)\n+\t\t*pattern_baselen = -1;\n \t*pattern = p;\n \t*patternlen = len;\n }\n@@ -432,8 +438,10 @@ void add_exclude(const char *string, const char *base,\n \tint patternlen;\n \tint flags;\n \tint nowildcardlen;\n+\tint pattern_baselen;\n \n-\tparse_exclude_pattern(&string, &patternlen, &flags, &nowildcardlen);\n+\tparse_exclude_pattern(&string, &patternlen, &flags,\n+\t\t\t &nowildcardlen, &pattern_baselen);\n \tif (flags & EXC_FLAG_MUSTBEDIR) {\n \t\tchar *s;\n \t\tx = xmalloc(sizeof(*x) + patternlen + 1);\n@@ -449,6 +457,7 @@ void add_exclude(const char *string, const char *base,\n \tx->nowildcardlen = nowildcardlen;\n \tx->base = base;\n \tx->baselen = baselen;\n+\tx->pattern_baselen = pattern_baselen;\n \tx->flags = flags;\n \tx->srcpos = srcpos;\n \tALLOC_GROW(el->excludes, el->nr + 1, el->alloc);\ndiff --git a/dir.h b/dir.h\nindex 0748407..cb50a85 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -44,6 +44,7 @@ struct exclude_list {\n \t\tint nowildcardlen;\n \t\tconst char *base;\n \t\tint baselen;\n+\t\tint pattern_baselen;\n \t\tint flags;\n \n \t\t/*\n@@ -172,7 +173,10 @@ extern struct exclude_list *add_exclude_list(struct dir_struct *dir,\n extern int add_excludes_from_file_to_list(const char *fname, const char *base, int baselen,\n \t\t\t\t\t struct exclude_list *el, int check_index);\n extern void add_excludes_from_file(struct dir_struct *, const char *fname);\n-extern void parse_exclude_pattern(const char **string, int *patternlen, int *flags, int *nowildcardlen);\n+extern void parse_exclude_pattern(const char **string,\n+\t\t\t\t int *patternlen, int *flags,\n+\t\t\t\t int *nowildcardlen,\n+\t\t\t\t int *pattern_baselen);\n extern void add_exclude(const char *string, const char *base,\n \t\t\tint baselen, struct exclude_list *el, int srcpos);\n extern void clear_exclude_list(struct exclude_list *el);\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"211125","messageId":"1363093500-16796-10-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1363093500-16796-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v3 09/13] exclude: filter out patterns not applicable to the current directory","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-12T13:04:56Z","receivedAt":"2013-03-12T13:04:56Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":".gitignore files are spread over directories (*) so that when we check\nfor ignored files at foo, we are not bothered by foo/bar/.gitignore,\nwhich contains ignore rules for foo/bar only.\n\nThis is not enough. foo/.gitignore can contain the pattern\n\"foo/bar/*.c\". When we stay at foo, we know that the pattern cannot\nmatch anything. Similarly, the pattern \"/autom4te.cache\" at root\ndirectory cannot match anything in foo. This patch attempts to filter\nout such patterns to drive down matching cost.\n\nThe algorithm implemented here is a naive one. Patterns can be either\nactive or passive:\n\n - When we enter a new directory (e.g. from root to foo), currently\n active patterns may no longer be applicable and can be turned to\n passive.\n\n - On the opposite, when we leave a directory (foo back to roo),\n passive patterns may come alive again.\n\nWe could do smarter things. But this implementation cuts a big portion\nof cost already (and solves the \"root .gitignore is evil\" problem).\nThere's probably no need to be smart.\n\n(*) this design forces us to try to find .gitignore at every\ndirectory. On webkit.git that equals to 6k open syscalls. It feels\nlike \".svn on every directory\" again. I suggest we add\n~/.gitignore.master, containing the list .gitignore files in\nworktree. If this file exists, we don't poke at every directory for\n.gitignore.\n\ntreat_leading_path: 0.000 0.000\nread_directory: 3.455 2.879\n+treat_one_path: 2.203 1.620\n++is_excluded: 2.000 1.416\n+++prep_exclude: 0.171 0.198\n+++matching: 1.509 0.904\n++dir_exist: 0.036 0.035\n++index_name_exists: 0.292 0.289\nlazy_init_name_hash: 0.257 0.257\n+simplify_away: 0.084 0.085\n+dir_add_name: 0.446 0.446\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n dir.c | 93 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--\n dir.h | 1 +\n 2 files changed, 92 insertions(+), 2 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 932fd2f..c57bf06 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -458,7 +458,7 @@ void add_exclude(const char *string, const char *base,\n \tx->base = base;\n \tx->baselen = baselen;\n \tx->pattern_baselen = pattern_baselen;\n-\tx->flags = flags;\n+\tx->flags = flags | EXC_FLAG_ACTIVE;\n \tx->srcpos = srcpos;\n \tALLOC_GROW(el->excludes, el->nr + 1, el->alloc);\n \tel->excludes[el->nr++] = x;\n@@ -591,6 +591,87 @@ void add_excludes_from_file(struct dir_struct *dir, const char *fname)\n \t\tdie(\"cannot use %s as an exclude file\", fname);\n }\n \n+static int pattern_match_base(struct dir_struct *dir,\n+\t\t\t const char *base, int baselen,\n+\t\t\t const struct exclude *exc)\n+{\n+\tconst char *pattern;\n+\n+\t/*\n+\t * TODO: if a patterns come from a .gitignore, exc->base would\n+\t * be the same for all of them. We could compare once and\n+\t * reuse the result, instead of perform the comparison per\n+\t * pattern like this.\n+\t */\n+\tif (exc->baselen) {\n+\t\tif (baselen < exc->baselen + 1)\n+\t\t\treturn 0;\n+\n+\t\tif (base[exc->baselen] != '/' ||\n+\t\t memcmp(base, exc->base, exc->baselen))\n+\t\t\treturn 0;\n+\n+\t\tbase += exc->baselen + 1;\n+\t\tbaselen -= exc->baselen + 1;\n+\t}\n+\n+\tif (baselen != exc->pattern_baselen)\n+\t\treturn 0;\n+\n+\tif (exc->pattern_baselen) {\n+\t\tpattern = exc->pattern;\n+\t\tif (*pattern == '/')\n+\t\t\tpattern++;\n+\t\tif (memcmp(base, pattern, exc->pattern_baselen))\n+\t\t\treturn 0;\n+\t}\n+\n+\treturn 1;\n+}\n+\n+/*\n+ * If pushed is non-zero, we have entered a new directory. Some\n+ * pathname patterns may no longer applicable. Go over all active\n+ * patterns and disable them if so.\n+ *\n+ * If popped is non-zero, we have left a directory. Inactive patterns\n+ * may be applicable again. Go over them and re-enable if so.\n+ */\n+static void scan_patterns(struct dir_struct *dir,\n+\t\t\t const char *base, int baselen,\n+\t\t\t int pushed, int popped)\n+{\n+\tint i, j, k;\n+\n+\tfor (i = EXC_CMDL; i <= EXC_FILE; i++) {\n+\t\tstruct exclude_list_group *group = &dir->exclude_list_group[i];\n+\t\tfor (j = group->nr - 1; j >= 0; j--) {\n+\t\t\tstruct exclude_list *list = &group->el[j];\n+\t\t\tfor (k = 0; k < list->nr; k++) {\n+\t\t\t\tstruct exclude *exc = list->excludes[k];\n+\n+\t\t\t\t/*\n+\t\t\t\t * No base (i.e. EXC_FLAG_NODIR) or\n+\t\t\t\t * applicable to many bases (\"**\"\n+\t\t\t\t * patterns)\n+\t\t\t\t */\n+\t\t\t\tif (exc->pattern_baselen == -1)\n+\t\t\t\t\tcontinue;\n+\n+\t\t\t\tif (exc->flags & EXC_FLAG_ACTIVE) {\n+\t\t\t\t\tif (pushed &&\n+\t\t\t\t\t !pattern_match_base(dir, base, baselen, exc))\n+\t\t\t\t\t\texc->flags &= ~EXC_FLAG_ACTIVE;\n+\t\t\t\t} else {\n+\t\t\t\t\tif (popped &&\n+\t\t\t\t\t pattern_match_base(dir, base, baselen, exc))\n+\t\t\t\t\t\texc->flags |= EXC_FLAG_ACTIVE;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\t}\n+}\n+\n /*\n * Loads the per-directory exclude list for the substring of base\n * which has a char length of baselen.\n@@ -600,7 +681,7 @@ static void prep_exclude(struct dir_struct *dir, const char *base, int baselen)\n \tstruct exclude_list_group *group;\n \tstruct exclude_list *el;\n \tstruct exclude_stack *stk = NULL;\n-\tint current;\n+\tint current, popped = 0, pushed = 0;\n \n \tif ((!dir->exclude_per_dir) ||\n \t (baselen + strlen(dir->exclude_per_dir) >= PATH_MAX))\n@@ -621,6 +702,7 @@ static void prep_exclude(struct dir_struct *dir, const char *base, int baselen)\n \t\tclear_exclude_list(el);\n \t\tfree(stk);\n \t\tgroup->nr--;\n+\t\tpopped++;\n \t}\n \n \t/* Read from the parent directories and push them down. */\n@@ -659,8 +741,12 @@ static void prep_exclude(struct dir_struct *dir, const char *base, int baselen)\n \t\t\t\t\t el, 1);\n \t\tdir->exclude_stack = stk;\n \t\tcurrent = stk->baselen;\n+\t\tpushed++;\n \t}\n \tdir->basebuf[baselen] = '\\0';\n+\n+\tif (pushed | popped)\n+\t\tscan_patterns(dir, base, baselen, pushed, popped);\n }\n \n int match_basename(const char *basename, int basenamelen,\n@@ -755,6 +841,9 @@ static struct exclude *last_exclude_matching_from_list(const char *pathname,\n \t\tconst char *exclude = x->pattern;\n \t\tint prefix = x->nowildcardlen;\n \n+\t\tif (!(x->flags & EXC_FLAG_ACTIVE))\n+\t\t\tcontinue;\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);\ndiff --git a/dir.h b/dir.h\nindex cb50a85..247bfda 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -14,6 +14,7 @@ struct dir_entry {\n #define EXC_FLAG_ENDSWITH 4\n #define EXC_FLAG_MUSTBEDIR 8\n #define EXC_FLAG_NEGATIVE 16\n+#define EXC_FLAG_ACTIVE 32\n \n /*\n * Each excludes file will be parsed into a fresh exclude_list which\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"211126","messageId":"1363093500-16796-11-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1363093500-16796-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v3 10/13] read_directory: avoid invoking exclude machinery on tracked files","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-12T13:04:57Z","receivedAt":"2013-03-12T13:04:57Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"read_directory() (and its friendly wrapper fill_directory) collects\nuntracked/ignored files by traversing through the whole worktree,\nfeeding every entry to treat_one_path(), where each entry is checked\nagainst .gitignore patterns.\n\nOne may see that tracked files can't be excluded and we do not need to\nrun them through exclude machinery. On repos where there are many\n.gitignore patterns and/or a lot of tracked files, this unnecessary\nprocessing can become expensive.\n\nThis patch avoids it mostly for normal cases. Directories are still\nprocessed as before. DIR_SHOW_IGNORED and DIR_COLLECT_IGNORED are not\nnormally used unless some options are given (e.g. \"checkout\n--overwrite-ignore\", \"add -f\"...)\n\ntreat_one_path's behavior changes when taking this shortcut. With\ncurrent code, when a non-directory path is not excluded,\ntreat_one_path calls treat_file, which returns the initial value of\nexclude_file and causes treat_one_path to return path_handled. With\nthis patch, on the same conditions, treat_one_path returns\npath_ignored.\n\nread_directory_recursive() cares about this difference. Check out the\nsnippet:\n\n\twhile (...) {\n\t\tswitch (treat_path(...)) {\n\t\tcase path_ignored:\n\t\t\tcontinue;\n\t\tcase path_handled:\n\t\t\tbreak;\n\t\t}\n\t\tcontents++;\n\t\tif (check_only)\n\t\t\tbreak;\n\t\tdir_add_name(dir, path.buf, path.len);\n\t}\n\nIf path_handled is returned, contents goes up. And if check_only is\ntrue, the loop could be broken early. These will not happen when\ntreat_one_path (and its wrapper treat_path) returns\npath_ignored. dir_add_name internally does a cache_name_exists() check\nso it makes no difference.\n\nTo avoid this behavior change, treat_one_path is instructed to skip\nthe optimization when check_only or contents is used.\n\nFinally some numbers (best of 20 runs) that shows why it's worth all\nthe hassle:\n\ngit status | webkit linux-2.6 libreoffice-core gentoo-x86\n-------------+----------------------------------------------\nbefore | 1.097s 0.208s 0.399s 0.539s\nafter | 0.736s 0.159s 0.248s 0.501s\nnr. patterns | 89 376 19 0\nnr. tracked | 182k 40k 63k 101k\n\ntreat_leading_path: 0.000 0.000\nread_directory: 2.879 1.299\n+treat_one_path: 1.620 0.599\n++is_excluded: 1.416 0.103\n+++prep_exclude: 0.198 0.040\n+++matching: 0.904 0.036\n++dir_exist: 0.035 0.036\n++index_name_exists: 0.289 0.291\nlazy_init_name_hash: 0.257 0.257\n+simplify_away: 0.085 0.082\n+dir_add_name: 0.446 0.000\n\nTracked-down-by: Karsten Blees \nSigned-off-by: Nguyễn Thái Ngọc Duy \nSigned-off-by: Junio C Hamano \n\n---\n dir.c | 80 ++++++++++++++++++++++++++++++++++++++++++++-----------------------\n 1 file changed, 53 insertions(+), 27 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex c57bf06..6809dd2 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -43,8 +43,11 @@ struct path_simplify {\n \tconst char *path;\n };\n \n-static int read_directory_recursive(struct dir_struct *dir, const char *path, int len,\n-\tint check_only, const struct path_simplify *simplify);\n+static void read_directory_recursive(struct dir_struct *dir,\n+\t\t\t\t const char *path, int len,\n+\t\t\t\t int check_only,\n+\t\t\t\t const struct path_simplify *simplify,\n+\t\t\t\t int *contents);\n static int get_dtype(struct dirent *de, const char *path, int len);\n \n static inline int memequal_icase(const char *a, const char *b, int n)\n@@ -1184,7 +1187,7 @@ static enum directory_treatment treat_directory(struct dir_struct *dir,\n \tconst char *dirname, int len, int exclude,\n \tconst struct path_simplify *simplify)\n {\n-\tint ret;\n+\tint contents = 0, ret;\n \tSTART_CLOCK();\n \t/* The \"len-1\" is to strip the final '/' */\n \tret = directory_exists_in_index(dirname, len-1);\n@@ -1219,19 +1222,19 @@ static enum directory_treatment treat_directory(struct dir_struct *dir,\n \t * check if it contains only ignored files\n \t */\n \tif ((dir->flags & DIR_SHOW_IGNORED) && !exclude) {\n-\t\tint ignored;\n \t\tdir->flags &= ~DIR_SHOW_IGNORED;\n \t\tdir->flags |= DIR_HIDE_EMPTY_DIRECTORIES;\n-\t\tignored = read_directory_recursive(dir, dirname, len, 1, simplify);\n+\t\tread_directory_recursive(dir, dirname, len, 1, simplify, &contents);\n \t\tdir->flags &= ~DIR_HIDE_EMPTY_DIRECTORIES;\n \t\tdir->flags |= DIR_SHOW_IGNORED;\n \n-\t\treturn ignored ? ignore_directory : show_directory;\n+\t\treturn contents ? ignore_directory : show_directory;\n \t}\n \tif (!(dir->flags & DIR_SHOW_IGNORED) &&\n \t !(dir->flags & DIR_HIDE_EMPTY_DIRECTORIES))\n \t\treturn show_directory;\n-\tif (!read_directory_recursive(dir, dirname, len, 1, simplify))\n+\tread_directory_recursive(dir, dirname, len, 1, simplify, &contents);\n+\tif (!contents)\n \t\treturn ignore_directory;\n \treturn show_directory;\n }\n@@ -1398,10 +1401,26 @@ enum path_treatment {\n static enum path_treatment treat_one_path(struct dir_struct *dir,\n \t\t\t\t\t struct strbuf *path,\n \t\t\t\t\t const struct path_simplify *simplify,\n-\t\t\t\t\t int dtype, struct dirent *de)\n+\t\t\t\t\t int dtype, struct dirent *de,\n+\t\t\t\t\t int exclude_shortcut_ok)\n {\n \tint exclude;\n \n+\tif (dtype == DT_UNKNOWN)\n+\t\tdtype = get_dtype(de, path->buf, path->len);\n+\n+\tif (exclude_shortcut_ok &&\n+\t !(dir->flags & DIR_SHOW_IGNORED) &&\n+\t !(dir->flags & DIR_COLLECT_IGNORED) &&\n+\t dtype != DT_DIR) {\n+\t\tstruct cache_entry *ce;\n+\t\tSTART_CLOCK();\n+\t\tce = cache_name_exists(path->buf, path->len, ignore_case);\n+\t\tSTOP_CLOCK(tv_index_name_exists);\n+\t\tif (ce)\n+\t\t\treturn path_ignored;\n+\t}\n+\n \tSTART_CLOCK();\n \texclude = is_excluded(dir, path->buf, path->len, &dtype);\n \tSTOP_CLOCK(tv_is_excluded);\n@@ -1417,9 +1436,6 @@ static enum path_treatment treat_one_path(struct dir_struct *dir,\n \tif (exclude && !(dir->flags & DIR_SHOW_IGNORED))\n \t\treturn path_ignored;\n \n-\tif (dtype == DT_UNKNOWN)\n-\t\tdtype = get_dtype(de, path->buf, path->len);\n-\n \tswitch (dtype) {\n \tdefault:\n \t\treturn path_ignored;\n@@ -1451,7 +1467,8 @@ static enum path_treatment treat_path(struct dir_struct *dir,\n \t\t\t\t struct dirent *de,\n \t\t\t\t struct strbuf *path,\n \t\t\t\t int baselen,\n-\t\t\t\t const struct path_simplify *simplify)\n+\t\t\t\t const struct path_simplify *simplify,\n+\t\t\t\t int exclude_shortcut_ok)\n {\n \tint dtype, ret;\n \n@@ -1467,7 +1484,7 @@ static enum path_treatment treat_path(struct dir_struct *dir,\n \n \tdtype = DTYPE(de);\n \tSTART_CLOCK();\n-\tret = treat_one_path(dir, path, simplify, dtype, de);\n+\tret = treat_one_path(dir, path, simplify, dtype, de, exclude_shortcut_ok);\n \tSTOP_CLOCK(tv_treat_one_path);\n \treturn ret;\n }\n@@ -1481,13 +1498,13 @@ static enum path_treatment treat_path(struct dir_struct *dir,\n * Also, we ignore the name \".git\" (even if it is not a directory).\n * That likely will not change.\n */\n-static int read_directory_recursive(struct dir_struct *dir,\n-\t\t\t\t const char *base, int baselen,\n-\t\t\t\t int check_only,\n-\t\t\t\t const struct path_simplify *simplify)\n+static void read_directory_recursive(struct dir_struct *dir,\n+\t\t\t\t const char *base, int baselen,\n+\t\t\t\t int check_only,\n+\t\t\t\t const struct path_simplify *simplify,\n+\t\t\t\t int *contents)\n {\n \tDIR *fdir;\n-\tint contents = 0;\n \tstruct dirent *de;\n \tstruct strbuf path = STRBUF_INIT;\n \n@@ -1499,18 +1516,29 @@ static int read_directory_recursive(struct dir_struct *dir,\n \n \tdir->exclude_prepared = 0;\n \twhile ((de = readdir(fdir)) != NULL) {\n-\t\tswitch (treat_path(dir, de, &path, baselen, simplify)) {\n+\t\tswitch (treat_path(dir, de, &path, baselen,\n+\t\t\t\t simplify,\n+\t\t\t\t !check_only && !contents)) {\n \t\tcase path_recurse:\n-\t\t\tcontents += read_directory_recursive(dir, path.buf,\n-\t\t\t\t\t\t\t path.len, 0,\n-\t\t\t\t\t\t\t simplify);\n+\t\t\tread_directory_recursive(dir, path.buf,\n+\t\t\t\t\t\t path.len, 0,\n+\t\t\t\t\t\t simplify,\n+\t\t\t\t\t\t contents);\n \t\t\tcontinue;\n \t\tcase path_ignored:\n \t\t\tcontinue;\n \t\tcase path_handled:\n \t\t\tbreak;\n \t\t}\n-\t\tcontents++;\n+\t\t/*\n+\t\t * Update the last argument to treat_path if anything\n+\t\t * else is done after this point. This is because if\n+\t\t * treat_path's exclude_shortcut_ok is true, it may\n+\t\t * incorrectly return path_ignored (and never reaches\n+\t\t * this part) instead of path_handled.\n+\t\t */\n+\t\tif (contents)\n+\t\t\t(*contents)++;\n \t\tif (check_only)\n \t\t\tbreak;\n \t\tSTART_CLOCK();\n@@ -1521,8 +1549,6 @@ static int read_directory_recursive(struct dir_struct *dir,\n out:\n \tdir->exclude_prepared = 0;\n \tstrbuf_release(&path);\n-\n-\treturn contents;\n }\n \n static int cmp_name(const void *p1, const void *p2)\n@@ -1593,7 +1619,7 @@ static int treat_leading_path(struct dir_struct *dir,\n \t\t\tbreak;\n \t\tdir->exclude_prepared = 0;\n \t\tif (treat_one_path(dir, &sb, simplify,\n-\t\t\t\t DT_DIR, NULL) == path_ignored)\n+\t\t\t\t DT_DIR, NULL, 0) == path_ignored)\n \t\t\tbreak; /* do not recurse into it */\n \t\tif (len <= baselen) {\n \t\t\trc = 1;\n@@ -1621,7 +1647,7 @@ int read_directory(struct dir_struct *dir, const char *path, int len, const char\n \t\tSTOP_CLOCK(tv_lazy_init_name_hash);\n #endif\n \t\tSTART_CLOCK();\n-\t\tread_directory_recursive(dir, path, len, 0, simplify);\n+\t\tread_directory_recursive(dir, path, len, 0, simplify, NULL);\n \t\tSTOP_CLOCK(tv_read_directory);\n \t}\n #ifdef MEASURE_EXCLUDE\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"211127","messageId":"1363093500-16796-12-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1363093500-16796-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v3 11/13] Preallocate hash tables when the number of inserts are known in advance","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-12T13:04:58Z","receivedAt":"2013-03-12T13:04:58Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This avoids unnecessary allocations and reinsertions. On webkit.git\n(i.e. about 100k inserts to the name hash table), this reduces about\n100ms out of 3s user time.\n\ntreat_leading_path: 0.000 0.000\nread_directory: 1.299 1.305\n+treat_one_path: 0.599 0.599\n++is_excluded: 0.103 0.103\n+++prep_exclude: 0.040 0.040\n+++matching: 0.036 0.035\n++dir_exist: 0.036 0.035\n++index_name_exists: 0.291 0.292\nlazy_init_name_hash: 0.257 0.155\n+simplify_away: 0.082 0.083\n+dir_add_name: 0.000 0.000\n\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n diffcore-rename.c | 1 +\n hash.h | 7 +++++++\n name-hash.c | 1 +\n 3 files changed, 9 insertions(+)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 512d0ac..8d3d9bb 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -389,6 +389,7 @@ static int find_exact_renames(struct diff_options *options)\n \tstruct hash_table file_table;\n \n \tinit_hash(&file_table);\n+\tpreallocate_hash(&file_table, (rename_src_nr + rename_dst_nr) * 2);\n \tfor (i = 0; i < rename_src_nr; i++)\n \t\tinsert_file_table(&file_table, -1, i, rename_src[i].p->one);\n \ndiff --git a/hash.h b/hash.h\nindex b875ce6..244d1fe 100644\n--- a/hash.h\n+++ b/hash.h\n@@ -40,4 +40,11 @@ static inline void init_hash(struct hash_table *table)\n \ttable->array = NULL;\n }\n \n+static inline void preallocate_hash(struct hash_table *table, unsigned int size)\n+{\n+\tassert(table->size == 0 && table->nr == 0 && table->array == NULL);\n+\ttable->size = size;\n+\ttable->array = xcalloc(sizeof(struct hash_table_entry), size);\n+}\n+\n #endif\ndiff --git a/name-hash.c b/name-hash.c\nindex 942c459..1287a19 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -92,6 +92,7 @@ static void lazy_init_name_hash(struct index_state *istate)\n \n \tif (istate->name_hash_initialized)\n \t\treturn;\n+\tpreallocate_hash(&istate->name_hash, istate->cache_nr * 2);\n \tfor (nr = 0; nr < istate->cache_nr; nr++)\n \t\thash_index_entry(istate, istate->cache[nr]);\n \tistate->name_hash_initialized = 1;\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"211129","messageId":"1363093500-16796-13-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1363093500-16796-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v3 12/13] name-hash: allow to lookup a name with precalculated base hash","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-12T13:04:59Z","receivedAt":"2013-03-12T13:04:59Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"index_name_exists_base() differs from index_name_exists() in how the\nhash is calculated. It uses the base hash as the seed and skips the\nbaselen part.\n\nThe intention is to reduce hashing cost during directory traversal,\nwhere the hash of the directory is calculated once, and used as base\nhash for all entries inside.\n\nThis poses a constraint in hash function. The function has not changed\nsince 2008. With luck it'll never change again. If resuming hashing at\nany characters are not feasible with a new (better) hash function,\nmaybe we could stop at directory boundary.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n Makefile | 1 +\n cache.h | 2 --\n dir.c | 1 +\n name-hash.c | 48 ++++++++++++++++++++++--------------------------\n name-hash.h (new) | 45 +++++++++++++++++++++++++++++++++++++++++++++\n read-cache.c | 1 +\n unpack-trees.c | 1 +\n 7 files changed, 71 insertions(+), 28 deletions(-)\n create mode 100644 name-hash.h\n\ndiff --git a/Makefile b/Makefile\nindex 26d3332..8d753af 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -690,6 +690,7 @@ LIB_H += mailmap.h\n LIB_H += merge-blobs.h\n LIB_H += merge-recursive.h\n LIB_H += mergesort.h\n+LIB_H += name-hash.h\n LIB_H += notes-cache.h\n LIB_H += notes-merge.h\n LIB_H += notes.h\ndiff --git a/cache.h b/cache.h\nindex e493563..cf33c67 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -313,7 +313,6 @@ static inline void remove_name_hash(struct cache_entry *ce)\n #define refresh_cache(flags) refresh_index(&the_index, (flags), NULL, NULL, NULL)\n #define ce_match_stat(ce, st, options) ie_match_stat(&the_index, (ce), (st), (options))\n #define ce_modified(ce, st, options) ie_modified(&the_index, (ce), (st), (options))\n-#define cache_name_exists(name, namelen, igncase) index_name_exists(&the_index, (name), (namelen), (igncase))\n #define cache_name_is_other(name, namelen) index_name_is_other(&the_index, (name), (namelen))\n #define resolve_undo_clear() resolve_undo_clear_index(&the_index)\n #define unmerge_cache_entry_at(at) unmerge_index_entry_at(&the_index, at)\n@@ -442,7 +441,6 @@ extern int write_index(struct index_state *, int newfd);\n extern int discard_index(struct index_state *);\n extern int unmerged_index(const struct index_state *);\n extern int verify_path(const char *path);\n-extern struct cache_entry *index_name_exists(struct index_state *istate, const char *name, int namelen, int igncase);\n extern int index_name_pos(const struct index_state *, const char *name, int namelen);\n #define ADD_CACHE_OK_TO_ADD 1\t\t/* Ok to add */\n #define ADD_CACHE_OK_TO_REPLACE 2\t/* Ok to replace file/directory */\ndiff --git a/dir.c b/dir.c\nindex 6809dd2..5fda5af 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -11,6 +11,7 @@\n #include \"dir.h\"\n #include \"refs.h\"\n #include \"wildmatch.h\"\n+#include \"name-hash.h\"\n \n #ifdef MEASURE_EXCLUDE\n static uint32_t tv_treat_leading_path;\ndiff --git a/name-hash.c b/name-hash.c\nindex 1287a19..572d232 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -7,30 +7,7 @@\n */\n #define NO_THE_INDEX_COMPATIBILITY_MACROS\n #include \"cache.h\"\n-\n-/*\n- * This removes bit 5 if bit 6 is set.\n- *\n- * That will make US-ASCII characters hash to their upper-case\n- * equivalent. We could easily do this one whole word at a time,\n- * but that's for future worries.\n- */\n-static inline unsigned char icase_hash(unsigned char c)\n-{\n-\treturn c & ~((c & 0x40) >> 1);\n-}\n-\n-static unsigned int hash_name(const char *name, int namelen)\n-{\n-\tunsigned int hash = 0x123;\n-\n-\twhile (namelen--) {\n-\t\tunsigned char c = *name++;\n-\t\tc = icase_hash(c);\n-\t\thash = hash*101 + c;\n-\t}\n-\treturn hash;\n-}\n+#include \"name-hash.h\"\n \n static void hash_index_entry_directories(struct index_state *istate, struct cache_entry *ce)\n {\n@@ -152,9 +129,11 @@ static int same_name(const struct cache_entry *ce, const char *name, int namelen\n \treturn slow_same_name(name, namelen, ce->name, namelen < len ? namelen : len);\n }\n \n-struct cache_entry *index_name_exists(struct index_state *istate, const char *name, int namelen, int icase)\n+static inline struct cache_entry *find_entry_by_hash(struct index_state *istate,\n+\t\t\t\t\t\t const char *name, int namelen,\n+\t\t\t\t\t\t unsigned int hash,\n+\t\t\t\t\t\t int icase)\n {\n-\tunsigned int hash = hash_name(name, namelen);\n \tstruct cache_entry *ce;\n \n \tlazy_init_name_hash(istate);\n@@ -189,3 +168,20 @@ struct cache_entry *index_name_exists(struct index_state *istate, const char *na\n \t}\n \treturn NULL;\n }\n+\n+struct cache_entry *index_name_exists(struct index_state *istate,\n+\t\t\t\t const char *name, int namelen,\n+\t\t\t\t int icase)\n+{\n+\tunsigned int hash = hash_name(name, namelen);\n+\treturn find_entry_by_hash(istate, name, namelen, hash, icase);\n+}\n+\n+struct cache_entry *index_name_exists_base(struct index_state *istate,\n+\t\t\t\t\t unsigned int basehash, int baselen,\n+\t\t\t\t\t const char *name, int namelen,\n+\t\t\t\t\t int icase)\n+{\n+\tunsigned int hash = hash_name_from(basehash, name + baselen, namelen - baselen);\n+\treturn find_entry_by_hash(istate, name, namelen, hash, icase);\n+}\ndiff --git a/name-hash.h b/name-hash.h\nnew file mode 100644\nindex 0000000..997de30\n--- /dev/null\n+++ b/name-hash.h\n@@ -0,0 +1,45 @@\n+#ifndef NAME_HASH_H\n+#define NAME_HASH_H\n+\n+extern struct cache_entry *index_name_exists(struct index_state *istate,\n+\t\t\t\t\t const char *name, int namelen,\n+\t\t\t\t\t int igncase);\n+extern struct cache_entry *index_name_exists_base(struct index_state *istate,\n+\t\t\t\t\t\t unsigned int basehash, int baselen,\n+\t\t\t\t\t\t const char *name, int namelen,\n+\t\t\t\t\t\t int igncase);\n+\n+static inline struct cache_entry *cache_name_exists(const char *name, int namelen, int igncase)\n+{\n+\treturn index_name_exists(&the_index, name, namelen, igncase);\n+}\n+\n+/*\n+ * This removes bit 5 if bit 6 is set.\n+ *\n+ * That will make US-ASCII characters hash to their upper-case\n+ * equivalent. We could easily do this one whole word at a time,\n+ * but that's for future worries.\n+ */\n+static inline unsigned char icase_hash(unsigned char c)\n+{\n+\treturn c & ~((c & 0x40) >> 1);\n+}\n+\n+static inline unsigned int hash_name_from(unsigned int hash,\n+\t\t\t\t\t const char *name, int namelen)\n+{\n+\twhile (namelen--) {\n+\t\tunsigned char c = *name++;\n+\t\tc = icase_hash(c);\n+\t\thash = hash*101 + c;\n+\t}\n+\treturn hash;\n+}\n+\n+static inline unsigned int hash_name(const char *name, int namelen)\n+{\n+\treturn hash_name_from(0x123, name, namelen);\n+}\n+\n+#endif\ndiff --git a/read-cache.c b/read-cache.c\nindex 827ae55..8bd3ec8 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -14,6 +14,7 @@\n #include \"resolve-undo.h\"\n #include \"strbuf.h\"\n #include \"varint.h\"\n+#include \"name-hash.h\"\n \n static struct cache_entry *refresh_cache_entry(struct cache_entry *ce, int really);\n \ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 09e53df..60fa5d4 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -8,6 +8,7 @@\n #include \"progress.h\"\n #include \"refs.h\"\n #include \"attr.h\"\n+#include \"name-hash.h\"\n \n /*\n * Error messages expected by scripts out of plumbing commands such as\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"211128","messageId":"1363093500-16796-14-git-send-email-pclouds@gmail.com","threadId":"33112","inReplyTo":"1363093500-16796-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v3 13/13] read_directory: calculate name hashes incrementally","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-12T13:05:00Z","receivedAt":"2013-03-12T13:05:00Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Instead of index_name_exists() calculating a hash for full pathname\nfor every entry, we calculate partial hash per directory, use it as a\nseed. The number of characters that icase_hash has to chew will\nreduce.\n\ntreat_leading_path: 0.000 0.000\nread_directory: 1.296 1.235\n+treat_one_path: 0.599 0.531\n++is_excluded: 0.102 0.102\n+++prep_exclude: 0.040 0.040\n+++matching: 0.035 0.035\n++dir_exist: 0.035 0.035\n++index_name_exists: 0.292 0.225\nlazy_init_name_hash: 0.155 0.155\n+simplify_away: 0.082 0.083\n+dir_add_name: 0.000 0.000\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n dir.c | 44 +++++++++++++++++++++++++++++++++-----------\n 1 file changed, 33 insertions(+), 11 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 5fda5af..8638dcd 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -46,6 +46,7 @@ struct path_simplify {\n \n static void read_directory_recursive(struct dir_struct *dir,\n \t\t\t\t const char *path, int len,\n+\t\t\t\t unsigned int hash,\n \t\t\t\t int check_only,\n \t\t\t\t const struct path_simplify *simplify,\n \t\t\t\t int *contents);\n@@ -1044,12 +1045,17 @@ static struct dir_entry *dir_entry_new(const char *pathname, int len)\n \treturn ent;\n }\n \n-static struct dir_entry *dir_add_name(struct dir_struct *dir, const char *pathname, int len)\n+static struct dir_entry *dir_add_name(struct dir_struct *dir,\n+\t\t\t\t const char *pathname, int len,\n+\t\t\t\t unsigned int hash, int baselen)\n {\n \tif (!(dir->flags & DIR_SHOW_IGNORED)) {\n \t\tstruct cache_entry *ce;\n \t\tSTART_CLOCK();\n-\t\tce = cache_name_exists(pathname, len, ignore_case);\n+\t\tce = index_name_exists_base(&the_index,\n+\t\t\t\t\t hash, baselen,\n+\t\t\t\t\t pathname, len,\n+\t\t\t\t\t ignore_case);\n \t\tSTOP_CLOCK(tv_index_name_exists);\n \t\tif (ce)\n \t\t\treturn NULL;\n@@ -1225,7 +1231,9 @@ static enum directory_treatment treat_directory(struct dir_struct *dir,\n \tif ((dir->flags & DIR_SHOW_IGNORED) && !exclude) {\n \t\tdir->flags &= ~DIR_SHOW_IGNORED;\n \t\tdir->flags |= DIR_HIDE_EMPTY_DIRECTORIES;\n-\t\tread_directory_recursive(dir, dirname, len, 1, simplify, &contents);\n+\t\tread_directory_recursive(dir, dirname, len,\n+\t\t\t\t\t hash_name(dirname, len),\n+\t\t\t\t\t 1, simplify, &contents);\n \t\tdir->flags &= ~DIR_HIDE_EMPTY_DIRECTORIES;\n \t\tdir->flags |= DIR_SHOW_IGNORED;\n \n@@ -1234,7 +1242,9 @@ static enum directory_treatment treat_directory(struct dir_struct *dir,\n \tif (!(dir->flags & DIR_SHOW_IGNORED) &&\n \t !(dir->flags & DIR_HIDE_EMPTY_DIRECTORIES))\n \t\treturn show_directory;\n-\tread_directory_recursive(dir, dirname, len, 1, simplify, &contents);\n+\tread_directory_recursive(dir, dirname, len,\n+\t\t\t\t hash_name(dirname, len),\n+\t\t\t\t 1, simplify, &contents);\n \tif (!contents)\n \t\treturn ignore_directory;\n \treturn show_directory;\n@@ -1401,6 +1411,8 @@ enum path_treatment {\n \n static enum path_treatment treat_one_path(struct dir_struct *dir,\n \t\t\t\t\t struct strbuf *path,\n+\t\t\t\t\t unsigned int hash,\n+\t\t\t\t\t int baselen,\n \t\t\t\t\t const struct path_simplify *simplify,\n \t\t\t\t\t int dtype, struct dirent *de,\n \t\t\t\t\t int exclude_shortcut_ok)\n@@ -1416,7 +1428,8 @@ static enum path_treatment treat_one_path(struct dir_struct *dir,\n \t dtype != DT_DIR) {\n \t\tstruct cache_entry *ce;\n \t\tSTART_CLOCK();\n-\t\tce = cache_name_exists(path->buf, path->len, ignore_case);\n+\t\tce = index_name_exists_base(&the_index, hash, baselen,\n+\t\t\t\t\t path->buf, path->len, ignore_case);\n \t\tSTOP_CLOCK(tv_index_name_exists);\n \t\tif (ce)\n \t\t\treturn path_ignored;\n@@ -1467,6 +1480,7 @@ static enum path_treatment treat_one_path(struct dir_struct *dir,\n static enum path_treatment treat_path(struct dir_struct *dir,\n \t\t\t\t struct dirent *de,\n \t\t\t\t struct strbuf *path,\n+\t\t\t\t unsigned int hash,\n \t\t\t\t int baselen,\n \t\t\t\t const struct path_simplify *simplify,\n \t\t\t\t int exclude_shortcut_ok)\n@@ -1485,7 +1499,8 @@ static enum path_treatment treat_path(struct dir_struct *dir,\n \n \tdtype = DTYPE(de);\n \tSTART_CLOCK();\n-\tret = treat_one_path(dir, path, simplify, dtype, de, exclude_shortcut_ok);\n+\tret = treat_one_path(dir, path, hash, baselen,\n+\t\t\t simplify, dtype, de, exclude_shortcut_ok);\n \tSTOP_CLOCK(tv_treat_one_path);\n \treturn ret;\n }\n@@ -1501,6 +1516,7 @@ static enum path_treatment treat_path(struct dir_struct *dir,\n */\n static void read_directory_recursive(struct dir_struct *dir,\n \t\t\t\t const char *base, int baselen,\n+\t\t\t\t unsigned int hash,\n \t\t\t\t int check_only,\n \t\t\t\t const struct path_simplify *simplify,\n \t\t\t\t int *contents)\n@@ -1517,12 +1533,16 @@ static void read_directory_recursive(struct dir_struct *dir,\n \n \tdir->exclude_prepared = 0;\n \twhile ((de = readdir(fdir)) != NULL) {\n-\t\tswitch (treat_path(dir, de, &path, baselen,\n+\t\tswitch (treat_path(dir, de, &path, hash, baselen,\n \t\t\t\t simplify,\n \t\t\t\t !check_only && !contents)) {\n \t\tcase path_recurse:\n \t\t\tread_directory_recursive(dir, path.buf,\n-\t\t\t\t\t\t path.len, 0,\n+\t\t\t\t\t\t path.len,\n+\t\t\t\t\t\t hash_name_from(hash,\n+\t\t\t\t\t\t\t\tpath.buf + baselen,\n+\t\t\t\t\t\t\t\tpath.len - baselen),\n+\t\t\t\t\t\t 0,\n \t\t\t\t\t\t simplify,\n \t\t\t\t\t\t contents);\n \t\t\tcontinue;\n@@ -1543,7 +1563,7 @@ static void read_directory_recursive(struct dir_struct *dir,\n \t\tif (check_only)\n \t\t\tbreak;\n \t\tSTART_CLOCK();\n-\t\tdir_add_name(dir, path.buf, path.len);\n+\t\tdir_add_name(dir, path.buf, path.len, hash, baselen);\n \t\tSTOP_CLOCK(tv_dir_add_name);\n \t}\n \tclosedir(fdir);\n@@ -1619,7 +1639,7 @@ static int treat_leading_path(struct dir_struct *dir,\n \t\tif (simplify_away(sb.buf, sb.len, simplify))\n \t\t\tbreak;\n \t\tdir->exclude_prepared = 0;\n-\t\tif (treat_one_path(dir, &sb, simplify,\n+\t\tif (treat_one_path(dir, &sb, 0, 0, simplify,\n \t\t\t\t DT_DIR, NULL, 0) == path_ignored)\n \t\t\tbreak; /* do not recurse into it */\n \t\tif (len <= baselen) {\n@@ -1648,7 +1668,9 @@ int read_directory(struct dir_struct *dir, const char *path, int len, const char\n \t\tSTOP_CLOCK(tv_lazy_init_name_hash);\n #endif\n \t\tSTART_CLOCK();\n-\t\tread_directory_recursive(dir, path, len, 0, simplify, NULL);\n+\t\tread_directory_recursive(dir, path, len,\n+\t\t\t\t\t hash_name(path, len),\n+\t\t\t\t\t 0, simplify, NULL);\n \t\tSTOP_CLOCK(tv_read_directory);\n \t}\n #ifdef MEASURE_EXCLUDE\n-- \n1.8.1.2.536.gf441e6d\n"},{"id":"211144","messageId":"CALWbr2w71DsORxsFBBj4N2wzYQomjvCqxGfovbTDjGAT9eASyQ@mail.gmail.com","threadId":"33112","inReplyTo":"1363093500-16796-5-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH v3 04/13] match_basename: use strncmp instead of strcmp","fromName":"Antoine Pelisse","fromEmail":"apelisse@gmail.com","sentAt":"2013-03-12T17:40:40Z","receivedAt":"2013-03-12T17:40:40Z","isPatch":true,"sender":{"key":"apelisse@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1929644?v=4"},"body":"> --- a/dir.c\n> +++ b/dir.c\n> @@ -636,12 +636,14 @@ int match_basename(const char *basename, int basenamelen,\n> int flags)\n> {\n> if (prefix == patternlen) {\n> - if (!strcmp_icase(pattern, basename))\n> + if (patternlen == basenamelen &&\n> + !strncmp_icase(pattern, basename, patternlen))\n> return 1;\n> } else if (flags & EXC_FLAG_ENDSWITH) {\n> if (patternlen - 1 <= basenamelen &&\n> - !strcmp_icase(pattern + 1,\n> - basename + basenamelen - patternlen + 1))\n> + !strncmp_icase(pattern + 1,\n> + basename + basenamelen - patternlen + 1,\n> + patternlen - 1))\n> return 1;\n\n\nI can see that you kept strncmp(), was it worse with memcmp() ?\n"},{"id":"211160","messageId":"7v7glc72rn.fsf@alter.siamese.dyndns.org","threadId":"33112","inReplyTo":"CACsJy8A_4SqLu5L6P0PJ78Lwy12fjL7T2p-KbVEVLJmKNqhyRw@mail.gmail.com","subject":"Re: [PATCH v2 3/6] match_basename: use strncmp instead of strcmp","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-12T20:59:40Z","receivedAt":"2013-03-12T20:59:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen writes:\n\n> glibc's C strncmp version does 4-byte comparison at a time when n >=4,\n> then fall back to 1-byte for the rest. I don't know if it's faster\n> than a plain always 1-byte comparison though. There's also the hand\n> written assembly version that compares n from 1..16, not exactly sure\n> how this version works yet.\n\nIt sounds to me more like \"a very popular implementation of\nstrcmp/strncmp pair found to have more optimized strncmp than\nstrcmp\". While that may be a good reason to justify this patch,\nI do not think it justifies this:\n\n>> strncmp is provided length information which could be taken advantage\n>> by the underlying implementation.\n\nAfter all, strcmp() could also be optimized to fetch word-at-a-time\nwhile being careful about not overstepping the page boundary.\n"},{"id":"211175","messageId":"CAPig+cTjmEVpr7gK4wp_+mvO9AHUenvpzGAy2wGht=HB+quvLQ@mail.gmail.com","threadId":"33112","inReplyTo":"1363093500-16796-10-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH v3 09/13] exclude: filter out patterns not applicable to the current directory","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2013-03-12T23:13:02Z","receivedAt":"2013-03-12T23:13:02Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Tue, Mar 12, 2013 at 9:04 AM, Nguyễn Thái Ngọc Duy wrote:\n> The algorithm implemented here is a naive one. Patterns can be either\n> active or passive:\n>\n> - When we enter a new directory (e.g. from root to foo), currently\n> active patterns may no longer be applicable and can be turned to\n> passive.\n>\n> - On the opposite, when we leave a directory (foo back to roo),\n\ns/roo/root/\n\nAlso, perhaps you meant s/On/Or/ ?\n\n> +/*\n> + * If pushed is non-zero, we have entered a new directory. Some\n> + * pathname patterns may no longer applicable. Go over all active\n\ns/applicable/be applicable/\n\n-- ES\n"},{"id":"211185","messageId":"CACsJy8An08kFz4iCa-0U8Q30jUNqKzfZHK_jNdXOtnzqqRJEdg@mail.gmail.com","threadId":"33112","inReplyTo":"CALWbr2w71DsORxsFBBj4N2wzYQomjvCqxGfovbTDjGAT9eASyQ@mail.gmail.com","subject":"Re: [PATCH v3 04/13] match_basename: use strncmp instead of strcmp","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-13T01:05:58Z","receivedAt":"2013-03-13T01:05:58Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Mar 13, 2013 at 12:40 AM, Antoine Pelisse wrote:\n>> --- a/dir.c\n>> +++ b/dir.c\n>> @@ -636,12 +636,14 @@ int match_basename(const char *basename, int basenamelen,\n>> int flags)\n>> {\n>> if (prefix == patternlen) {\n>> - if (!strcmp_icase(pattern, basename))\n>> + if (patternlen == basenamelen &&\n>> + !strncmp_icase(pattern, basename, patternlen))\n>> return 1;\n>> } else if (flags & EXC_FLAG_ENDSWITH) {\n>> if (patternlen - 1 <= basenamelen &&\n>> - !strcmp_icase(pattern + 1,\n>> - basename + basenamelen - patternlen + 1))\n>> + !strncmp_icase(pattern + 1,\n>> + basename + basenamelen - patternlen + 1,\n>> + patternlen - 1))\n>> return 1;\n>\n>\n> I can see that you kept strncmp(), was it worse with memcmp() ?\n\nOne step at a time. 05/13 replace strncmp_icase with memcmp (for when\nignore_case == 0).\n-- \nDuy\n"},{"id":"211186","messageId":"CACsJy8DLDZqacrEZ4T0VkSr00wW2z6q-MsX0NKjcPhLdtgFV5Q@mail.gmail.com","threadId":"33112","inReplyTo":"7v7glc72rn.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2 3/6] match_basename: use strncmp instead of strcmp","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-13T01:11:00Z","receivedAt":"2013-03-13T01:11:00Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Mar 13, 2013 at 3:59 AM, Junio C Hamano wrote:\n>>> strncmp is provided length information which could be taken advantage\n>>> by the underlying implementation.\n>\n> After all, strcmp() could also be optimized to fetch word-at-a-time\n> while being careful about not overstepping the page boundary.\n\nIt boils down to giving more information to the underlying\nimplementation with hope that it can be useful for something. Although\nat this point I think strncmp vs strcmp vs memcmp may be not worth\ndoing (we keep explicit length comparison to reduce *cmp calls\nthough). The gain is relatively small and will become even smaller\nafter we avoid running exclude on tracked files (which eliminates like\n2/3 of the processed entries).\n-- \nDuy\n"},{"id":"211189","messageId":"CACsJy8Du7XMPWa032kSp0-z6j2ggOYHAQ0xadt=-XCATM5rPRw@mail.gmail.com","threadId":"33112","inReplyTo":"1363093500-16796-6-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH v3 05/13] match_{base,path}name: replace strncmp_icase with memequal_icase","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-13T01:14:14Z","receivedAt":"2013-03-13T01:14:14Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Mar 12, 2013 at 8:04 PM, Nguyễn Thái Ngọc Duy wrote:\n> +static inline int memequal_icase(const char *a, const char *b, int n)\n> +{\n> + if (!memcmp(a, b, n))\n> + return 1;\n> +\n> + if (!ignore_case)\n> + return 0;\n> +\n> + /*\n> + * This assumes that ASCII is used in most repositories. We\n> + * try the ascii-only version first (i.e. Git's\n> + * toupper). Failing that, fall back to normal strncasecmp.\n> + */\n> + while (n && toupper(*a) == toupper(*b)) {\n> + a++;\n> + b++;\n> + n--;\n> + }\n> + if (!n)\n> + return 1;\n> + return !strncasecmp(a, b, n);\n> +}\n\nNote, the ignore_case == 1 codepath was not tested and measured. I\nsuspect that strncasecmp may be more complex to support locales and\nthe \"LANG=C\" version should suffice in most case. But it's just\nguesses at this moment.\n-- \nDuy\n"},{"id":"211292","messageId":"CACsJy8BbS_iNvSRxdg0WVfF4V3oifh1_qTD6qBch6247o5bwxA@mail.gmail.com","threadId":"33112","inReplyTo":"1363093500-16796-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH v3 00/13] Exclude optimizations","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-14T13:05:57Z","receivedAt":"2013-03-14T13:05:57Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Just thinking out loud. If I'm not mistaken, a directory's mtime is\nonly changed when files are added are removed in that directory. And\nthat's all we care about in read_directory. So if we keep a secondary\nindex containing the list of all (tracked and untracked) .gitignore\nfiles and all untracked files (regardless ignore status), we could\navoid reading a directory if:\n\n - all relevant .gitignore are unchanged\n - the directory's stat is unchanged\n\nIn that case we already have the list of untracked files. Exclude can\nbe run over to filter out ignored files. And because we know these are\nnot tracked, we do not need to call index_name_exists (not if\nignore_case == 0).\n\nIn the best case, nothing's added or removed, read_directory just\nissues a bunch of lstat (like index refresh), filter out ignored files\nand _not_ trigger (nor pay penalty for) lazy_init_name_hash. webkit\nhas 11k untracked files. I don't think we have problems storing that\nlist as we already have to chew 182k entries in index.\n\nDid I make any mistakes above?\n-- \nDuy\n"}]}