From: Bart Schaefer <schaefer@brasslantern.com>
To: zsh-workers@zsh.org
Subject: Re: Substitution ${...///} slows down when certain UTF character occurs
Date: Sun, 27 Sep 2015 09:11:21 -0700 [thread overview]
Message-ID: <150927091121.ZM25721@torch.brasslantern.com> (raw)
In-Reply-To: <CAKc7PVC_12=vVfCKGhxd9L06=+o0-r7Zti+Ag1xnv8C4tEwvmQ@mail.gmail.com>
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.
next prev parent reply other threads:[~2015-09-27 16:11 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-09-26 12:19 Sebastian Gniazdowski
2015-09-26 20:44 ` Bart Schaefer
2015-09-27 8:13 ` Sebastian Gniazdowski
2015-09-27 16:11 ` Bart Schaefer [this message]
2015-09-28 8:51 ` Peter Stephenson
2015-09-28 11:30 ` Peter Stephenson
2015-09-28 19:23 ` Peter Stephenson
2015-09-29 8:44 ` Peter Stephenson
2015-09-29 18:37 ` Peter Stephenson
2015-09-29 19:23 ` Bart Schaefer
2015-09-30 8:59 ` Peter Stephenson
2015-09-30 14:04 ` Peter Stephenson
2015-09-30 21:19 ` Bart Schaefer
2015-10-01 8:41 ` Peter Stephenson
2015-10-01 14:28 ` Heap corruption [the thread formerly known as substitution] Peter Stephenson
2015-10-01 15:07 ` Bart Schaefer
2015-10-01 15:13 ` Peter Stephenson
2015-10-03 18:59 ` Peter Stephenson
2015-10-01 13:45 ` Substitution ${...///} slows down when certain UTF character occurs Sebastian Gniazdowski
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=150927091121.ZM25721@torch.brasslantern.com \
--to=schaefer@brasslantern.com \
--cc=zsh-workers@zsh.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/zsh/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).