Use the new os.scandir() function in os.walk()

[vstinner]

BPO	23605
Nosy	@vstinner, @benhoyt, @serhiy-storchaka
Files	os_walk_1.patch: First cut at os.walk() using scandir walk_added_symlink_to_dir.patch walk_added_symlink_to_dir-2.patch fast_bottom-up.patch fast_bottom-up-2.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 = None
closed_at = <Date 2015-03-30.12:48:56.877>
created_at = <Date 2015-03-08.02:36:13.909>
labels = ['performance']
title = 'Use the new os.scandir() function in os.walk()'
updated_at = <Date 2015-03-30.12:48:56.876>
user = 'https://github.com/vstinner'

bugs.python.org fields:

activity = <Date 2015-03-30.12:48:56.876>
actor = 'vstinner'
assignee = 'none'
closed = True
closed_date = <Date 2015-03-30.12:48:56.877>
closer = 'vstinner'
components = []
creation = <Date 2015-03-08.02:36:13.909>
creator = 'vstinner'
dependencies = []
files = ['38385', '38450', '38451', '38452', '38471']
hgrepos = []
issue_num = 23605
keywords = ['patch']
message_count = 34.0
messages = ['237504', '237507', '237625', '237636', '237726', '237756', '237757', '237759', '237775', '237777', '237779', '237911', '237912', '237913', '237916', '237917', '237921', '237922', '237923', '237924', '238002', '238023', '238024', '238026', '238027', '238399', '238400', '239373', '239377', '239591', '239600', '239603', '239604', '239605']
nosy_count = 5.0
nosy_names = ['scott.dial', 'vstinner', 'benhoyt', 'python-dev', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = None
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue23605'
versions = ['Python 3.5']

[vstinner]

The PEP-471 announces a huge speed up of the os.walk() function, but os.walk() was not modified yet. I just merged the implementation of os.scandir() (issue bpo-22524), it's now time to work on os.walk().

We need a patch and benchmarks on Linux and Windows.

On NFS shares (on Linux), d_type is not filled (set to DT_UNKNOWN, so a syscall is required to get the file type). Benchmarks of os.walk() on a NFS share is also required.

[benhoyt]

Attaching a first cut at this -- basically the implementation I use for walk() in scandir.py on GitHub.

One thing that's really weird to me: are the os.walk() unit tests actually being run? In test_os.py, I notice everything's in WalkTest.setUp, which is kinda weird -- and it's not actually running. At least when I add a "1/0" inside setUp() to force an error and run "python -m test test_os" I don't get any errors...

[vstinner]

I reviewed your patch.

[vstinner]

Note: glob.glob() might be faster with os.scandir() on very large directories. But on my benchmarks, listdir() was always faster than scandir() when only the name of directory entries i used. Maybe we need an option glob.glob(pattern, scandir=True) :-p

[scottdial]

I cloned https://github.com/benhoyt/scandir @ 494f34d784 and ran benchmark.py on a couple systems that are Linux backed by a couple different NFS servers of various quality.

First, a Linux VM backed by a Mac OS X NFS server backed by a SSD:

$ python benchmark.py
Using slower ctypes version of scandir
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on benchtree, repeat 1/3...
Benchmarking walks on benchtree, repeat 2/3...
Benchmarking walks on benchtree, repeat 3/3...
os.walk took 0.088s, scandir.walk took 0.084s -- 1.1x as fast
$ python benchmark.py -s
Using slower ctypes version of scandir
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on benchtree, repeat 1/3...
Benchmarking walks on benchtree, repeat 2/3...
Benchmarking walks on benchtree, repeat 3/3...
os.walk size 23400, scandir.walk size 23400 -- equal
os.walk took 0.142s, scandir.walk took 0.145s -- 1.0x as fast

Second, a Linux VM backed by a Linux NFS server backed by a NAS with big, slow drives:

$ python benchmark.py
Using slower ctypes version of scandir
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on benchtree, repeat 1/3...
Benchmarking walks on benchtree, repeat 2/3...
Benchmarking walks on benchtree, repeat 3/3...
os.walk took 0.071s, scandir.walk took 0.063s -- 1.1x as fast
$ python benchmark.py -s
Using slower ctypes version of scandir
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on benchtree, repeat 1/3...
Benchmarking walks on benchtree, repeat 2/3...
Benchmarking walks on benchtree, repeat 3/3...
os.walk size 23400, scandir.walk size 23400 -- equal
os.walk took 0.118s, scandir.walk took 0.141s -- 0.8x as fast

Finally, a linux VM backed by a Linux NFS server backed by a NAS with small, fast SAS drives:

$ python benchmark.py
Using slower ctypes version of scandir
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on benchtree, repeat 1/3...
Benchmarking walks on benchtree, repeat 2/3...
Benchmarking walks on benchtree, repeat 3/3...
os.walk took 0.159s, scandir.walk took 0.119s -- 1.3x as fast
$ python benchmark.py -s
Using slower ctypes version of scandir
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on benchtree, repeat 1/3...
Benchmarking walks on benchtree, repeat 2/3...
Benchmarking walks on benchtree, repeat 3/3...
os.walk size 23400, scandir.walk size 23400 -- equal
os.walk took 0.229s, scandir.walk took 0.232s -- 1.0x as fast

A major factor that is not addressed above is that the performance is dramatically different if the metadata cache for the NFS mount is disabled, which is not the default. In the above data, the first system is normally configured in such a manner in order to ensure that the filesystem is coherent. The results of that test is much more dramatic:

$ python benchmark.py
Using slower ctypes version of scandir
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on benchtree, repeat 1/3...
Benchmarking walks on benchtree, repeat 2/3...
Benchmarking walks on benchtree, repeat 3/3...
os.walk took 4.835s, scandir.walk took 0.097s -- 49.9x as fast
$ python benchmark.py -s
Using slower ctypes version of scandir
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on benchtree, repeat 1/3...
Benchmarking walks on benchtree, repeat 2/3...
Benchmarking walks on benchtree, repeat 3/3...
os.walk size 23400, scandir.walk size 23400 -- equal
os.walk took 9.945s, scandir.walk took 5.373s -- 1.9x as fast

[python-dev]

New changeset f805fdacdfe0 by Victor Stinner in branch 'default':
Issue bpo-23605: os.walk() now calls os.scandir() instead of os.listdir().
https://hg.python.org/cpython/rev/f805fdacdfe0

[vstinner]

My suggestion to add a new walk_dirs list is wrong: os.walk() documentation explicitly says that the dirs list can be modified to delete some directories:
https://docs.python.org/dev/library/os.html#os.walk
"""
When topdown is True, the caller can modify the dirnames list in-place (perhaps using del or slice assignment), and walk() will only recurse into the subdirectories whose names remain in dirnames; this can be used to prune the search, impose a specific order of visiting, or even to inform walk() about directories the caller creates or renames before it resumes walk() again.
"""

os_walk_1.patch is inefficient: it also calls entry.is_symlink() for file entries.

I reworked your patch to only call is_symlink() for directories.

Thanks for the patch Ben. I think that we are now done with the PEP-471 no? Maybe some doc changes (I'm now reviewing your doc change in issue bpo-22524).

[python-dev]

New changeset 50e32059a404 by Victor Stinner in branch '3.4':
Issue bpo-23605: os.walk() doc now mentions shutil.rmtree() in the last example
https://hg.python.org/cpython/rev/50e32059a404

[serhiy-storchaka]

When followlinks is true, symlinks is not needed.

But I this commit breaks a code like following:

def unsymlink(top):
    for root, dirs, files in os.walk(top):
        for name in dirs:
            path = os.path.join(root, name)
            if os.path.islink(path):
                target = os.path.join(root, os.readlink(path))
                os.unlink(path)
                shutil.copytree(target, path)
        for name in files:
            path = os.path.join(root, name)
            if os.path.islink(path):
                target = os.path.join(root, os.readlink(path))
                os.unlink(path)
                shutil.copy2(target, path)

[vstinner]

Serhiy Storchaka added the comment:

When followlinks is true, symlinks is not needed.

Hum, it's not easy to understand your code. I guess that the problem
is that a symlink to a directory can become something else (not a
directory or a symlink to a directory).

I noticed this race condition in the new implementation of os.walk(),
but I don't think that the issue is really new. The old implementation
of os.walk() already uses a list of directories. The caller can remove
a directory or replace a directory with something else.

Since the bug is not documented in os.walk(), I chose to not document
it neither. But it would be better to warn users to not do that :-)

@serhiy: I agree that the new implementation changes the behaviour,
but I don't consider it as as bug. Do you think that it's a bug?

[serhiy-storchaka]

My first note was about efficiency of the implementation. When followlinks is
true, you can avoid testing entry.is_link() and creating the symlinks set.

The new implementation of os.walk() changes a behavior. The problem is that a
symlink to a directory can become a directory. It is documented that the
caller can remove or add a directory to directory list and for sure this
feature is used in third-party code. In my example a directory list is even
not changed, but file system is changed.

I think that majority of uses of os.walk() will be not affected by this change,
but for sure there is a code that will be broken and we can receive bug
reports after releasing 3.6.

New behavior also is not consistent with os.fwalk().

[benhoyt]

@scott Dial: just a response about this benchmark: note that this benchmark isn't really valid, as it says "Using slower ctypes version of scandir", which is the slow all-Python version. You want it to be saying "Using Python 3.5's builtin os.scandir()".