From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 22616 invoked by alias); 14 Mar 2018 02:43:58 -0000 Mailing-List: contact zsh-workers-help@zsh.org; run by ezmlm Precedence: bulk X-No-Archive: yes List-Id: Zsh Workers List List-Post: List-Help: List-Unsubscribe: X-Seq: 42457 Received: (qmail 20938 invoked by uid 1010); 14 Mar 2018 02:43:57 -0000 X-Qmail-Scanner-Diagnostics: from mail-ot0-f176.google.com by f.primenet.com.au (envelope-from , uid 7791) with qmail-scanner-2.11 (clamdscan: 0.99.2/21882. spamassassin: 3.4.1. Clear:RC:0(74.125.82.176):SA:0(-1.7/5.0):. Processed in 2.108682 secs); 14 Mar 2018 02:43:57 -0000 X-Spam-Checker-Version: SpamAssassin 3.4.1 (2015-04-28) on f.primenet.com.au X-Spam-Level: X-Spam-Status: No, score=-1.7 required=5.0 tests=BAYES_00, FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL,SPF_PASS,T_DKIM_INVALID,UNPARSEABLE_RELAY autolearn=no autolearn_force=no version=3.4.1 X-Envelope-From: phy1729@gmail.com X-Qmail-Scanner-Mime-Attachments: | X-Qmail-Scanner-Zip-Files: | DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:subject:message-id:mail-followup-to:mime-version :content-disposition:user-agent; bh=qddU8p747V7wTBRSErlptfhm54X6FTFkP/Jfv/vf9z4=; b=cjGyGGUEh5W3RH9SLB2h5Vo9aeRasIqxbo4+BUiaBv5x0Z1Wzdc2d/NvJeaWjUTpVc ovG/bC9SGQPXMJZ0r9V9br/ZoW7auv3QBxi1Ht2E77cjNoH0ALRKLK+8jQH4UwKubGAb /wMK7+OTvkP1AJb1o/AKuU3Wl5ytX8LQNIkanJLGMizg9HJyEUk9Nm3mbeL4sR1ldSJp XjJSRn5UxU62NOBnP56e1I9ZewCKv0Uy78Q54UoY01ga7HmciNxcyO17f0inFiTz1ikv beh0nJx8YfsPUfabY8zJjJN4ssbb1nsSvUSrr0+H2ehvgNuuY8DT83SnMD49wZb0oZex 1Ctw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:subject:message-id:mail-followup-to :mime-version:content-disposition:user-agent; bh=qddU8p747V7wTBRSErlptfhm54X6FTFkP/Jfv/vf9z4=; b=RMOQmY682ZIGYXRUHjEQGNaj/5r+6e/VcFrqPE4aZgL7QqGPXPQbDx4mdnmClWYVyk OHcH2BvfiA16MhSmvwaGKW6NnM8v08q6Ic8eSjKCJbdLECvNI6BKrUWdCsDXDDRFm8q8 WnFqpNOWwEptEO03Ak2A1sFxdVWbCvxVhUlV2QpxeYxJNtfe2IxmvadHvJmA9cqW79Tp RznXrzVOQlKBjphjrLSVbpSPPcmAufWeUIed5M6sJW9yQznJCtcLWySCghrXRCkcLHKZ J6Nc8qpRf/DFgZIcfDfyoPo1x+GIDmfpjXqOMn3STSVg0yPV8S7wBjhMRmDL9oEYJrIz m0kQ== X-Gm-Message-State: AElRT7EvcOa3mB5lOKc2IgIQecrdgJ88JlQkEZJUottX5UReQFHXFYE5 lgurGZ2BSYia5opjM/slie0A0eVM X-Google-Smtp-Source: AG47ELsDx1cmQ8Hm4g+5M9YTLeae6stY01wUHiF2qHQk1WGZsRCrRXr4PCCgSuxtXmHqh2NC15VAlg== X-Received: by 10.157.61.99 with SMTP id a90mr1848058otc.35.1520995432301; Tue, 13 Mar 2018 19:43:52 -0700 (PDT) Date: Tue, 13 Mar 2018 21:43:49 -0500 From: Matthew Martin To: zsh-workers@zsh.org Subject: [patch] memoize string offset lookups Message-ID: <20180314024348.GA51231@CptOrmolo.darkstar> Mail-Followup-To: zsh-workers@zsh.org MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.9.3 (2018-01-21) (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 */