{"thread":{"id":"33115","subject":"[PATCH] Replace strcmp_icase with strequal_icase","startedAt":"2013-03-09T08:42:54Z","lastAt":"2013-03-09T12:40:12Z","messageCount":9,"participants":["Fredrik Gustafsson","Duy Nguyen"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"210882","messageId":"1362818574-16873-1-git-send-email-iveqy@iveqy.com","threadId":"33115","inReplyTo":null,"subject":"[PATCH] Replace strcmp_icase with strequal_icase","fromName":"Fredrik Gustafsson","fromEmail":"iveqy@iveqy.com","sentAt":"2013-03-09T08:42:54Z","receivedAt":"2013-03-09T08:42:54Z","isPatch":true,"sender":{"key":"iveqy@iveqy.com","avatar":"https://avatars.githubusercontent.com/u/761743?v=4"},"body":"To improve performance.\ngit status before:\nuser    0m0.020s\nuser    0m0.024s\nuser    0m0.024s\nuser    0m0.020s\nuser    0m0.024s\nuser    0m0.028s\nuser    0m0.024s\nuser    0m0.024s\nuser    0m0.016s\nuser    0m0.028s\n\ngit status after:\nuser    0m0.012s\nuser    0m0.008s\nuser    0m0.008s\nuser    0m0.008s\nuser    0m0.008s\nuser    0m0.008s\nuser    0m0.008s\nuser    0m0.004s\nuser    0m0.008s\nuser    0m0.016s\n\nSigned-off-by: Fredrik Gustafsson <iveqy@iveqy.com>\n---\n dir.c | 17 ++++++++++++++---\n 1 file changed, 14 insertions(+), 3 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 57394e4..2b801e8 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -37,6 +37,17 @@ int fnmatch_icase(const char *pattern, const char *string, int flags)\n \treturn fnmatch(pattern, string, flags | (ignore_case ? FNM_CASEFOLD : 0));\n }\n \n+int strequal_icase(const char *first, const char *second)\n+{\n+\twhile (*first && *second) {\n+\t\tif( toupper(*first) != toupper(*second))\n+\t\t\tbreak;\n+\t\tfirst++;\n+\t\tsecond++;\n+\t}\n+\treturn toupper(*first) == toupper(*second);\n+}\n+\n inline int git_fnmatch(const char *pattern, const char *string,\n \t\t       int flags, int prefix)\n {\n@@ -626,11 +637,11 @@ 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 (!strequal_icase(pattern, basename))\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    !strequal_icase(pattern + 1,\n \t\t\t\t  basename + basenamelen - patternlen + 1))\n \t\t\treturn 1;\n \t} else {\n@@ -663,7 +674,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    strequal_icase(pathname, base))\n \t\treturn 0;\n \n \tnamelen = baselen ? pathlen - baselen - 1 : pathlen;\n-- \n1.8.1.5\n"},{"id":"210884","messageId":"20130309085713.GA23639@paksenarrion.iveqy.com","threadId":"33115","inReplyTo":"1362818574-16873-1-git-send-email-iveqy@iveqy.com","subject":"Re: [PATCH] Replace strcmp_icase with strequal_icase","fromName":"Fredrik Gustafsson","fromEmail":"iveqy@iveqy.com","sentAt":"2013-03-09T08:57:13Z","receivedAt":"2013-03-09T08:57:13Z","isPatch":true,"sender":{"key":"iveqy@iveqy.com","avatar":"https://avatars.githubusercontent.com/u/761743?v=4"},"body":"Please ignore last e-mail. Sorry for the disturbance.\n\n-- \nMed vänliga hälsningar\nFredrik Gustafsson\n\ntel: 0733-608274\ne-post: iveqy@iveqy.com\n"},{"id":"210887","messageId":"20130309102155.GA11616@lanh","threadId":"33115","inReplyTo":"1362818574-16873-1-git-send-email-iveqy@iveqy.com","subject":"Re: [PATCH] Replace strcmp_icase with strequal_icase","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-09T10:21:55Z","receivedAt":"2013-03-09T10:21:55Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Mar 09, 2013 at 09:42:54AM +0100, Fredrik Gustafsson wrote:\n> To improve performance.\n> git status before:\n> user    0m0.020s\n> user    0m0.024s\n> user    0m0.024s\n> user    0m0.020s\n> user    0m0.024s\n> user    0m0.028s\n> user    0m0.024s\n> user    0m0.024s\n> user    0m0.016s\n> user    0m0.028s\n> \n> git status after:\n> user    0m0.012s\n> user    0m0.008s\n> user    0m0.008s\n> user    0m0.008s\n> user    0m0.008s\n> user    0m0.008s\n> user    0m0.008s\n> user    0m0.004s\n> user    0m0.008s\n> user    0m0.016s\n\nI tested a slightly different version that checks ignore_case, inlines\nif possible and replaces one more strncmp_icase call site (the top\ncall site in webkit.git). The numbers are impressive (well not as\nimpressive as yours, but I guess it depends on the actual .gitignore\npatterns). On top of my 3/3\n\n        before      after\nuser    0m0.508s    0m0.392s\nuser    0m0.511s    0m0.394s\nuser    0m0.513s    0m0.405s\nuser    0m0.516s    0m0.407s\nuser    0m0.516s    0m0.407s\nuser    0m0.518s    0m0.410s\nuser    0m0.519s    0m0.412s\nuser    0m0.524s    0m0.415s\nuser    0m0.527s    0m0.415s\nuser    0m0.534s    0m0.417s\n\nI still need to run the test suite. Then maybe reroll my series with\nthis.\n\n-- 8< --\ndiff --git a/dir.c b/dir.c\nindex 2a91d14..6a9b4b7 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -21,6 +21,24 @@ 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 strnequal_icase(const char *first, const char *second, int length)\n+{\n+\tif (ignore_case) {\n+\t\twhile (length && toupper(*first) == toupper(*second)) {\n+\t\t\tfirst++;\n+\t\t\tsecond++;\n+\t\t\tlength--;\n+\t\t}\n+\t} else {\n+\t\twhile (length && *first == *second) {\n+\t\t\tfirst++;\n+\t\t\tsecond++;\n+\t\t\tlength--;\n+\t\t}\n+\t}\n+\treturn length == 0;\n+}\n+\n inline int git_fnmatch(const char *pattern, const char *string,\n \t\t       int flags, int prefix)\n {\n@@ -611,11 +629,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 +667,7 @@ int match_pathname(const char *pathname, int pathlen,\n \t */\n \tif (pathlen < baselen + 1 ||\n \t    (baselen && pathname[baselen] != '/') ||\n-\t    (baselen && strncmp_icase(pathname, base, baselen)))\n+\t    (baselen && !strnequal_icase(pathname, base, baselen)))\n \t\treturn 0;\n \n \tnamelen = baselen ? pathlen - baselen - 1 : pathlen;\n@@ -663,7 +681,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-- 8< --\n"},{"id":"210888","messageId":"CACsJy8CphBDKsAAKjCoze98jv=4U+3pN3cW1OYD5XNhYgfcVCA@mail.gmail.com","threadId":"33115","inReplyTo":"1362818574-16873-1-git-send-email-iveqy@iveqy.com","subject":"Re: [PATCH] Replace strcmp_icase with strequal_icase","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-09T10:40:55Z","receivedAt":"2013-03-09T10:40:55Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Mar 9, 2013 at 3:42 PM, Fredrik Gustafsson <iveqy@iveqy.com> wrote:\n> To improve performance.\n\nBTW, by rolling our own string comparison, we may lose certain\noptimizations done by C library. In case of glibc, it may choose to\nrun an sse4.2 version where 16 bytes are compared at a time. Maybe we\nencounter \"string not equal\" much often than \"string equal\" and such\nan optimization is unncessary, I don't know. Measured numbers say it's\nunncessary as my cpu supports sse4.2.\n-- \nDuy\n"},{"id":"210890","messageId":"CACsJy8BbXjJeTgo0DzKKMY7B3NZB=r3r+Z-WsWJR=t00DkTVzQ@mail.gmail.com","threadId":"33115","inReplyTo":"CACsJy8CphBDKsAAKjCoze98jv=4U+3pN3cW1OYD5XNhYgfcVCA@mail.gmail.com","subject":"Re: [PATCH] Replace strcmp_icase with strequal_icase","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-09T10:54:45Z","receivedAt":"2013-03-09T10:54:45Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Mar 9, 2013 at 5:40 PM, Duy Nguyen <pclouds@gmail.com> wrote:\n> On Sat, Mar 9, 2013 at 3:42 PM, Fredrik Gustafsson <iveqy@iveqy.com> wrote:\n>> To improve performance.\n>\n> BTW, by rolling our own string comparison, we may lose certain\n> optimizations done by C library. In case of glibc, it may choose to\n> run an sse4.2 version where 16 bytes are compared at a time. Maybe we\n> encounter \"string not equal\" much often than \"string equal\" and such\n> an optimization is unncessary, I don't know. Measured numbers say it's\n> unncessary as my cpu supports sse4.2.\n\nAnother problem is locale. Git's toupper() does not care about locale,\nwhich should be fine in most cases. strcasecmp is locale-aware, our\nnew str[n]equal_icase is not. It probably does not matter for\n(ascii-based) pathnames, I guess. core.ignorecase users, any comments?\n-- \nDuy\n"},{"id":"210891","messageId":"20130309110815.GA8328@paksenarrion.iveqy.com","threadId":"33115","inReplyTo":"CACsJy8BbXjJeTgo0DzKKMY7B3NZB=r3r+Z-WsWJR=t00DkTVzQ@mail.gmail.com","subject":"Re: [PATCH] Replace strcmp_icase with strequal_icase","fromName":"Fredrik Gustafsson","fromEmail":"iveqy@iveqy.com","sentAt":"2013-03-09T11:08:15Z","receivedAt":"2013-03-09T11:08:15Z","isPatch":true,"sender":{"key":"iveqy@iveqy.com","avatar":"https://avatars.githubusercontent.com/u/761743?v=4"},"body":"On Sat, Mar 09, 2013 at 05:54:45PM +0700, Duy Nguyen wrote:\n> On Sat, Mar 9, 2013 at 5:40 PM, Duy Nguyen <pclouds@gmail.com> wrote:\n> > On Sat, Mar 9, 2013 at 3:42 PM, Fredrik Gustafsson <iveqy@iveqy.com> wrote:\n> >> To improve performance.\n> >\n> > BTW, by rolling our own string comparison, we may lose certain\n> > optimizations done by C library. In case of glibc, it may choose to\n> > run an sse4.2 version where 16 bytes are compared at a time. Maybe we\n> > encounter \"string not equal\" much often than \"string equal\" and such\n> > an optimization is unncessary, I don't know. Measured numbers say it's\n> > unncessary as my cpu supports sse4.2.\n> \n> Another problem is locale. Git's toupper() does not care about locale,\n> which should be fine in most cases. strcasecmp is locale-aware, our\n> new str[n]equal_icase is not. It probably does not matter for\n> (ascii-based) pathnames, I guess. core.ignorecase users, any comments?\n> -- \n> Duy\n\nActually when implemented a str[n]equal_icase that actually should work.\nI break the test suite when trying to replace\nstrncmp_icase(pathname, base, baselen)) on line 711 in dir.c and I don't\nget any significant improvements.\n\nI like work in this area though, slow commit's are my worst git problem.\nI often have to wait 10s. for a commit to be calculated.\n\n\n-- \nMed vänliga hälsningar\nFredrik Gustafsson\n\ntel: 0733-608274\ne-post: iveqy@iveqy.com\n\n\nFrom c5d1f436cdbe7b12c67e81cf1d2904d1fb2e9b6b Mon Sep 17 00:00:00 2001\nFrom: Fredrik Gustafsson <iveqy@iveqy.com>\nDate: Sat, 9 Mar 2013 09:27:16 +0100\nSubject: [PATCH] Replace strcmp_icase with strequal_icase\n\nTo improve performance.\ngit status before:\nuser    0m0.020s\nuser    0m0.024s\nuser    0m0.024s\nuser    0m0.020s\nuser    0m0.024s\nuser    0m0.028s\nuser    0m0.024s\nuser    0m0.024s\nuser    0m0.016s\nuser    0m0.028s\n\ngit status after:\nwip\n\nTried to replace strncmp_icase on line 711 in dir.c but then failed to\nrun the testsuite. Did not got any relevant speed improvements of this.\n---\n dir.c |   49 +++++++++++++++++++++++++++++++++++++++++++++++--\n 1 files changed, 47 insertions(+), 2 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 57394e4..aace36a 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -37,6 +37,51 @@ int fnmatch_icase(const char *pattern, const char *string, int flags)\n \treturn fnmatch(pattern, string, flags | (ignore_case ? FNM_CASEFOLD : 0));\n }\n \n+int strnequal_icase(const char *first, const char *second, size_t count)\n+{\n+\tif (ignore_case) {\n+\t\twhile (*first && *second && count) {\n+\t\t\tif( toupper(*first) != toupper(*second))\n+\t\t\t\tbreak;\n+\t\t\tfirst++;\n+\t\t\tsecond++;\n+\t\t\tcount--;\n+\t\t}\n+\t\treturn toupper(*first) == toupper(*second);\n+\t} else {\n+\t\twhile (*first && *second && count) {\n+\t\t\tif( *first != *second)\n+\t\t\t\tbreak;\n+\t\t\tfirst++;\n+\t\t\tsecond++;\n+\t\t\tcount--;\n+\t\t}\n+\t\treturn *first == *second;\n+\t}\n+\n+}\n+\n+int strequal_icase(const char *first, const char *second)\n+{\n+\tif (ignore_case) {\n+\t\twhile (*first && *second) {\n+\t\t\tif( toupper(*first) != toupper(*second))\n+\t\t\t\tbreak;\n+\t\t\tfirst++;\n+\t\t\tsecond++;\n+\t\t}\n+\t\treturn toupper(*first) == toupper(*second);\n+\t} else {\n+\t\twhile (*first && *second) {\n+\t\t\tif( *first != *second)\n+\t\t\t\tbreak;\n+\t\t\tfirst++;\n+\t\t\tsecond++;\n+\t\t}\n+\t\treturn *first == *second;\n+\t}\n+}\n+\n inline int git_fnmatch(const char *pattern, const char *string,\n \t\t       int flags, int prefix)\n {\n@@ -626,11 +671,11 @@ 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 (strequal_icase(pattern, basename))\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    strequal_icase(pattern + 1,\n \t\t\t\t  basename + basenamelen - patternlen + 1))\n \t\t\treturn 1;\n \t} else {\n-- \n1.7.2.5\n"},{"id":"210893","messageId":"CACsJy8D4Yqm3s+ALf=KnMQRQ6SrVcM5jjktpGXiGcOaqtEsyMg@mail.gmail.com","threadId":"33115","inReplyTo":"20130309110815.GA8328@paksenarrion.iveqy.com","subject":"Re: [PATCH] Replace strcmp_icase with strequal_icase","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-09T12:05:37Z","receivedAt":"2013-03-09T12:05:37Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Mar 9, 2013 at 6:08 PM, Fredrik Gustafsson <iveqy@iveqy.com> wrote:\n> Actually when implemented a str[n]equal_icase that actually should work.\n> I break the test suite when trying to replace\n> strncmp_icase(pathname, base, baselen)) on line 711 in dir.c and I don't\n> get any significant improvements.\n\nHmm.. mine passed the test suite.\n\n> I like work in this area though, slow commit's are my worst git problem.\n> I often have to wait 10s. for a commit to be calculated.\n\nPersonally I don't accept any often used git commands taking more than\n1 second (in hot cache case). What commands do you use? What's the\nsize of the repository in terms of tracked/untracked files?\n-- \nDuy\n"},{"id":"210894","messageId":"20130309122200.GA7755@paksenarrion.iveqy.com","threadId":"33115","inReplyTo":"CACsJy8D4Yqm3s+ALf=KnMQRQ6SrVcM5jjktpGXiGcOaqtEsyMg@mail.gmail.com","subject":"Re: [PATCH] Replace strcmp_icase with strequal_icase","fromName":"Fredrik Gustafsson","fromEmail":"iveqy@iveqy.com","sentAt":"2013-03-09T12:22:00Z","receivedAt":"2013-03-09T12:22:00Z","isPatch":true,"sender":{"key":"iveqy@iveqy.com","avatar":"https://avatars.githubusercontent.com/u/761743?v=4"},"body":"On Sat, Mar 09, 2013 at 07:05:37PM +0700, Duy Nguyen wrote:\n> On Sat, Mar 9, 2013 at 6:08 PM, Fredrik Gustafsson <iveqy@iveqy.com> wrote:\n> > Actually when implemented a str[n]equal_icase that actually should work.\n> > I break the test suite when trying to replace\n> > strncmp_icase(pathname, base, baselen)) on line 711 in dir.c and I don't\n> > get any significant improvements.\n> \n> Hmm.. mine passed the test suite.\n\nUsing my patch or your own code? Maybe I just did something wrong. Could\nyou see any improvements in speed?\n\n> \n> > I like work in this area though, slow commit's are my worst git problem.\n> > I often have to wait 10s. for a commit to be calculated.\n> \n> Personally I don't accept any often used git commands taking more than\n> 1 second (in hot cache case). What commands do you use? What's the\n> size of the repository in terms of tracked/untracked files?\n\nIt's a small repository, 100 MB. However I have a slow hdd which is\nalmost full. I often add one file and make an one-line change to an\nother file and then do a git commit -a. That will make git to look\nthrough the whole repo, which isn't in the kernel RAM cache but needs to\nbe reed from the hdd.\n\n-- \nMed vänliga hälsningar\nFredrik Gustafsson\n\ntel: 0733-608274\ne-post: iveqy@iveqy.com\n"},{"id":"210895","messageId":"CACsJy8DfsgzEiMELy4UHJ2fvExZjcmvRop4m7u1H3OibrJiSPg@mail.gmail.com","threadId":"33115","inReplyTo":"20130309122200.GA7755@paksenarrion.iveqy.com","subject":"Re: [PATCH] Replace strcmp_icase with strequal_icase","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-09T12:40:12Z","receivedAt":"2013-03-09T12:40:12Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Mar 9, 2013 at 7:22 PM, Fredrik Gustafsson <iveqy@iveqy.com> wrote:\n> On Sat, Mar 09, 2013 at 07:05:37PM +0700, Duy Nguyen wrote:\n>> On Sat, Mar 9, 2013 at 6:08 PM, Fredrik Gustafsson <iveqy@iveqy.com> wrote:\n>> > Actually when implemented a str[n]equal_icase that actually should work.\n>> > I break the test suite when trying to replace\n>> > strncmp_icase(pathname, base, baselen)) on line 711 in dir.c and I don't\n>> > get any significant improvements.\n>>\n>> Hmm.. mine passed the test suite.\n>\n> Using my patch or your own code? Maybe I just did something wrong. Could\n> you see any improvements in speed?\n\nIt's the one I posted in [1] and yes it improves speed, numbers in [1].\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/217712/focus=217724\n\n>> > I like work in this area though, slow commit's are my worst git problem.\n>> > I often have to wait 10s. for a commit to be calculated.\n>>\n>> Personally I don't accept any often used git commands taking more than\n>> 1 second (in hot cache case). What commands do you use? What's the\n>> size of the repository in terms of tracked/untracked files?\n>\n> It's a small repository, 100 MB. However I have a slow hdd which is\n> almost full. I often add one file and make an one-line change to an\n> other file and then do a git commit -a. That will make git to look\n> through the whole repo, which isn't in the kernel RAM cache but needs to\n> be reed from the hdd.\n\n\"commit -a\" does not run exclude (what I'm improving here). It's\nprobably stat problem. If you already know what files you have\nchanged, \"git add path...\" then commit without -a might help. Or turn\non core.ignorestat (read doc about it first).\n-- \nDuy\n"}]}