pathological bash-malloc behaviour

[Sergei Trofimovich]

Hi bash developers!

I think I encountered an unusual pathological behaviour of `bash-malloc`.
I have a directory with ~500_000 files and directories in it. I tried
to iterate through it with a single `for` loop using `*` glob and
noticed that glob expansion takes more time that actual loop payload
(the payload is to match and print a few names).

The reproducer (best ran on `tmpfs`):

    # prepare test directory with ~900_000 files of different name
    # lengths:
    $ mkdir dd; for i in {1..100000}; do echo 
dd/$i.{,1,22,333,4444,55555,666666,7777777,88888888,9999999999}; done | xargs 
touch

Make sure you have started a new interactive shell after directory
creation.

    # trigger bug:
    $ time { echo ./* > /dev/null; }
    real    7m9,378s
    user    7m8,327s
    sys     0m0,277s

    # second run is faster
    $ time { echo ./* > /dev/null; }
    real    0m1,915s
    user    0m1,723s
    sys     0m0,190s

    # until we do a minor change:
    $ time { echo .//* > /dev/null; }
    real    0m34,689s
    user    0m34,470s
    sys     0m0,199s

    # second run is faster again:
    $ time { echo .///* > /dev/null; }
    real    1m6,269s
    user    1m5,999s
    sys     0m0,195s

    # and so on:
    $ time { echo .///* > /dev/null; }
    real    1m6,269s
    user    1m5,999s
    sys     0m0,195s
    $ time { echo .///* > /dev/null; }
    real    0m2,420s
    user    0m2,212s
    sys     0m0,206s

Note that initial expansion always takes 100x of the time we do it
the second time. This happens on `x86_64-linux` system with `bash`
configured as `./configure`. I suspect it has to do with the total
amount of memory allocated (and freed) by `bash` by the time the test
is ran.

If I `./configure` `bash` as `--without-bash-malloc` I see faster
behaviour on `glibc` system:

    $ time { echo * > /dev/null; }
    real    0m0,969s
    user    0m0,737s
    sys     0m0,231s
    $ time { echo ./* > /dev/null; }
    real    0m1,296s
    user    0m1,097s
    sys     0m0,198s
    $ time { echo .//* > /dev/null; }
    real    0m1,380s
    user    0m1,183s
    sys     0m0,196s
    $ time { echo .///* > /dev/null; }
    real    0m1,408s
    user    0m1,225s
    sys     0m0,181s
    $ time { echo .////////////////////* > /dev/null; }
    real    0m2,520s
    user    0m2,309s
    sys     0m0,203s

The performance analysis points at `internal_malloc()` as the main CPU
user:

  $ perf top -p $pid
  99,54%  bash      [.] internal_malloc.constprop.0
   0,03%  [kernel]  [k] read_tsc
   0,03%  [kernel]  [k] __update_load_avg_se
  ...

`INSTALL` file says that `--with-bash-malloc` is enabled by default and
hints that it's possibly a faster allocator that default system's one.

Should the allocator be tweaked to handle this pathological behaviour?
Or maybe it's a good time for `linux` target to switch to
`--without-bash-malloc` as a faster default?

Thanks!

-- 

  Sergei