Using iterative filesystem walk instead of recursive

Core Development
21

Ah, the recursive one might’ve been slower because of the recursive yielding:

Worst case quadratic time, e.g., with 1000 dirs at depth 1000, it had a million yields.

(That quadratic time recursive yielding is also a still open general question of mine.)

Demo, walking 'd/' * 800 takes ~4 times as long as 'd/' * 400 (because it’s twice as many dirs and they get yielded through twice as many generator iterators):

depth 400:  26 ms
depth 800: 105 ms
depth 400:  28 ms
depth 800: 101 ms
depth 400:  25 ms
depth 800: 111 ms
Code 
import os
from time import time

for n in [400, 800] * 3:
    os.makedirs('d/' * n)
    t0 = time()
    for _ in range(10):
      for _ in os.walk('.'):
        pass
    print(f'depth {n}: {round((time() - t0) * 100):3} ms')
    os.removedirs('d/' * n)

Try it online!

2 Likes