Async, parallel directory I/O

[tavianator]

bfs 3.0 will do opendir() + readdir() asynchronously and in parallel.

Preparation

• Thread safety #99

Implementaton

• Async I/O queue #100

Optimization

• Do readdir()/getdents() from the background thread
• Pre-allocate the highest FD to avoid kernel contention resizing the FD table
• I/O queue scalability #102
• Arena allocation #104
• io_uring #65
  • openat()
  • getdents() (if added to io_uring)
  • statx()?

Benchmarking

Try to quantify improvement and avoid regressions in these scenarios:

• Complete traversal of

  • Small trees (e.g. bfs itself)
  • Medium trees (e.g. Linux)
  • Large trees (e.g. Android)

• Early termination, as a proxy for interactive use (bfs -name <something unique> -quit)

  • Shallow file
  • Medium file
  • Deep file

• Search strategies

  • bfs
  • dfs
  • ids
  • eds

• Cold page/buffer cache

[tavianator]

This is now done! All that's left is #65.

Command	Mean [s]	Min [s]	Max [s]	Relative
./bfs-2.6.3 ~ -false	4.835 ± 0.021	4.816	4.891	1.82 ± 0.04
./bfs-a1490d9 ~ -false	2.661 ± 0.063	2.582	2.768	1.00
fd -u '^$' ~	7.085 ± 0.022	7.059	7.128	2.66 ± 0.06