Async, parallel directory I/O
tavianator opened this issue · 1 comments
tavianator commented
bfs 3.0 will do opendir() + readdir() asynchronously and in parallel.
Preparation
Implementaton
Optimization
- Do readdir()/getdents() from the background thread
- Pre-allocate the highest FD to avoid kernel contention resizing the FD table
- #102
- #104
- #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 commented
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 |