PEP 471 implementation: os.scandir() directory scanning function

[benhoyt]

BPO	22524
Nosy	@tebeka, @pitrou, @vstinner, @giampaolo, @tjguk, @benhoyt, @4kir4, @socketpair, @MojoVampire
Files	scandir-1.patch: Patch to document, implement, and test os.scandir() clear_system_cache.patch do_os_walk_getsize.patch scandir-2.patch get_tree_size_listdir.diff scandir-3.patch scandir-4.patch scandir-5.patch bench_scandir.py bench_scandir2.py scandir-6.patch scandir-7.patch: Updated all-C implementation scandir-8.patch: Updated all-C implementation per Victor's review whatsnew.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-09.09:52:18.560>
created_at = <Date 2014-09-30.14:42:42.209>
labels = ['type-feature', 'library']
title = 'PEP 471 implementation: os.scandir() directory scanning function'
updated_at = <Date 2015-03-10.13:24:41.391>
user = 'https://github.com/benhoyt'

bugs.python.org fields:

activity = <Date 2015-03-10.13:24:41.391>
actor = 'benhoyt'
assignee = 'none'
closed = True
closed_date = <Date 2015-03-09.09:52:18.560>
closer = 'vstinner'
components = ['Library (Lib)']
creation = <Date 2014-09-30.14:42:42.209>
creator = 'benhoyt'
dependencies = []
files = ['36831', '36847', '36848', '36963', '37292', '38108', '38111', '38113', '38114', '38120', '38121', '38259', '38374', '38421']
hgrepos = []
issue_num = 22524
keywords = ['patch']
message_count = 56.0
messages = ['227933', '228751', '228775', '228780', '228784', '228786', '228818', '228819', '228821', '228854', '228855', '228857', '228858', '228866', '228867', '228872', '228873', '229659', '231673', '231677', '231682', '231684', '231703', '231745', '235458', '235806', '235833', '235835', '235848', '235849', '235859', '235860', '235865', '235873', '235874', '235883', '235884', '235888', '235920', '235940', '236205', '236738', '237328', '237446', '237489', '237490', '237495', '237496', '237497', '237505', '237624', '237627', '237753', '237758', '237761', '237765']
nosy_count = 12.0
nosy_names = ['tebeka', 'pitrou', 'vstinner', 'giampaolo.rodola', 'tim.golden', 'benhoyt', 'abacabadabacaba', 'akira', 'socketpair', 'python-dev', 'josh.r', 'alexei.romanov']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = None
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue22524'
versions = ['Python 3.5']

[benhoyt]

Opening this to track the implementation of PEP-471: os.scandir() [1]. This supercedes Issue bpo-11406 (and possibly others)?

The implementation is most of the way there, but not yet done as a CPythono 3.5 patch. Before I have a proper patch, it's available on GitHub [2] -- see posixmodule_scandir*.c, test/test_scandir.py, and os.rst.

[1] http://legacy.python.org/dev/peps/pep-0471/
[2] https://github.com/benhoyt/scandir

[benhoyt]

Attaching my first patch here. It includes docs, the implementation of scandir and DirEntry in posixmodule.c, and tests in test_scandir.py. It does not yet include the changes for os.walk() to use scandir; I'm hoping to do that in a separate patch for easier code review.

I'd love some code and documentation review, as well as some thoughts on these open questions:

1. posixmodule.c is getting kinda huge and unwieldy; it'd be nice to implement this in a separate C file, but that comes with its own problems, as several functions would need to be made available externally.

2. While writing the tests, I was getting issues with Windows (apparently) not deleting the symlinks immediately in my teardown function, so for the moment I just don't call the teardown function at all. Not great; I think we'll want a better solution.

3. Partly due to Rename README to README.rst and enhance formatting #2, I haven't yet added tests for the file-not-found condition if a file is found by the directory scanning but then deleted before a DirEntry.is_dir() or DirEntry.is_file() call. I intend to add these tests, and there's a TODO comment in test_scandir.py so I remember.

4. test_scandir.py will need some further cleanup for inclusion in CPython; it's currently taken straight from my scandir module, which supports Python down to Python 2.6.

[vstinner]

Hi Ben,

I started to review your patch, sorry for the delay :-( It's convinient to have the patch on Rietveld to comment it inline.

I didn't expect so much C code. The posixmodule.c is really huge. Well, it's just the longest C file of Python 3.5. Your patch adds 781 more lines to it. It's maybe time to split the file into smaller files.

At the same time, reading C code is boring and it's too easy to "implement bugs". I need to be convinced that the speedup announced in the PEP requires so much C code. In the PEP and https://github.com/benhoyt/scandir#benchmarks it's not clear if the speedup comes from the C code (instead of implementing scandir in pure Python, for example using ctypes) or the lower number of syscalls.

To have a fair benchmark, the best would be to have a C part only implementing opendir/readir and FirstFindFile/FindFileXXX (I'm not sure that ctypes is as fast as C code written with the Python C API), and a Python part which implements the nice Python API.

If the speedup is 10% or lower, I would prefer to not add so much C code and take the compromise of a thin C wrapper and implement scandir in Python.

If we implement os.scandir() in Python, should we still try to share code with os.listdir()? I see that importlib uses os.listdir(), so we need a listdir() function implemented in C at least for importlib.

[pitrou]

I agree that having a high-level wrapper around a low-level C primitive would be cool, but someone has to experiment on that to find out how much performance it would cost.

You may want to have the C primitive return results in batches (of e.g. 10 or 100 entries) to limit the overhead, btw.

[vstinner]

You may want to have the C primitive return results in batches (of e.g. 10 or 100 entries) to limit the overhead, btw.

Ah yes, good idea. I read that internally readdir() also fetchs many
entries in a single syscall (prefetch" / readahead, I don't know how
to call that).

[benhoyt]

Thanks for the initial response and code review, Victor. I'll take a look and respond further in the next few days.

In the meantime, however, I'm definitely open to splitting scandir out into its own C file. This will mean a little refactoring (making some functions public/non-static).

Based on the numbers so far, I'm not so keen on implementing just the sys calls in C and the rest in Python. I already do basically this with ctypes in the scandir module, and it's slowish. I'll send proper numbers through soon, but here's what I remember from running benchmark.py on my Windows laptop with SSD drive:

ctypes version: os.walk() 9x faster with scandir
CPython 3.5 C version (debug): os.walk() 24x faster with scandir
CPython 3.5 C version (release): os.walk() 55x faster with scandir

So you do get a lot of speedup from just the ctypes version, but you get a lot more (55/9 = 6x more here) by using the all-C version. Again, these numbers are from memory -- I'll send exact ones later.

One of the problems is that creating the DirEntry objects and calling their methods is fairly expensive, and if this is all done in Python, you lose a lot. I believe scandir() would end up being slower than listdir() in many cases.

[benhoyt]

Here are the actual numbers (instead of just from memory) running on my Windows laptop, which happens to have an SSD drive, so os.walk() with scandir is particularly good here.

python 3.4: benchmark.py -c python (all implemented in Python using ctypes):

os.walk took 1.011s, scandir.walk took 0.057s -- 17.8x as fast

python 3.4: benchmark.py -c c (using _scandir.c, so the iteration implemented in C, the DirEntry object in Python):

os.walk took 1.014s, scandir.walk took 0.039s -- 25.8x as fast

python 3.5: benchmark.py -c os (using the new all-C version in posixmodule.c):

os.walk took 0.983s, scandir.walk took 0.019s -- 52.3x as fast

So as you can see, there's still another 2x speedup to be gained from having everything in C. I know it's a bit more to review, but my thinking is if we're going to speed this baby up, let's speed it right up!

I haven't done these tests on Linux yet.

[pitrou]

Ben, how can I run the benchmark on my own machine?

Thanks!

[pitrou]

Ok, I've found it. The numbers don't look that good here (Linux, SSD):

$ ~/cpython/opt/python benchmark.py -c python /usr/share/ 
[...]
os.walk took 1.266s, scandir.walk took 1.852s -- 0.7x as fast

$ ~/cpython/opt/python benchmark.py -c c /usr/share/ 
[...]
os.walk took 1.276s, scandir.walk took 1.266s -- 1.0x as fast

$ ~/cpython/opt/python benchmark.py -c os /usr/share/ 
[...]
os.walk took 1.278s, scandir.walk took 0.585s -- 2.2x as fast

[vstinner]

I cloned https://github.com/benhoyt/scandir. I understand that the --scandir command line option of benchmark.py are these choices:

• generic = call listdir() and then use "yield GenericDirEntry" which caches os.stat() and os.lstat() results
• python = ctypes implemented calling opendir/readdir and yields PosixDirEntry objects which uses d_type field from readdir() in is_dir(), is_file() and is_symlink(). Cache the result of os.stat() and os.lstat()
• c = "scandir_helper" (iterator) implemented in C (Python C API) yielding PosixDirEntry objects (same class than the "python" benchmark)

I checked with an assertion: d_type of readdir() is never DT_UNKNOWN on my Linux Fedora 20. Statistics of PosixDirEntry on my /usr/share tree:

• 155544 PosixDirEntry instances
• fast-path (use d_type) taken 466632 times in is_dir/is_symlink
• slow-path (need to call os.stat or os.lstat) taken 7828 times in is_dir/is_symlink
• os.stat called 7832 times
• os.stat called 0 times

7832 is the number of symbolic links in my /usr/share tree. 95% of entries don't need stat() in scandir.walk() when using readdir().

So is_dir() and is_symlink() are approximatively called 3 times per entry: scandir.walk() calls is_dir() and is_symlink() on each entry, but is_dir() also calls is_symlink() by default (because the default value of the follow_symlinks parameter is True).

I ran benchmark.py on my Linux Fedora 20 (Linux kernel 3.14). I have two HDD configured as RAID0. I don't think that my disk config is revelant: I also have 12 GB of memory, I hope that /usr/share tree is fully cached. For example, "free -m" tells me that 8.8 GB are cached.

The generic implementation looks inefficient: it is 2 times slower. Is there a bug? GenericDirEntry caches os.stat() and os.lstat() result, it should be as fast or faster than os.walk(), no? Or is it the cost of a generator?

The "c" implementation is 35% faster than the "python" implementation (python=1.170 sec, c=0.762 sec).

Result of benchmark:

haypo@smithers$ python3 setup.py build && for scandir in generic python c; do echo; echo "=== $scandir ==="; PYTHONPATH=build/lib.linux-x86_64-3.3/ python3 benchmark.py /usr/share -c $scandir || break; done
running build
running build_py
running build_ext

=== generic ===
Using very slow generic version of scandir
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on /usr/share, repeat 1/3...
Benchmarking walks on /usr/share, repeat 2/3...
Benchmarking walks on /usr/share, repeat 3/3...
os.walk took 1.340s, scandir.walk took 2.471s -- 0.5x as fast

=== python ===
Using slower ctypes version of scandir
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on /usr/share, repeat 1/3...
Benchmarking walks on /usr/share, repeat 2/3...
Benchmarking walks on /usr/share, repeat 3/3...
os.walk took 1.318s, scandir.walk took 1.170s -- 1.1x as fast

=== c ===
Using fast C version of scandir
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on /usr/share, repeat 1/3...
Benchmarking walks on /usr/share, repeat 2/3...
Benchmarking walks on /usr/share, repeat 3/3...
os.walk took 1.317s, scandir.walk took 0.762s -- 1.7x as fast

[vstinner]

I also ran the benchmark without cache on disk. It looks like my hard drive is too slow to see a real speedup of scandir(). The maximum speedup is 2.7 seconds lesser when testing the "c" scandir (24.089 => 21.374 seconds): "1.1x as fast".

I modified the benchmark to flush all caches, I added the following line into do_scandir_walk():

   os.system("sudo bash -c 'echo 3 > /proc/sys/vm/drop_caches'")

I also commented the first call to do_scandir_walk() ("Priming the system's cache..."), just to make the benchmark faster.

(See attached clear_system_cache.patch for all changes.)

Result of the modified benchmark without cache:

haypo@smithers$ python3 setup.py build && for scandir in generic python c; do echo; echo "=== $scandir ==="; PYTHONPATH=build/lib.linux-x86_64-3.3/ python3 benchmark.py /usr/share -c $scandir || break; done
running build
running build_py
running build_ext

=== generic ===
Using very slow generic version of scandir
Comparing against builtin version of os.walk()
Benchmarking walks on /usr/share, repeat 1/3...
Benchmarking walks on /usr/share, repeat 2/3...
Benchmarking walks on /usr/share, repeat 3/3...
os.walk took 24.324s, scandir.walk took 24.215s -- 1.0x as fast

=== python ===
Using slower ctypes version of scandir
Comparing against builtin version of os.walk()
Benchmarking walks on /usr/share, repeat 1/3...
Benchmarking walks on /usr/share, repeat 2/3...
Benchmarking walks on /usr/share, repeat 3/3...
os.walk took 24.089s, scandir.walk took 21.374s -- 1.1x as fast

=== c ===
Using fast C version of scandir
Comparing against builtin version of os.walk()
Benchmarking walks on /usr/share, repeat 1/3...
Benchmarking walks on /usr/share, repeat 2/3...
Benchmarking walks on /usr/share, repeat 3/3...
os.walk took 24.225s, scandir.walk took 21.390s -- 1.1x as fast

[vstinner]

My previous benchmark runs were with the system Python 3.3.

New benchmark with a Python 3.5 patched with scandir-1.patch (compiled in release mode: ./configure && make).

"os" (os.scandir) is 2 times faster than "c" (_scandir.scandir_helper): c=0.533 sec, os=0.268 sec.

On all implementations, scandir.walk() is only much faster than os.walk() when "os" (os.scandir) is used: "3.2x as fast" (860 ms => 268 ms).

I guess that on Linux the speedup highly depends on the number of symbolic links.

It would help if benchmark.py created the tree to have more reliable numbers, and being able to compare trees without symlinks, with a few symlinks (ex: 10%), and with a lot of symlinks (ex: 99%).

Benchmark results:

haypo@smithers$ ~/prog/python/default/python setup.py build && for scandir in generic python c os; do echo; echo "=== $scandir ==="; PYTHONPATH=build/lib.linux-x86_64-3.5/ ~/prog/python/default/python benchmark.py /usr/share -c $scandir || break; done
running build
running build_py
copying scandir.py -> build/lib.linux-x86_64-3.5
running build_ext

=== generic ===
Using very slow generic version of scandir
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on /usr/share, repeat 1/3...
Benchmarking walks on /usr/share, repeat 2/3...
Benchmarking walks on /usr/share, repeat 3/3...
os.walk took 0.857s, scandir.walk took 1.627s -- 0.5x as fast

=== python ===
Using slower ctypes version of scandir
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on /usr/share, repeat 1/3...
Benchmarking walks on /usr/share, repeat 2/3...
Benchmarking walks on /usr/share, repeat 3/3...
os.walk took 0.856s, scandir.walk took 0.915s -- 0.9x as fast

=== c ===
Using fast C version of scandir
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on /usr/share, repeat 1/3...
Benchmarking walks on /usr/share, repeat 2/3...
Benchmarking walks on /usr/share, repeat 3/3...
os.walk took 0.857s, scandir.walk took 0.533s -- 1.6x as fast

=== os ===
Using Python 3.5's builtin os.scandir()
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on /usr/share, repeat 1/3...
Benchmarking walks on /usr/share, repeat 2/3...
Benchmarking walks on /usr/share, repeat 3/3...
os.walk took 0.860s, scandir.walk took 0.268s -- 3.2x as fast

[vstinner]

On Windows, I guess that "benchmark.py --size" is faster with scandir() than with os.walk(), because os.stat() is never called.

benchmark.py has a bug in do_os_walk() when the --size option is used: attached do_os_walk_getsize.patch is needed.

Sizes returned by os.walk() and scandir.walk() are different. I guess that the behaviour of symbolic links to directory is different. Because of that, I'm not sure that benchmark timings are reliable, but well, it should give us an idea of performances.

To compute the size of a tree, scandir() is twice faster (2.1x as fast) than os.walk(): os.walk=1.435 sec, scandir.walk=0.675 sec.

"os" is 41% faster than "c": c=1150 ms, os=675 ms.

Results of "benchmark.py --size" on my Linux Fedora 20:

haypo@smithers$ ~/prog/python/default/python setup.py build && for scandir in generic python c os; do echo; echo "=== $scandir ==="; PYTHONPATH=build/lib.linux-x86_64-3.5/ ~/prog/python/default/python benchmark.py -s /usr/share -c $scandir || break; done
running build
running build_py
running build_ext

=== generic ===
Using very slow generic version of scandir
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on /usr/share, repeat 1/3...
Benchmarking walks on /usr/share, repeat 2/3...
Benchmarking walks on /usr/share, repeat 3/3...
os.walk size 3064748475, scandir.walk size 2924332540 -- NOT EQUAL!
os.walk took 1.425s, scandir.walk took 1.147s -- 1.2x as fast

=== python ===
Using slower ctypes version of scandir
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on /usr/share, repeat 1/3...
Benchmarking walks on /usr/share, repeat 2/3...
Benchmarking walks on /usr/share, repeat 3/3...
os.walk size 3064748475, scandir.walk size 2924332540 -- NOT EQUAL!
os.walk took 1.421s, scandir.walk took 1.651s -- 0.9x as fast

=== c ===
Using fast C version of scandir
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on /usr/share, repeat 1/3...
Benchmarking walks on /usr/share, repeat 2/3...
Benchmarking walks on /usr/share, repeat 3/3...
os.walk size 3064748475, scandir.walk size 2924332540 -- NOT EQUAL!
os.walk took 1.426s, scandir.walk took 1.150s -- 1.2x as fast

=== os ===
Using Python 3.5's builtin os.scandir()
Comparing against builtin version of os.walk()
Priming the system's cache...
Benchmarking walks on /usr/share, repeat 1/3...
Benchmarking walks on /usr/share, repeat 2/3...
Benchmarking walks on /usr/share, repeat 3/3...
os.walk size 3064748475, scandir.walk size 2924332540 -- NOT EQUAL!
os.walk took 1.435s, scandir.walk took 0.675s -- 2.1x as fast