1 unstable release

0.1.0 Sep 19, 2024

#214 in Concurrency

29 downloads per month

MIT/Apache

41KB
775 lines

chili

Crates.io Docs

Rust port of Spice, a low-overhead parallelization library

Very low-overhead parallelization primitive, almost identical to rayon::join. At any fork point during computation, it may run the two passed closures in parallel.

It works best in cases where there are many small computations and where it is expensive to estimate how many are left on the current branch in order to stop trying to share work across threads.

Example

The following example sums up all nodes in a binary tree in parallel.

fn sum(node: &Node, scope: &mut Scope<'_>) -> u64 {
    let (left, right) = scope.join(
        |s| node.left.as_deref().map(|n| sum(n, s)).unwrap_or_default(),
        |s| node.right.as_deref().map(|n| sum(n, s)).unwrap_or_default(),
    );

    node.val + left + right
}

This is the ideal example since per-node computation is very cheap and the nodes don't keep track of how many descendants are left.

Benchmarks

The following benchmarks measure the time it takes to sum up all the values in a balanced binary tree with varying number of nodes.

AMD Ryzen 7 4800HS (8 cores)

While the improvement over the baseline in the 134M nodes case is close to the theoretical maximum, it's worth noting that the actual time per node is 0.8ns vs. a theoretical 1.8 / 8 = 0.2ns, if we're to compare against the 1K nodes case.

Number of nodes Baseline Rayon chili Baseline / chili
1023 1.8 µs 51.1 µs 3.4 µs x0.53
16777215 94.4 ms 58.1 ms 13.6 ms x6.94
134217727 797.5 ms 497.2 ms 101.8 ms x7.83

Apple M1 (8 cores)

Number of nodes Baseline Rayon chili Baseline / chili
1023 1.6 µs 29.2 µs 3.5 µs x0.46
16777215 39.4 ms 40.5 ms 11.2 ms x3.51
67108863 156.5 ms 167.1 ms 44.3 ms x3.53

chili overhead on AMD Ryzen 7 4800HS (8 cores)

The overhead in the 1K nodes case remains approximately constant with respect to the number of threads.

Number of nodes Baseline 1 thread 2 threads 4 threads 8 threads
1023 1.8 ns 3.5 ns 3.5 µs 3.5 µs 3.5 µs

Dependencies

~0–660KB
~12K SLoC