Hey@serhiy-storchaka, just for context: this change doesn't provide much of a speedup in itself, but it enables more significant speedups seen inGH-119186. I've separated it out here because it's an observable change that breaks a test. But I suspect that doesn't matter as thescandir() result order is arbitrary and the order of sibling visits can't be influenced. What do you think? Thank you!

Ifos.walk(topdown=False) reverses the order of visiting directories, this should be fixed.

It presently visits sibling directories in the same order they appear indirnames.

What I'm proposing here is that we don'tneed to visit sibling directories in the same order they appear indirnames in bottom-up mode, because:

1. The order is arbitrary (it comes fromos.scandir())
2. Users aren't able to influence the order mid-walk by re-orderingdirnames (this is only possible in top-down mode)

Perhaps a worked example would be helpful? I can put one together.

Here's an example, first with the currentmain:

>>>os.mkdir('mydir')>>>os.mkdir('mydir/subdir1')>>>os.mkdir('mydir/subdir2')>>>forentryinos.walk('mydir',topdown=False):...print(entry)...     ('mydir/subdir2', [], [])('mydir/subdir1', [], [])('mydir', ['subdir2','subdir1'], [])

And with this PR:

>>>forentryinos.walk('mydir',topdown=False):...print(entry)...     ('mydir/subdir1', [], [])('mydir/subdir2', [], [])('mydir', ['subdir2','subdir1'], [])

Note how the entry forsubdir1 is now yielded beforesubdir2, and how this no longer corresponds to the order indirnames formydir.

If we think the new behaviour is acceptable (e.g. because we never guaranteed the order of sibling visits) then it unlocks an optimization: we can add paths to the stackwhile scanning directories rather than in a separate loop afterwards.

I think that it would be confusing ifos.walk(),grep.grep(), or manual recursive use ofos.listdir() andos.scandir() produce different results. The order depends on the file system, but at least it is consistent.

The fact that the current code needs to reverse the lists of directories is just an implementation detail. It is not exposed to the user. If the code useddeque instead of a list, it would not need to reverse them.

BTW, how much it makes difference? What it in comparison of usingdeque?

That makes sense, thanks.

BTW, how much it makes difference?

Taking into account the speedups inGH-119186 andGH-121433, it's about 1% foros.walk() and 6% foros.fwalk(). Nothing special.

What it in comparison of using deque?

I'll get back to you.

Hm, thedeque would help with a breadth-first implementation, but I don't think it helps here without alot of code changes. I'll close this PR and its two dependents.