This is the mail archive of the
cygwin@cygwin.com
mailing list for the Cygwin project.
RE: Tab completion list takes enormously long time to generate from empty string
- From: Randall R Schulz <rrschulz at cris dot com>
- To: "Magnus Holmgren" <magho at home dot se>, <cygwin at cygwin dot com>
- Date: Mon, 13 Jan 2003 16:28:00 -0800
- Subject: RE: Tab completion list takes enormously long time to generate from empty string
- References: <LNBBJIKCLBKJMCCLELOEGEBOCJAA.magho@home.se>
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/