simd-vector-engine 0.1.0

Runtime-dispatched SIMD kernels for scanning i32/f32 slices: count, sum, find and stream compaction on AVX-512, AVX2, NEON with a scalar fallback
Documentation
// Многопоточный слой над engine.
// Одно ядро упирается в ~20-24 ГБ/с из-за числа Line Fill Buffer'ов, а не ширины регистра.
// Границы чанков кратны 64 элементам: выравнивание сохраняется, кэш-линии не делятся.

use std::sync::OnceLock;
use std::thread;

use crate::engine;

// ниже этого размера spawn дороже работы
const MIN_PARALLEL: usize = 1 << 16;
// 64 элемента = 256 байт
const GRAIN: usize = 64;
// запас под перелив AVX2-ядра за курсор
const TAIL_GUARD: usize = 16;

/// Переопределяется через `SVE_THREADS`.
pub fn threads() -> usize {
    static T: OnceLock<usize> = OnceLock::new();
    *T.get_or_init(|| {
        if let Ok(s) = std::env::var("SVE_THREADS") {
            if let Ok(v) = s.parse::<usize>() {
                if v >= 1 {
                    return v;
                }
            }
        }
        thread::available_parallelism()
            .map(|v| v.get())
            .unwrap_or(1)
    })
}

fn chunk_len(n: usize, t: usize) -> usize {
    let raw = n.div_ceil(t.max(1));
    raw.div_ceil(GRAIN) * GRAIN
}

fn worth_it(n: usize) -> Option<usize> {
    let t = threads();
    if t <= 1 || n < MIN_PARALLEL {
        None
    } else {
        Some(t)
    }
}

pub fn count_gt_i32(data: &[i32], threshold: i32) -> usize {
    let Some(t) = worth_it(data.len()) else {
        return engine::count_gt_i32(data, threshold);
    };
    let cl = chunk_len(data.len(), t);

    // scope гарантирует join до выхода из блока, поэтому без Arc и копий
    thread::scope(|s| {
        let handles: Vec<_> = data
            .chunks(cl)
            .map(|c| s.spawn(move || engine::count_gt_i32(c, threshold)))
            .collect();
        handles.into_iter().map(|h| h.join().unwrap()).sum()
    })
}

pub fn count_gt_f32(data: &[f32], threshold: f32) -> usize {
    let Some(t) = worth_it(data.len()) else {
        return engine::count_gt_f32(data, threshold);
    };
    let cl = chunk_len(data.len(), t);
    thread::scope(|s| {
        let handles: Vec<_> = data
            .chunks(cl)
            .map(|c| s.spawn(move || engine::count_gt_f32(c, threshold)))
            .collect();
        handles.into_iter().map(|h| h.join().unwrap()).sum()
    })
}

/// Сложение i64 ассоциативно, результат не зависит от числа потоков.
pub fn sum_i32(data: &[i32]) -> i64 {
    let Some(t) = worth_it(data.len()) else {
        return engine::sum_i32(data);
    };
    let cl = chunk_len(data.len(), t);
    thread::scope(|s| {
        let handles: Vec<_> = data
            .chunks(cl)
            .map(|c| s.spawn(move || engine::sum_i32(c)))
            .collect();
        handles.into_iter().map(|h| h.join().unwrap()).sum()
    })
}

/// Потоки ищут независимо, берётся минимальный индекс. На раннем вхождении
/// это медленнее однопоточной версии.
pub fn find_i32(data: &[i32], needle: i32) -> Option<usize> {
    let Some(t) = worth_it(data.len()) else {
        return engine::find_i32(data, needle);
    };
    let cl = chunk_len(data.len(), t);
    thread::scope(|s| {
        let handles: Vec<_> = data
            .chunks(cl)
            .enumerate()
            .map(|(i, c)| s.spawn(move || engine::find_i32(c, needle).map(|k| i * cl + k)))
            .collect();
        handles.into_iter().filter_map(|h| h.join().unwrap()).min()
    })
}

/// Два прохода: сначала длины чанков, потом запись по префикс-сумме.
/// На замерах медленнее однопоточной версии: упирается в запись и RFO, см. README.
pub fn filter_into_i32(data: &[i32], threshold: i32, out: &mut [i32]) -> usize {
    let Some(t) = worth_it(data.len()) else {
        return engine::filter_into_i32(data, threshold, out);
    };
    let n = data.len();
    assert!(out.len() >= n, "out должен вмещать весь вход");
    let cl = chunk_len(n, t);

    let counts: Vec<usize> = thread::scope(|s| {
        let hs: Vec<_> = data
            .chunks(cl)
            .map(|c| s.spawn(move || engine::count_gt_i32(c, threshold)))
            .collect();
        hs.into_iter().map(|h| h.join().unwrap()).collect()
    });
    let total: usize = counts.iter().sum();

    thread::scope(|s| {
        let mut rest: &mut [i32] = &mut out[..total];
        for (c, &cnt) in data.chunks(cl).zip(counts.iter()) {
            let (mine, tail) = rest.split_at_mut(cnt);
            rest = tail;
            s.spawn(move || fill_exact(c, threshold, mine));
        }
    });

    total
}

/// Пишет ровно `dst.len()` элементов.
///
/// AVX2-ядро может вылить до 7 элементов за возвращаемую границу, а зоны потоков
/// нарезаны вплотную. Поэтому хвост с TAIL_GUARD совпадений дописывается скалярно.
fn fill_exact(c: &[i32], threshold: i32, dst: &mut [i32]) {
    let mut found = 0usize;
    let mut split = c.len();
    while split > 0 && found < TAIL_GUARD {
        split -= 1;
        if c[split] > threshold {
            found += 1;
        }
    }

    let (body_end, mut w) = if found >= TAIL_GUARD {
        (split, engine::filter_dispatch(&c[..split], threshold, dst))
    } else {
        (0, 0)
    };

    for &x in &c[body_end..] {
        if x > threshold {
            dst[w] = x;
            w += 1;
        }
    }
    debug_assert_eq!(w, dst.len());
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::aligned::AlignedVec;
    use crate::kernels::scalar;

    fn sample() -> AlignedVec<i32> {
        // длина не кратна ни GRAIN, ни числу потоков
        AlignedVec::from_fn(1_000_003, |i| (i as i32 % 1000) - 500)
    }

    #[test]
    fn par_count_matches_scalar() {
        let v = sample();
        assert_eq!(count_gt_i32(&v, 250), scalar::count_gt_i32(&v, 250));
    }

    #[test]
    fn par_sum_is_bitwise_identical() {
        let v = sample();
        assert_eq!(sum_i32(&v), scalar::sum_i32(&v));
    }

    #[test]
    fn par_find_returns_first_not_any() {
        let mut v = sample();
        let slice = v.as_mut_slice();
        // два вхождения в разных чанках
        slice[123_457] = 777_777;
        slice[888_888] = 777_777;
        assert_eq!(find_i32(&v, 777_777), Some(123_457));
        assert_eq!(find_i32(&v, 424_242), None);
    }

    #[test]
    fn par_filter_matches_scalar_exactly() {
        let v = sample();
        let mut a = vec![0i32; v.len()];
        let mut b = vec![0i32; v.len()];
        let n1 = filter_into_i32(&v, 250, &mut a);
        let n2 = scalar::filter_into_i32(&v, 250, &mut b);
        assert_eq!(n1, n2);
        assert_eq!(a[..n1], b[..n2]);
    }

    #[test]
    fn tiny_input_falls_back_to_single_thread() {
        let v: Vec<i32> = (0..100).collect();
        assert_eq!(count_gt_i32(&v, 50), 49);
    }
}