Re: startup time is quadratic in argc

[Chet Ramey]

On 2/3/18 8:47 PM, Ambrose Feinstein wrote:
> I was surprised to discover this:
> 
> $ time ./bash -c : $(seq 1000)
> 0.01s wall 0.00s user 0.00s system
> $ time ./bash -c : $(seq 10000)
> 0.40s wall 0.39s user 0.00s system
> $ time ./bash -c : $(seq 20000)
> 1.32s wall 1.31s user 0.01s system
> $ time ./bash -c : $(seq 40000)
> 4.57s wall 4.54s user 0.02s system
> 
> That's a fresh build of bash 4.4.18.  None of the other shells I have
> handy exhibit this (zsh, ksh, dash).
> 
> The trouble seems to be that bind_args() reverses argv, which means
> that push_args() has to insert each element from the left.

Not exactly. The loop using make_word_list builds the list in reverse
order, so REVERSE_LIST has to be called to put the arguments back in
the original order. Then you call remember_args to save $@. All that
is very cheap and fast.

The push_args call is indeed where the script spends most of its time.
Pushing 40,000 elements onto a stack, renumbering the elements each
time, is quite expensive.

I wonder if there's a lazier way to do that, while maintaining backwards
compatibility.


-- 
``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/