[PR #574] perf(walk): flatten recursion via rayon::scope, drop -S stack-size knob #557

New Issue

2026-06-08T11:29:23+03:00

zhus commented

2026-06-08 11:29:23 +03:00

📋 Pull Request Information

Original PR: https://github.com/bootandy/dust/pull/574
Author: @arcuru
Created: 5/12/2026
Status: 🔄 Open

Base: master ← Head: walker-scope

📝 Commits (1)

aa433ae perf(walk): flatten recursion via rayon::scope, drop -S stack-size knob

📊 Changes

12 files changed (+433 additions, -317 deletions)

View changed files

📝 Cargo.lock (+9 -141)
📝 Cargo.toml (+0 -1)
📝 README.md (+1 -1)
📝 completions/_dust (+2 -2)
📝 completions/_dust.ps1 (+2 -2)
📝 completions/dust.elv (+2 -2)
📝 completions/dust.fish (+1 -1)
📝 man-page/dust.1 (+1 -1)
📝 src/cli.rs (+2 -3)
📝 src/config.rs (+0 -9)
📝 src/dir_walker.rs (+397 -102)
📝 src/main.rs (+16 -52)

📄 Description

Replaces the recursive walk() function with a scope-based work queue. Each directory becomes an independent rayon task that spawns subtasks for its subdirectories, then completes. An AtomicUsize pending counter alongside a Mutex<Vec<Node>> for children, combined with an Arc parent chain,
iteratively bubbles completions up to the root.

Stack depth is now O(1) regardless of tree depth, so the -S/--stack-size flag (and its 1 GiB-per-thread heuristic at startup) are no longer needed. sysinfo is dropped with them.

Benchmarks

target	before	after	speedup
balanced (1000 dirs / 20k files)	270 ms	9.5 ms	28.4×
wide_flat (1 dir, 100k files)	361 ms	79 ms	4.6×
deep_narrow (1500-deep chain)	511 ms	157 ms	3.3×
home (200k entries, ZFS)	440 ms	188 ms	2.3×
/nix/store (25.6M paths, ZFS)	48 s	27 s	1.8×

The gains primarily come from 3 places:

Removing the par_bridge iterator mutex
Better work distribution with rayon
Dropping sysinfo::System::new_all() (costs >100ms on my host and is unnecessary even on the old path)

Further Work

I have a stack of changes on top of this with further work, most of which is fairly minor improvements but some edge cases benefit a lot. ~~e.g. using AT_STATX_DONT_SYNC can give big speed boosts for networked drives from my testing. Let me know if you'd be interested in further changes, I have to clean them up a little bit.~~ Nvm I got bored - #575

The main blocker here becomes the stat calls on everything. For cold caches, slow drives, and networked drives they still benefit quite a bit from more parallelism in the stat calls. In one case I was able to see a 14x improvement for a networked filesystem by running everything async, but that heavily regressed the more common warm cache performance.

After experimenting with io_uring, async rust, batching, and more, I didn't find anything that was a pure win for the common case and also handled the edge cases well without a major rewrite. To squeeze much more performance out of the core loop in all scenarios you likely need to switch to a custom threadpool that can be resized as needed. I think that's what ripgrep does. I suspect further speed boosts probably aren't desirable here.

Increasing the thread count with -T is easy though and would get perf conscious people most of the way there. In the warm cache case you don't want to increase that above core count so the default still shouldn't change.

AI-Usage

I am a real human person who is knowledgeable in this area. I did use AI to assist with this change and as such I labeled commits with "Assisted-by:" following the same scheme used by Fedora.

_{🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.}

## 📋 Pull Request Information **Original PR:** https://github.com/bootandy/dust/pull/574 **Author:** [@arcuru](https://github.com/arcuru) **Created:** 5/12/2026 **Status:** 🔄 Open **Base:** `master` ← **Head:** `walker-scope` --- ### 📝 Commits (1) - [`aa433ae`](https://github.com/bootandy/dust/commit/aa433ae7ff7c1f23bfbdd13fba551f8074abff87) perf(walk): flatten recursion via rayon::scope, drop -S stack-size knob ### 📊 Changes **12 files changed** (+433 additions, -317 deletions) <details> <summary>View changed files</summary> 📝 `Cargo.lock` (+9 -141) 📝 `Cargo.toml` (+0 -1) 📝 `README.md` (+1 -1) 📝 `completions/_dust` (+2 -2) 📝 `completions/_dust.ps1` (+2 -2) 📝 `completions/dust.elv` (+2 -2) 📝 `completions/dust.fish` (+1 -1) 📝 `man-page/dust.1` (+1 -1) 📝 `src/cli.rs` (+2 -3) 📝 `src/config.rs` (+0 -9) 📝 `src/dir_walker.rs` (+397 -102) 📝 `src/main.rs` (+16 -52) </details> ### 📄 Description Replaces the recursive `walk()` function with a scope-based work queue. Each directory becomes an independent rayon task that spawns subtasks for its subdirectories, then completes. An `AtomicUsize` pending counter alongside a `Mutex<Vec<Node>>` for children, combined with an `Arc` parent chain, iteratively bubbles completions up to the root. Stack depth is now O(1) regardless of tree depth, so the `-S`/`--stack-size` flag (and its 1 GiB-per-thread heuristic at startup) are no longer needed. `sysinfo` is dropped with them. ## Benchmarks | target | before | after | speedup | | --------------------------------- | -----: | -----: | --------: | | balanced (1000 dirs / 20k files) | 270 ms | 9.5 ms | **28.4×** | | wide_flat (1 dir, 100k files) | 361 ms | 79 ms | **4.6×** | | deep_narrow (1500-deep chain) | 511 ms | 157 ms | **3.3×** | | home (200k entries, ZFS) | 440 ms | 188 ms | 2.3× | | /nix/store (25.6M paths, ZFS) | 48 s | 27 s | 1.8× | The gains primarily come from 3 places: 1. Removing the par_bridge iterator mutex 2. Better work distribution with rayon 3. Dropping `sysinfo::System::new_all()` (costs >100ms on my host and is unnecessary even on the old path) ## Further Work I have a stack of changes on top of this with further work, most of which is fairly minor improvements but some edge cases benefit a lot. ~~e.g. using AT_STATX_DONT_SYNC can give big speed boosts for networked drives from my testing. Let me know if you'd be interested in further changes, I have to clean them up a little bit.~~ Nvm I got bored - #575 The main blocker here becomes the stat calls on everything. For cold caches, slow drives, and networked drives they still benefit quite a bit from more parallelism in the stat calls. In one case I was able to see a 14x improvement for a networked filesystem by running everything async, but that heavily regressed the more common warm cache performance. After experimenting with io_uring, async rust, batching, and more, I didn't find anything that was a pure win for the common case and also handled the edge cases well without a major rewrite. To squeeze much more performance out of the core loop in all scenarios you likely need to switch to a custom threadpool that can be resized as needed. I think that's what ripgrep does. I suspect further speed boosts probably aren't desirable here. Increasing the thread count with `-T` is easy though and would get perf conscious people most of the way there. In the warm cache case you don't want to increase that above core count so the default still shouldn't change. ## AI-Usage I am a real human person who is knowledgeable in this area. I did use AI to assist with this change and as such I labeled commits with "Assisted-by:" following the same scheme used by [Fedora](https://docs.fedoraproject.org/en-US/council/policy/ai-contribution-policy/). --- <sub>🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.</sub>

zhus added the pull-request label 2026-06-08 11:29:23 +03:00

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: bootandy/archived-dust#557