Functions that do a recursive filesystem walk such as os.walk, pathlib.Path.walk, and shutil.rmtree hit the recursion limit on deep directory trees. I suggest these functions be changed to be iterative rather than recursive. I’d think this would improve performance as well. It’s pretty easy to hit the limit especially if generating directory trees programmatically, and this prevents walking arbitrary trees without adjusting the recursion limit.
I wanted to do this for a while but never had the courage for some reason. Yet your work has inspired me to try to do this for pathlib.Path.walk! Thanks for your commits!
I haven’t seen such a case in my career. However, I also do not see much benefit in using a recursive solution. It is slightly simpler but it is also slightly slower and puts an unnecessary limitation on python’s walk which could become problematic some day.
And the changes proposed in the issue above do not make scaling or working with walk problematic so I think they are pretty much worth the slightly increased complexity.
Update:
Forgot to mention: the proposed changes also let us get rid of an extra Path._walk method and os.walk function.
I thought about this idea, but decided that it is easier to increase the recursion limit than to rewrite every recursive filesystem walk in the stdlib. Increasing the recursion limit is more universal solution, and in recent Python releases there is no physical limit on recursion in pure Python code.
I think that we can increase the default recursion limit by order or two. But the code which consumes the C stack should increase the depth by more than 1, to prevent the stack overflow. @markshannon
I don’t have anything to add except that this is an excellent point. I’ve faced similar problems with IMAP folders hundreds of levels deep, so it’s not unbelievable that this could be a problem with regular filesystem directories.
@jonburdo and I have measured our versions and I think there was a 6%-7% increase in speed in each. I measured by walking through the entire cpython repository.
That’s not a very good benchmark because it is the one we have. Besides it makes sense: less function calls almost always means better performance, especially if all other operations are the same. Unless, of course, we have JIT which we don’t :))
I’m not saying it’s worse. I mean, code simplicity wise it’s worse of course but let’s ignore that. I’m saying it’s different. If you remove the function calls (win!) one now pay something for that by having to manually handle the stack (lose!). So one has two numbers X and Y and the win/loss is X-Y. It matters if X is bigger than Y or not. One can’t just say that less function calls means it’s faster.
Aaaanyway, if you see a few percentage points of a win on one scenario, it would be very good to see if that generalizes, it’s certainly reason for optimism.
Me, too. Doesn’t match what I’ve seen previously. When people replaced built-in recursion by implementing their own iteratively in Python, it got slower.
It isn’t even fewer function calls. Instead of the recursive call, you have the stack.append(...) call.
