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

[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).

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