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

[Paulo César Pereira de Andrade <paulo.cesar.pereira.de.andrade@xxxxxxxxx>]

2014-09-08 11:01 GMT-03:00 Peter Stephenson <p.stephenson@xxxxxxxxxxx>:
> On Mon, 08 Sep 2014 10:27:48 -0300
> Paulo César Pereira de Andrade
> <paulo.cesar.pereira.de.andrade@xxxxxxxxx> 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