Skip to content

du: Add parallel traversal for performance#9195

Closed
quantum-encoding wants to merge 4 commits intouutils:mainfrom
quantum-encoding:du-parallel-optimization
Closed

du: Add parallel traversal for performance#9195
quantum-encoding wants to merge 4 commits intouutils:mainfrom
quantum-encoding:du-parallel-optimization

Conversation

@quantum-encoding
Copy link
Copy Markdown
Contributor

@quantum-encoding quantum-encoding commented Nov 8, 2025

Introduces parallel directory traversal using Rayon to significantly improve performance on large directory trees.

The implementation is conservative, only activating on directories with more than 4 subdirectories to avoid threading overhead on small workloads.

Benchmark on a 219 GB directory (172k subdirs, 1.17M files):

Sequential: 8.880s

Parallel: 4.687s

Speedup: 1.90x

@sylvestre
Copy link
Copy Markdown
Contributor

sylvestre commented Nov 8, 2025

please provide benchmark with hyperfine gnu

@github-actions
Copy link
Copy Markdown

github-actions bot commented Nov 8, 2025

GNU testsuite comparison:

Skipping an intermittent issue tests/misc/tee (passes in this run but fails in the 'main' branch)

@sylvestre sylvestre mentioned this pull request Nov 8, 2025
Merged
@quantum-encoding @sylvestre
du: Add parallel traversal for performance
0fbdc11 
Introduces parallel directory traversal using Rayon to significantly
improve performance on large directory trees.

The implementation is conservative, only activating on directories with
more than 4 subdirectories to avoid threading overhead on small workloads.

Benchmark on a 219 GB directory (172k subdirs, 1.17M files):

    Sequential: 8.880s

    Parallel: 4.687s

    Speedup: 1.90x
@quantum-encoding @sylvestre
Fix formatting (cargo fmt)
2d4023d
@quantum-encoding @sylvestre
Add spell-checker ignore directive for mpsc
16bb63b
@sylvestre sylvestre force-pushed the du-parallel-optimization branch from d15d7bc to 16bb63b Compare November 8, 2025 19:30
@codspeed-hq
Copy link
Copy Markdown

codspeed-hq bot commented Nov 8, 2025 •
edited
Loading

CodSpeed Performance Report

Merging #9195 will not alter performance

Comparing quantum-encoding:du-parallel-optimization (7aa6912) with main (2d718f2)

Summary

✅ 127 untouched
⏩ 6 skipped1

Footnotes

  1. 6 benchmarks were skipped, so the baseline results were used instead. If they were deleted from the codebase, click here and archive them to remove them from the performance reports. ↩

@github-actions
Copy link
Copy Markdown

github-actions bot commented Nov 8, 2025

GNU testsuite comparison:

Skipping an intermittent issue tests/misc/tee (passes in this run but fails in the 'main' branch)

@quantum-encoding
Copy link
Copy Markdown
Contributor Author

quantum-encoding commented Nov 8, 2025

[founder@quantum-encoding-ltd coreutils]$ unset LD_PRELOAD
[founder@quantum-encoding-ltd coreutils]$ ./run_full_benchmark.sh
=== SYSTEM INFO ===
Date: Sat Nov 8 09:05:03 PM CET 2025
CPU: 11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz
Threads: 16
OS: 6.17.5-arch1-1

=== BUILD ===
[libwarden.so] 🛡️ Guardian Shield V7.2 - Scanning background process...
Finished release profile [optimized] target(s) in 0.08s

=== BENCHMARK 1: random stuff (219 GB, 172K dirs, 1.17M files) ===
Benchmark 1: du -sh /home/founder/storage_transfer
Time (mean ± σ): 2.397 s ± 0.015 s [User: 0.269 s, System: 2.124 s]
Range (min … max): 2.379 s … 2.420 s 5 runs

Benchmark 2: ./target/release/du -sh /home/founder/storage_transfer
Time (mean ± σ): 3.348 s ± 0.027 s [User: 0.768 s, System: 2.786 s]
Range (min … max): 3.325 s … 3.395 s 5 runs

Summary
du -sh /home/founder/storage_transfer ran
1.40 ± 0.01 times faster than ./target/release/du -sh /home/founder/storage_transfer

=== BENCHMARK 2: /usr ===
Benchmark 1: sudo du -sh /usr
Time (mean ± σ): 1.702 s ± 0.173 s [User: 0.141 s, System: 0.224 s]
Range (min … max): 1.537 s … 1.979 s 5 runs

Benchmark 2: sudo ./target/release/du -sh /usr
Time (mean ± σ): 2.099 s ± 0.262 s [User: 0.147 s, System: 0.229 s]
Range (min … max): 1.889 s … 2.410 s 5 runs

Warning: The first benchmarking run for this command was significantly slower than the rest (2.361 s). This could be caused by (filesystem) caches that were not filled until after the first run. You are already using the '--warmup' option which helps to fill these caches before the actual benchmark. You can either try to increase the warmup count further or re-run this benchmark on a quiet system in case it was a random outlier. Alternatively, consider using the '--prepare' option to clear the caches before each timing run.

Summary
sudo du -sh /usr ran
1.23 ± 0.20 times faster than sudo ./target/release/du -sh /usr

=== BENCHMARK 3: /usr/lib ===
Benchmark 1: sudo du -sh /usr/lib
Time (mean ± σ): 1.194 s ± 0.090 s [User: 0.143 s, System: 0.217 s]
Range (min … max): 1.095 s … 1.313 s 5 runs

Benchmark 2: sudo ./target/release/du -sh /usr/lib
Time (mean ± σ): 1.187 s ± 0.137 s [User: 0.147 s, System: 0.221 s]
Range (min … max): 1.052 s … 1.402 s 5 runs

Summary
sudo ./target/release/du -sh /usr/lib ran
1.01 ± 0.14 times faster than sudo du -sh /usr/lib

=== BENCHMARK 4: /usr/share ===
Benchmark 1: sudo du -sh /usr/share
Time (mean ± σ): 1.344 s ± 0.162 s [User: 0.145 s, System: 0.220 s]
Range (min … max): 1.144 s … 1.560 s 5 runs

Benchmark 2: sudo ./target/release/du -sh /usr/share
Time (mean ± σ): 1.409 s ± 0.184 s [User: 0.147 s, System: 0.221 s]
Range (min … max): 1.198 s … 1.643 s 5 runs

Summary
sudo du -sh /usr/share ran
1.05 ± 0.19 times faster than sudo ./target/release/du -sh /usr/share

=== BENCHMARK 5: /var ===
Benchmark 1: sudo du -sh /var
Time (mean ± σ): 973.0 ms ± 194.7 ms [User: 145.0 ms, System: 205.6 ms]
Range (min … max): 660.8 ms … 1179.2 ms 5 runs

Benchmark 2: sudo ./target/release/du -sh /var
Time (mean ± σ): 767.2 ms ± 115.4 ms [User: 148.9 ms, System: 201.8 ms]
Range (min … max): 664.1 ms … 944.7 ms 5 runs

Summary
sudo ./target/release/du -sh /var ran
1.27 ± 0.32 times faster than sudo du -sh /var

[founder@quantum-encoding-ltd coreutils]$ ./benchmark_multi_dirs.sh
=== MULTI-DIRECTORY BENCHMARK ===

[1/3] Benchmarking /usr/lib
Benchmark 1: sudo du -sh /usr/lib
Time (mean ± σ): 1.273 s ± 0.099 s [User: 0.150 s, System: 0.209 s]
Range (min … max): 1.196 s … 1.436 s 5 runs

Benchmark 2: sudo ./target/release/du -sh /usr/lib
Time (mean ± σ): 1.228 s ± 0.111 s [User: 0.147 s, System: 0.209 s]
Range (min … max): 1.104 s … 1.349 s 5 runs

Summary
sudo ./target/release/du -sh /usr/lib ran
1.04 ± 0.12 times faster than sudo du -sh /usr/lib

[2/3] Benchmarking /usr/share
Benchmark 1: sudo du -sh /usr/share
Time (mean ± σ): 1.193 s ± 0.122 s [User: 0.146 s, System: 0.216 s]
Range (min … max): 1.032 s … 1.308 s 5 runs

Benchmark 2: sudo ./target/release/du -sh /usr/share
Time (mean ± σ): 1.358 s ± 0.188 s [User: 0.148 s, System: 0.215 s]
Range (min … max): 1.177 s … 1.644 s 5 runs

Summary
sudo du -sh /usr/share ran
1.14 ± 0.20 times faster than sudo ./target/release/du -sh /usr/share

[3/3] Benchmarking /var
Benchmark 1: sudo du -sh /var
Time (mean ± σ): 850.7 ms ± 133.3 ms [User: 149.7 ms, System: 204.4 ms]
Range (min … max): 753.8 ms … 1078.1 ms 5 runs

Benchmark 2: sudo ./target/release/du -sh /var
Time (mean ± σ): 908.9 ms ± 208.4 ms [User: 146.0 ms, System: 212.2 ms]
Range (min … max): 673.8 ms … 1102.7 ms 5 runs

Summary
sudo du -sh /var ran
1.07 ± 0.30 times faster than sudo ./target/release/du -sh /var
[founder@quantum-encoding-ltd coreutils]$

@sylvestre
Copy link
Copy Markdown
Contributor

sylvestre commented Feb 4, 2026

still draft for a while
please reopen when ready (or ping me)
thanks

@sylvestre sylvestre closed this Feb 4, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@quantum-encoding @sylvestre