DynQueue: A Parallel Work Queue That Grows While It Drains

Last week dynqueue 0.4.0 and 0.5.0 shipped. The headline is a breaking fix: dynamically enqueued work is now actually distributed across worker threads instead of piling up on the thread that produced it.

DISCLAIMER: This article and most of the code was written with AI agents. Use at your own risk.

The problem

A lot of parallel workloads don’t know their size up front: tree walks, graph traversal, worklist algorithms like compiler dataflow analyses or mark-and-sweep. You process an item, and processing it discovers more items.

The naive Rayon approach — a parallel iterator over the initial collection — breaks down here. ParallelIterator is built around split + fold: the collection is partitioned up front and each worker drains only its own partition. Items enqueued during the fold can’t be re-partitioned, so they stay on the producing thread. The whole dynamic workload runs at roughly single thread speed.

rayon::scope can express dynamic work, but then every generated job is its own closure, and you wire up the task spawning yourself. What’s often wanted is the worklist shape: one callback, one queue of homogeneous items.

The fix

DynQueue used to be a static Rayon unindexed producer. The ParallelIterator API was replaced with for_each_dyn, which drains one shared, mutex-guarded worklist from all workers, so newly enqueued items are picked up by any idle worker:

use dynqueue::IntoDynQueue as _;

let out = std::sync::Mutex::new(Vec::new());
vec![1, 2, 3]
    .into_dyn_queue()
    .for_each_dyn(|handle, value| {
        if value == 2 {
            handle.enqueue(4)
        }
        out.lock().unwrap().push(value);
    });

The tricky parts were termination and panics: a single gate plus a per-item in-flight counter makes the “is the queue actually empty?” decision race-free, and an RAII guard stops a panicking callback from hanging the drain. The handle is now a borrowing handle, so stashing it for later is a compile error instead of a runtime strong_count panic.

Measured on a heavy dynamic workload with 4 threads:

The rest of the week

• A regression test that fails if dynamic work stops being parallelized — the bug was silent, so the test had to be loud.
• Coverage at 100% — regions, functions and lines of src/lib.rs, all measured, not eyeballed.
• dua, an example that builds a parallel du on for_each_dyn: one callback walks the tree enqueuing directory entries, errors are enqueued as work items instead of panicking, and it’s byte-exact against du -b.
• Edition 2024, MSRV 1.87, rayon floored to 1.x.
• release-please with crates.io trusted publishing via OIDC, so 0.4.0 and 0.5.0 went out the door without touching a token.

The queue back-end is pluggable via a Queue trait (Vec, VecDeque, and crossbeam_queue::SegQueue behind a feature flag ship today).

It’s on crates.io and docs.rs, source at github.com/haraldh/dynqueue.