From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <zsh-workers-return-36660-mason-zsh=primenet.com.au@zsh.org>
Received: (qmail 17657 invoked by alias); 27 Sep 2015 16:11:27 -0000
Mailing-List: contact zsh-workers-help@zsh.org; run by ezmlm
Precedence: bulk
X-No-Archive: yes
List-Id: Zsh Workers List <zsh-workers.zsh.org>
List-Post: <mailto:zsh-workers@zsh.org>
List-Help: <mailto:zsh-workers-help@zsh.org>
X-Seq: 36660
Received: (qmail 20510 invoked from network); 27 Sep 2015 16:11:26 -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=PJ+Q56DiniIilQizchnsUthNMn3BPk8DJB6aRW/ZhBc=;
        b=A7ssDGS450YW11tr162wdjCZyvp/vAyZrrjUmaPAb8uIdiiUOcq0f1K3FY86baCSmt
         TYHRrChwxmtRDDxHZlUrXnyZMDmPwFHo32r+vDTQ5qZX9QF/pC9GNdVpt7jtqw0ajGo4
         BVrn725mLGfpw+gmg36Cw9oPtwpCils1y5B8Tvj56J6iZHzW0sVhJFaJTKZEYsk2ZXw+
         f1tK+xsP+z2ecTvJZLytAZ5hjQP75zNEQARvbPGllrUWmpFmN4pVA1mXKcUi1EbDH9ZA
         UvdA7DeUbqCvwMlnOxlmludDKuq7R3QnFpjnSvDmCqDckGHSdFsrJjDa/wjHQxpW8tTP
         iNMg==
X-Gm-Message-State: ALoCoQnGJ5AzqKmWMjUh8ruQD3Y8ZC/fIMmE5CPK6+Lczyg3RgTFEsDPqEIBC7gG4dedIsL3lygU
X-Received: by 10.202.44.206 with SMTP id s197mr8027717ois.11.1443370284273;
        Sun, 27 Sep 2015 09:11:24 -0700 (PDT)
From: Bart Schaefer <schaefer@brasslantern.com>
Message-Id: <150927091121.ZM25721@torch.brasslantern.com>
Date: Sun, 27 Sep 2015 09:11:21 -0700
In-Reply-To: <CAKc7PVC_12=vVfCKGhxd9L06=+o0-r7Zti+Ag1xnv8C4tEwvmQ@mail.gmail.com>
Comments: In reply to Sebastian Gniazdowski <sgniazdowski@gmail.com>
        "Re: Substitution ${...///} slows down when certain UTF character occurs" (Sep 27, 10:13am)
References: <CAKc7PVBuCuLux8WhBORuYo_vQUQ18OP-XMQXWdYkL84pFLt+LQ@mail.gmail.com> 
	<150926134410.ZM17546@torch.brasslantern.com> 
	<CAKc7PVC_12=vVfCKGhxd9L06=+o0-r7Zti+Ag1xnv8C4tEwvmQ@mail.gmail.com>
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 27, 10:13am, Sebastian Gniazdowski wrote:
} Subject: Re: Substitution ${...///} slows down when certain UTF character 
}
} On 26 September 2015 at 22:44, Bart Schaefer <schaefer@brasslantern.com> wrote:
} > 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.
} 
} That's a huge plus that it's still instant fast for strings of that
} length if there is no unlucky unicode character.

It'll get worse if there are partial matches, e.g., if you had 30000
repetitions of "wfei" and scanned for "wfeiwj" there'd be a whole lot
of backtracking.  There are no "w" anywhere in your sample $str so
each of the comparisons is only one equality test.

Still I think the biggest issue is that unmetafication happening too
low down.  Since pattry*() is being called repeatedly with the same two
first arguments (prog and string) it might be possible to cache the
unmetafied string after the first call.