Re: Combination of "eval set -- ..." and $() command substitution is slow

[Chet Ramey]

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/