RE: Tab completion list takes enormously long time to generate from empty string

[Randall R Schulz <rrschulz at cris dot com>]

Mangus,

At 16:12 2003-01-13, Magnus Holmgren wrote:
> > -----Original Message-----
> > From: Magnus Holmgren [mailto:magho@home.se]
> > Sent: Monday, January 13, 2003 7:51 PM
> > To: cygwin@cygwin.com
> > Subject: Tab completion list takes enormously long time to generate 
> from empty string
> >
> >
> > Greetings.
> >
> > When I press tab in bash without having typed anything at all
> > (which is somewhat abusive but it easily happens), bash works for
> > 15 minutes, going through $PATH looking for executables (and in
> > the end producing nothing) on a 2x450 MHz PIII. Is that normal?
The time consumed in this sort of thing is almost certainly dominated by 
I/O activity, not CPU load.

How long does it take Cygwin Setup to compute the list of packages that are 
candidates for download or installation? If your 15 minute time to produce 
a list of executables for command completion is any indication, it must be 
hours!

On my 2.4 GHz single processor system with fast disks, it takes only a few 
seconds to get the beep on the first tab and only about a second or two to 
be asked if I want to see all 3719 possibilities on the second tab.

It's too bad so many DLLs are produced in this list. Must they have execute 
bits set to be loaded?


> > My $PATH contains the usual /usr/local/bin:/usr/bin:/bin, the
> > WINNT and System32 directories, plus some relatively neglectable
> > ones (18 directories in total), but the number of directories in
> > the path and the time it takes to go through their contents is
> > not the problem. Matching an executable in the last directory in
> > $PATH only takes about 0.2 s. Instead, the huge size of the
> > resulting list seems to be what causes the delay, especially when
> > considering that no disk I/O at all is performed during 14 min 59
> > sec of the 15 minutes...
> >
> > I suspect that someone has chosen a sorting algorithm with time
> > complexity O(N^2). Or O(2^N)...
> >
> > Maybe I can find that out myself.
> >
> > Cheers,
> > Magnus
>
> Correction; there is no writing to disk, but certainly loads of *reading*, 
> and quicksort seems to be used, so I don't blame the sorting anymore.
>
> I reckon that all files in $PATH (except .exe-s) have to be opened to see 
> if they start with #!, and that that takes some time. Getting rid of some 
> entries in $PATH surely reduces the time consumed, but I still think that 
> more than five seconds is too much.
Any perceptible delay in getting a result from a computer is too long. So 
it goes...


> Some optimizations should be possible, such as only checking files with 
> certain extensions, like .sh, .pl, and none at all for the magic "#!" or 
> caching the list in some form. A second option might even be to disallow 
> tab completion of commands without entering a prefix.
This is the sort of thing the "-x," "-E" and "-X" options to "mount" are 
meant to address. Check them out, they can probably help a lot with this 
problem.

Randall Schulz


> /Magnus

--
Unsubscribe info:      http://cygwin.com/ml/#unsubscribe-simple
Bug reporting:         http://cygwin.com/bugs.html
Documentation:         http://cygwin.com/docs.html
FAQ:                   http://cygwin.com/faq/