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]>
diff -rc bash-3.0/externs.h bash-3.0.new/externs.h
*** bash-3.0/externs.h Tue Apr 13 05:30:08 2004
--- bash-3.0.new/externs.h Thu Apr 28 23:09:46 2005
***************
*** 124,129 ****
--- 124,130 ----
extern int list_length ();
extern GENERIC_LIST *list_append ();
extern GENERIC_LIST *list_remove ();
+ extern GENERIC_LIST *list_tail ();
/* Declarations for functions defined in stringlib.c */
extern int find_string_in_alist __P((char *, STRING_INT_ALIST *, int));
diff -rc bash-3.0/list.c bash-3.0.new/list.c
*** bash-3.0/list.c Mon Mar 18 19:13:54 2002
--- bash-3.0.new/list.c Thu Apr 28 23:14:10 2005
***************
*** 103,108 ****
--- 103,123 ----
return (head);
}
+ /* When appending multiple times, make the O(n) walk only once.
+ * Ideally, we should have some more efficient structure, storing tail and
+ * length at least...
+ */
+ GENERIC_LIST *
+ list_tail (head)
+ GENERIC_LIST *head;
+ {
+ if (!head)
+ return NULL;
+ for (; head->next; head = head->next)
+ ;
+ return head;
+ }
+
#ifdef INCLUDE_UNUSED
/* Delete the element of LIST which satisfies the predicate function COMPARER.
Returns the element that was deleted, so you can dispose of it, or -1 if
diff -rc bash-3.0/subst.c bash-3.0.new/subst.c
*** bash-3.0/subst.c Sun Jul 4 19:56:13 2004
--- bash-3.0.new/subst.c Thu Apr 28 23:56:47 2005
***************
*** 6834,6845 ****
word_list_split (list)
WORD_LIST *list;
{
! WORD_LIST *result, *t, *tresult;
! for (t = list, result = (WORD_LIST *)NULL; t; t = t->next)
{
tresult = word_split (t->word, ifs_value);
! result = (WORD_LIST *) list_append (result, tresult);
}
return (result);
}
--- 6834,6848 ----
word_list_split (list)
WORD_LIST *list;
{
! WORD_LIST *result, *t, *tresult, *tail;
! for (t = list, tail = result = (WORD_LIST *)NULL; t; t = t->next)
{
tresult = word_split (t->word, ifs_value);
! if (!result)
! result = tresult;
! list_append(tail, tresult);
! tail = (WORD_LIST *)list_tail(tresult);
}
return (result);
}
_______________________________________________
Bug-bash mailing list
Bug-bash@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-bash
