Global replacement in variable expansion is very slow (exponential?)

[Karsten Sperling]

Configuration Information [Automatically generated, do not change]:
Machine: i486
OS: linux-gnu
Compiler: gcc
Compilation CFLAGS:  -DPROGRAM='bash' -DCONF_HOSTTYPE='i486'
-DCONF_OSTYPE='linux-gnu' -DCONF_MACHTYPE='i486-pc-linux-gnu'
-DCONF_VENDOR='pc' -DLOCALEDIR='/usr/share/locale' -DPACKAGE='bash'
-DSHELL -DHAVE_CONFIG_H   -I.  -I../bash -I../bash/include -I../bash/lib
  -g -O2 -Wall
uname output: Linux cargocult 2.6.22-14-generic #1 SMP Tue Feb 12
07:42:25 UTC 2008 i686 GNU/Linux
Machine Type: i486-pc-linux-gnu

Bash Version: 3.2
Patch Level: 25
Release Status: release

Description:
        ${var//pattern/} style replacement is very slow for even
moderately large strings.
        String length vs. user time for a simple example with many
replacements:

          length: 1000  user: 0m0.112s
          length: 2000  user: 0m0.660s
          length: 3000  user: 0m1.968s
          length: 4000  user: 0m4.368s
          length: 5000  user: 0m8.101s

        This should take a linear (or near-linear) amount of time;
        it looks like there is way too much reallocation and
        copying happening.

Repeat-By:
        karsten@cargocult:/tmp$ string="$(seq -f %09g 500)."; echo
"length: ${#string}"; time string="${string//0/}"
        length: 5000

        real    0m8.119s
        user    0m8.101s
        sys     0m0.016s