Thanks, Victor.

I haven't quite grokked all the changes here -- it's gotten somewhat more complicated with the scandir_it and manual next() call -- but I ran some benchmarks (via a hacked version of my scandir project's benchmark.py). The results were surprising, and in a good way:

Dev version in hg (no extra islink syscall):
--------------------------------------------
Windows: 13.1x as fast (68.8x as fast in funky caching mode)
Linux: 7.8x as fast

With Victor's fast_bottom_up patch (100% correct behaviour):
--------------------------------------------
Windows: 9.4x as fast (50.2x as fast in funky caching mode)
Linux: 6.5x as fast

So os.walk() will still be 10x as fast on Windows if you apply this patch, and 6x as fast on my Linux VM. I haven't dug too deeply to know quite why the numbers are this good, especially on Linux, but that's what I'm seeing, which is great!