Skip to main content

code_system_graph_core/
parallel.rs

1//! Bounded scoped-thread fan-out whose results never depend on scheduling.
2
3use std::sync::atomic::{AtomicUsize, Ordering};
4
5/// Applies `operation` to every item with at most `workers` threads and returns results in item
6/// order, so callers observe the same sequence for every worker count.
7pub fn map_ordered<T, R, F>(items: &[T], workers: usize, operation: F) -> Vec<R>
8where
9    T: Sync,
10    R: Send,
11    F: Fn(&T) -> R + Sync,
12{
13    let workers = workers.clamp(1, items.len().max(1));
14    if workers == 1 {
15        return items.iter().map(operation).collect();
16    }
17    let next = AtomicUsize::new(0);
18    let mut indexed = std::thread::scope(|scope| {
19        let handles = (0..workers)
20            .map(|_| {
21                scope.spawn(|| {
22                    let mut produced = Vec::new();
23                    loop {
24                        let index = next.fetch_add(1, Ordering::Relaxed);
25                        let Some(item) = items.get(index) else {
26                            break;
27                        };
28                        produced.push((index, operation(item)));
29                    }
30                    produced
31                })
32            })
33            .collect::<Vec<_>>();
34        handles
35            .into_iter()
36            .flat_map(|handle| match handle.join() {
37                Ok(produced) => produced,
38                Err(panic) => std::panic::resume_unwind(panic),
39            })
40            .collect::<Vec<_>>()
41    });
42    indexed.sort_unstable_by_key(|(index, _)| *index);
43    indexed.into_iter().map(|(_, result)| result).collect()
44}
45
46#[cfg(test)]
47mod tests {
48    use super::*;
49
50    #[test]
51    fn map_ordered_should_return_item_order_for_every_worker_count() {
52        let items = (0..257_u64).collect::<Vec<_>>();
53        let expected = items.iter().map(|value| value * 3).collect::<Vec<_>>();
54
55        for workers in [1, 2, 7, 64, 1_000] {
56            assert_eq!(map_ordered(&items, workers, |value| value * 3), expected);
57        }
58    }
59
60    #[test]
61    fn map_ordered_should_accept_empty_input() {
62        let items: [u8; 0] = [];
63
64        assert_eq!(map_ordered(&items, 8, |value| *value), Vec::<u8>::new());
65    }
66}