* There is a serious inefficiency in the way zsh handles wildcards
@ 2014-09-08 13:27 Paulo César Pereira de Andrade
2014-09-08 14:01 ` Peter Stephenson
0 siblings, 1 reply; 4+ messages in thread
From: Paulo César Pereira de Andrade @ 2014-09-08 13:27 UTC (permalink / raw)
To: zsh-users
Hello,
I had a bug report described as @subject. The test case was described as:
---%<---
$ time zsh -c "ls /tmp/*****.*****"
real 0m0.006s
user 0m0.004s
sys 0m0.002s
$ time zsh -c "ls /tmp/******.******"
real 0m0.032s
user 0m0.031s
sys 0m0.001s
$ time zsh -c "ls /tmp/*******.*******"
real 0m0.127s
user 0m0.125s
sys 0m0.003s
$ time zsh -c "ls /tmp/********.********"
real 0m0.485s
user 0m0.484s
sys 0m0.002s
$ time zsh -c "ls /tmp/**********.**********"
real 0m5.933s
user 0m5.937s
sys 0m0.002s
---%<---
I did look a bit in zsh sources, and wrote this patch, that should not interfere
on the special handling of **/ and ***/, and just avoid the very deep recursions
that consume a huge amount of cpu, and apparently yield nothing.
---%<---
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?
The user reports those patterns are generated by one of their scripts.
Thanks,
Paulo
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: There is a serious inefficiency in the way zsh handles wildcards
2014-09-08 13:27 There is a serious inefficiency in the way zsh handles wildcards Paulo César Pereira de Andrade
@ 2014-09-08 14:01 ` Peter Stephenson
2014-09-11 13:54 ` Paulo César Pereira de Andrade
0 siblings, 1 reply; 4+ messages in thread
From: Peter Stephenson @ 2014-09-08 14:01 UTC (permalink / raw)
To: Paulo César Pereira de Andrade, zsh-users
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).
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: There is a serious inefficiency in the way zsh handles wildcards
2014-09-08 14:01 ` Peter Stephenson
@ 2014-09-11 13:54 ` Paulo César Pereira de Andrade
2014-09-11 14:02 ` Peter Stephenson
0 siblings, 1 reply; 4+ messages in thread
From: Paulo César Pereira de Andrade @ 2014-09-11 13:54 UTC (permalink / raw)
To: Peter Stephenson; +Cc: zsh-users
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: There is a serious inefficiency in the way zsh handles wildcards
2014-09-11 13:54 ` Paulo César Pereira de Andrade
@ 2014-09-11 14:02 ` Peter Stephenson
0 siblings, 0 replies; 4+ messages in thread
From: Peter Stephenson @ 2014-09-11 14:02 UTC (permalink / raw)
To: zsh-users
On Thu, 11 Sep 2014 10:54:23 -0300
Paulo César Pereira de Andrade
<paulo.cesar.pereira.de.andrade@gmail.com> wrote:
> 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.
I've a vague feeling I optimised it some time ago so that if there was a
string component to the pattern it searched for that to check it was
worth doing all the hairy pattern stuff, but I may be misremembering
and I'm too lazy to check...
pws
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2014-09-11 14:12 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-09-08 13:27 There is a serious inefficiency in the way zsh handles wildcards Paulo César Pereira de Andrade
2014-09-08 14:01 ` Peter Stephenson
2014-09-11 13:54 ` Paulo César Pereira de Andrade
2014-09-11 14:02 ` Peter Stephenson
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).