Optimize dependency file search I tried to look into the slowdown reported in https://github.com/rust-lang/cargo/issues/16665. I created a Rust hello world program, and used this Python script to create a directory containing 200k files: ```python from pathlib import Path dir = Path("deps") dir.mkdir(parents=True, exist_ok=True) for i in range(200000): path = dir / f"file{i:07}.o" with open(path, "w") as f: f.write("\n") ``` Then I tried to do various small microoptimalizations and simplifications to the code that iterates the search directories. Each individual commit improved performance, with the third one having the biggest effect. Here are the results on `main` vs the last commit with the stage1 compiler on Linux, using `hyperfine "rustc +stage1 src/main.rs -L deps" -r 30` (there's IO involved, so it's good to let it run for a while): ```bash Benchmark 1: rustc +stage1 src/main.rs -L deps Time (mean ± σ): 299.4 ms ± 2.7 ms [User: 161.9 ms, System: 144.9 ms] Range (min … max): 294.8 ms … 307.1 ms 30 runs Benchmark 1: rustc +stage1 src/main.rs -L deps Time (mean ± σ): 208.1 ms ± 4.5 ms [User: 87.3 ms, System: 128.7 ms] Range (min … max): 202.4 ms … 219.6 ms 30 runs ``` Would be cool if someone could try this on macOS (maybe @ehuss - not sure if you have macOS or you only commented about its behavior on the Cargo issue :) ). I also tried to prefilter the paths (not in this PR); right now we load everything and then we filter files with given prefixes, that's wasteful. Filtering just files starting with `lib` would get us down to ~150ms here. (The baseline without `-L` is ~80ms on my PC). The rest of the 70ms is essentially allocations from iterating the directory entries and sorting. That would be very hard to change - iterating the directory entries (de)allocates a lot of intermediate paths :( We'd have to implement the iteration by hand with either arena allocation, or at least some better management of memory. r? @nnethercote