Skip to main content

simd_vector_engine/
parallel.rs

1// Многопоточный слой над engine.
2// Одно ядро упирается в ~20-24 ГБ/с из-за числа Line Fill Buffer'ов, а не ширины регистра.
3// Границы чанков кратны 64 элементам: выравнивание сохраняется, кэш-линии не делятся.
4
5use std::sync::OnceLock;
6use std::thread;
7
8use crate::engine;
9
10// ниже этого размера spawn дороже работы
11const MIN_PARALLEL: usize = 1 << 16;
12// 64 элемента = 256 байт
13const GRAIN: usize = 64;
14// запас под перелив AVX2-ядра за курсор
15const TAIL_GUARD: usize = 16;
16
17/// Переопределяется через `SVE_THREADS`.
18pub fn threads() -> usize {
19    static T: OnceLock<usize> = OnceLock::new();
20    *T.get_or_init(|| {
21        if let Ok(s) = std::env::var("SVE_THREADS") {
22            if let Ok(v) = s.parse::<usize>() {
23                if v >= 1 {
24                    return v;
25                }
26            }
27        }
28        thread::available_parallelism()
29            .map(|v| v.get())
30            .unwrap_or(1)
31    })
32}
33
34fn chunk_len(n: usize, t: usize) -> usize {
35    let raw = n.div_ceil(t.max(1));
36    raw.div_ceil(GRAIN) * GRAIN
37}
38
39fn worth_it(n: usize) -> Option<usize> {
40    let t = threads();
41    if t <= 1 || n < MIN_PARALLEL {
42        None
43    } else {
44        Some(t)
45    }
46}
47
48pub fn count_gt_i32(data: &[i32], threshold: i32) -> usize {
49    let Some(t) = worth_it(data.len()) else {
50        return engine::count_gt_i32(data, threshold);
51    };
52    let cl = chunk_len(data.len(), t);
53
54    // scope гарантирует join до выхода из блока, поэтому без Arc и копий
55    thread::scope(|s| {
56        let handles: Vec<_> = data
57            .chunks(cl)
58            .map(|c| s.spawn(move || engine::count_gt_i32(c, threshold)))
59            .collect();
60        handles.into_iter().map(|h| h.join().unwrap()).sum()
61    })
62}
63
64pub fn count_gt_f32(data: &[f32], threshold: f32) -> usize {
65    let Some(t) = worth_it(data.len()) else {
66        return engine::count_gt_f32(data, threshold);
67    };
68    let cl = chunk_len(data.len(), t);
69    thread::scope(|s| {
70        let handles: Vec<_> = data
71            .chunks(cl)
72            .map(|c| s.spawn(move || engine::count_gt_f32(c, threshold)))
73            .collect();
74        handles.into_iter().map(|h| h.join().unwrap()).sum()
75    })
76}
77
78/// Сложение i64 ассоциативно, результат не зависит от числа потоков.
79pub fn sum_i32(data: &[i32]) -> i64 {
80    let Some(t) = worth_it(data.len()) else {
81        return engine::sum_i32(data);
82    };
83    let cl = chunk_len(data.len(), t);
84    thread::scope(|s| {
85        let handles: Vec<_> = data
86            .chunks(cl)
87            .map(|c| s.spawn(move || engine::sum_i32(c)))
88            .collect();
89        handles.into_iter().map(|h| h.join().unwrap()).sum()
90    })
91}
92
93/// Потоки ищут независимо, берётся минимальный индекс. На раннем вхождении
94/// это медленнее однопоточной версии.
95pub fn find_i32(data: &[i32], needle: i32) -> Option<usize> {
96    let Some(t) = worth_it(data.len()) else {
97        return engine::find_i32(data, needle);
98    };
99    let cl = chunk_len(data.len(), t);
100    thread::scope(|s| {
101        let handles: Vec<_> = data
102            .chunks(cl)
103            .enumerate()
104            .map(|(i, c)| s.spawn(move || engine::find_i32(c, needle).map(|k| i * cl + k)))
105            .collect();
106        handles.into_iter().filter_map(|h| h.join().unwrap()).min()
107    })
108}
109
110/// Два прохода: сначала длины чанков, потом запись по префикс-сумме.
111/// На замерах медленнее однопоточной версии: упирается в запись и RFO, см. README.
112pub fn filter_into_i32(data: &[i32], threshold: i32, out: &mut [i32]) -> usize {
113    let Some(t) = worth_it(data.len()) else {
114        return engine::filter_into_i32(data, threshold, out);
115    };
116    let n = data.len();
117    assert!(out.len() >= n, "out должен вмещать весь вход");
118    let cl = chunk_len(n, t);
119
120    let counts: Vec<usize> = thread::scope(|s| {
121        let hs: Vec<_> = data
122            .chunks(cl)
123            .map(|c| s.spawn(move || engine::count_gt_i32(c, threshold)))
124            .collect();
125        hs.into_iter().map(|h| h.join().unwrap()).collect()
126    });
127    let total: usize = counts.iter().sum();
128
129    thread::scope(|s| {
130        let mut rest: &mut [i32] = &mut out[..total];
131        for (c, &cnt) in data.chunks(cl).zip(counts.iter()) {
132            let (mine, tail) = rest.split_at_mut(cnt);
133            rest = tail;
134            s.spawn(move || fill_exact(c, threshold, mine));
135        }
136    });
137
138    total
139}
140
141/// Пишет ровно `dst.len()` элементов.
142///
143/// AVX2-ядро может вылить до 7 элементов за возвращаемую границу, а зоны потоков
144/// нарезаны вплотную. Поэтому хвост с TAIL_GUARD совпадений дописывается скалярно.
145fn fill_exact(c: &[i32], threshold: i32, dst: &mut [i32]) {
146    let mut found = 0usize;
147    let mut split = c.len();
148    while split > 0 && found < TAIL_GUARD {
149        split -= 1;
150        if c[split] > threshold {
151            found += 1;
152        }
153    }
154
155    let (body_end, mut w) = if found >= TAIL_GUARD {
156        (split, engine::filter_dispatch(&c[..split], threshold, dst))
157    } else {
158        (0, 0)
159    };
160
161    for &x in &c[body_end..] {
162        if x > threshold {
163            dst[w] = x;
164            w += 1;
165        }
166    }
167    debug_assert_eq!(w, dst.len());
168}
169
170#[cfg(test)]
171mod tests {
172    use super::*;
173    use crate::aligned::AlignedVec;
174    use crate::kernels::scalar;
175
176    fn sample() -> AlignedVec<i32> {
177        // длина не кратна ни GRAIN, ни числу потоков
178        AlignedVec::from_fn(1_000_003, |i| (i as i32 % 1000) - 500)
179    }
180
181    #[test]
182    fn par_count_matches_scalar() {
183        let v = sample();
184        assert_eq!(count_gt_i32(&v, 250), scalar::count_gt_i32(&v, 250));
185    }
186
187    #[test]
188    fn par_sum_is_bitwise_identical() {
189        let v = sample();
190        assert_eq!(sum_i32(&v), scalar::sum_i32(&v));
191    }
192
193    #[test]
194    fn par_find_returns_first_not_any() {
195        let mut v = sample();
196        let slice = v.as_mut_slice();
197        // два вхождения в разных чанках
198        slice[123_457] = 777_777;
199        slice[888_888] = 777_777;
200        assert_eq!(find_i32(&v, 777_777), Some(123_457));
201        assert_eq!(find_i32(&v, 424_242), None);
202    }
203
204    #[test]
205    fn par_filter_matches_scalar_exactly() {
206        let v = sample();
207        let mut a = vec![0i32; v.len()];
208        let mut b = vec![0i32; v.len()];
209        let n1 = filter_into_i32(&v, 250, &mut a);
210        let n2 = scalar::filter_into_i32(&v, 250, &mut b);
211        assert_eq!(n1, n2);
212        assert_eq!(a[..n1], b[..n2]);
213    }
214
215    #[test]
216    fn tiny_input_falls_back_to_single_thread() {
217        let v: Vec<i32> = (0..100).collect();
218        assert_eq!(count_gt_i32(&v, 50), 49);
219    }
220}