Use scandir() to speed up the glob module

[xdegaye]

BPO	25596
Nosy	@gvanrossum, @vstinner, @benhoyt, @xdegaye, @dimaqq, @serhiy-storchaka
Dependencies	bpo-16620: Avoid using private function glob.glob1() in msi module and tools bpo-25994: File descriptor leaks in os.scandir()
Files	glob_isdir.patch glob_isdir_2.patch glob_scandir.patch glob_scandir_2.patch glob_scandir_doc.patch glob_scandir_2_diff.patch glob_scandir_3.patch glob_scandir_4.patch glob_scandir_5.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/serhiy-storchaka'
closed_at = <Date 2016-09-07.11:10:52.544>
created_at = <Date 2015-11-10.11:18:07.859>
labels = ['type-feature', 'library']
title = 'Use scandir() to speed up the glob module'
updated_at = <Date 2016-09-07.11:10:52.543>
user = 'https://github.com/xdegaye'

bugs.python.org fields:

activity = <Date 2016-09-07.11:10:52.543>
actor = 'serhiy.storchaka'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2016-09-07.11:10:52.544>
closer = 'serhiy.storchaka'
components = ['Library (Lib)']
creation = <Date 2015-11-10.11:18:07.859>
creator = 'xdegaye'
dependencies = ['16620', '25994']
files = ['40996', '40999', '41474', '41481', '41533', '41570', '41571', '41576', '41895']
hgrepos = []
issue_num = 25596
keywords = ['patch']
message_count = 30.0
messages = ['254440', '254449', '257347', '257354', '257403', '257421', '257423', '257424', '257456', '257655', '257659', '257758', '257912', '257930', '257938', '257947', '257953', '257954', '257958', '258009', '258015', '258016', '260098', '273912', '274611', '274612', '274696', '274770', '274783', '274794']
nosy_count = 7.0
nosy_names = ['gvanrossum', 'vstinner', 'benhoyt', 'xdegaye', 'python-dev', 'Dima.Tisnek', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue25596'
versions = ['Python 3.6']

[xdegaye]

The glob module happily joins names of regular files together with os.path.join() or attempts to list the files contained into a regular file (sic). The same 'except os.error' statement is used to handle both these cases and the case of a non readable directory.

The attached patch makes the code more correct and easier to understand.

[xdegaye]

This second patch rewrites the conditionals that decide whether to call _iglob() recursively, in a more natural way and without changing the behavior from the first patch.
Note that when 'dirname == pathname', then basename is empty and glob2() or glob1() are not called.

The patch also refactors the code with a new _listdir() function.

[serhiy-storchaka]

In general the patch LGTM. It allows to speed up glob by 5-10% in warn test. But much more gain we can achieve by using os.scandir(). Here are results of microbenchmarks:

$ ./python -m timeit -s "from glob import glob" -- "glob('**/*', recursive=True)"
Unpatched:        201 msec per loop
Using isdir():    181 msec per loop
Using scandir():  65.2 msec per loop

$ ./python -m timeit -s "from glob import glob" -- "glob('/usr/lib*/**/*', recursive=True)"
Unpatched:        2.06 sec per loop
Using isdir():    1.92 sec per loop
Using scandir():  820 msec per loop

$ ./python -m timeit -s "from glob import glob" -- "glob('/usr/lib*/**/', recursive=True)"
Unpatched:        1.77 sec per loop
Using isdir():    1.61 sec per loop
Using scandir():  431 msec per loop

Yet one benefit is that iglob() now yields path names without the delay for reading the full content of a directory (see bpo-22167).

[bitdancer]

I don't think it is a good idea to break backward compatibility here even if the globN are internal functions. Better would be to continue to have globN functions that support the existing API and emit deprecation warnings.

[serhiy-storchaka]

I think so too. I just wanted someone to confirmed that it is not overcautiousness. For now glob1() is used only in one place in the stdlib (bpo-16620).

But there was other problem with previous patch, the same as with current implementation of os.walk() (bpo-25995). It makes glob to use a lot of file descriptors.

Updated patch lefts deprecated glob1() and glob2() and makes glob to consume all scandir iterator before starting to yield values (but the problem with fd leaks on non-refcounted implementations is still left, bpo-25994). This doesn't affect performance, but lefts the issue with delaying (bpo-22167).

[xdegaye]

os.scandir() is called recursively in the last patch and the file descriptors are not closed until returning from the recursion.
The glob functions should fail explicitly when scandir() raises OSERROR with posix errno set to EMFILE (The process has too many files open), or even better, silently ignore only the PermissionError exception instead of ignoring OSERROR.

[xdegaye]

I may be missing something, anyway here are few comments on the patch:
Is the call to entry.is_symlink() in _iterdir() necessary since is_dir() follows symlinks ?
If _iterdir() would yield the DirEntry instance instead of DirEntry.name, then _rlistdir() could use x.is_dir() to know whether it is correct to iterate over _rlistdir(x.path, dironly)

[serhiy-storchaka]

os.scandir() is called recursively in the last patch and the file descriptors are not closed until returning from the recursion.

No, os.scandir() is called non-recursively in _iterdir(), and since _iterdir() results are always accumulated in a list, a recursion starts only after exhausting the os.scandir() iterator and closing the file descriptor. We need first to resolve bpo-25994 to close the file descriptor explicitly.

The glob functions should fail explicitly when scandir() raises OSERROR with posix errno set to EMFILE (The process has too many files open), or even better, silently ignore only the PermissionError exception instead of ignoring OSERROR.

Patched code passes existing tests. Do you have additional tests?

Is the call to entry.is_symlink() in _iterdir() necessary since is_dir() follows symlinks ?

Ah, I thought is_dir() doesn't follow symlinks. Yes, now the call to entry.is_symlink() is not necessary.

If _iterdir() would yield the DirEntry instance instead of DirEntry.name, then _rlistdir() could use x.is_dir() to know whether it is correct to iterate over _rlistdir(x.path, dironly)

Yes, but this can complicate the rest of the code. _rlistdir() is called with dironly=False only when the pattern ends with '**'. I'm not sure this is enough important case for optimization. In most cases '**' is used in the middle of the pattern, and all names yielded by _iterdir() are directory names (or broken symlinks).

[xdegaye]

and since _iterdir() results are always accumulated in a list

Right, I failed to note that point. And so, since the file descriptor opened by os.scandir() is closed within each call to recursive _rlistdir(), then my other comment about EMFILE does not stand as well.

[vstinner]

Related issue: bpo-26032 "Use scandir() to speed up pathlib globbing".

[gvanrossum]

(IOW once this patch has been applied maybe you can do the same for globbing in pathlib as requested in issue bpo-26032.)

[xdegaye]

Adding a doc patch.