[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Patch to make word_list_split O(n) instead of O(n^2)
From: |
Chet Ramey |
Subject: |
Re: Patch to make word_list_split O(n) instead of O(n^2) |
Date: |
Fri, 29 Apr 2005 13:40:02 -0400 |
User-agent: |
Mozilla Thunderbird 1.0.2 (Macintosh/20050317) |
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/
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- Re: Patch to make word_list_split O(n) instead of O(n^2),
Chet Ramey <=