Mailing-List: contact cygwin-help AT cygwin DOT com; run by ezmlm
Sender: cygwin-owner AT cygwin DOT com
Mail-Followup-To: cygwin AT cygwin DOT com
Message-ID: <19920-22003121402330270@M2W030.mail2web.com>
Reply-To: lhall AT rfk DOT com
From: "lhall AT pop DOT ma DOT ultranet DOT com" <lhall AT pop DOT ma DOT ultranet DOT com>
To: magho AT home DOT se, cygwin AT cygwin DOT com
Subject: RE: Tab completion list takes enormously long time to generate from empty string
Date: Mon, 13 Jan 2003 19:23:30 -0500
MIME-Version: 1.0
Content-type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit

Don't forget to check out the available documentation when looking 
for optimizations.  For instance, you will find worthwhile information
in the output of 'mount --help' with supporting prose in the Cygwin
User's Guide:

http://cygwin.com/cygwin-ug-net/using-utils.html#MOUNT

I expect this information is directly applicable in your quest for 
performance improvements.

Larry

Original Message:
-----------------
From: Magnus Holmgren magho AT home DOT se
Date: Tue, 14 Jan 2003 01:12:23 +0100
To: cygwin AT cygwin DOT com
Subject: RE: Tab completion list takes enormously long time to generate
from empty string


> -----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?
> 
> 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.

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.

/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/


--------------------------------------------------------------------
mail2web - Check your email from the web at
http://mail2web.com/ .


--
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/