Re: findutils support in 1.7.0

[Corinna Vinschen <corinna-cygwin at cygwin dot com>]

On Apr 26 06:14, Eric Blake wrote:
> According to Corinna Vinschen on 4/26/2008 2:39 AM:
>
> [moving to -devel]
>
>>>   Also, it looks like long path names are currently
>>> quadratic in behavior,
>> Dunno about that.  Right now the path is converted from multibyte
>> to wchar and vice versa a couple of times more often than necessary,
>> probably, but it shouldn't be quadratic.  Do you have a simple(tm)
>> testcase to reproduce?

Windows.  Always in for a surprise.  It appears that the quadratic
behaviour is actually Windows' fault.  I used strace on your testcase
and changed the debug output in path.cc, symlink_info::check so that
two debug strings are generated, one before, and one after the call
to NtQueryAttributesFile (NTQAF).  That allowed me to get the timing of
the NTQAF itself.  Instead of printing the actual filename, I printed
the length of the filename.

What happens is that for each subdirectory which should be created,
NTQAF is called twice (confdir3, confdir3.lnk)(*), and in both cases you
get a status C0000034 (STATUS_OBJECT_NAME_NOT_FOUND).

For each subdirectory iteration, the *first* call to NTQAF gets slower
than in the previous iteration.  The *second* call, the one checking for
confdir3.lnk is rather fast, though also not as fast as for shorter path
lengths.

A quick spreadsheet:

pathlength   1. NTQAF  2. NTQAF
  bytes         us         us

    44         112         94
    98         112         95
   215         118        105
   440         288        155
   800         581        121
  1250         874        140
  2006        1987        195
  3005        5361        281
  4004        8965        298
  4958       13630        382


OH BOY!!!!!

Since later calls to the same filename are not as slow, it appears that,
for each deep subdir access, the first access in that subdir is really
slow, further calls are not.

As you know, NtQueryAttributesFile is the NT equivalent of
GetFileAttributes.  Maybe this function is slow by design and we're better
off using something along the lines of either

  NtOpenFile
  NtQueryInformationFile
  NtClose

or, maybe, something like

  NtOpenFile(parentdir)
  NtQueryDirectoryFile
  NtClose

but that's something I will have to test first.  I guess you will be
surprised to read that now, but I'm slightly disappointed at Windows...


Corinna

(*) Which is a bug, actually.  To avoid name collision with existing
    .exe files, this test should always check for .exe as well.


-- 
Corinna Vinschen                  Please, send mails regarding Cygwin to
Cygwin Project Co-Leader          cygwin AT cygwin DOT com
Red Hat