Skip to content

GH-119169: Speed up os.walk(topdown=False) #119186

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
barneygale wants to merge 12 commits into from
Closed

GH-119169: Speed up os.walk(topdown=False) #119186

Changes from 1 commit
Commits
Show all changes
12 commits
Select commit Hold shift + click to select a range
74a495c
GH-119169: Speed up `os.walk()`
barneygale May 19, 2024
eb4b6ff
Merge branch 'main' into os-walk-speedup
barneygale May 23, 2024
46a3ba5
Simplify bottom-up implementation.
barneygale May 23, 2024
2d957a8
Merge branch 'main' into os-walk-speedup
barneygale May 30, 2024
a638202
Apply the same changes to fwalk()
barneygale May 30, 2024
91b5a78
Simplify code slightly
barneygale May 30, 2024
b32c1c0
Simplify exception handling in fwalk()
barneygale Jul 6, 2024
8c7cf04
Merge branch 'main' into os-walk-speedup
barneygale Jul 6, 2024
efd31e2
Undo trailing slash optimisation (moved to another PR)
barneygale Jul 6, 2024
5b89c57
Undo fwalk() changes.
barneygale Jul 6, 2024
525618c
Fix news entry.
barneygale Jul 6, 2024
d3af655
Merge branch 'main' into os-walk-speedup
barneygale Jul 8, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Simplify bottom-up implementation.
  • Loading branch information
@barneygale
barneygale committed May 23, 2024
commit 46a3ba54ac805786649f8ab0e5dd0ace2051f58b
43 changes: 15 additions & 28 deletions Lib/os.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -353,7 +353,9 @@ def walk(top, topdown=True, onerror=None, followlinks=False):

dirs = []
nondirs = []
walk_dirs = []
if not topdown:
# Yield after sub-directory traversal if going bottom up
stack.append((top, dirs, nondirs))

# We may not have read permission for top, in which case we can't
# get a list of the files the directory contains.
Expand All @@ -363,40 +365,31 @@ def walk(top, topdown=True, onerror=None, followlinks=False):
try:
with scandir(top) as entries:
for entry in entries:
is_dir = False
try:
is_dir = entry.is_dir()
if entry.is_dir():
is_dir = True
# Bottom-up: traverse into sub-directory, but exclude
# symlinks to directories if followlinks is False
if not topdown and (followlinks or not entry.is_symlink()):
stack.append(entry.path)
except OSError:
# If is_dir() raises an OSError, consider the entry not to
# be a directory, same behaviour as os.path.isdir().
is_dir = False
pass

if is_dir:
dirs.append(entry.name)
else:
nondirs.append(entry.name)
continue
if topdown:
continue

# Bottom-up: traverse into sub-directory, but exclude
# symlinks to directories if followlinks is False
if followlinks:
walk_into = True
else:
try:
is_symlink = entry.is_symlink()
except OSError:
# If is_symlink() raises an OSError, consider the
# entry not to be a symbolic link, same behaviour
# as os.path.islink().
is_symlink = False
walk_into = not is_symlink

if walk_into:
walk_dirs.append(entry.path)
except OSError as error:
if onerror is not None:
onerror(error)
if not topdown:
# Undo additions to stack.
while not isinstance(stack.pop(), tuple):
pass
continue

if topdown:
Expand All @@ -413,12 +406,6 @@ def walk(top, topdown=True, onerror=None, followlinks=False):
# above.
if followlinks or not islink(new_path):
stack.append(new_path)
else:
# Yield after sub-directory traversal if going bottom up
stack.append((top, dirs, nondirs))
# Traverse into sub-directories
for new_path in reversed(walk_dirs):
stack.append(new_path)

__all__.append("walk")

Expand Down