[MERGE] Fast _walkdirs for win32
Alexander Belchenko
bialix at ukr.net
Thu Jul 17 13:48:04 BST 2008
You can ignore my mail if you wish, but I simply can't pass over this patch.
Thank you for writing this, I knew bzr must have this long ago,
but I was unable to write such code myself.
John Arbash Meinel пишет:
> Attached is a patch which follows up on my earlier work to use the
> windows native FindFile APIs for walkdirs. It is a pretty good fit,
> because walkdirs wants to return the stat information along with the
> paths, and that is what FindFile* does. (In fact, it uses FindFile* for
> each os.stat, and another one for the os.listdir.)
[...]
> It seems that the overhead of creating a FindFirstFile for every stat is
> pretty horrendous. Specifically, for a tree of 9k entries, --lsprof puts
> 3.5s/5s to nt.lstat().
And penalty on this much higher on FAT32, as I discover in the past.
> Anyway, this isn't urgent for 1.6, but it is a rather nice improvement,
> so I'd like to get it in sooner rather than later. (Otherwise I'm going
> to be tempted to run something other than bzr.dev as my primary 'bzr',
> which I'm not keen on doing.)
Because 1.6 is anyway out of regular schedule,
IMO your patch should be merged into 1.6.
I have some minor comments on your patch itself.
First at all it does not compile for me with Pyrex 0.9.6.3.
What version of Pyrex you're used?
1) My Pyrex don't understand inplace xor (^=).
I'm forced to replace them with explicit xor operator:
cdef int _get_mode_bits(WIN32_FIND_DATAW *data):
cdef int mode_bits
mode_bits = 0100666 # writeable file, the most common
if data.dwFileAttributes & FILE_ATTRIBUTE_READONLY == FILE_ATTRIBUTE_READONLY:
mode_bits = mode_bits ^ 0222 # remove the write bits
if data.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY == FILE_ATTRIBUTE_DIRECTORY:
# Remove the FILE bit, set the DIR bit, and set the EXEC bits
mode_bits = mode_bits ^ 0140111
return mode_bits
2) But anyway it failed because linker cannot find Win32 API functions:
C:\work\Bazaar\mydev.packs\win32_find_files>make
"building extension modules."
python setup.py build_ext -i
running build_ext
pyrexc bzrlib/_walkdirs_win32.pyx --> bzrlib/_walkdirs_win32.c
building 'bzrlib._walkdirs_win32' extension
c:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\bin\cl.exe /c /nologo /Ox /MD /W3 /GX /DNDEBUG
-IC:\Python\2.5.1\include
-IC:\Python\2.5.1\PC /Tcbzrlib/_walkdirs_win32.c /Fobuild\temp.win32-2.5\Release\bzrlib/_walkdirs_win32.obj
_walkdirs_win32.c
c:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\PlatformSDK\Include\WinBase.h(1579) : warning C4007: 'WinMain' :
must be
'__stdcall'
c:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\bin\link.exe /DLL /nologo /INCREMENTAL:NO
/LIBPATH:C:\Python\2.5.1\libs /
LIBPATH:C:\Python\2.5.1\PCBuild /EXPORT:init_walkdirs_win32 build\temp.win32-2.5\Release\bzrlib/_walkdirs_win32.obj
/OUT:bzrlib\
_walkdirs_win32.pyd /IMPLIB:build\temp.win32-2.5\Release\bzrlib\_walkdirs_win32.lib
Creating library build\temp.win32-2.5\Release\bzrlib\_walkdirs_win32.lib and object
build\temp.win32-2.5\Release\bzrlib\_walk
dirs_win32.exp
_walkdirs_win32.obj : error LNK2019: unresolved external symbol __imp__FindClose referenced in function
___pyx_f_15_walkdirs_win
32_11Win32Finder__get_files_in
_walkdirs_win32.obj : error LNK2019: unresolved external symbol __imp__FindNextFileW referenced in function
___pyx_f_15_walkdirs
_win32_11Win32Finder__get_files_in
_walkdirs_win32.obj : error LNK2019: unresolved external symbol __imp__GetLastError referenced in function
___pyx_f_15_walkdirs_
win32_11Win32Finder__get_files_in
_walkdirs_win32.obj : error LNK2019: unresolved external symbol __imp__FindFirstFileW referenced in function
___pyx_f_15_walkdir
s_win32_11Win32Finder__get_files_in
bzrlib\_walkdirs_win32.pyd : fatal error LNK1120: 4 unresolved externals
Building of "bzrlib._walkdirs_win32" extension failed, will use the Python version instead
I found that if I compile _walkdirs_win32.c with custom setup.py (without involving Pyrex at all)
I get the same error. When I looked at the generated C code I saw this definition:
#ifndef WIN32
#define __stdcall
#define __cdecl
#endif
If I manually add
#define WIN32_LEAN_AND_MEAN
#include <windows.h>
before mentioned lines *then* module compiled successfully without any warning or error.
I don't know is it Pyrex bug or not.
=== added file 'bzrlib/_walkdirs_win32.pyx'
--- bzrlib/_walkdirs_win32.pyx 1970-01-01 00:00:00 +0000
+++ bzrlib/_walkdirs_win32.pyx 2008-07-17 04:49:57 +0000
[...]
+cdef extern from "_walkdirs_win32.h":
+ cdef struct _HANDLE:
+ pass
+ ctypedef _HANDLE *HANDLE
+ ctypedef unsigned long DWORD
+ ctypedef long long __int64
+ ctypedef unsigned short WCHAR
+ cdef struct _FILETIME:
+ DWORD dwHighDateTime
+ DWORD dwLowDateTime
+ ctypedef _FILETIME FILETIME
+
+ cdef struct _WIN32_FIND_DATAW:
+ DWORD dwFileAttributes
+ FILETIME ftCreationTime
+ FILETIME ftLastAccessTime
+ FILETIME ftLastWriteTime
+ DWORD nFileSizeHigh
+ DWORD nFileSizeLow
+ # Some reserved stuff here
+ WCHAR cFileName[260] # MAX_PATH
+ WCHAR cAlternateFilename[14]
+
+ # We have to use the typedef trick, otherwise pyrex uses:
+ # struct WIN32_FIND_DATAW
+ # which fails due to 'incomplete type'
+ ctypedef _WIN32_FIND_DATAW WIN32_FIND_DATAW
+
+ cdef HANDLE INVALID_HANDLE_VALUE
+ cdef HANDLE FindFirstFileW(WCHAR *path, WIN32_FIND_DATAW *data)
+ cdef int FindNextFileW(HANDLE search, WIN32_FIND_DATAW *data)
+ cdef int FindClose(HANDLE search)
+
+ cdef DWORD FILE_ATTRIBUTE_READONLY
+ cdef DWORD FILE_ATTRIBUTE_DIRECTORY
+ cdef int ERROR_NO_MORE_FILES
+
+ cdef int GetLastError()
+
+ # Wide character functions
+ DWORD wcslen(WCHAR *)
^-- You don't need to use cdef's in this block, because you're using
"cdef extern from" construct at the top. They are don't seem to harm though.
[...]
+cdef __int64 _get_size(WIN32_FIND_DATAW *data):
+ # Pyrex casts a DWORD into a PyLong anyway, so it is safe to do << 32
+ # on a DWORD
+ return ((<__int64>data.nFileSizeHigh) << 32) + data.nFileSizeLow
^-- Your comment here is misleading IMO. You explicitly cast nFileSizeHigh
to 64-bit integer, so it's definitely safe to shift lower 32 bits
to higher half. And you return from function __int64 value, so there is no
DWORD anymore.
[...]
+ def _get_files_in(self, directory, relprefix):
^-- I'd like to suggest to add some docstring here.
Although it's not public interface, but there 'directory'
expected to be unicode, and 'relprefix' is utf-8 string.
It's unclear for casual reader (like me).
+ cdef WIN32_FIND_DATAW search_data
+ cdef HANDLE hFindFile
+ cdef int last_err
+ cdef WCHAR *query
+ cdef int result
+
+ top_star = directory + '*'
+
+ dirblock = []
+
+ query = PyUnicode_AS_UNICODE(top_star)
+ hFindFile = FindFirstFileW(query, &search_data)
+ if hFindFile == INVALID_HANDLE_VALUE:
+ # Raise an exception? This path doesn't seem to exist
+ raise WindowsError(GetLastError(), top_star)
^-- Umm, I see this code path is not tested explicitly?
Who will catch this exception?
I assume this is just safeguard and this should never happens because
_walkdirs_utf8_win32_find_file supposed to be used on real WT always?
+
+ try:
+ result = 1
+ while result:
+ # Skip '.' and '..'
+ if _should_skip(&search_data):
+ result = FindNextFileW(hFindFile, &search_data)
+ continue
+ name_unicode = _get_name(&search_data)
+ name_utf8 = PyUnicode_AsUTF8String(name_unicode)
^-- here you're using explicit suffixes to differentiate unicode/utf-8
+ relpath = relprefix + name_utf8
+ abspath = directory + name_unicode
^-- but here is not :-(
Probably it's just consistency with other walkdir walkers...
But it's still confusing (me personally).
+ PyList_Append(dirblock,
+ (relpath, name_utf8,
+ self._get_kind(&search_data),
+ self._get_stat_value(&search_data),
+ abspath))
+
+ result = FindNextFileW(hFindFile, &search_data)
+ # FindNextFileW sets GetLastError() == ERROR_NO_MORE_FILES when it
+ # actually finishes. If we have anything else, then we have a
+ # genuine problem
+ last_err = GetLastError()
+ if last_err != ERROR_NO_MORE_FILES:
+ raise WindowsError(last_err)
+ finally:
+ result = FindClose(hFindFile)
+ if result == 0:
+ last_err = GetLastError()
+ pass
^-- you don't need 'pass' here, perhaps.
You pick GetLastError here but don't use it.
Does it's just for clearing Windows' internal variable?
+ return dirblock
[...]
+def _walkdirs_utf8_win32_find_file(top, prefix=""):
+ """Implement a version of walkdirs_utf8 for win32.
+
+ This uses the find files api to both list the files and to stat them.
+ """
+ return Win32Finder(top, prefix=prefix)
^-- You have almost identical copy of this function in the osutils.py --v
=== modified file 'bzrlib/osutils.py'
--- bzrlib/osutils.py 2008-06-11 03:56:46 +0000
+++ bzrlib/osutils.py 2008-07-17 04:49:57 +0000
@@ -1271,6 +1278,15 @@
pending.extend(d for d in reversed(dirblock) if d[2] == _directory)
+def _walkdirs_utf8_win32_find_file(top, prefix=""):
+ """
+ Because Win32 has a Unicode api, all of the 'path-from-top' entries will be
+ Unicode paths.
+ """
+ from bzrlib._walkdirs_win32 import Win32Finder
+ return Win32Finder(top, prefix=prefix)
+
+
def copy_tree(from_path, to_path, handlers={}):
"""Copy all of the entries in from_path into to_path.
^-- But comments here and there are different.
I see copy in osutils used only for testing.
May be there is possible way to avoid this duplication somehow?
=== modified file 'bzrlib/osutils.py'
--- bzrlib/osutils.py 2008-06-11 03:56:46 +0000
+++ bzrlib/osutils.py 2008-07-17 04:49:57 +0000
@@ -1190,8 +1191,14 @@
pass to os functions to affect the file in question. (such as os.lstat)
"""
fs_encoding = _fs_enc.upper()
- if (sys.platform == 'win32' or
- fs_encoding not in ('UTF-8', 'US-ASCII', 'ANSI_X3.4-1968')): # ascii
+ if (sys.platform == 'win32'):
+ try:
+ from bzrlib._walkdirs_win32 import _walkdirs_utf8_win32_find_file
+ except ImportError:
+ return _walkdirs_unicode_to_utf8(top, prefix=prefix)
+ else:
+ return _walkdirs_utf8_win32_find_file(top, prefix=prefix)
+ if (fs_encoding not in ('UTF-8', 'US-ASCII', 'ANSI_X3.4-1968')): # ascii
return _walkdirs_unicode_to_utf8(top, prefix=prefix)
else:
return _walkdirs_fs_utf8(top, prefix=prefix)
^-- Windows 98 does not have Unicode API for FindFirstFileW and Co.
Although I remember clearly that bzr does not support Windows 98 explicitly,
you could change your check for platform so it will be win98-friendly:
+ if win32utils.winver == 'Windows NT':
+ try:
+ from bzrlib._walkdirs_win32 import _walkdirs_utf8_win32_find_file
+ except ImportError:
+ return _walkdirs_unicode_to_utf8(top, prefix=prefix)
+ else:
+ return _walkdirs_utf8_win32_find_file(top, prefix=prefix)
win32utils.winver == 'Windows NT' on non-windows platforms will be False as well.
But of course such change is entirely for your taste.
I don't dig into tests details, but I'm like your pyrex code.
I don't know is my vote worth something, but +1 from me anyway.
And something indirectly related to your pyrex code.
About a year(?) ago I was experimenting on bringing my code for fake cygwin-like
symlinks (win32symlink plugin) into bzrlib. I was failed in the past
because my code required another stat call for every file, and I found that
this slowdown walkdir operations for ~80% on FAT32 and ~15% on NTFS.
Now with your very carefully optimized pyrex extension fake symlinks have another
chance for life. To differentiate fake symlinks from regular files SYSTEM file
attribute is used. So in your pyrex code only one function _get_mode_bits needs
to be tweaked. (And also providing support in some osutils functions too).
More information about the bazaar
mailing list