Mangus, At 16:12 2003-01-13, Magnus Holmgren wrote:
> -----Original Message-----The time consumed in this sort of thing is almost certainly dominated by I/O activity, not CPU load.
> From: Magnus Holmgren [mailto:[EMAIL PROTECTED]]
> Sent: Monday, January 13, 2003 7:51 PM
> To: [EMAIL PROTECTED]
> 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?
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, theAny perceptible delay in getting a result from a computer is too long. So it goes...
> 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.
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/
