Speedup scanning for excluded files.
PATCH 1/1 Speedup scanning for excluded files.
Try to avoid a lot of work while scanning for excluded files, by caching some more information when setting up the exclusion data structure.
Speeds up 'git runstatus' on a repository containing the Qt sources by 30% and reduces the amount of instructions executed (as measured by valgrind) by a factor of 2.
---
I did a short timing measurement on the git repository itself, the timings without and with the patch give:
[lars@dahab git (speedup)]$ time git runstatus > /dev/null
real 0m0.098s user 0m0.068s sys 0m0.020s
[lars@dahab git (speedup)]$ time ./git runstatus > /dev/null
real 0m0.033s user 0m0.012s sys 0m0.016s
Cheers,
Lars
dir.c | 58 ++++++++++++++++++++++++++++++++++++++++++---------------- dir.h | 7 +++++++ 2 files changed, 49 insertions(+), 16 deletions(-)
dir.c +0 -0
@@ -118,14 +118,32 @@ int match_pathspec(const char **pathspec, const char
*name, int namelen, int pre
return retval;
}
+static int no_wildcard(const char *string)
+{
+ return !strchr(string, '*') && !strchr(string, '?')
&& !strchr(string, '[') && !strchr(string, '{'); +}
+
void add_exclude(const char *string, const char *base,
int baselen, struct exclude_list *which)
{
struct exclude *x = xmalloc(sizeof (*x));
+ x->to_exclude = 1;
+ if (*string == '!') {
+ x->to_exclude = 0;
+ string++;
+ }
x->pattern = string;
+ x->patternlen = strlen(string);
x->base = base;
x->baselen = baselen;
+ x->flags = 0;
+ if (!strchr(string, '/'))
+ x->flags |= EXC_FLAG_NODIR;
+ if (no_wildcard(string))
+ x->flags |= EXC_FLAG_NOWILDCARD;
+ if (*string == '*' && no_wildcard(string+1))
+ x->flags |= EXC_FLAG_ENDSWITH;
if (which->nr == which->alloc) {
which->alloc = alloc_nr(which->alloc); which->excludes = xrealloc(which->excludes,
@@ -209,7 +227,7 @@ void pop_exclude_per_directory(struct dir_struct *dir, int stk)
* Return 1 for exclude, 0 for include and -1 for undecided.
*/
static int excluded_1(const char *pathname,
- int pathlen,
+ int pathlen, const char *basename,
struct exclude_list *el)
{
int i;
@@ -218,19 +236,20 @@ static int excluded_1(const char *pathname,
for (i = el->nr - 1; 0 <= i; i--) {
struct exclude *x = el->excludes[i]; const char *exclude = x->pattern;
- int to_exclude = 1;
+ int to_exclude = x->to_exclude;
- if (*exclude == '!') {
- to_exclude = 0;
- exclude++;
- }
-
- if (!strchr(exclude, '/')) {
+ if (x->flags & EXC_FLAG_NODIR) {
/* match basename */
- const char *basename = strrchr(pathname, '/');
- basename = (basename) ? basename+1 : pathname;
- if (fnmatch(exclude, basename, 0) == 0)
- return to_exclude;
+ if (x->flags & EXC_FLAG_NOWILDCARD) {
+ if (!strcmp(exclude, basename))
+ return to_exclude;
+ } else if (x->flags & EXC_FLAG_ENDSWITH) {
+ if (!strcmp(exclude + 1, pathname +
pathlen -x->patternlen + 1))
+ return to_exclude;
+ } else {
+ if (fnmatch(exclude, basename, 0) == 0)
+ return to_exclude;
+ }
}
else {
/* match with FNM_PATHNAME:
@@ -246,10 +265,15 @@ static int excluded_1(const char *pathname,
strncmp(pathname, x->base, baselen)) continue;
- if (fnmatch(exclude, pathname+baselen,
- FNM_PATHNAME) == 0)
+ if (x->flags & EXC_FLAG_NOWILDCARD) {
+ if (!strcmp(exclude, pathname + baselen))
+ return to_exclude;
+ } else {
+ if (fnmatch(exclude, pathname+baselen,
+ FNM_PATHNAME) == 0)
return to_exclude;
- }
+ }
+ }
}
}
return -1; /* undecided */
@@ -259,9 +283,11 @@ int excluded(struct dir_struct *dir, const char *pathname)
{
int pathlen = strlen(pathname);
int st;
+ const char *basename = strrchr(pathname, '/');
+ basename = (basename) ? basename+1 : pathname;
for (st = EXC_CMDL; st <= EXC_FILE; st++) {
- switch (excluded_1(pathname, pathlen, &dir->exclude_list[st])) {
+ switch (excluded_1(pathname, pathlen, basename, &dir->exclude_list[st])) {
case 0:
return 0;
case 1:
dir.h +7 -0
@@ -17,13 +17,20 @@ struct dir_entry {char name[FLEX_ARRAY ];/* more */ }; +#define EXC_FLAG_NODIR 1 +#define EXC_FLAG_NOWILDCARD 2 +#define EXC_FLAG_ENDSWITH 4 +struct exclude_list {int nr;int alloc;struct exclude {const char *pattern; +int patternlen;const char *base;int baselen; +int to_exclude; +int flags; } **excludes; };
Signature · 1 line
1.5.3.4.383.gd90a7
Quoted 4 lines · Lars Knoll
(quoted diff) +3
-0+static int no_wildcard(const char *string) +{ + return !strchr(string, '*') && !strchr(string, '?')&& !strchr(string, '[') && !strchr(string, '{');
return string[strcspn(string, "*?[{")] == '\0';is faster as it doesn't scan the string 4 time in the case where there is no wildcard.
Review
Quoted 8 lines
(quoted diff) +3
-0+} + void add_exclude(const char *string, const char *base, int baselen, struct exclude_list *which) { struct exclude *x = xmalloc(sizeof (*x)); + x->to_exclude = 1;
You used spaces in here, and in many places of your patch.
Signature · 3 lines
·O· Pierre Habouzit ··O [email protected] OOO http://www.madism.org
Quoted 1 line
From
51b364c9c87bec89556a2089cc5363c588ea2ff5Mon Sep 17 00:00:00 2001
From: Lars Knoll <[email protected]>
Date: Sun, 28 Oct 2007 21:27:13 +0100
Subject: [PATCH] Speedup scanning for excluded files.
Try to avoid a lot of work scanning for excluded files, by caching some more information when setting up the exclusion data structure.
Speeds up 'git runstatus' on a repository containing the Qt sources by 30% and reduces the amount of instructions executed (as measured by valgrind) by a factor of 2.
---
Fixed both the indentation and the no_wildcard method as Pierre pointed out.
Lars
dir.c | 60 +++++++++++++++++++++++++++++++++++++++++++----------------- dir.h | 7 +++++++ 2 files changed, 50 insertions(+), 17 deletions(-)
dir.c +43 -17
@@ -118,14 +118,32 @@ int match_pathspec(const char **pathspec, const char *name, int namelen, int prereturn retval; } +static int no_wildcard (const char *string) +{ +return string[strcspn (string,"*?[{" )] =='\0' ; +} +void add_exclude (const char *string,const char *base,int baselen,struct exclude_list *which) {struct exclude *x =xmalloc (sizeof (*x)); + x->to_exclude =1 ; +if (*string =='!' ) { + x->to_exclude =0 ; + string++; + } x->pattern = string; + x->patternlen =strlen (string); x->base = base; x->baselen = baselen; + x->flags =0 ; +if (!strchr (string,'/' )) + x->flags |=EXC_FLAG_NODIR ; +if (no_wildcard (string)) + x->flags |=EXC_FLAG_NOWILDCARD ; +if (*string =='*' &&no_wildcard (string+1 )) + x->flags |=EXC_FLAG_ENDSWITH ;if (which->nr == which->alloc) { which->alloc =alloc_nr (which->alloc); which->excludes = xrealloc(which->excludes,
@@ -209,7 +227,7 @@ void pop_exclude_per_directory(struct dir_struct *dir, int stk)* Return 1 for exclude, 0 for include and -1 for undecided. */ static int excluded_1 (const char *pathname, -int pathlen, +int pathlen,const char *basename,struct exclude_list *el) {int i;
@@ -218,19 +236,20 @@ static int excluded_1(const char *pathname,for (i = el->nr -1 ;0 <= i; i--) {struct exclude *x = el->excludes[i];const char *exclude = x->pattern; -int to_exclude =1 ; +int to_exclude = x->to_exclude; -if (*exclude =='!' ) { - to_exclude =0 ; - exclude++; - } - -if (!strchr (exclude,'/' )) { +if (x->flags &EXC_FLAG_NODIR ) {/* match basename */ -const char *basename =strrchr (pathname,'/' ); - basename = (basename) ? basename+1 : pathname; -if (fnmatch (exclude, basename,0 ) ==0 ) -return to_exclude; +if (x->flags &EXC_FLAG_NOWILDCARD ) { +if (!strcmp (exclude, basename)) +return to_exclude; + }else if (x->flags &EXC_FLAG_ENDSWITH ) { +if (!strcmp (exclude +1 , pathname + pathlen -x->patternlen +1 )) +return to_exclude; + }else { +if (fnmatch (exclude, basename,0 ) ==0 ) +return to_exclude; + } }else {/* match with FNM_PATHNAME:
@@ -246,9 +265,14 @@ static int excluded_1(const char *pathname, strncmp(pathname, x->base, baselen))continue ; -if (fnmatch (exclude, pathname+baselen, -FNM_PATHNAME ) ==0 ) -return to_exclude; +if (x->flags &EXC_FLAG_NOWILDCARD ) { +if (!strcmp (exclude, pathname + baselen)) +return to_exclude; + }else { +if (fnmatch (exclude, pathname+baselen, +FNM_PATHNAME ) ==0 ) +return to_exclude; + } } } }
@@ -259,9 +283,11 @@ int excluded(struct dir_struct *dir, const char *pathname) {int pathlen =strlen (pathname);int st; - +const char *basename =strrchr (pathname,'/' ); + basename = (basename) ? basename+1 : pathname; +for (st =EXC_CMDL ; st <=EXC_FILE ; st++) { -switch (excluded_1 (pathname, pathlen, &dir->exclude_list[st])) { +switch (excluded_1 (pathname, pathlen, basename, &dir->exclude_list[st])) {case 0 :return 0 ;case 1 :
dir.h +7 -0
@@ -17,13 +17,20 @@ struct dir_entry {char name[FLEX_ARRAY ];/* more */ }; +#define EXC_FLAG_NODIR 1 +#define EXC_FLAG_NOWILDCARD 2 +#define EXC_FLAG_ENDSWITH 4 +struct exclude_list {int nr;int alloc;struct exclude {const char *pattern; +int patternlen;const char *base;int baselen; +int to_exclude; +int flags; } **excludes; };
Signature · 1 line
1.5.3.4.383.gd90a7
dir.c static int excluded_1(const char *pathname, · line 247
Quoted 2 lines
dir.c +2
-0+ }else if (x->flags &EXC_FLAG_ENDSWITH ) { +if (!strcmp (exclude +1 , pathname + pathlen -x->patternlen +1 ))
Is there some guarantee that the result of that subtraction is still within the string?
Morten
Quoted 5 lines · Morten Welinder
dir.c static int excluded_1(const char *pathname, · line 247
Quoted 2 lines
dir.c +2
-0+ }else if (x->flags &EXC_FLAG_ENDSWITH ) { +if (!strcmp (exclude +1 , pathname + pathlen -x->patternlen +1 ))Is there some guarantee that the result of that subtraction is still within the string?
Good eyes.
If pattern is "*.exe", patternlen is 5, and strcmp wants to compare 4 chars, so pathlen is better be at least that long, and we do allow that pattern to match a hidden file ".exe".
Like this?
if (x->patternlen - 1 <= pathlen &&
!strcmp(exclude + 1, pathname + pathlen - x->patternlen + 1))
return to_exclude;Quoted 14 lines · Junio C Hamano
Quoted 6 lines · Morten Welinder
Quoted 3 lines
+ } else if (
x->flags&EXC_FLAG_ENDSWITH)
{ + if (!strcmp(exclude + 1,
pathname + pathlen -x->patternlen + 1))Is there some guarantee that the result of that subtraction is still within the string?
Good eyes.
If pattern is "*.exe", patternlen is 5, and strcmp wants to compare 4 chars, so pathlen is better be at least that long, and we do allow that pattern to match a hidden file ".exe".
Quoted 5 lines
Like this?
if (x->patternlen - 1 <= pathlen && !strcmp(exclude + 1, pathname + pathlen - x->patternlen + 1)) return to_exclude;
Yes, that looks right. Thanks for catching that one.
Lars
PATCH v3 1/1 Speedup scanning for excluded files.
Try to avoid a lot of work scanning for excluded files, by caching some more information when setting up the exclusion data structure.
Speeds up 'git runstatus' on a repository containing the Qt sources by 30% and reduces the amount of instructions executed (as measured by valgrind) by a factor of 2. A 'git runstatus' on the git repository goes from 100M instructions down to about 22M.
---
Included an out of bounds check for the issue Morten found.
dir.c | 61 ++++++++++++++++++++++++++++++++++++++++++++----------------- dir.h | 7 +++++++ 2 files changed, 51 insertions(+), 17 deletions(-)
dir.c +44 -17
@@ -118,14 +118,32 @@ int match_pathspec(const char **pathspec, const char *name, int namelen, int prereturn retval; } +static int no_wildcard (const char *string) +{ +return string[strcspn (string,"*?[{" )] =='\0' ; +} +void add_exclude (const char *string,const char *base,int baselen,struct exclude_list *which) {struct exclude *x =xmalloc (sizeof (*x)); + x->to_exclude =1 ; +if (*string =='!' ) { + x->to_exclude =0 ; + string++; + } x->pattern = string; + x->patternlen =strlen (string); x->base = base; x->baselen = baselen; + x->flags =0 ; +if (!strchr (string,'/' )) + x->flags |=EXC_FLAG_NODIR ; +if (no_wildcard (string)) + x->flags |=EXC_FLAG_NOWILDCARD ; +if (*string =='*' &&no_wildcard (string+1 )) + x->flags |=EXC_FLAG_ENDSWITH ;if (which->nr == which->alloc) { which->alloc =alloc_nr (which->alloc); which->excludes = xrealloc(which->excludes,
@@ -209,7 +227,7 @@ void pop_exclude_per_directory(struct dir_struct *dir, int stk)* Return 1 for exclude, 0 for include and -1 for undecided. */ static int excluded_1 (const char *pathname, -int pathlen, +int pathlen,const char *basename,struct exclude_list *el) {int i;
@@ -218,19 +236,21 @@ static int excluded_1(const char *pathname,for (i = el->nr -1 ;0 <= i; i--) {struct exclude *x = el->excludes[i];const char *exclude = x->pattern; -int to_exclude =1 ; +int to_exclude = x->to_exclude; -if (*exclude =='!' ) { - to_exclude =0 ; - exclude++; - } - -if (!strchr (exclude,'/' )) { +if (x->flags &EXC_FLAG_NODIR ) {/* match basename */ -const char *basename =strrchr (pathname,'/' ); - basename = (basename) ? basename+1 : pathname; -if (fnmatch (exclude, basename,0 ) ==0 ) -return to_exclude; +if (x->flags &EXC_FLAG_NOWILDCARD ) { +if (!strcmp (exclude, basename)) +return to_exclude; + }else if (x->flags &EXC_FLAG_ENDSWITH ) { +if (x->patternlen -1 <= pathlen && + !strcmp (exclude +1 , pathname + pathlen - x->patternlen +1 )) +return to_exclude; + }else { +if (fnmatch (exclude, basename,0 ) ==0 ) +return to_exclude; + } }else {/* match with FNM_PATHNAME:
@@ -246,9 +266,14 @@ static int excluded_1(const char *pathname, strncmp(pathname, x->base, baselen))continue ; -if (fnmatch (exclude, pathname+baselen, -FNM_PATHNAME ) ==0 ) -return to_exclude; +if (x->flags &EXC_FLAG_NOWILDCARD ) { +if (!strcmp (exclude, pathname + baselen)) +return to_exclude; + }else { +if (fnmatch (exclude, pathname+baselen, +FNM_PATHNAME ) ==0 ) +return to_exclude; + } } } }
@@ -259,9 +284,11 @@ int excluded(struct dir_struct *dir, const char *pathname) {int pathlen =strlen (pathname);int st; - +const char *basename =strrchr (pathname,'/' ); + basename = (basename) ? basename+1 : pathname; +for (st =EXC_CMDL ; st <=EXC_FILE ; st++) { -switch (excluded_1 (pathname, pathlen, &dir->exclude_list[st])) { +switch (excluded_1 (pathname, pathlen, basename, &dir->exclude_list[st])) {case 0 :return 0 ;case 1 :
dir.h +7 -0
@@ -17,13 +17,20 @@ struct dir_entry {char name[FLEX_ARRAY ];/* more */ }; +#define EXC_FLAG_NODIR 1 +#define EXC_FLAG_NOWILDCARD 2 +#define EXC_FLAG_ENDSWITH 4 +struct exclude_list {int nr;int alloc;struct exclude {const char *pattern; +int patternlen;const char *base;int baselen; +int to_exclude; +int flags; } **excludes; };
Signature · 1 line
1.5.3.4.383.gd90a7
Thanks. This looks obviously correct and tempts me to apply directly to 'master'.
There are similar logic on the gitattributes side (attr.c) which might benefit from such an optimization as well. In the longer run, we might even want to introduce 'ignored' attribute to the gitattributes mechanism and make the unified result to supersede gitignore.