[patch] memoize string offset lookups

[Matthew Martin <phy1729@gmail.com>]

(Idea from 42227.)

Below patch caches the relevant information for the last getarg call in
the param struct to hopefully speedup future calls. In the best case, it
is quite successful.

% ../zsh-unpatched -fc 'a=$(repeat 50000; print -n a); time ( for (( i=1; i <= 50000; i++)); print $a[i] >/dev/null; )'
( for ((i=1; i <= 50000; i++)) do; print $a[i] > /dev/null; done; )  4.56s user 0.46s system 99% cpu 5.035 total
% ./zsh -fc 'a=$(repeat 50000; print -n a); time ( for (( i=1; i <= 50000; i++)); print $a[i] >/dev/null; )' 
( for ((i=1; i <= 50000; i++)) do; print $a[i] > /dev/null; done; )  0.68s user 0.29s system 99% cpu 0.970 total

% ../zsh-unpatched -fc 'a=$(repeat 100000; print -n a); time ( for (( i=1; i <= 100000; i++)); print $a[i] >/dev/null; )'
( for ((i=1; i <= 100000; i++)) do; print $a[i] > /dev/null; done; )  18.00s user 0.64s system 99% cpu 18.710 total
% ./zsh -fc 'a=$(repeat 100000; print -n a); time ( for (( i=1; i <= 100000; i++)); print $a[i] >/dev/null; )'
( for ((i=1; i <= 100000; i++)) do; print $a[i] > /dev/null; done; )  1.80s user 0.66s system 99% cpu 2.475 total

But in the worst case it hurts.

% ../zsh-unpatched -fc 'a=$(repeat 50000; print -n a); time ( for (( i=50000; i; i--)); print $a[i] >/dev/null; )' 
( for ((i=50000; i; i--)) do; print $a[i] > /dev/null; done; )  4.68s user 0.33s system 99% cpu 5.022 total
% ./zsh -fc 'a=$(repeat 50000; print -n a); time ( for (( i=50000; i; i--)); print $a[i] >/dev/null; )' 
( for ((i=50000; i; i--)) do; print $a[i] > /dev/null; done; )  6.88s user 0.51s system 99% cpu 7.422 tota

Any ideas if the worst case can be improved?

- Matthew Martin



diff --git a/Src/params.c b/Src/params.c
index de7730ae7..5556ca634 100644
--- a/Src/params.c
+++ b/Src/params.c
@@ -1476,11 +1476,22 @@ getarg(char **str, int *inv, Value v, int a2, zlong *w,
 	     * for Meta characters and maybe for multibyte characters.
 	     */
 	    if (r > 0) {
-		zlong nchars = r;
+		zlong nchars;
 
 		MB_METACHARINIT();
-		for (t = s; nchars && *t; nchars--)
+		if (v->pm->prev_idx > 0 && v->pm->prev_idx <= r) {
+		    t = s + v->pm->prev_off;
+		    lastcharlen = v->pm->prev_lcl;
+		    nchars = r - v->pm->prev_idx;
+		} else {
+		    t = s;
+		    nchars = r;
+		}
+		for (; nchars && *t; nchars--)
 		    t += (lastcharlen = MB_METACHARLEN(t));
+		v->pm->prev_idx = r;
+		v->pm->prev_lcl = lastcharlen;
+		v->pm->prev_off = t - s;
 		/* for consistency, keep any remainder off the end */
 		r = (zlong)(t - s) + nchars;
 		if (prevcharlen && !nchars /* ignore if off the end */)
diff --git a/Src/zsh.h b/Src/zsh.h
index 8b4898477..99508dc05 100644
--- a/Src/zsh.h
+++ b/Src/zsh.h
@@ -1820,6 +1820,9 @@ struct param {
     char *ename;		/* name of corresponding environment var */
     Param old;			/* old struct for use with local         */
     int level;			/* if (old != NULL), level of localness  */
+    zlong prev_idx;		/* previous offset in getargs() */
+    zlong prev_off;		/* previous offset into */
+    int prev_lcl;		/* previous lastcharlen */
 };
 
 /* structure stored in struct param's u.data by tied arrays */