Funnel: Parallel Fused Hylomorphism
The funnel executor parallelizes a fused hylomorphism — an unfold (tree traversal) composed with a fold (bottom-up accumulation) where the intermediate tree is never materialized. Children are discovered one at a time through a push-based callback, processed concurrently across worker threads, and their results flow back to the parent through defunctionalized continuations.
What a fused hylomorphism is
A hylomorphism composes an unfold (anamorphism) with a fold (catamorphism). The unfold generates a tree structure from a seed; the fold consumes it bottom-up. When fused, the two interleave: each node is produced, its children recursively processed, and their results accumulated — without materializing the tree.
In hylic terms: a Treeish<N> (the coalgebra) exposes
visit(&node, |child| ...) and a Fold<N, H, R> (the algebra,
factored as init/accumulate/finalize)
provides the per-node bracket. The executor calls visit to
discover children, recursively processes each, accumulates their R
results into the parent’s H heap, and finalizes. The intermediate
tree is never materialized as a data structure.
The funnel parallelizes this: children beyond the first are pushed to a work-stealing queue. Worker threads steal and process subtrees concurrently. Results flow back through continuations to the parent’s accumulator. The challenge is coordinating the fold — detecting when all children are done, accumulating their results, and cascading upward — without locks, without allocation on the critical path.
Design values
Four properties define the funnel’s design:
-
Iterator-based traversal. The graph exposes
visit(&node, |child| ...). Children arrive one at a time. There is nochildren(&node) -> Vec<N>. -
Fully parallel. Each child beyond the first is pushed to a work-stealing queue. Workers steal and process subtrees concurrently. The first child is walked inline — zero queue overhead on the DFS spine.
-
Fused unfold+fold. Results accumulate into the parent as they arrive (streaming) or in bulk by the last thread (finalize). The tree is never materialized.
-
Zero allocation on the hot path. Tasks are enum variants stored inline in deque slots. Multi-child accumulators are arena-allocated. Single-child nodes carry their heap inside the continuation. No
Box<dyn FnOnce>, noArcper task.
Where funnel sits
| Executor | Parallelism | Unfold/fold fusion | Task repr | Allocation |
|---|---|---|---|---|
| Fused | none | fully fused | stack frames | zero |
| Funnel | CPS + work-stealing | fully fused | FunnelTask enum | arenas |
Fused is the sequential baseline — zero overhead, callback-based recursion on a single thread. Funnel preserves the fused property while adding parallelism through CPS (continuation-passing style) and work-stealing queues. The fold/graph are unchanged between the two — only the executor differs.
Both use the same Exec<D, S>
type-level pattern. Funnel’s policy system is an instance of the
generic Spec → Store → Handle
pattern for zero-cost executor configuration.
Module map
The funnel’s code is organized into four clusters:
Three behavioral axes
The funnel is parameterized along three independent axes, all
resolved at compile time through the FunnelPolicy trait:
#![allow(unused)]
fn main() {
/// Bundles queue topology, accumulation strategy, and wake policy.
/// One type parameter on the executor replaces three.
pub trait FunnelPolicy: 'static {
type Queue: WorkStealing;
type Accumulate: AccumulateStrategy;
type Wake: WakeStrategy;
}
}Each axis is a trait with its own Spec, Store/State, and
implementations. The Policy<Q, A, W> struct bundles any combination:
#![allow(unused)]
fn main() {
/// Generic policy: any combination of axes. Named presets are type aliases over this.
pub struct Policy<
Q: WorkStealing = queue::PerWorker,
A: AccumulateStrategy = accumulate::OnFinalize,
W: WakeStrategy = wake::EveryPush,
>(PhantomData<(Q, A, W)>);
impl<Q: WorkStealing, A: AccumulateStrategy, W: WakeStrategy> FunnelPolicy for Policy<Q, A, W> {
type Queue = Q;
type Accumulate = A;
type Wake = W;
}
}Named presets are type aliases:
#![allow(unused)]
fn main() {
// ── Named presets (type aliases) ─────────────────
//
// Each is a concrete instantiation of Policy<Q, A, W>.
// `Default` aliases the robust all-rounder; other names describe
// the workload shape they're tuned for.
/// PerWorker + OnFinalize + EveryPush. The robust all-rounder.
pub type Robust = Policy;
/// The default policy. Alias for Robust.
pub type Default = Robust;
/// Same axes as Default. Distinguished by Spec configuration (larger arenas).
pub type GraphHeavy = Robust;
/// Shared + OnArrival + EveryPush. Wide trees (bf=20+).
pub type WideLight = Policy<queue::Shared, accumulate::OnArrival>;
/// PerWorker + OnFinalize + OncePerBatch. Overhead-sensitive (noop-like).
pub type LowOverhead = Policy<queue::PerWorker, accumulate::OnFinalize, wake::OncePerBatch>;
/// PerWorker + OnArrival + EveryPush. Streaming sweep with per-worker deques.
pub type PerWorkerArrival = Policy<queue::PerWorker, accumulate::OnArrival>;
/// Shared + OnFinalize + EveryPush.
pub type SharedDefault = Policy<queue::Shared>;
/// PerWorker + OnFinalize + EveryK<4>. Balanced wakeups for heavy workloads.
pub type HighThroughput = Policy<queue::PerWorker, accumulate::OnFinalize, wake::EveryK<4>>;
/// Shared + OnArrival + OncePerBatch.
pub type StreamingWide = Policy<queue::Shared, accumulate::OnArrival, wake::OncePerBatch>;
/// PerWorker + OnFinalize + EveryK<2>. For deep narrow trees (bf=2).
pub type DeepNarrow = Policy<queue::PerWorker, accumulate::OnFinalize, wake::EveryK<2>>;
````<div class="mdbook-graphviz-output"><!-- Generated by graphviz version 2.43.0 (0) --><!-- Title: %3 Pages: 1 --><svg width="671pt" height="188pt" viewBox="0.00 0.00 671.00 188.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"><g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 184)"><title>%3</title><polygon fill="white" stroke="transparent" points="-4,4 -4,-184 667,-184 667,4 -4,4"/><!-- policy --><g id="node1" class="node"><title>policy</title><path fill="#e2d9f3" stroke="black" d="M352,-180C352,-180 255,-180 255,-180 249,-180 243,-174 243,-168 243,-168 243,-156 243,-156 243,-150 249,-144 255,-144 255,-144 352,-144 352,-144 358,-144 364,-150 364,-156 364,-156 364,-168 364,-168 364,-174 358,-180 352,-180"/><text text-anchor="middle" x="303.5" y="-165" font-family="sans-serif" font-size="10.00">FunnelPolicy</text><text text-anchor="middle" x="303.5" y="-154" font-family="sans-serif" font-size="10.00">(one type parameter)</text></g><!-- q --><g id="node2" class="node"><title>q</title><path fill="#cce5ff" stroke="black" d="M192,-108C192,-108 135,-108 135,-108 129,-108 123,-102 123,-96 123,-96 123,-84 123,-84 123,-78 129,-72 135,-72 135,-72 192,-72 192,-72 198,-72 204,-78 204,-84 204,-84 204,-96 204,-96 204,-102 198,-108 192,-108"/><text text-anchor="middle" x="163.5" y="-93" font-family="sans-serif" font-size="10.00">Queue</text><text text-anchor="middle" x="163.5" y="-82" font-family="sans-serif" font-size="10.00">WorkStealing</text></g><!-- policy->q --><g id="edge1" class="edge"><title>policy->q</title><path fill="none" stroke="black" d="M269.25,-143.88C250.44,-134.47 226.92,-122.71 206.83,-112.67"/><polygon fill="black" stroke="black" points="208.39,-109.53 197.88,-108.19 205.26,-115.79 208.39,-109.53"/></g><!-- a --><g id="node3" class="node"><title>a</title><path fill="#fff3cd" stroke="black" d="M349.5,-108C349.5,-108 257.5,-108 257.5,-108 251.5,-108 245.5,-102 245.5,-96 245.5,-96 245.5,-84 245.5,-84 245.5,-78 251.5,-72 257.5,-72 257.5,-72 349.5,-72 349.5,-72 355.5,-72 361.5,-78 361.5,-84 361.5,-84 361.5,-96 361.5,-96 361.5,-102 355.5,-108 349.5,-108"/><text text-anchor="middle" x="303.5" y="-93" font-family="sans-serif" font-size="10.00">Accumulate</text><text text-anchor="middle" x="303.5" y="-82" font-family="sans-serif" font-size="10.00">AccumulateStrategy</text></g><!-- policy->a --><g id="edge2" class="edge"><title>policy->a</title><path fill="none" stroke="black" d="M303.5,-143.7C303.5,-135.98 303.5,-126.71 303.5,-118.11"/><polygon fill="black" stroke="black" points="307,-118.1 303.5,-108.1 300,-118.1 307,-118.1"/></g><!-- w --><g id="node4" class="node"><title>w</title><path fill="#d4edda" stroke="black" d="M520.5,-108C520.5,-108 460.5,-108 460.5,-108 454.5,-108 448.5,-102 448.5,-96 448.5,-96 448.5,-84 448.5,-84 448.5,-78 454.5,-72 460.5,-72 460.5,-72 520.5,-72 520.5,-72 526.5,-72 532.5,-78 532.5,-84 532.5,-84 532.5,-96 532.5,-96 532.5,-102 526.5,-108 520.5,-108"/><text text-anchor="middle" x="490.5" y="-93" font-family="sans-serif" font-size="10.00">Wake</text><text text-anchor="middle" x="490.5" y="-82" font-family="sans-serif" font-size="10.00">WakeStrategy</text></g><!-- policy->w --><g id="edge3" class="edge"><title>policy->w</title><path fill="none" stroke="black" d="M349.25,-143.88C376.33,-133.74 410.72,-120.87 438.78,-110.36"/><polygon fill="black" stroke="black" points="440.29,-113.53 448.42,-106.75 437.83,-106.98 440.29,-113.53"/></g><!-- pw --><g id="node5" class="node"><title>pw</title><path fill="#cce5ff" stroke="black" d="M99,-36C99,-36 12,-36 12,-36 6,-36 0,-30 0,-24 0,-24 0,-12 0,-12 0,-6 6,0 12,0 12,0 99,0 99,0 105,0 111,-6 111,-12 111,-12 111,-24 111,-24 111,-30 105,-36 99,-36"/><text text-anchor="middle" x="55.5" y="-20.8" font-family="sans-serif" font-size="9.00">PerWorker</text><text text-anchor="middle" x="55.5" y="-10.8" font-family="sans-serif" font-size="9.00">Chase-Lev + bitmask</text></g><!-- q->pw --><g id="edge4" class="edge"><title>q->pw</title><path fill="none" stroke="black" d="M137.08,-71.88C123.09,-62.81 105.72,-51.55 90.61,-41.76"/><polygon fill="black" stroke="black" points="92.32,-38.69 82.02,-36.19 88.51,-44.57 92.32,-38.69"/></g><!-- shared --><g id="node6" class="node"><title>shared</title><path fill="#cce5ff" stroke="black" d="M185.5,-36C185.5,-36 141.5,-36 141.5,-36 135.5,-36 129.5,-30 129.5,-24 129.5,-24 129.5,-12 129.5,-12 129.5,-6 135.5,0 141.5,0 141.5,0 185.5,0 185.5,0 191.5,0 197.5,-6 197.5,-12 197.5,-12 197.5,-24 197.5,-24 197.5,-30 191.5,-36 185.5,-36"/><text text-anchor="middle" x="163.5" y="-20.8" font-family="sans-serif" font-size="9.00">Shared</text><text text-anchor="middle" x="163.5" y="-10.8" font-family="sans-serif" font-size="9.00">StealQueue</text></g><!-- q->shared --><g id="edge5" class="edge"><title>q->shared</title><path fill="none" stroke="black" d="M163.5,-71.7C163.5,-63.98 163.5,-54.71 163.5,-46.11"/><polygon fill="black" stroke="black" points="167,-46.1 163.5,-36.1 160,-46.1 167,-46.1"/></g><!-- arrive --><g id="node7" class="node"><title>arrive</title><path fill="#fff3cd" stroke="black" d="M297.5,-36C297.5,-36 227.5,-36 227.5,-36 221.5,-36 215.5,-30 215.5,-24 215.5,-24 215.5,-12 215.5,-12 215.5,-6 221.5,0 227.5,0 227.5,0 297.5,0 297.5,0 303.5,0 309.5,-6 309.5,-12 309.5,-12 309.5,-24 309.5,-24 309.5,-30 303.5,-36 297.5,-36"/><text text-anchor="middle" x="262.5" y="-20.8" font-family="sans-serif" font-size="9.00">OnArrival</text><text text-anchor="middle" x="262.5" y="-10.8" font-family="sans-serif" font-size="9.00">streaming sweep</text></g><!-- a->arrive --><g id="edge6" class="edge"><title>a->arrive</title><path fill="none" stroke="black" d="M293.37,-71.7C288.65,-63.64 282.94,-53.89 277.72,-44.98"/><polygon fill="black" stroke="black" points="280.59,-42.96 272.52,-36.1 274.55,-46.5 280.59,-42.96"/></g><!-- finalize --><g id="node8" class="node"><title>finalize</title><path fill="#fff3cd" stroke="black" d="M383.5,-36C383.5,-36 339.5,-36 339.5,-36 333.5,-36 327.5,-30 327.5,-24 327.5,-24 327.5,-12 327.5,-12 327.5,-6 333.5,0 339.5,0 339.5,0 383.5,0 383.5,0 389.5,0 395.5,-6 395.5,-12 395.5,-12 395.5,-24 395.5,-24 395.5,-30 389.5,-36 383.5,-36"/><text text-anchor="middle" x="361.5" y="-20.8" font-family="sans-serif" font-size="9.00">OnFinalize</text><text text-anchor="middle" x="361.5" y="-10.8" font-family="sans-serif" font-size="9.00">bulk sweep</text></g><!-- a->finalize --><g id="edge7" class="edge"><title>a->finalize</title><path fill="none" stroke="black" d="M317.84,-71.7C324.79,-63.3 333.27,-53.07 340.9,-43.86"/><polygon fill="black" stroke="black" points="343.64,-46.04 347.33,-36.1 338.25,-41.57 343.64,-46.04"/></g><!-- every --><g id="node9" class="node"><title>every</title><path fill="#d4edda" stroke="black" d="M465.5,-36C465.5,-36 425.5,-36 425.5,-36 419.5,-36 413.5,-30 413.5,-24 413.5,-24 413.5,-12 413.5,-12 413.5,-6 419.5,0 425.5,0 425.5,0 465.5,0 465.5,0 471.5,0 477.5,-6 477.5,-12 477.5,-12 477.5,-24 477.5,-24 477.5,-30 471.5,-36 465.5,-36"/><text text-anchor="middle" x="445.5" y="-15.8" font-family="sans-serif" font-size="9.00">EveryPush</text></g><!-- w->every --><g id="edge8" class="edge"><title>w->every</title><path fill="none" stroke="black" d="M479.38,-71.7C474.14,-63.56 467.8,-53.69 462.02,-44.7"/><polygon fill="black" stroke="black" points="464.85,-42.62 456.5,-36.1 458.96,-46.41 464.85,-42.62"/></g><!-- once --><g id="node10" class="node"><title>once</title><path fill="#d4edda" stroke="black" d="M563.5,-36C563.5,-36 507.5,-36 507.5,-36 501.5,-36 495.5,-30 495.5,-24 495.5,-24 495.5,-12 495.5,-12 495.5,-6 501.5,0 507.5,0 507.5,0 563.5,0 563.5,0 569.5,0 575.5,-6 575.5,-12 575.5,-12 575.5,-24 575.5,-24 575.5,-30 569.5,-36 563.5,-36"/><text text-anchor="middle" x="535.5" y="-15.8" font-family="sans-serif" font-size="9.00">OncePerBatch</text></g><!-- w->once --><g id="edge9" class="edge"><title>w->once</title><path fill="none" stroke="black" d="M501.62,-71.7C506.86,-63.56 513.2,-53.69 518.98,-44.7"/><polygon fill="black" stroke="black" points="522.04,-46.41 524.5,-36.1 516.15,-42.62 522.04,-46.41"/></g><!-- everyk --><g id="node11" class="node"><title>everyk</title><path fill="#d4edda" stroke="black" d="M651,-36C651,-36 606,-36 606,-36 600,-36 594,-30 594,-24 594,-24 594,-12 594,-12 594,-6 600,0 606,0 606,0 651,0 651,0 657,0 663,-6 663,-12 663,-12 663,-24 663,-24 663,-30 657,-36 651,-36"/><text text-anchor="middle" x="628.5" y="-15.8" font-family="sans-serif" font-size="9.00">EveryK<K></text></g><!-- w->everyk --><g id="edge10" class="edge"><title>w->everyk</title><path fill="none" stroke="black" d="M524.26,-71.88C542.72,-62.51 565.78,-50.81 585.52,-40.8"/><polygon fill="black" stroke="black" points="587.28,-43.83 594.61,-36.19 584.11,-37.59 587.28,-43.83"/></g></g></svg></div>
See [Policies](policies.md) for the full decision guide and
benchmark-informed recommendations.
# Reading order
|Page|What you learn|
|----|--------------|
|[CPS walk](cps_walk.md)|The downward pass: how nodes are processed and tasks created|
|[Continuations](continuations.md)|`FunnelTask`, `Cont`, `ChainNode`, `RootCell` — the CPS data types|
|[Cascade](cascade.md)|`fire_cont`: the trampolined upward pass|
|[Ticket system](ticket_system.md)|Packed `AtomicU64` for exactly-one-finalizer detection|
|[Pool and dispatch](pool_dispatch.md)|Thread pool, `Job` struct, the `dispatch()` CPS lifecycle|
|[Queue strategies](queue_strategies.md)|PerWorker (Chase-Lev + bitmask) vs Shared (StealQueue)|
|[Accumulation](accumulation.md)|OnArrival (streaming sweep) vs OnFinalize (bulk)|
|[Policies](policies.md)|`FunnelPolicy` GAT, three axes, named presets, decision guide|
|[Infrastructure](infrastructure.md)|Arena, ContArena, WorkerDeque, EventCount|
|[Testing](testing.md)|Correctness, stress, interleaving proof|
}