Path: csiph.com!xmission!news.snarked.org!news.linkpendium.com!news.linkpendium.com!panix!usenet.stanford.edu!not-for-mail
From: Chet Ramey <chet.ramey@case.edu>
Newsgroups: gnu.bash.bug
Subject: Re: Combination of "eval set -- ..." and $() command substitution is slow
Date: Mon, 15 Jul 2019 11:56:59 -0400
Lines: 82
Approved: bug-bash@gnu.org
Message-ID: <mailman.1431.1563206228.2688.bug-bash@gnu.org>
References: <bcd08f6c-1c13-0eb4-92b2-4e904b19a0ce@e-nautia.com> <7ba227f9-ed87-8224-6f07-fd444488d472@case.edu> <a4fe11cc-d0be-3cf3-e6bf-721c1d1c986e@e-nautia.com> <7aa96e7f-696c-b9e4-21c0-cde4e16f661a@case.edu>
Reply-To: chet.ramey@case.edu
NNTP-Posting-Host: lists.gnu.org
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Cc: chet.ramey@case.edu
To: astian <astian@e-nautia.com>, bug-bash@gnu.org
Envelope-to: bug-bash@gnu.org
Openpgp: preference=signencrypt
Autocrypt: addr=chet.ramey@case.edu; prefer-encrypt=mutual; keydata= xsDiBEEOsGwRBACFa0A1oa71HSZLWxAx0svXzhOZNQZOzqHmSuGOG92jIpQpr8DpvgRh40Yp AwdcXb8QG1J5yGAKeevNE1zCFaA725vGSdHUyypHouV0xoWwukYO6qlyyX+2BZU+okBUqoWQ koWxiYaCSfzB2Ln7pmdys1fJhcgBKf3VjWCjd2XJTwCgoFJOwyBFJdugjfwjSoRSwDOIMf0D /iQKqlWhIO1LGpMrGX0il0/x4zj0NAcSwAk7LaPZbN4UPjn5pqGEHBlf1+xDDQCkAoZ/VqES GZragl4VqJfxBr29Ag0UDvNbUbXoxQsARdero1M8GiAIRc50hj7HXFoERwenbNDJL86GPLAQ OTGOCa4W2o29nFfFjQrsrrYHzVtyA/9oyKvTeEMJ7NA3VJdWcmn7gOu0FxEmSNhSoV1T4vP2 1Wf7f5niCCRKQLNyUy0wEApQi4tSysdz+AbgAc0b/bHYVzIf2uO2lIEZQNNt+3g2bmXgloWm W5fsm/di50Gm1l1Na63d3RZ00SeFQos6WEwLUHEB0yp6KXluXLLIZitEJM0gQ2hldCBSYW1l eSA8Y2hldC5yYW1leUBjYXNlLmVkdT7CYQQTEQIAIQIbAwYLCQgHAwIDFQIDAxYCAQIeAQIX gAUCRX3FIgIZAQAKCRC7WGnwZOp0q069AKCNDRn+zzN/AHbaynls/Lvq1kH/RQCgkLvF8bDs maUHSxSIPqzlGuKWDxbOwE0EQQ6wbxAEAJCukwDigRDPhAuI+lf+6P64lWanIFOXIndqhvU1 3cDbQ/Wt5LwPzm2QTvd7F+fcHOgZ8KOFScbDpjJaRqwIybMTcIN0B2pBLX/C10W1aY+cUrXZ gXUGVISEMmpaP9v02auToo7XXVEHC+XLO9IU7/xaU98FL69l6/K4xeNSBRM/AAMHA/wNAmRB pcyK0+VggZ5esQaIP/LyolAm2qwcmrd3dZi+g24s7yjV0EUwvRP7xHRDQFgkAo6++QbuecU/ J90lxrVnQwucZmfz9zgWDkT/MpfB/CNRSKLFjhYq2yHmHWT6vEjw9Ry/hF6Pc0oh1a62USdf aKAiim0nVxxQmPmiRvtCmcJJBBgRAgAJBQJBDrBvAhsMAAoJELtYafBk6nSr43AAn2ZZFQg8 Gs/zUzvXMt7evaFqVTzcAJ0cHtKpP1i/4H4R9+OsYeQdxxWxTQ==
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:60.0) Gecko/20100101 Thunderbird/60.8.0
In-Reply-To: <a4fe11cc-d0be-3cf3-e6bf-721c1d1c986e@e-nautia.com>
Content-Language: en-US
Precedence: list
Xref: csiph.com gnu.bash.bug:15172

On 7/13/19 1:36 PM, astian wrote:

> Chet Ramey:
>>>     - $() seems generally slightly slower than ``, but becomes pathologically
>>>       so when preceded with "eval set -- ...".
>>
>> It is slightly slower -- POSIX requires that the shell parse the contents
>> of $(...) to determine that it's a valid script as part of finding the
>> closing `)'. The rules for finding the closing "`" don't have that
>> requirement.
>>
>>>     - "eval set -- ..." itself doesn't seem slow at all, but obviously it has
>>>       side-effects not captured by the "time" measurement tool.
>>
>> What happens is you end up with a 4900-character command string that you
>> have to parse multiple times. But that's not the worst of it.
> 
> Since this statement ought to run exactly once, naïvely I would expect that by
> "multiple times" you really mean at most "twice": once for the top-level
> script, another time "inside" the eval "sub-script".

I meant scan, as part of set_line_mbstate(), examining the contents. One
side effect of running the parser so many times (the command substitutions)
is that it saves and restores the previous value of the shell's input line.
Using `eval' sets that to the 4900-character string. Part of restoring the
old value of the line was running through it to set the multibyte state of
the characters, so you run through set_line_mbstate on the 4900-character
string every time you run the parser for the $(...) command substitution.

> 
>> The gprof output provides a clue.
>>
>>
>>>       case 1 1 0 (pathological):
>>>        %   cumulative   self              self     total
>>>       time   seconds   seconds    calls  us/call  us/call  name
>>>       38.89      0.21     0.21    28890     7.27     7.27  set_line_mbstate
>>
>> set_line_mbstate() runs through each command line before parsing, creating
>> a bitmap that indicates whether each element is a single-byte character or
>> part of a multi-byte character. The scanner uses this to determine whether
>> a shell metacharacter should act as a delimiter or get skipped over as part
>> of a multibyte character. For a single run with args `1 1 0', it gets
>> called around 7300 times, with around 2400 of them for the 4900-character
>> string with all the arguments.
>>
>> When you're in a multibyte locale (en_US.UTF-8 is one such), each one of
>> those characters requires a call to mbrlen/mbrtowc. So that ends up being
>> 2400 * 4900 calls to mbrlen.
> 
> I am indeed using an UTF-8 locale, but I tested also with export LC_ALL=C and the
> behaviour did not change, I should have mentioned that.

Once you take care of that bottleneck, it's the parser.

>> There is something happening here -- there's no way there should be that
>> many calls to set_line_mbstate(),
> 
> Notice that there are almost as many calls (only 2 fewer) in case "0 1 0" (in
> which eval is not used) yet in that case the performance is not harmed.

Yes, but the string it runs through is literally a thousand times shorter.

In any event, it's the parser. Yacc-based parsers are fairly slow, and
running yyparse 2400 times (1200 to find the closing paren while scanning
the double-quoted string, then 1200 more times (!) to find it again while
doing the command substitution -- I should do something about that)
accounts for almost all of the performance difference. It just about
doubles the number of malloc/free calls, for example.

On a version of your script where I ran `f' in a loop 10 times to
exaggerate performance issues, running the parser for the $(...) command
substitution accounted for around 35% of the program's running time,
according to gprof.


Chet
-- 
``The lyf so short, the craft so long to lerne.'' - Chaucer
		 ``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, UTech, CWRU    chet@case.edu    http://tiswww.cwru.edu/~chet/