Concurrency as a Product Decision

Ripgrep’s normal parallel search uses synchronous I/O plus several OS threads. That is not an implementation accident; it matches the unit of work.

The unit of parallelism is a file

Within one file, the searcher reads and matches sequentially. Across files, workers run in parallel. This gives each worker a substantial unit of work and keeps line ordering within a file straightforward.

worker 0: discover a.rs → search a.rs → commit a.rs output
worker 1: discover b.rs → search b.rs → commit b.rs output
worker 2: descend src/ → discover c.rs → search c.rs

Splitting individual lines among workers would introduce ordering, cross-line-match, context-line, and buffering problems for much smaller tasks.

Why fuse traversal and searching?

WalkParallel::run creates one callback per traversal worker. The callback searches the visited file immediately. There is no central path channel and no second search pool.

This removes a queue and avoids having separate thread counts for traversal and search. It also means a thread blocked on a slow file is temporarily unavailable for traversal, which work stealing mitigates by letting other workers take directories from its deque.

Local deques, global stealing

Every worker has a LIFO Crossbeam deque. Local LIFO processing encourages depth-first traversal, reducing the number of live paths and inherited ignore matchers. An idle worker attempts steal_batch_and_pop from its peers.

Source: Stack::new_for_each_thread, Stack::steal

This is dynamic load balancing. A directory tree is rarely balanced enough for static partitions: one root may contain ten files while another contains ten thousand.

Shared state is deliberately tiny

The parallel search shares only what must cross worker boundaries:

• AtomicBool for “searched anything?” and “matched anything?”;
• Mutex<Stats> only when aggregate statistics were requested;
• the output writer’s internal serialization;
• AtomicBool for immediate shutdown; and
• AtomicUsize for termination detection.

Everything expensive and frequently mutated—the matcher, line buffers, printer, and file output buffer—is cloned or constructed per worker.

Termination is a distributed state transition

An empty local deque does not mean the search is finished; another worker may discover more directories. A worker first marks itself inactive. Only the worker that observes the active count reach zero knows every deque was empty at the same coordination point. It injects a quit message, which other workers repeat as they exit.

Source: Worker::get_work

Concurrency versus async

Async would help if ripgrep needed to maintain huge numbers of mostly-idle operations. Its dominant operation is instead a bounded number of active file reads and CPU searches. A small OS-thread pool is a direct fit and permits the entire matching stack to remain synchronous.