Michal Marek wrote:
> Configuration Information [Automatically generated, do not change]:
> Machine: i686
> OS: linux-gnu
> Compiler: gcc
> Compilation CFLAGS: -DPROGRAM='bash' -DCONF_HOSTTYPE='i686'
> -DCONF_OSTYPE='linux-gnu' -DCONF_MACHTYPE='i686-pc-linux-gnu'
> -DCONF_VENDOR='pc' -DLOCALEDIR='/usr/local/share/locale' -DPACKAGE='bash'
> -DSHELL -DHAVE_CONFIG_H -I. -I. -I./include -I./lib -g -O2
> uname output: Linux klokan 2.6.10-1.770_FC3 #1 Thu Feb 24 14:00:06 EST 2005
> i686 i686 i386 GNU/Linux
> Machine Type: i686-pc-linux-gnu
>
> Bash Version: 3.0
> Patch Level: 0
> Release Status: release
>
> Description:
> word_list_split () from subst.c (and probably other functions)
> superfluously takes O(n^2) time, since it operates on a single
> linked list in a inefficient way. Namely, it calls an O(n)
> function list_append () from list.c for each word added. This
> doesn't cause problems for most scripts etc., since the command
> line is usually short, but it's for example annoying when using
> certain functions of bash completion <http://www.caliban.org/bash/>.
>
>
> Repeat-By:
> a) install bash completion and type
>
> $ man <tab>
>
> It will take a while until the "Display all X possibilities"
> prompt is displayed.
>
> b)
> #!/bin/bash
> a=( `perl -e "print \"abcdefghijkl \"x$1"` )
> echo "[EMAIL PROTECTED]" >/dev/null # this is slow
>
> running time ./test 5000; time ./test 10000; time ./test 15000;
> etc. shows that the time is +- quadratic.
>
> Fix:
>
> list.c externs.h
> - new function list_tail(GENERIC_LIST *), returning list tail or 0
>
> subst.c
> - Make word_list_split O(n) instead of O(n^2). It was slowing down
> bash completion <http://www.caliban.org/bash/> for instance.
> From Michal Marek <[EMAIL PROTECTED]>
Thanks for the patch. I made a similar change early last September,
and that change will be in bash-3.1.
Chet
--
``The lyf so short, the craft so long to lerne.'' - Chaucer
( ``Discere est Dolere'' -- chet )
Live...Laugh...Love
Chet Ramey, ITS, CWRU [EMAIL PROTECTED] http://cnswww.cns.cwru.edu/~chet/
_______________________________________________
Bug-bash mailing list
Bug-bash@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-bash
