Improve performance of pathlib.scandir()

[ShaiAvr]

BPO	37935
Nosy	@brettcannon, @gpshead, @pitrou, @serhiy-storchaka, @hongweipeng, @ShaiAvr
PRs	bpo-37935: Improve performance of pathlib.scandir() #15331 bpo-37935: Added tests for os.walk(), glob.iglob() and Path.glob() #15956 [3.8] bpo-37935: Added tests for os.walk(), glob.iglob() and Path.glob() (GH-15956) #16043

^{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/gpshead'
closed_at = None
created_at = <Date 2019-08-24.06:31:41.093>
labels = ['3.8', 'library', '3.9', 'performance']
title = 'Improve performance of pathlib.scandir()'
updated_at = <Date 2019-09-12.15:07:49.880>
user = 'https://github.com/ShaiAvr'

bugs.python.org fields:

activity = <Date 2019-09-12.15:07:49.880>
actor = 'gregory.p.smith'
assignee = 'gregory.p.smith'
closed = False
closed_date = None
closer = None
components = ['Library (Lib)']
creation = <Date 2019-08-24.06:31:41.093>
creator = 'Shai'
dependencies = []
files = []
hgrepos = []
issue_num = 37935
keywords = ['patch']
message_count = 13.0
messages = ['350354', '350589', '350604', '350605', '350608', '350613', '351706', '351735', '351736', '351756', '351901', '352148', '352194']
nosy_count = 6.0
nosy_names = ['brett.cannon', 'gregory.p.smith', 'pitrou', 'serhiy.storchaka', 'hongweipeng', 'Shai']
pr_nums = ['15331', '15956', '16043']
priority = 'normal'
resolution = None
stage = 'patch review'
status = 'open'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue37935'
versions = ['Python 3.8', 'Python 3.9']

[ShaiAvr]

I recently have taken a look in the source code of the pathlib module, and I saw something weird there:

when the module used the scandir function, it first converted its iterator into a list and then used it in a for loop. The list wasn't used anywhere else, so I think the conversion to list is just a waste of performance.

In addition, I noticed that the scandir iterator is never closed (it's not used in a with statement and its close method isn't called). I know that the iterator is closed automatically when it's garbaged collected, but according to the docs, it's advisable to close it explicitly.

I've created a pull request that fixes these issues:
PR 15331

In the PR, I changed the code so the scandir iterator is used directly instead of being converted into a list and I wrapped its usage in a with statement to close resources properly.

[hongweipeng]

Scandir() will be close when it iteration is over.You can see ScandirIterator_iternext:

static PyObject *
ScandirIterator_iternext(ScandirIterator *iterator)
{
    while (1) {
        ...
    }
    /* Error or no more files */
    ScandirIterator_closedir(iterator);
    return NULL;
}

So, entries = list(scandir(parent_path)) resources in this code can be properly closed.

[ShaiAvr]

From the docs (https://docs.python.org/3/library/os.html#os.scandir.close):

"This is called automatically when the iterator is exhausted or garbage collected, or when an error happens during iterating. However it is advisable to call it explicitly or use the with statement.".

The iterator is indeed closed properly, but the docs state that it's still advisable to close it explicitly, which is why I wrapped it in a with statement.

However, the more important change is that the iterator is no longer converted into a list, which should reduce the iterations from 2N to N, when N is the number of entries in the directory (one N when converting to list and another one when iterating it). This should enhance the performance of the functions that use scandir.

[serhiy-storchaka]

Could you please provide any microbenchmarks that show the performance improvement?

[ShaiAvr]

I'm new to contributing here. I've never done benchmarking before.

I'd appreciate it if you could provide a guide to benchmarking.
You could look at the changes I made in the pull request (PR 15331). They're easy to follow and I think that removing a useless call to list() should enhance the performance, but I'd like to have benchmarking to back this up, so if someone more experienced could do this or at least provide a link to a guide, I'd really appreciate it.

[serhiy-storchaka]

I think using the timeit module is enough. For more precise benchmarking you may need to use the pyperf module, but I think this is not a case.

For example, something like:

./python -m timeit -s "from pathlib import Path; p = Patch('...')" "for x in p.rglob('...'): pass"

[gpshead]

Shai, please open the 'Your Details' link in the bugs.python.org sidebar and make sure you have your github username filled in. it needs to say ShaiAvr for our CLA automation to understand.

Avoiding calling list() on the output of scandir() is always desirable. :)

[serhiy-storchaka]

The title is misleading. There is no pathlib.scandir().

[serhiy-storchaka]

Any optimization can be accepted only when we have any prove that the change actually has measurable effect, and that it is large enough.

Avoiding calling list() on the output of scandir() may be not harmless. For example it will left open a file descriptor. This can cause issues if walk a deep tree, especially if do this in few threads simultaneously. list() guaranties that it is open in very limited time (although using a context manager is desirable).

[gpshead]

For some context here, the pathlib scandir code was written by Serhiy in https://bugs.python.org/issue26032 and related commit 680cb15.

Any optimization can be accepted only when we have any prove that the change actually has measurable effect, and that it is large enough.

While often good advice, there is no such blanket policy. Saying that comes across as dismissive. A better way to phrase such a statement is as a question:

In what practical scenarios does this change provide a demonstrable benefit?

The improvement in this case could be avoiding an explosion of memory use in some circumstances. Depending on the particular filesystem. (the original reason based on real world production experience that I pushed to have our os.scandir API created in the first place)

Avoiding calling list() on the output of scandir() may be not harmless.

Keeping it may not be harmless either. :)

One key point of os.scandir() is to be iterated over instead of turned into a list to avoid using too much memory. Code that requires a list could've just called listdir() (as the previous code did in both of these places) - if that is intentional, we should include an explicit comment stating why a preloaded list was intentional.

Either these list calls go away as is natural with scandir, or comments should be added explaining why they are important (related: unittests exercising the situations they are important for would be ideal)

As you're the original author of the pathlib scandir code, do you remember what the intent of these list(scandir) calls was?

One potential difference without them: If someone is selecting via pathlib and modifying directory file contents while iterating over the results, the lists may be important. (what happens in this case presumably depends on the underlying os fs implementation)

It sounds like we don't have test cases covering such scenarios.