And now something completly differenet: fast_bottom-up.patch, fast bottom-up, but "slow" top-down.

In bottom-up mode (topdown=False), use entry.path and entry.is_symlink() => optimization compared to Python 3.4 (avoid one call to os.stat()).

In top-down mode (topdown=True, default), use os.path.join() and os.path.islink() => no change compared to Python 3.4 on this part. More globally, os.walk() should still be much faster in Python 3.5 than in Python 3.5 thanks to entry.is_dir() which avoids a call to os.path.isdir() (and so os.stat()).

Correctness matters more than performances!

> 2. Accept and document behavior change. This will break someone's code. :-(
> 3. Left os.walk as was (or only partially optimized as in 1), and add a new function with new behavior.
> 4. Add new boolean parameter that control behavior to os.walk().

Sorry but all these options sucks :-p

> 5. Try to detect when dir list or filesystem were changed. Victor's patch does the first. For the second we can check if top directory inode and mtime were changed. But I afraid this wouldn't decrease a number of system calls.

By experience, it's very hard to write portable code. Even if we find a way to detect FS change on some platforms, it will not work on some other platforms.