There is a serious inefficiency in the way zsh handles wildcards

There is a serious inefficiency in the way zsh handles wildcards

[Paulo César Pereira de Andrade]

  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

Re: There is a serious inefficiency in the way zsh handles wildcards

[Peter Stephenson]

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

Re: There is a serious inefficiency in the way zsh handles wildcards

[Paulo César Pereira de Andrade]

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

Re: There is a serious inefficiency in the way zsh handles wildcards

[Peter Stephenson]

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