Re: Bash performance when declaring variables

[Chet Ramey]

On 4/16/15 12:48 PM, Eduardo A. Bustamante López wrote:
> On Thu, Apr 16, 2015 at 11:07:34AM -0400, Chet Ramey wrote:
> [...]
>> I knew that rang a bell somewhere.  mt_hash is a function in the bash
>> malloc library that keeps track of all allocations and deallocations in
>> a table.  It's part of the debugging that is enabled when you build from
>> the devel code.  It's been well-known for a long time that the debugging
>> code in malloc slows bash down considerably; that's why it's not enabled
>> as part of bash releases.
> 
> Actually, this is the post that motivated me to look into this:
> (yes, the conclusion is idiotic, but I guess the rest of the post is pretty
> okay).

I don't know, he kind of lost me with the first sentence.  Then again, the
Internet has always been the home of hyperbole.

> http://spencertipping.com/posts/2013.0814.bash-is-irrecoverably-broken.html
> 
> Now, there is some truth to what he says:
> 
> dualbus@yaqui ...src/gnu/bash % time ./bash -c 'i=0; while ((i++<1000)); do 
> declare a$RANDOM$RANDOM=1; done' 
> ./bash -c 'i=0; while ((i++<1000)); do declare a$RANDOM$RANDOM=1; done'  
> 0.01s user 0.06s system 93% cpu 0.077 total
> dualbus@yaqui ...src/gnu/bash % time ./bash -c 'i=0; while ((i++<10000)); do 
> declare a$RANDOM$RANDOM=1; done'
> ./bash -c 'i=0; while ((i++<10000)); do declare a$RANDOM$RANDOM=1; done'  
> 0.16s user 0.48s system 98% cpu 0.643 total
> dualbus@yaqui ...src/gnu/bash % time ./bash -c 'i=0; while ((i++<100000)); do 
> declare a$RANDOM$RANDOM=1; done'
> ./bash -c 'i=0; while ((i++<100000)); do declare a$RANDOM$RANDOM=1; done'  
> 15.44s user 6.51s system 99% cpu 21.959 total

Sure, some.  He apparently doesn't think that any hashing technique other
than open addressing is legitimate hashing, and that kind of diminishes his
arguments.

He's correct about the hashing implementation: bash hash tables, which are
used all over the place for variable and other storage, use separate
chaining to do collision resolution.  That means you're always going to
have some cost associated with searching the linked list attached to each
hash bucket.

The bash-4.3 implementation uses 64 hash buckets, and I changed that to 128
a while back in the devel branch.  That seems to be the right balance of
space and lookup speed for the majority of bash scripts.  I don't think it
would be unreasonable to double that to something like 256 hash buckets,
and it wouldn't cost any memory to speak of, but tuning bash for an
unrepresentative example that doesn't actually occur in real use doesn't
seem like a useful thing to do.  The same thing goes for resizing the hash
table, which would, of course, require creating an entirely new one and
rehashing each element of the old one into the new.  That's easy enough to
write, and I might do it when I have a few minutes, but is the problem
that is designed to solve worth even the implementation effort?  How many
scripts create 64K variables?

> I built bash like this:
> 
> CFLAGS='-pg -g -O0' ./configure --silent && make -sj4 DEBUG= MALLOC_DEBUG=
> 
> To make sure the malloc debugging code doesn't interfere.
> 
> I got a gprof profile with that last run, which gave:
> 
> Each sample counts as 0.01 seconds.
>   %   cumulative   self              self     total           
>  time   seconds   seconds    calls   s/call   s/call  name    
>  71.42     12.07    12.07  1100104     0.00     0.00  hash_search
>  21.18     15.65     3.58   275435     0.00     0.00  morecore
>   1.63     15.93     0.28  6800525     0.00     0.00  internal_malloc
>   0.71     16.05     0.12  6200116     0.00     0.00  internal_free
>   0.59     16.15     0.10   300001     0.00     0.00  expand_word_internal
>   0.24     16.19     0.04  6800474     0.00     0.00  sh_xmalloc
>   0.18     16.22     0.03  7203779     0.00     0.00  is_basic
>   0.18     16.25     0.03  1932530     0.00     0.00  is_basic
>   0.18     16.28     0.03   200002     0.00     0.00  subexpr
>   0.18     16.31     0.03   100008     0.00     0.00  find_special_var
>   0.15     16.33     0.03                             pagealign

I'm not surprised that these functions dominate the run time.  You're
basically doing nothing but assigning variables.  You have to allocate
memory for the variables, and you have to search the variable hash table
to see whether or not the variable already exists.

Chet
-- 
``The lyf so short, the craft so long to lerne.'' - Chaucer
                 ``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, ITS, CWRU    chet@case.edu    http://cnswww.cns.cwru.edu/~chet/