diff options
author | Tavian Barnes <tavianator@tavianator.com> | 2023-08-21 13:58:27 -0400 |
---|---|---|
committer | Andrew Gallant <jamslam@gmail.com> | 2023-09-20 11:52:42 -0400 |
commit | d938e955af7a39ac0245b1ce84924f7f4a2141ac (patch) | |
tree | 613dbc09c36628cffc3a85de8fc1512e943eb7e4 /CHANGELOG.md | |
parent | cad1f5fae2e4b48d8942add9dc4c950a170b5d2e (diff) |
ignore: use work-stealing stack instead of Arc<Mutex<Vec<_>>>
This represents yet another iteration on how `ignore` enqueues and
distributes work in parallel. The original implementation used a
multi-producer/multi-consumer thread safe queue from crossbeam. At some
point, I migrated to a simple `Arc<Mutex<Vec<_>>>` and treated it as a
stack so that we did depth first traversal. This helped with memory
usage in very wide directories.
But it turns out that a naive stack-behind-a-mutex can be quite a bit
slower than something that's a little smarter, such as a work-stealing
stack used in this commit. My hypothesis for why this helps is that
without the stealing component, work distribution can get stuck in
sub-optimal configurations that depend on which directory entries get
assigned to a particular worker. It's likely that this can result in
some workers getting "more" work than others, just by chance, and thus
remain idle. But the work-stealing approach heads that off.
This does re-introduce a dependency on parts of crossbeam which is kind
of a bummer, but it's carrying its weight for now.
Closes #1823, Closes #2591
Ref https://github.com/sharkdp/fd/issues/28
Diffstat (limited to 'CHANGELOG.md')
-rw-r--r-- | CHANGELOG.md | 5 |
1 files changed, 5 insertions, 0 deletions
diff --git a/CHANGELOG.md b/CHANGELOG.md index 05a2a781..9d47a8ca 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -8,6 +8,11 @@ Unreleased changes. Release notes have not yet been written. `rg -B1 -A2`. That is, `-A` and `-B` no longer completely override `-C`. Instead, they only partially override `-C`. +Performance improvements: + +* [PERF #2591](https://github.com/BurntSushi/ripgrep/pull/2591): + Parallel directory traversal now uses work stealing for faster searches. + Feature enhancements: * Added or improved file type filtering for Ada, DITA, Elixir, Fuchsia, Gentoo, |