From: "Paulo César Pereira de Andrade" <paulo.cesar.pereira.de.andrade@gmail.com>
To: Peter Stephenson <p.stephenson@samsung.com>
Cc: zsh-users@zsh.org
Subject: Re: There is a serious inefficiency in the way zsh handles wildcards
Date: Thu, 11 Sep 2014 10:54:23 -0300 [thread overview]
Message-ID: <CAHAq8pGY7SyXQfJPzty+th-8Dd1Y9tbWLUPubRMe8_CW+5m2Wg@mail.gmail.com> (raw)
In-Reply-To: <20140908150135.6bbf5356@pwslap01u.europe.root.pri>
2014-09-08 11:01 GMT-03:00 Peter Stephenson <p.stephenson@samsung.com>:
> On Mon, 08 Sep 2014 10:27:48 -0300
> Paulo César Pereira de Andrade
> <paulo.cesar.pereira.de.andrade@gmail.com> wrote:
>> ---%<---
>> diff -up zsh-5.0.2/Src/pattern.c.orig zsh-5.0.2/Src/pattern.c
>> --- zsh-5.0.2/Src/pattern.c.orig 2014-09-03 12:21:44.673792750 -0300
>> +++ zsh-5.0.2/Src/pattern.c 2014-09-03 12:22:28.069303587 -0300
>> @@ -2911,6 +2911,10 @@ patmatch(Upat prog)
>> break;
>> case P_STAR:
>> /* Handle specially for speed, although really P_ONEHASH+P_ANY */
>> + while (P_OP(next) == P_STAR) {
>> + scan = next;
>> + next = PATNEXT(scan);
>> + }
>> case P_ONEHASH:
>> case P_TWOHASH:
>> /*
>> ---%<---
>>
>> Do you believe this patch is OK?
>
> In other words, if we're handling a "*" down in the pattern code --- as
> you say, we've already decided higher up if it's the special ** or ***
> for directories so there's no problem with those --- we can skip any
> immediately following *s because they don't add anything but will provoke
> horrifically inefficient recursion. (That's because when backtracking
> we keep trying each separate * from each position --- the number of
> possibilities is humongous.)
>
> Yes, that sounds entirely reasonable. It doesn't patch cleanly any
> more; I think the following works and I've added a new test (all tests
> pass).
Just as a note, I noticed that the huge slowdown usually would
only happen if there was a match, if there was nothing matching
/tmp/*.* (usually a directory or a symlink to one) handling of the
pattern would not cause noticeable delay.
> diff --git a/Src/pattern.c b/Src/pattern.c
> index 94a299e..adc73c1 100644
> --- a/Src/pattern.c
> +++ b/Src/pattern.c
> @@ -3012,6 +3012,16 @@ patmatch(Upat prog)
> break;
> case P_STAR:
> /* Handle specially for speed, although really P_ONEHASH+P_ANY */
> + while (P_OP(next) == P_STAR) {
> + /*
> + * If there's another * following we can optimise it
> + * out. Chains of *'s can give pathologically bad
> + * performance.
> + */
> + scan = next;
> + next = PATNEXT(scan);
> + }
> + /*FALLTHROUGH*/
> case P_ONEHASH:
> case P_TWOHASH:
> /*
> diff --git a/Test/D02glob.ztst b/Test/D02glob.ztst
> index 4697ca4..217ce7c 100644
> --- a/Test/D02glob.ztst
> +++ b/Test/D02glob.ztst
> @@ -565,3 +565,10 @@
> print $match[1]
> 0:(#q) is ignored completely in conditional pattern matching
> >fichier
> +
> +# The following should not cause excessive slowdown.
> + print glob.tmp/*.*
> + print glob.tmp/**************************.*************************
> +0:Optimisation to squeeze multiple *'s used as ordinary glob wildcards.
> +>glob.tmp/ra=1.0_et=3.5
> +>glob.tmp/ra=1.0_et=3.5
>
>
> Thanks.
> pws
Thanks for applying the patch!
Paulo
next prev parent reply other threads:[~2014-09-11 13:54 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-09-08 13:27 Paulo César Pereira de Andrade
2014-09-08 14:01 ` Peter Stephenson
2014-09-11 13:54 ` Paulo César Pereira de Andrade [this message]
2014-09-11 14:02 ` Peter Stephenson
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAHAq8pGY7SyXQfJPzty+th-8Dd1Y9tbWLUPubRMe8_CW+5m2Wg@mail.gmail.com \
--to=paulo.cesar.pereira.de.andrade@gmail.com \
--cc=p.stephenson@samsung.com \
--cc=zsh-users@zsh.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/zsh/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).