# [PATCH] Speedup scanning for excluded files. 8 messages from 2007-10-29 to 2007-10-30. Participants: Lars Knoll, Pierre Habouzit, Junio C Hamano, Morten Welinder. Thread: https://gitlist.dev/t/10507 ## Lars Knoll, 2007-10-29 07:45 Subject: [PATCH] Speedup scanning for excluded files. Message-ID: <200710290845.26727.lars@trolltech.com> URL: https://gitlist.dev/e/200710290845.26727.lars%40trolltech.com ``` 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(-) diff --git a/dir.c b/dir.c index 4c17d36..7bb5add 100644 --- a/dir.c +++ b/dir.c @@ -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: diff --git a/dir.h b/dir.h index a248a23..4dc3c6e 100644 --- a/dir.h +++ b/dir.h @@ -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; }; -- 1.5.3.4.383.gd90a7 ``` ## Pierre Habouzit, 2007-10-29 08:02 Subject: Re: [PATCH] Speedup scanning for excluded files. Message-ID: <20071029080234.GA22826@artemis.corp> URL: https://gitlist.dev/e/20071029080234.GA22826%40artemis.corp In-Reply-To: <200710290845.26727.lars@trolltech.com> ``` On Mon, Oct 29, 2007 at 07:45:26AM +0000, Lars Knoll wrote: > +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. > +} > + > 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. -- ·O· Pierre Habouzit ··O madcoder@debian.org OOO http://www.madism.org ``` ## Lars Knoll, 2007-10-29 08:59 Subject: Re: [PATCH] Speedup scanning for excluded files. Message-ID: <200710290959.32538.lars@trolltech.com> URL: https://gitlist.dev/e/200710290959.32538.lars%40trolltech.com In-Reply-To: <20071029080234.GA22826@artemis.corp> ``` >From 51b364c9c87bec89556a2089cc5363c588ea2ff5 Mon Sep 17 00:00:00 2001 From: Lars Knoll 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(-) diff --git a/dir.c b/dir.c index 4c17d36..f4e130c 100644 --- a/dir.c +++ b/dir.c @@ -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 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: diff --git a/dir.h b/dir.h index a248a23..3ce8dbe 100644 --- a/dir.h +++ b/dir.h @@ -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; }; -- 1.5.3.4.383.gd90a7 ``` ## Junio C Hamano, 2007-10-29 22:17 Subject: Re: [PATCH] Speedup scanning for excluded files. Message-ID: <7v8x5ltvjj.fsf@gitster.siamese.dyndns.org> URL: https://gitlist.dev/e/7v8x5ltvjj.fsf%40gitster.siamese.dyndns.org In-Reply-To: <200710290959.32538.lars@trolltech.com> ``` 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. ``` ## Morten Welinder, 2007-10-29 22:59 Subject: Re: [PATCH] Speedup scanning for excluded files. Message-ID: <118833cc0710291559kbd874a8o8111b9495090ef27@mail.gmail.com> URL: https://gitlist.dev/e/118833cc0710291559kbd874a8o8111b9495090ef27%40mail.gmail.com In-Reply-To: <200710290959.32538.lars@trolltech.com> ``` > + } 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 ``` ## Junio C Hamano, 2007-10-30 00:00 Subject: Re: [PATCH] Speedup scanning for excluded files. Message-ID: <7vzly1sc7p.fsf@gitster.siamese.dyndns.org> URL: https://gitlist.dev/e/7vzly1sc7p.fsf%40gitster.siamese.dyndns.org In-Reply-To: <118833cc0710291559kbd874a8o8111b9495090ef27@mail.gmail.com> ``` "Morten Welinder" writes: >> + } 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; ``` ## Lars Knoll, 2007-10-30 07:28 Subject: Re: [PATCH] Speedup scanning for excluded files. Message-ID: <200710300828.49840.lars@trolltech.com> URL: https://gitlist.dev/e/200710300828.49840.lars%40trolltech.com In-Reply-To: <7vzly1sc7p.fsf@gitster.siamese.dyndns.org> ``` On Tuesday 30 October 2007, Junio C Hamano wrote: > "Morten Welinder" writes: > >> + } 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; Yes, that looks right. Thanks for catching that one. Lars ``` ## Lars Knoll, 2007-10-30 07:46 Subject: [PATCH v3] Speedup scanning for excluded files. Message-ID: <200710300846.02010.lars@trolltech.com> URL: https://gitlist.dev/e/200710300846.02010.lars%40trolltech.com In-Reply-To: <200710300828.49840.lars@trolltech.com> ``` 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. Signed-off-by: Lars Knoll --- Included an out of bounds check for the issue Morten found. dir.c | 61 ++++++++++++++++++++++++++++++++++++++++++++----------------- dir.h | 7 +++++++ 2 files changed, 51 insertions(+), 17 deletions(-) diff --git a/dir.c b/dir.c index 4c17d36..b3d7462 100644 --- a/dir.c +++ b/dir.c @@ -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 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: diff --git a/dir.h b/dir.h index a248a23..3ce8dbe 100644 --- a/dir.h +++ b/dir.h @@ -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; }; -- 1.5.3.4.383.gd90a7 ```