# How ripgrep's Parallel Directory Traversal Works: A Technical Deep Dive

> Discover how ripgrep achieves efficient parallel directory traversal with its custom WorkParallel iterator and work-stealing deque for balanced load handling. Optimize your searches now.

- Repository: [Andrew Gallant/ripgrep](https://github.com/BurntSushi/ripgrep)
- Tags: deep-dive
- Published: 2026-03-05

---

**ripgrep traverses directories in parallel using `WalkParallel`, a custom iterator built on crossbeam's work-stealing deque where per-thread `Worker` instances pop directories from local LIFO stacks and steal batches from peers to balance load.**

ripgrep (rg) is renowned for its speed, largely due to how it walks directory trees concurrently while respecting ignore rules. This article examines the internal mechanics of ripgrep's parallel directory traversal as implemented in the `ignore` crate within the BurntSushi/ripgrep repository.

## The Architecture of ripgrep's Parallel Directory Traversal

At the heart of the system is a work-stealing scheduler that distributes directory entries across threads while maintaining depth-first semantics.

### Core Data Structures

The implementation revolves around five primary types defined in [`crates/ignore/src/walk.rs`](https://github.com/BurntSushi/ripgrep/blob/main/crates/ignore/src/walk.rs):

- **`WalkParallel`** – Holds the configuration (paths, ignore root, thread count, etc.) and spawns the workers.
- **`Worker<'s>`** – The per-thread entity that both consumes work (directories) and produces new work for child entries.
- **`Stack`** – A LIFO deque (`crossbeam_deque::Worker`) used as a **work-stealing stack**. Depth-first order reduces memory pressure because a deep branch is exhausted before many sibling entries accumulate.
- **`Work`** – Bundles a `DirEntry`, the current `Ignore` matcher, and the optional *root device* number (used for `same_file_system`).
- **`Message`** – Either a `Work` or a `Quit` signal that travels between workers.

### The Work-Stealing Stack

ripgrep uses the **crossbeam-deque** crate to implement a work-stealing queue with LIFO semantics. Each thread maintains a local `Stack` (a `crossbeam_deque::Worker<Message>`) for depth-first processing. When a worker exhausts its local stack, it attempts to **steal** a batch of work from another thread's stealer (`crossbeam_deque::Stealer`), ensuring load balancing without a central coordinator.

## Three Stages of Parallel Traversal

The traversal proceeds through three distinct phases orchestrated by `WalkParallel`.

### Stage 1: Building the WalkParallel Iterator

The process begins with `WalkBuilder::build_parallel()`, which creates a `WalkParallel` object that captures all user-specified options (ignore rules, depth limits, symlink handling, etc.).

```rust
// crates/ignore/src/walk.rs
let walker = WalkBuilder::new(".")
    .threads(4)
    .build_parallel();

```

This method returns a configured `WalkParallel` struct ready to spawn workers.

### Stage 2: Spawning Worker Threads

`WalkParallel::run` (or the higher-level `WalkParallel::visit`) determines the number of threads (`WalkParallel::threads`) and spawns one **`Worker`** per thread. Each worker owns a **`Stack`** (a per-thread LIFO queue) and shares the list of *stealers* for other workers.

The initialization distributes root paths round-robin across the worker stacks:

```rust
// Simplified from walk.rs
fn new_for_each_thread(threads: usize, init: Vec<Message>) -> Vec<Stack> {
    // Creates one Deque per thread and distributes initial work
}

```

### Stage 3: Processing Work Items

Workers repeatedly call `Worker::get_work()` → `Stack::pop()`. The `pop` operation first tries the local deque and, if empty, **steals** a batch from another worker (`Stack::steal`).

A work item is a `Message::Work(Work)` that wraps a `DirEntry` and the associated ignore matcher. The worker then executes `Worker::run_one` which:

- Checks depth, symlink, and *same-file-system* constraints.
- Calls the user-provided visitor (the callback supplied by `run`/`visit`).
- Reads the directory (`Work::read_dir`) and, for every child entry, runs `Worker::generate_work` to decide whether to **push** a new `Work` onto the stack or ignore it (respecting ignore files, size limits, filters, etc.).

```rust
// Conceptual flow in walk.rs
loop {
    match self.get_work() {
        Some(Message::Work(work)) => self.run_one(work, &mut visitor),
        Some(Message::Quit) | None => break,
    }
}

```

## How Work-Stealing Balances the Load

The work-stealing algorithm ensures threads remain busy even with unbalanced directory trees:

1. **Initial distribution** – Root paths are distributed round-robin across thread stacks.
2. **Local pop** – Workers process their own LIFO stacks depth-first, exhausting deep branches before moving to siblings.
3. **Steal if empty** – When a worker's stack is empty, it iterates over all *stealers* (skipping its own) and attempts `steal_batch_and_pop`. The first successful steal yields a batch of `Message::Work` items.

```rust
fn steal(&self) -> Option<Message> {
    let (left, right) = self.stealers.split_at(self.index);
    let right = &right[1..];          // skip self
    right.iter()
         .chain(left.iter())
         .map(|s| s.steal_batch_and_pop(&self.deque))
         .find_map(|s| s.success())
}

```

This **batch stealing** reduces synchronization overhead compared to stealing single items, while the LIFO ordering maintains depth-first semantics that minimize memory pressure.

## Integrating Ignore Rules During Parallel Traversal

ripgrep respects `.gitignore` and other ignore files even while traversing in parallel. Each `Work` struct carries a clone of the current `Ignore` matcher (`work.ignore`). When a directory is entered, `work.add_parents()` augments the matcher with any `.gitignore`, `.ignore`, etc. found in that directory.

When generating child work via `Worker::generate_work`, the function first checks `should_skip_entry`, which consults the matcher and immediately discards entries that match an ignore rule. Otherwise, it pushes the child `Work` onto the stack. This design ensures **ignore evaluation is done exactly once per directory**, even across parallel threads, preventing redundant filesystem checks.

## Practical Code Examples

### Simple Parallel Walk

Print every file path using a parallel walker:

```rust
use ignore::WalkBuilder;
use ignore::WalkState;

fn main() {
    // Build a parallel walker starting at the current directory
    let walker = WalkBuilder::new(".")
        .threads(4)
        .build_parallel();

    // Run the parallel walk; the closure receives each DirEntry (or an Error)
    walker.run(|| {
        Box::new(move |result| {
            match result {
                Ok(entry) => println!("{}", entry.path().display()),
                Err(err) => eprintln!("error: {}", err),
            }
            WalkState::Continue
        })
    });
}

```

### Early Exit After Finding a Match

Stop all workers immediately upon finding the first match:

```rust
use ignore::{WalkBuilder, WalkState};

fn find_first_match(pattern: &str) {
    let builder = WalkBuilder::new(".")
        .threads(8)
        .max_depth(Some(5));

    builder.build_parallel().run(|| {
        let pat = pattern.to_owned();
        Box::new(move |res| {
            if let Ok(entry) = res {
                if entry.path().to_string_lossy().contains(&pat) {
                    println!("found: {}", entry.path().display());
                    return WalkState::Quit;
                }
            }
            WalkState::Continue
        })
    });
}

```

Returning `WalkState::Quit` triggers the atomic `quit_now` flag, causing all workers to stop as soon as possible.

### Filtering Entries

Exclude specific directories using a custom filter:

```rust
use ignore::{WalkBuilder, WalkState};

let builder = WalkBuilder::new(".")
    .filter_entry(|e| !e.path().ends_with("target"))
    .build_parallel();

builder.run(|| {
    Box::new(move |res| {
        if let Ok(entry) = res {
            println!("{}", entry.path().display());
        }
        WalkState::Continue
    })
});

```

The filter is stored in `WalkParallel` and consulted in `Worker::generate_work` before pushing work onto the stack.

## Summary

- **ripgrep's parallel directory traversal** is implemented via `WalkParallel` in [`crates/ignore/src/walk.rs`](https://github.com/BurntSushi/ripgrep/blob/main/crates/ignore/src/walk.rs), built on the `crossbeam-deque` work-stealing stack.
- **Depth-first traversal** is achieved through per-thread LIFO stacks, minimizing memory pressure by exhausting deep branches before handling siblings.
- **Work-stealing** ensures load balancing: idle workers steal batches of directories from busy peers using `steal_batch_and_pop`.
- **Ignore rule integration** happens exactly once per directory via the `Ignore` matcher carried in each `Work` item, respecting `.gitignore` and custom filters without redundant checks.
- **Early termination** is supported through an atomic `quit_now` flag that propagates `WalkState::Quit` to all workers immediately.

## Frequently Asked Questions

### How does ripgrep decide how many threads to use for directory traversal?

By default, ripgrep uses the number of logical CPUs detected on the system. You can override this via `WalkBuilder::threads(n)` or the `-j/--threads` CLI flag. The `WalkParallel::run` method spawns exactly this number of `Worker` threads, each with its own `Stack` for work-stealing.

### What is the difference between WalkParallel::run and WalkParallel::visit?

`WalkParallel::run` accepts a closure factory that produces per-thread visitors, giving you full control over thread-local state and the ability to return `WalkState::Quit` for early termination. `WalkParallel::visit` is a higher-level convenience method that handles the closure boxing internally and is used when you don't need fine-grained control over the thread-local state or early exit semantics.

### How does ripgrep handle ignore files (.gitignore) during parallel walks?

Each `Work` item carries an `Ignore` matcher that represents the cumulative ignore rules up to that directory. When a worker enters a directory, it calls `add_parents()` to load any `.gitignore` or `.ignore` files found there, updating the matcher. Before pushing child entries onto the stack, `Worker::generate_work` calls `should_skip_entry` to check the matcher, ensuring ignore rules are evaluated exactly once per entry even when work is stolen between threads.

### Why does ripgrep use depth-first traversal instead of breadth-first?

ripgrep uses depth-first traversal (LIFO stack order) to minimize memory pressure. By fully exhausting a deep branch of the directory tree before moving to sibling directories, the walker keeps fewer open directory handles and pending work items in memory at any given time. This is particularly important when searching large, deeply nested repositories where a breadth-first approach would require buffering all entries at each depth level before proceeding.