Re: Patch to make word_list_split O(n) instead of O(n^2)

[Chet Ramey]

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 "${a[@]}" >/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 <michal.marek@matfyz.cz>

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    chet@case.edu    http://cnswww.cns.cwru.edu/~chet/