๐ŸŽ“ A1Learner
๐Ÿ”

Rust Parallel Map & Reduce

A parallel chain in rayon runs filter, map, and a join across many threads. Filter keeps some values first, map changes what is left, and a join adds the partial answers into one.

Filter in parallel

filter keeps the values that pass the test. The test runs on every core.

let evens: Vec<i32> = (1..=10).into_par_iter().filter(|n| n % 2 == 0).collect();
println!("evens = {:?}", evens);

Chain steps like always

Say words holds "rust", "is", "fast", "and" and "safe". Long words survive the filter. map then shouts them.

let picked: Vec<String> = words.par_iter().filter(|w| w.len() > 3).map(|w| w.to_uppercase()).collect();
println!("picked = {:?}", picked);

fold builds one partial per worker

Say nums holds the numbers 1 to 10. fold starts each worker with the identity value 0. Each worker adds up only its own chunk.

let total: i32 = nums.par_iter().fold(|| 0, |acc, n| acc + n).sum();
println!("total = {}", total);

reduce joins the partials

reduce takes an identity and a joining rule. Here the rule is plain addition.

let total: i32 = (1..=10).into_par_iter().map(|n| n * n).reduce(|| 0, |a, b| a + b);
println!("total = {}", total);

find_first keeps order. find_any takes any.

Both searches hunt a multiple of 7. find_first promises the earliest one. find_any promises only some one.

let first = (1..=100).into_par_iter().find_first(|n| n % 7 == 0);
let any = (1..=100).into_par_iter().find_any(|n| n % 7 == 0);
println!("first = {:?}", first);
println!("found = {}", any.is_some());

Example

// Cargo.toml: rayon = "1"
use rayon::prelude::*;

fn main() {
    let orders = vec![
        ("pens", 12),
        ("books", 60),
        ("lamp", 45),
        ("desk", 120),
        ("chair", 85),
        ("mug", 9),
    ];
    let big_total: i32 = orders
        .par_iter()
        .filter(|order| order.1 >= 50)
        .map(|order| order.1)
        .sum();
    let big_count = orders.par_iter().filter(|order| order.1 >= 50).count();
    println!("orders = {}", orders.len());
    println!("big orders = {}", big_count);
    println!("big total = {}", big_total);
}

Key points

  • The joining rule must be associative.
  • (a + b) + c must equal a + (b + c).
  • Rayon regroups the work on every run.
  • The identity must be a true identity.
  • Joining it with a value must return that value.
  • Use fold to build a partial answer per worker.
  • Use reduce or sum to join the partials.
  • Adding floats is not grouping-proof.
  • A parallel float sum can differ in the last bits from run to run.
  • A parallel chain gives the same answer as the sequential chain.
  • Parallel map and reduce spread filter and map over many threads, then join the partial answers into one result.

In this example, orders holds six sales. Each sale is a name and an amount. The filter keeps sales of 50 or more. Three sales pass. map then drops the names and keeps the amounts. sum adds them to 265. A second chain counts the same sales. Both chains ran in parallel. Both answers match the sequential ones.

Note

Only the grouping of the work changes.

Try it Yourself

Edit the code, then press Run.

Running is simulated ยท Rust Playground

Exercise

Why can a parallel float sum differ in the last bits from one run to the next?