From: Jun T <takimoto-j@kba.biglobe.ne.jp>
To: zsh-workers@zsh.org
Subject: Re: [BUG] Glob handling is brittle
Date: Tue, 27 Nov 2018 21:14:20 +0900 [thread overview]
Message-ID: <942D7657-1371-4A04-B2E7-1CBFE9DC0966@kba.biglobe.ne.jp> (raw)
In-Reply-To: <4a07ef77-de18-8966-5f3e-bd544aaaae3f@inlv.org>
> 2018/11/26 14:38, Martijn Dekker <martijn@inlv.org> wrote:
>
> The script below reliably makes zsh hang.
(snip)
> case '\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\' in
> ( *\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\\
> *\\*\\*\\*\\*\\*\\*\\*\\*\\*\\* )
> echo ok ;;
> esac
zsh is not hanging; it is just very slow.
On my Mac it takes about 130 sec to print 'ok', and it uses up almost
all the memory (16GB) in my Mac (so macOS starts the memory compression.
If one more \\ were added swap would start, I guess).
We can use any other character than '\' to reproduce the problem. In the
script below, str='aaa...a' is compared with pat='a*a*a*...*a*' while
increasing the number of 'a's in str:
zmodload zsh/datetime
str=''
pat='*'
repeat 30; do
str=$str'a'
pat=$pat'a*'
t0=$EPOCHREALTIME
[[ $str = ${~pat} ]] && \
printf '%2d: %9.4f\n' ${#str} $(( $EPOCHREALTIME - $t0 ))
done
The output looks like:
1: 0.0000
(snip)
11: 0.0001
12: 0.0001
13: 0.0002
14: 0.0005
15: 0.0010
16: 0.0019
17: 0.0039
18: 0.0078
19: 0.0155
20: 0.0306
21: 0.0621
22: 0.1219
23: 0.2459
24: 0.4879
25: 0.9834
26: 1.9586
27: 3.9203
28: 7.8332
29: 15.6636
30: 31.3442
So the cpu time is proportional to 2**${#str}.
I don't know whether this can be 'fixed' easily.
next prev parent reply other threads:[~2018-11-27 12:51 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-11-26 5:38 Martijn Dekker
2018-11-27 12:14 ` Jun T [this message]
2018-11-27 15:08 ` Peter Stephenson
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=942D7657-1371-4A04-B2E7-1CBFE9DC0966@kba.biglobe.ne.jp \
--to=takimoto-j@kba.biglobe.ne.jp \
--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).