gh-89727: Fix os.walk RecursionError on deep trees #99803

jonburdo · 2022-11-27T00:10:49Z

Use a stack to implement os.walk iteratively instead of recursively to avoid hitting recursion limits on deeply nested trees.

Issue: Change shutil.rmtree and os.walk to support very deep hierarchies #89727

bedevere-bot · 2022-11-27T00:10:55Z

Most changes to Python require a NEWS entry.

Please add it using the blurb_it web app or the blurb command-line tool.

cpython-cla-bot · 2022-11-27T00:11:22Z

All commit authors signed the Contributor License Agreement.

careljonkhout · 2022-11-29T18:48:24Z

These changes look good to me. I would sure like to see this issue fixed. Please add a news entry as suggested by the belverdere bot, so that this PR can move along.

Use a stack to implement os.walk iteratively instead of recursively to avoid hitting recursion limits on deeply nested trees.

carljm · 2022-12-15T16:38:51Z

Just a note, it's better to push additional commits instead of force-pushing an amended commit. The latter invalidates previous reviews and generally makes it harder for reviewers to see the changes over time. The multiple commits will get squashed on merge anyway. (This also applies to updating from main: merge in main, don't rebase.)

carljm

Code changes LGTM.

I think a test should be added here that the recursion limit does not limit depth for os.walk, to prevent regression of the bug. A super-deep directory structure should not be needed for this test, because the test can temporarily set a low recursion limit. It looks like test.support.infinite_recursion can be used for this, although it's badly named for the purpose; should probably move the body of it to a new test.support.temp_recursion_limit function (with no default depth value) and make test.support.infinite_recursion a thin wrapper around it that just provides the default value of 75.

carljm · 2022-12-15T17:08:54Z

(It's not clear to me from the logs whether the Win x64 test failure is related or just flaky; if it fails again after update, then it deserves further investigation.)

JelleZijlstra · 2022-12-15T17:15:56Z

The Windows error (PermissionError: [WinError 32] The process cannot access the file because it is being used by another process: 'D:\\a\\cpython\\cpython\\build\\test_python_6880�\\test_python_worker_1068�') looks like a flake to me; I've seen it randomly show up before.

Ovsyanka83 · 2022-12-15T21:52:24Z

Lib/os.py

@@ -343,86 +343,96 @@ def walk(top, topdown=True, onerror=None, followlinks=False):
    return _walk(fspath(top), topdown, onerror, followlinks)

 def _walk(top, topdown, onerror, followlinks):


I suggest we remove the _walk function and simply put everything under walk because the second one was only necessary because of sys.audit not making sense for recursive calls.

Ovsyanka83 · 2022-12-15T22:42:42Z

Lib/os.py

-        return
+    stack = [(False, top)]
+    while stack:
+        is_result, top = stack.pop()


I don't like the is_result name for some reason. I feel like we need something better but I cannot come up with anything yet.

In case we will not find a better name, I believe we should add a comment describing what this variable signifies.

Yeah, I wasn't sure what to call it. Maybe must_yield?

Something like that would make a lot more sense, yeah. I used must_be_yielded_immediately in my PR but it's a questionable name.

Ovsyanka83 · 2022-12-15T22:42:42Z

Lib/os.py

-        if onerror is not None:
-            onerror(error)
-        return
+    stack = [(False, top)]


Will it make more sense to use a deque here? They are optimized for appending and popping while having the same interface.

I think when append and pop occur only at the end (as in this case), performance of list and deque is basically the same. When append/pop can occur at the start, then you need deque ("double-ended queue") to avoid O(n) copy.

In theory I think a deque is a slightly better fit, since we're only popping and appending (at a certain point list has to reallocate right?), but I don't think there's much of a difference in this case. I changed it to a deque, but can change back to a list if that's preferred

Yes, list has to realloc occasionally, but proportional over-allocation means that this is amortized linear cost over a long sequence of appends (as in this use case). Deque in the same usage scenario has to repeatedly allocate new "chunks" of a fixed size, so this is also linear cost. I wrote a small microbenchmark modeling "hundreds of thousands of appends, then pop them all off" and there is no detectable performance difference on my machine. I personally don't think deque has any advantage here that makes it worth the import (which has to be inline to avoid a module-level dependency, adding some cost to every call.)

Yeah, good points. I just did some rough benchmarking as well and found no real difference.

Also, I didn't find the exact cause, but adding from collections import deque to the top of Lib/os.py seemed to cause test failures under test_embed and test_site. Moving the import inside of the walk function seems to work, but at that point I agree it's not worth it.

I'll switch back to list

Ovsyanka83 · 2022-12-16T10:20:37Z

Lib/test/support/__init__.py

@@ -2178,19 +2178,23 @@ def check_disallow_instantiation(testcase, tp, *args, **kwds):
    testcase.assertRaisesRegex(TypeError, msg, tp, *args, **kwds)

 @contextlib.contextmanager
+def temp_recursion_limit(limit):


Given that it's a contextmanager, I believe the better name would be "set_recursion_limit" similar to "redirect_stdout" because the nature of a contextmanager implies that it's temporary.

carljm

Modulo still somewhat preferring list over needing to import deque, the current version seems good to me.

jonburdo · 2022-12-17T17:11:16Z

Btw, to get a rough estimate, I did a quick performance test on my machine to compare main with this branch:

# commit d4052d835bd6f1b648d533dab8c228b6e3944651
pyperf timeit -s 'import os; p = os.path.expanduser("~")' 'list(os.walk(p))' -o main.json
# commit 507b650a7d8dc01b6115f434591238699ef8ad38
pyperf timeit -s 'import os; p = os.path.expanduser("~")' 'list(os.walk(p))' -o iterative-os-walk.json
pyperf compare_to main.json iterative-os-walk.json

This gives:

Mean +- std dev: [main] 4.04 sec +- 0.04 sec -> [iterative-os-walk] 3.76 sec +- 0.04 sec: 1.07x faster

Looks like I get around a 7% improvement.

Ovsyanka83

LGTM. I am still iffy about the must_yield variable but it's the lesser evil compared to any other name I thought of.

Thank you for your hard work!

jonburdo · 2022-12-17T17:48:03Z

LGTM. I am still iffy about the must_yield variable but it's the lesser evil compared to any other name I thought of.

Yeah, I couldn't think of anything better. Maybe we'll come up with a better name in the future

Thank you for your hard work!

Happy to do it! Thanks for the help :)

JelleZijlstra

Thanks, I have a few nits.

JelleZijlstra · 2022-12-17T18:07:28Z

Lib/test/test_os.py

+        os.makedirs(os.path.join(self.walk_path, *(['d'] * 50)))
+        with set_recursion_limit(50):
+            all = list(self.walk(self.walk_path))
+        self.assertEqual(len(all), 54)


Maybe also test that the return value is correct?

Yeah, good idea

Lib/os.py

JelleZijlstra · 2022-12-17T18:07:28Z

Lib/os.py

+        if topdown:
+            yield top, dirs, nondirs
+            # Traverse into sub-directories
+            islink, join = path.islink, path.join


If we're caching these functions in locals, might as well do it outside the main while loop to micro-optimize a bit more.

Lib/os.py

Co-authored-by: Jelle Zijlstra <jelle.zijlstra@gmail.com>

JelleZijlstra · 2022-12-19T00:30:57Z

From discussion on the issue, we shouldn't backport this, so I'm going to merge it into 3.12 (only) soon unless further feedback comes up.

Thanks for your contribution!

* main: pythongh-89727: Fix os.walk RecursionError on deep trees (python#99803) Docs: Don't upload CI artifacts (python#100330) pythongh-94912: Added marker for non-standard coroutine function detection (python#99247) Correct CVE-2020-10735 documentation (python#100306) pythongh-100272: Fix JSON serialization of OrderedDict (pythonGH-100273) pythongh-93649: Split tracemalloc tests from _testcapimodule.c (python#99551) Docs: Use `PY_VERSION_HEX` for version comparison (python#100179) pythongh-97909: Fix markup for `PyMethodDef` members (python#100089) pythongh-99240: Reset pointer to NULL when the pointed memory is freed in argument parsing (python#99890) pythongh-99240: Reset pointer to NULL when the pointed memory is freed in argument parsing (python#99890) pythonGH-98831: Add DECREF_INPUTS(), expanding to DECREF() each stack input (python#100205) pythongh-78707: deprecate passing >1 argument to `PurePath.[is_]relative_to()` (pythonGH-94469)

Ovsyanka83 · 2022-12-19T20:48:33Z

That was an incredibly fast merge. Congrats!

Use a stack to implement os.walk iteratively instead of recursively to avoid hitting recursion limits on deeply nested trees.

bedevere-bot mentioned this pull request Nov 27, 2022

Change shutil.rmtree and os.walk to support very deep hierarchies #89727

Open

bedevere-bot added the awaiting review label Nov 27, 2022

jonburdo force-pushed the iterative-os-walk branch from eeca07b to 694c71e Compare Nov 30, 2022

pythongh-89727: Fix os.walk RecursionError on deep trees

99f4691

Use a stack to implement os.walk iteratively instead of recursively to avoid hitting recursion limits on deeply nested trees.

jonburdo force-pushed the iterative-os-walk branch from 694c71e to 99f4691 Compare Dec 15, 2022

carljm requested changes Dec 15, 2022

View changes

bedevere-bot added awaiting core review and removed awaiting review labels Dec 15, 2022

Ovsyanka83 suggested changes Dec 15, 2022

View changes

jonburdo added 5 commits Dec 16, 2022

add unit test to ensure os.walk is not affect by recursion limit

3552d49

move os._walk code to os.walk

3078ea6

fix blurb to mention os.walk

f37bbe8

use deque in os.walk

f26a5b8

Merge branch 'main' into iterative-os-walk

955d21b

Ovsyanka83 suggested changes Dec 16, 2022

View changes

jonburdo added 4 commits Dec 16, 2022

Merge branch 'main' into iterative-os-walk

8fbfb2e

move deque import inside os.walk

ef46eda

rename temp_recursion_limit to set_recursion_limit

e261b9f

Merge branch 'main' into iterative-os-walk

5ec53f7

carljm approved these changes Dec 16, 2022

View changes

switch back to list instead of deque for os.walk stack

507b650

jonburdo requested a review from Ovsyanka83 Dec 17, 2022

Ovsyanka83 approved these changes Dec 17, 2022

View changes

JelleZijlstra reviewed Dec 17, 2022

View changes

python deleted a comment from netlify bot Dec 18, 2022

jonburdo and others added 5 commits Dec 18, 2022

Apply suggestions from code review

1c35610

Co-authored-by: Jelle Zijlstra <jelle.zijlstra@gmail.com>

clean up os.walk comments

73138a6

test correct value in test_walk_above_recursion_limit

2814cc5

set islink and join before loop in os.walk

37f3cc7

Merge branch 'main' into iterative-os-walk

d9c766c

jonburdo requested a review from JelleZijlstra Dec 19, 2022

JelleZijlstra approved these changes Dec 19, 2022

View changes

bedevere-bot added awaiting merge and removed awaiting core review labels Dec 19, 2022

JelleZijlstra self-assigned this Dec 19, 2022

jonburdo mentioned this pull request Dec 19, 2022

gh-89727: Fix os.fwalk RecursionError on deep trees #100347

Open

JelleZijlstra merged commit 797edb2 into python:main Dec 19, 2022
16 checks passed

bedevere-bot removed the awaiting merge label Dec 19, 2022

jonburdo deleted the iterative-os-walk branch Dec 19, 2022

gh-89727: Fix os.walk RecursionError on deep trees #99803

gh-89727: Fix os.walk RecursionError on deep trees #99803

jonburdo commented Nov 27, 2022 •

edited

bedevere-bot commented Nov 27, 2022

cpython-cla-bot bot commented Nov 27, 2022 •

edited

careljonkhout commented Nov 29, 2022

carljm commented Dec 15, 2022 •

edited

carljm left a comment

carljm commented Dec 15, 2022

JelleZijlstra commented Dec 15, 2022

Ovsyanka83 Dec 15, 2022

Ovsyanka83 Dec 15, 2022

jonburdo Dec 16, 2022

Ovsyanka83 Dec 16, 2022

Ovsyanka83 Dec 15, 2022

carljm Dec 15, 2022

jonburdo Dec 16, 2022

carljm Dec 16, 2022

jonburdo Dec 16, 2022

Ovsyanka83 Dec 16, 2022

carljm left a comment

jonburdo commented Dec 17, 2022

Ovsyanka83 left a comment

jonburdo commented Dec 17, 2022

JelleZijlstra left a comment

JelleZijlstra Dec 17, 2022

jonburdo Dec 18, 2022

JelleZijlstra Dec 17, 2022

JelleZijlstra commented Dec 19, 2022

Ovsyanka83 commented Dec 19, 2022

		@@ -343,86 +343,96 @@ def walk(top, topdown=True, onerror=None, followlinks=False):
		return _walk(fspath(top), topdown, onerror, followlinks)

		def _walk(top, topdown, onerror, followlinks):

gh-89727: Fix os.walk RecursionError on deep trees #99803

gh-89727: Fix os.walk RecursionError on deep trees #99803

Conversation

jonburdo commented Nov 27, 2022 • edited

bedevere-bot commented Nov 27, 2022

cpython-cla-bot bot commented Nov 27, 2022 • edited

careljonkhout commented Nov 29, 2022

carljm commented Dec 15, 2022 • edited

carljm left a comment

carljm commented Dec 15, 2022

JelleZijlstra commented Dec 15, 2022

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

carljm left a comment

jonburdo commented Dec 17, 2022

Ovsyanka83 left a comment

jonburdo commented Dec 17, 2022

JelleZijlstra left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

JelleZijlstra commented Dec 19, 2022

Ovsyanka83 commented Dec 19, 2022

jonburdo commented Nov 27, 2022 •

edited

cpython-cla-bot bot commented Nov 27, 2022 •

edited

carljm commented Dec 15, 2022 •

edited