From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 9404 invoked by alias); 26 Sep 2015 20:44:17 -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: X-Seq: 36647 Received: (qmail 10565 invoked from network); 26 Sep 2015 20:44:16 -0000 X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on f.primenet.com.au X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.0 X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:message-id:date:in-reply-to:comments :references:to:subject:mime-version:content-type; bh=IhwIx8NoIAtg2Q56RlkU8jbMGjlZccujadQ12lhVrJU=; b=QHx+3ZgHmMnhqb6FlQGFPbnaGAUPMf8BC4V7ixGsiabzJK8GaDmjMsG5rSOHzHRnTw D+ZimnWxTy3rOvqSbiCLcg4PCLryov0kaQ7bbWW923IuJzG+DOjjEbmKFOn4pdySiT1n zDO6xUa55T2vDMHGuhnd8K0d8kamD+zfdX+Mrkc/7Q5tESay7Ij9yXQ2Q1HPbG93xtMQ 72vKAVJBkx3wvrB8AWNyYHy/FgxxHMTvDD45pixqhx25hpR5wG9BdNri9ExnQBkuEQTL AbH7NKv13TqzoZY6qAeF5RTST+1To1Lk7dhVtHHOT6YoQ6PGYZjeulkR3XrVtpBysw9R /qXg== X-Gm-Message-State: ALoCoQnCZy/yLoXM5bOBsoeQe5f2p70Hlp1YqU9DL0QnRMdIb3i2RfyvuTBsVPfIhd+Re956WiwH X-Received: by 10.60.42.197 with SMTP id q5mr6431193oel.52.1443300253877; Sat, 26 Sep 2015 13:44:13 -0700 (PDT) From: Bart Schaefer Message-Id: <150926134410.ZM17546@torch.brasslantern.com> Date: Sat, 26 Sep 2015 13:44:10 -0700 In-Reply-To: Comments: In reply to Sebastian Gniazdowski "Substitution ${...///} slows down when certain UTF character occurs" (Sep 26, 2:19pm) References: X-Mailer: OpenZMail Classic (0.9.2 24April2005) To: zsh-workers@zsh.org Subject: Re: Substitution ${...///} slows down when certain UTF character occurs MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii On Sep 26, 2:19pm, Sebastian Gniazdowski wrote: } } I attach a script that does ${...///} substitution. I worry that the attachement hasn't come through correctly? When I unpack the base64 into text, I get (in part) str="c4d5148ca6 ce3a2d24203abfb385 30f5fe85434ae ... 5d468f6" Is the value of $str supposed to look like that? So the pattern in the ${str//...} replacement never matches? } It is very slow for some chars and very fast for others. How to explain } and hopefully fix this? Each time pattryrefs() fails to find a match, it increments the area to be searched by one character and then tries the entire pattern match again. So for a 120000-character string, it's doing a non- matching search 120000 times. I rewrote your test to use "float SECONDS" + "print $SECONDS" instead of forking off subshells for "time" and to use loops so I didn't have to comment things in and out. Observations: 1. It's only fast for the Yen symbol, which is the only one that does not have a byte with the high-order bit set. This case is avoiding this block in pattern.c: 2124 if (!(patflags & (PAT_PURES|PAT_ANY)) 2125 && (needfullpath || unmetalen != stringlen)) { 2126 /* 2127 * We need to copy if we need to prepend the path so far 2128 * (in which case we copy both chunks), or if we have 2129 * Meta characters. 2130 */ I.e., unmetalen == stringlen, so we do not allocate and copy the entire 120k bytes of $str for each pattern comparison. This means in the case where there are high-order characters, the search algorithm becomes O(N)^2 rather than O(N). 2. It's consistently slower the longer the prefix string before the high-order byte becomes. I believe this means that once the search loop has "gotten past" the high-order byte, it stops doing the O(N)^2 copy-and-scan and drops in to the O(N) scan of the original input string. But I haven't traced it down to exactly where that happens. The nested loops around line 2908 in glob.c, I suspect. So this could be sped up by factoring out the unmetafication, but it would require some pretty serious reworking of the relationship between pattrylen() / pattryrefs() and their callers.