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

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:

• 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.).

// 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:

// 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.).

// 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.

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:

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:

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:

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, 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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}