Mailing-List: contact cygwin-help AT cygwin DOT com; run by ezmlm
List-Subscribe: <mailto:cygwin-subscribe AT cygwin DOT com>
List-Archive: <http://sources.redhat.com/ml/cygwin/>
List-Post: <mailto:cygwin AT cygwin DOT com>
List-Help: <mailto:cygwin-help AT cygwin DOT com>, <http://sources.redhat.com/ml/#faqs>
Sender: cygwin-owner AT cygwin DOT com
Mail-Followup-To: cygwin AT cygwin DOT com
Delivered-To: mailing list cygwin AT cygwin DOT com
Message-Id: <5.2.0.9.2.20030113161921.028eed10@pop3.cris.com>
X-Sender: rrschulz AT pop3 DOT cris DOT com
Date: Mon, 13 Jan 2003 16:28:00 -0800
To: "Magnus Holmgren" <magho AT home DOT se>, <cygwin AT cygwin DOT com>
From: Randall R Schulz <rrschulz AT cris DOT com>
Subject: RE: Tab completion list takes enormously long time to generate
  from empty string
In-Reply-To: <LNBBJIKCLBKJMCCLELOEKEBPCJAA.magho@home.se>
References: <LNBBJIKCLBKJMCCLELOEGEBOCJAA DOT magho AT home DOT se>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"; format=flowed

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/