Build a Fast File Finder in Rust With Parallel Walking

find . -name '*special*' on a large source tree is one of those commands that feels instant until the tree is a monorepo with 400,000 files, at which point it takes long enough to notice. Tools like fd and ripgrep finish the same job several times faster, and the reason is not magic: they walk directories on several threads at once, skip directories you did not ask about, and avoid work per file. This guide builds the core of such a tool in plain Rust, measures what parallelism buys, and then shows what the ignore crate adds and when you should reach for it instead.

Everything here compiled and ran on Rust 1.99 with edition 2024, on a 10-core Apple silicon laptop with the test tree in the operating system's file cache. The timings are real and small, and the guide is explicit about what they do and do not prove.

Why walking a directory tree is slow

Listing a directory costs system calls: one to open it, one or more getdents calls to read its entries, and one to close it. A tree with 1,000 directories pays that cost 1,000 times no matter how few files match. Files themselves are cheap here, because DirEntry::file_type() usually comes straight from the directory listing and needs no extra stat call on Linux and macOS. The practical lesson is to avoid metadata() or path.is_dir() per entry, which do an extra system call each, and to use the file type that read_dir already gave you.

The second cost is waiting. A system call that reads a directory from a cold disk, a network file system or a busy machine blocks the thread. One thread walking sequentially stalls on each wait in turn. Many threads overlap the waits, and on a warm cache they overlap the CPU part of the calls as well. That is the whole case for a parallel walk, and it also tells you where it stops helping: once every core is busy issuing system calls, or the disk is saturated, more threads add contention instead of speed.

The sequential baseline

Measure before optimizing, and start with the simplest correct version. This one uses recursion over std::fs::read_dir and takes the file type from the entry.

fn walk_sequential(root: &Path, needle: &str, hits: &mut Vec<PathBuf>) {
    let Ok(entries) = fs::read_dir(root) else { return };
    for entry in entries.flatten() {
        let path = entry.path();
        let Ok(kind) = entry.file_type() else { continue };
        if kind.is_dir() {
            walk_sequential(&path, needle, hits);
        } else if entry.file_name().to_string_lossy().contains(needle) {
            hits.push(path);
        }
    }
}

Three decisions here are worth keeping. let Ok(entries) = ... else { return } skips a directory that cannot be read, for example one the user lacks permission for, instead of aborting the whole search; a finder that dies on the first Permission denied is unusable on a real machine. entries.flatten() drops entries that failed to read, for the same reason. And entry.file_type() does not follow symlinks, so a symlink to a directory is reported as a symlink rather than a directory and is not recursed into, which sidesteps infinite loops from a link that points at one of its own parents. If you want links followed, you must track visited directories by device and inode yourself, or use walkdir's follow_links(true), which does the loop detection for you.

Parallel: a shared stack of directories

The structure of a parallel walk is a work queue. Directories go in, workers take one, read it, push the subdirectories back, and record any matching files. The part that trips people up is not the queue but knowing when to stop.

An empty queue does not mean the walk is finished. At the start there is one directory, and while one worker reads it the queue is empty, yet three workers waiting on it would see an empty queue and quit, leaving the one worker to do everything alone. The walk would still return correct results and look fine, with no speedup. The correct condition is that the queue is empty and no worker is still reading a directory, which is the same as a counter of outstanding directories reaching zero. The program below keeps that counter in pending: it increments when a directory is queued, decrements when a worker finishes reading one, and a worker only exits when it sees an empty queue and pending == 0.

use std::fs;
use std::path::{Path, PathBuf};
use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::mpsc;
use std::sync::{Arc, Condvar, Mutex};
use std::thread;
use std::time::Instant;

fn walk_sequential(root: &Path, needle: &str, hits: &mut Vec<PathBuf>) {
    let Ok(entries) = fs::read_dir(root) else { return };
    for entry in entries.flatten() {
        let path = entry.path();
        let Ok(kind) = entry.file_type() else { continue };
        if kind.is_dir() {
            walk_sequential(&path, needle, hits);
        } else if entry.file_name().to_string_lossy().contains(needle) {
            hits.push(path);
        }
    }
}

/// A work queue of directories. `pending` counts directories queued or being read,
/// so workers know when the whole tree is done rather than just when the queue is empty.
struct Queue {
    dirs: Mutex<Vec<PathBuf>>,
    ready: Condvar,
    pending: AtomicUsize,
}

fn walk_parallel(root: &Path, needle: &str, threads: usize) -> Vec<PathBuf> {
    let queue = Arc::new(Queue {
        dirs: Mutex::new(vec![root.to_path_buf()]),
        ready: Condvar::new(),
        pending: AtomicUsize::new(1),
    });
    let (tx, rx) = mpsc::channel();

    let workers: Vec<_> = (0..threads)
        .map(|_| {
            let queue = Arc::clone(&queue);
            let tx = tx.clone();
            let needle = needle.to_string();
            thread::spawn(move || loop {
                let dir = {
                    let mut dirs = queue.dirs.lock().unwrap();
                    loop {
                        if let Some(dir) = dirs.pop() {
                            break dir;
                        }
                        if queue.pending.load(Ordering::SeqCst) == 0 {
                            return;
                        }
                        dirs = queue.ready.wait(dirs).unwrap();
                    }
                };
                if let Ok(entries) = fs::read_dir(&dir) {
                    for entry in entries.flatten() {
                        let Ok(kind) = entry.file_type() else { continue };
                        if kind.is_dir() {
                            queue.pending.fetch_add(1, Ordering::SeqCst);
                            queue.dirs.lock().unwrap().push(entry.path());
                            queue.ready.notify_one();
                        } else if entry.file_name().to_string_lossy().contains(&needle) {
                            let _ = tx.send(entry.path());
                        }
                    }
                }
                if queue.pending.fetch_sub(1, Ordering::SeqCst) == 1 {
                    queue.ready.notify_all();
                }
            })
        })
        .collect();
    drop(tx);

    let hits: Vec<PathBuf> = rx.iter().collect();
    for w in workers {
        w.join().unwrap();
    }
    hits
}

fn main() {
    let root = std::env::temp_dir().join("finder-lab");
    if !root.exists() {
        for a in 0..40 {
            for b in 0..25 {
                let dir = root.join(format!("pkg{a}/mod{b}/src"));
                fs::create_dir_all(&dir).unwrap();
                for f in 0..20 {
                    fs::write(dir.join(format!("file{f}.rs")), "x").unwrap();
                }
                fs::write(dir.join("lib_special.rs"), "x").unwrap();
            }
        }
    }

    let mut seq = Vec::new();
    let t = Instant::now();
    walk_sequential(&root, "special", &mut seq);
    println!("sequential:  {:>4} hits in {:>8.2?}", seq.len(), t.elapsed());

    for threads in [2, 4, 8] {
        let t = Instant::now();
        let hits = walk_parallel(&root, "special", threads);
        println!("{threads} threads:   {:>4} hits in {:>8.2?}", hits.len(), t.elapsed());
        assert_eq!(hits.len(), seq.len());
    }
}

Run in release mode over a generated tree of about 22,000 files in 2,000 directories (40 packages, each with 25 modules, each with a src directory), looking for the 1,000 files whose names contain special, it printed:

sequential:  1000 hits in  53.02ms
2 threads:   1000 hits in  30.77ms
4 threads:   1000 hits in  27.51ms
8 threads:   1000 hits in  23.48ms

The assertion in main checks that every parallel run found the same 1,000 files as the sequential one, which is the correctness test that matters: a parallel walk that is fast and wrong is worse than a slow one.

Reading the numbers honestly

The speedup is 2.3 times at 8 threads, not 8 times. That is a normal result for this kind of work. The tree is in the file cache, so there is no disk wait to hide, and what the threads overlap is the kernel's own work. Past two threads the gains shrink because the threads contend for the shared queue's Mutex and for kernel-internal locks on the directory structures. On a cold cache, or a network file system where each directory read costs milliseconds, the same code scales much better, because the threads overlap real waiting. Run your own measurement on the trees you search, with the cache both warm and cold (on Linux, echo 3 | sudo tee /proc/sys/vm/drop_caches between runs), and let that decide the default thread count. Two runs of this program differed by about 10 percent in the sequential case alone, so treat differences under that as noise and repeat any comparison several times.

Stream results, then sort if asked

Notice that matches travel over an mpsc channel. Workers send paths as they find them and the main thread collects them, which means a real tool can print each hit immediately instead of waiting for the walk to finish. Users notice that: seeing the first result after 5 ms feels instant even when the full walk takes 500. The price is that output order depends on thread timing, so two runs can list the same files differently. Make that an explicit flag. By default stream unordered; with --sort, collect everything and call sort_unstable() on the paths before printing. Tests need the sorted form to be deterministic.

What the ignore crate adds

Writing the walker teaches the mechanism, but the ignore crate is what ripgrep and fd use, and it solves the parts that are tedious to get right: reading .gitignore, .ignore and global git excludes while walking, skipping hidden files, handling symlinks, and running the walk in parallel with a work-stealing scheduler. Combined with globset for compiled glob matching, the same search is a few lines:

use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::Arc;
use std::time::Instant;

use globset::Glob;
use ignore::{WalkBuilder, WalkState};

fn main() -> anyhow::Result<()> {
    let root = std::env::temp_dir().join("finder-lab");
    let matcher = Glob::new("*special*")?.compile_matcher();
    let hits = Arc::new(AtomicUsize::new(0));

    let t = Instant::now();
    WalkBuilder::new(&root)
        .threads(8)
        .hidden(false)
        .git_ignore(true)
        .build_parallel()
        .run(|| {
            let matcher = matcher.clone();
            let hits = Arc::clone(&hits);
            Box::new(move |entry| {
                if let Ok(entry) = entry {
                    if entry.file_type().is_some_and(|t| t.is_file()) && matcher.is_match(entry.file_name()) {
                        hits.fetch_add(1, Ordering::Relaxed);
                    }
                }
                WalkState::Continue
            })
        });
    println!("ignore crate, 8 threads: {} hits in {:.2?}", hits.load(Ordering::Relaxed), t.elapsed());
    Ok(())
}

ignore crate, 8 threads: 1000 hits in 27.91ms

Run twice, the first run took 58.74 ms and the second 27.91 ms, which tells you something about the first-run effect on file metadata and about how noisy a single measurement is. In this synthetic tree the ignore walker lands in the same range as the hand-written one, not clearly faster, because the tree has no ignore files for it to be clever about. Where it earns its keep is on a real repository: a project with a 3 GB node_modules or target directory listed in .gitignore is searched in a fraction of the time, because the walker never enters ignored directories. Skipping a subtree beats walking it faster. That is also why a hand-rolled finder should accept an --exclude option from the first version, and apply it to directories before descending, not to file names afterward.

Two details in that snippet matter. matcher.clone() inside the run closure gives each thread its own handle on the compiled glob. And the closure returns WalkState::Continue; returning WalkState::Skip for a directory prunes it, and WalkState::Quit stops every thread, which is how you implement --max-results.

The same tool with walkdir, and a real exit code

If the tree is small or you only need correctness first, walkdir gives you a sequential walker with the awkward parts handled: symlink loops, depth limits, sorted traversal and errors reported per entry rather than aborting. Starting here is often the right call, and you switch to a parallel walker when the measurement says to. This version also shows the output manners a finder needs: sorted output on request, NUL-separated names, errors counted instead of printed one by one, and an exit status that scripts can use.

use std::io::{self, BufWriter, Write};
use std::path::PathBuf;
use std::process::ExitCode;

use walkdir::WalkDir;

struct Options {
    root: PathBuf,
    needle: String,
    sort: bool,
    print0: bool,
    follow_links: bool,
}

fn find(opts: &Options) -> (Vec<PathBuf>, usize) {
    let mut hits = Vec::new();
    let mut unreadable = 0;
    // follow_links(true) makes walkdir track ancestors and report a loop as an error entry.
    for entry in WalkDir::new(&opts.root).follow_links(opts.follow_links) {
        match entry {
            Ok(e) if e.file_type().is_file() && e.file_name().to_string_lossy().contains(&opts.needle) => {
                hits.push(e.into_path());
            }
            Ok(_) => {}
            Err(_) => unreadable += 1,
        }
    }
    if opts.sort {
        hits.sort_unstable();
    }
    (hits, unreadable)
}

fn main() -> ExitCode {
    let opts = Options {
        root: std::env::temp_dir().join("finder-lab/pkg0/mod0"),
        needle: "special".into(),
        sort: true,
        print0: false,
        follow_links: true,
    };
    let (hits, unreadable) = find(&opts);
    let mut out = BufWriter::new(io::stdout().lock());
    for hit in &hits {
        let shown = hit.strip_prefix(&opts.root).unwrap_or(hit).display().to_string();
        let sep = if opts.print0 { "\0" } else { "\n" };
        if write!(out, "{shown}{sep}").is_err() {
            break;
        }
    }
    let _ = out.flush();
    if unreadable > 0 {
        eprintln!("ff: {unreadable} entries could not be read");
    }
    // Like grep: 0 when something matched, 1 when nothing did.
    if hits.is_empty() { ExitCode::from(1) } else { ExitCode::SUCCESS }
}

src/lib_special.rs

The loop treats the three outcomes of an entry separately with one match: a matching file is kept, a non-matching entry is ignored, and an error increments a counter. With follow_links(true), walkdir remembers the directories on the current path, and a link that points back up the tree comes out as an Err entry instead of an endless recursion, so a loop costs you one counted failure and nothing else. The result is printed relative to the root with strip_prefix, and the write! result is checked, because a closed pipe is the normal way for head to end a conversation. The exit code follows grep: 1 for "nothing found" distinguishes an empty result from success without treating it as an error.

Pruning is the biggest win

All the threading in this guide buys a factor of two or three. Not entering a directory buys the factor of the directory's size. A target/ directory full of build artifacts can hold hundreds of thousands of files, and a finder that skips it is faster than any finder that visits it quickly. Both walkdir and ignore support pruning during the walk: in walkdir, WalkDir::new(root).into_iter().filter_entry(|e| keep(e)) stops descent into entries your predicate rejects, which is different from filtering the results afterward, because filter_entry stops the walk from entering the directory in the first place.

use walkdir::{DirEntry, WalkDir};

fn is_noise(entry: &DirEntry) -> bool {
    entry.file_type().is_dir()
        && matches!(entry.file_name().to_str(), Some("target" | "node_modules" | ".git"))
}

fn rust_sources(root: &std::path::Path) -> impl Iterator<Item = DirEntry> {
    WalkDir::new(root)
        .into_iter()
        .filter_entry(|e| !is_noise(e))
        .filter_map(Result::ok)
        .filter(|e| e.path().extension().is_some_and(|x| x == "rs"))
}

Compare filter_entry with a plain .filter(...) placed after the walk. They produce the same list, and the second one has already read every directory under target before throwing the entries away. On a repository with a large build directory, the difference between those two lines is the difference between a search that takes 40 ms and one that takes four seconds. When someone tells you their finder is slow, ask first what it walks, and second how fast it walks it.

Concurrency details worth knowing

Two properties of the hand-written parallel walker are easy to miss. The queue is a stack: workers pop from the end, so the walk is depth first per worker, which keeps the number of queued directories small and the working set cache friendly. A first-in first-out queue would be breadth first, hold a whole level of the tree in memory at once, and touch directories in an order that is worse for the disk. And the channel is unbounded, so a very fast walker feeding a slow consumer, such as a terminal over a slow SSH link, grows memory without limit. A sync_channel with a capacity of a few thousand makes workers block when the consumer falls behind, which converts a memory problem into back pressure, the right trade.

Matching: substring, glob or regex

The finder's matcher is the next design decision, and it changes performance more than people expect.

Compile the pattern once, before the walk, and share it by reference or clone the handle per thread. Compiling inside the per-file path is the mistake from profiling a slow endpoint in a different outfit. Match on the file name, not the full path, unless the pattern contains a path separator: matching *special* against /home/me/special-projects/readme.md would report every file under a directory that happens to contain the word. And be explicit about case. Smart case, case-insensitive unless the pattern contains an uppercase letter, is what fd and ripgrep do and what users expect after using them.

File names on Linux are bytes, not guaranteed UTF-8, which is why the code uses to_string_lossy() for matching. That replaces invalid bytes with a replacement character for comparison only and keeps the original PathBuf for output, so you never print or open a mangled path. If you need exact matching on non-UTF-8 names, compare OsStr values, using OsStrExt::as_bytes on Unix.

Testing a filesystem tool

Filesystem code is easy to test if you build the tree in the test. Create a temporary directory, write a few files and directories, run the walker, and compare against the exact set you expect. With the standard library alone, std::env::temp_dir() plus a unique name works; the tempfile crate cleans up automatically and is worth the dependency.

use std::fs;

#[test]
fn finds_matches_in_nested_directories_and_ignores_the_rest() {
    let root = tempfile::tempdir().unwrap();
    fs::create_dir_all(root.path().join("a/b")).unwrap();
    fs::write(root.path().join("a/b/lib_special.rs"), "").unwrap();
    fs::write(root.path().join("a/other.rs"), "").unwrap();
    fs::write(root.path().join("special.txt"), "").unwrap();

    let mut found = finder::walk_parallel(root.path(), "special", 4);
    found.sort();

    let relative: Vec<_> = found.iter().map(|p| p.strip_prefix(root.path()).unwrap().to_owned()).collect();
    assert_eq!(relative, [std::path::PathBuf::from("a/b/lib_special.rs"), "special.txt".into()]);
}

Add a test with an unreadable directory (chmod 000, skipped on Windows), one with a symlink loop (std::os::unix::fs::symlink(".", "loop")), and one with a file name that is not valid UTF-8. These three are the cases that crash or hang naive walkers, and finding that out in a unit test is cheaper than finding it on a customer's machine.

Design choices a finished tool needs

A few decisions separate a demo from something people adopt.

• Honor ignore files by default and provide --no-ignore and --hidden to opt out. People expect fd behavior now.
• Limit the thread count to std::thread::available_parallelism() by default, and let --threads override it. More threads than cores helps only on slow storage.
• Print paths relative to the search root unless asked otherwise, and use a NUL separator (--print0) so the output can feed xargs -0 safely when names contain spaces or newlines.
• Exit with status 1 when nothing matched and 0 when something did, as grep does, so scripts can branch on it. Reserve 2 for errors.
• Report unreadable directories on standard error once, counted, at the end, rather than a line per failure that buries the results.

When a parallel walker is the wrong choice

On a small tree, the thread startup cost is larger than the walk. Searching one project with a few hundred files is faster sequentially, and a tool that spawns eight threads for it wastes time. If you search the same tree repeatedly, build an index once (a list of paths in a file, or a trigram index) and query that; locate does this with a nightly database, and the trade-off is staleness. If the data lives in a database or an archive rather than a directory tree, the walk is the wrong abstraction. And if your process already runs on an async runtime, remember that std::fs calls block; run the walk inside spawn_blocking so it cannot stall your other tasks, or use a dedicated thread pool and send results back over a channel. For the next step in the same toolbox, see building a log analyzer with regex and iterators.

Finish by writing down what you measured. For this finder the useful summary is short: parallelism gave roughly a 2.3 times speedup on a warm 22,000 file tree, pruning ignored directories gives you the size of the directory skipped, and correctness (the same 1,000 hits from every strategy) is checked by an assertion rather than by eye. Keep that assertion in your benchmark harness. A faster finder that quietly skips a few files is the worst kind of regression, because nobody notices until the file they needed is not in the results.