Mail Archives: cygwin/2003/01/13/19:27:25
Mangus,
At 16:12 2003-01-13, Magnus Holmgren wrote:
> > -----Original Message-----
> > From: Magnus Holmgren [mailto:magho AT home DOT se]
> > Sent: Monday, January 13, 2003 7:51 PM
> > To: cygwin AT cygwin DOT 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/
- Raw text -