RE: Tab completion list takes enormously long time to generate from empty string

RE: Tab completion list takes enormously long time to generate from empty string

[lhall]

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@home.se
Date: Tue, 14 Jan 2003 01:12:23 +0100
To: cygwin@cygwin.com
Subject: RE: Tab completion list takes enormously long time to generate
from empty string


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

Re: Tab completion list takes enormously long time to generate from empty string

[Max Bowsher]

Magnus Holmgren wrote:
> But Cygwin setup doesn't have to open and read thousands of files.
> And it's not using cygwin1.dll. The Cygwin layer seems to slow down
> things considerably.  

Yes, stat is known to be an expensive operation.
 
> I was able to strip down my $PATH a bit (removing KDE for example),
> reducing the time needed to generate the list to some minute, but I'm
> not quite satisfied with that either.  
> 
>> It's too bad so many DLLs are produced in this list. Must they
>> have execute
>> bits set to be loaded?
>> 
> NT does have separate read and execute bits. I don't know if DLL:s
> have to have the execute bits set to be loaded,

Yes!

>> 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.
> 
> It helps a bit, or even a lot, but at the price that all files will
> be tab completed to. Unless I create a mount point to each directory
> in $PATH.  

Do you have that many that this is impractical?

Max.


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

RE: Tab completion list takes enormously long time to generate from empty string

[Magnus Holmgren]

> 
> 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.
> 
Well, there are certainly some disk I/O, but also 100% load on one processor,
so the operation seems to be CPU-bound anyway.

> 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!
> 
A few seconds. Bite that! :)
But Cygwin setup doesn't have to open and read thousands of files. And it's not using cygwin1.dll. The Cygwin layer seems to slow down things considerably.

> 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.
> 
I was able to strip down my $PATH a bit (removing KDE for example), reducing the time needed to generate the list to some minute, but I'm not quite satisfied with that either.

> It's too bad so many DLLs are produced in this list. Must they 
> have execute 
> bits set to be loaded?
> 
NT does have separate read and execute bits. I don't know if DLL:s have to have the execute bits set to be loaded, but it's rather laborious to change all the permissions anyway. Windows primarily relies on extensions to determine what files are executable, as you know. Perhaps cygwin should do that as well, i.e. only check files with known extensions for #!/path?

> 
> >
> >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...
> 
Hey! I didn't say that! I'll be fine with ten seconds! :-)

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

It helps a bit, or even a lot, but at the price that all files will be tab completed to. Unless I create a mount point to each directory in $PATH.

/Magnus

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

Re: Tab completion list takes enormously long time to generate from empty string

[Corinna Vinschen]

On Mon, Jan 13, 2003 at 04:28:00PM -0800, Randall R Schulz wrote:
> It's too bad so many DLLs are produced in this list. Must they have execute 
> bits set to be loaded?

Yes, unfortunately.

Corinna

-- 
Corinna Vinschen                  Please, send mails regarding Cygwin to
Cygwin Developer                                mailto:cygwin@cygwin.com
Red Hat, Inc.

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

RE: Tab completion list takes enormously long time to generate from empty string

[Jeremy Hetzler]

At 01:12 AM 1/14/2003 +0100, Magnus Holmgren wrote:
>  A second option might even be to disallow tab completion of commands 
> without entering a prefix.
>
>/Magnus

"shopt -s no_empty_cmd_completion" will do exactly that.

Jeremy


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

RE: Tab completion list takes enormously long time to generate from empty string

[Randall R Schulz]

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/

RE: Tab completion list takes enormously long time to generate from empty string

[Magnus Holmgren]

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

Tab completion list takes enormously long time to generate from empty string

[Magnus Holmgren]

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


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