Re: [PATCH 8/8] wildmatch: advance faster in <asterisk> + <literal> patterns
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Dec 28, 2012, 06:24 UTC
- Message-ID
- <7vpq1uk82q.fsf@alter.siamese.dyndns.org>
- In-Reply-To
- <1356163028-29967-9-git-send-email-pclouds@gmail.com>
Nguyễn Thái Ngọc Duy <pclouds@gmail.com> writes:
Show 28 quoted lines
> compat, '*/*/*' on linux-2.6.git file list 2000 times, before:
> wildmatch 7s 985049us
> fnmatch 2s 735541us or 34.26% faster
>
> and after:
> wildmatch 4s 492549us
> fnmatch 0s 888263us or 19.77% slower
>
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
> wildmatch.c | 21 +++++++++++++++++++++
> 1 file changed, 21 insertions(+)
>
> diff --git a/wildmatch.c b/wildmatch.c
> index 3794c4d..68b02e4 100644
> --- a/wildmatch.c
> +++ b/wildmatch.c
> @@ -132,6 +132,27 @@ static int dowild(const uchar *p, const uchar *text, unsigned int flags)
> while (1) {
> if (t_ch == '\0')
> break;
> + /*
> + * Try to advance faster when an asterisk is
> + * followed by a literal. We know in this case
> + * that the the string before the literal
> + * must belong to "*".
> + */
> + if (!is_glob_special(*p)) {So far, we have looked at "*x" or "**x" in the pattern, p points at 'x' (not an asterisk), and we have "text" to match. For "text" to match this pattern, the earlier part of it that is consumed to match the asterisk must be followed by "x". "special" tells us if we are allowed to treat '/' as matching the asterisk.
> + p_ch = *p; > + if ((flags & WM_CASEFOLD) && ISUPPER(p_ch)) > + p_ch = tolower(p_ch);
That "x" in the example is picked up here and stored in "p_ch". Let's skip over "text" and find that "x" in there.
> + while ((t_ch = *text) != '\0' &&
> + (!(flags & WM_PATHNAME) || t_ch != '/')) {Why do we look at (flags & WM_PATHMAME) and not "special" here?
> + if ((flags & WM_CASEFOLD) && ISUPPER(t_ch)) > + t_ch = tolower(t_ch); > + if (t_ch == p_ch) > + break;
Found it.
> + text++; > + } > + if (t_ch != p_ch) > + return WM_NOMATCH;
If we did not find that "x", then "**x" or "*x" can never match. OK. And at this point "text" points at that "x" we found, and "p" points at "x" after the asterisk in the pattern.
Looks good so far. Thanks.
> + }
> if ((matched = dowild(p, text, flags)) != WM_NOMATCH) {
> if (!special || matched != WM_ABORT_TO_STARSTAR)
> return matched;