From: Bart Schaefer <schaefer@brasslantern.com>
To: zsh-workers@zsh.org
Subject: Re: Substitution ${...///} slows down when certain UTF character occurs
Date: Sat, 26 Sep 2015 13:44:10 -0700 [thread overview]
Message-ID: <150926134410.ZM17546@torch.brasslantern.com> (raw)
In-Reply-To: <CAKc7PVBuCuLux8WhBORuYo_vQUQ18OP-XMQXWdYkL84pFLt+LQ@mail.gmail.com>
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.
next prev parent reply other threads:[~2015-09-26 20:44 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 [this message]
2015-09-27 8:13 ` Sebastian Gniazdowski
2015-09-27 16:11 ` Bart Schaefer
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=150926134410.ZM17546@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).