Re: very long variable + parameter expansion = crazy cpu usage ?

[Chet Ramey]

Mike Frysinger wrote:
> i had some scripts that were acting up lately and i finally managed to track 
> it back to a very long varable + parameter expansion
> 
> i currently have a variable such that ${#var} ~= 2440.  when i try to do 
> something like [[ -z ${var/*ccache*} ]], it takes an abnormal amount of time 
> and proceeds to use 100% of my cpu.  when i say abnormal, i mean that i have 
> a 2.2gig amd64 with 2gigs of ram and this statement can easily take up ~20 
> seconds to complete when there's nothing else running on the system.

Bash doesn't attempt any optimization in this case; it just charges
ahead and tries to replace the longest match with the replacement
string.  In the case of your test, that results in 2999 unsuccessful
calls to strmatch/wcsmatch, with complexity exceeding O(N!) for a
string of length N.  As you can see, that takes quite a while.

I'll probably do something like checking whether or not the pattern
matches anywhere in the string before seeing where the longest match
might be.  That should cut down the number of unsuccessful calls to
strmatch/wcsmatch.

This could work for both pattern replacement and pattern removal.

Chet

-- 
``The lyf so short, the craft so long to lerne.'' - Chaucer
( ``Discere est Dolere'' -- chet )
                                                Live...Laugh...Love
Chet Ramey, ITS, CWRU    chet@case.edu    http://cnswww.cns.cwru.edu/~chet/