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
// Многопоточный слой (C++20). Зеркало src/parallel.rs.
//
// Одно ядро не выбирает всю полосу DRAM: его потолок задан числом
// Line Fill Buffer'ов (~10-12 одновременных промахов L1), а не шириной регистра.
// Поэтому после AVX-512 единственный способ ускориться ещё — больше ядер.
//
// Границы чанков кратны 64 элементам (256 байт): сохраняется 64-байтное
// выравнивание внутри каждого чанка и исключается false sharing.

#include "sve/sve.hpp"

#include <algorithm>
#include <cstring>
#include <thread>
#include <utility>
#include <vector>

#if defined(_MSC_VER)
#  include <cstdlib>
#endif

namespace sve::par {
namespace {

constexpr std::size_t kMinParallel = 1u << 16;
constexpr std::size_t kGrain       = 64;

std::size_t chunk_len(std::size_t n, std::size_t t) noexcept {
    const std::size_t raw = (n + t - 1) / t;
    return ((raw + kGrain - 1) / kGrain) * kGrain;
}

// Разбивка [0, n) на полуинтервалы.
std::vector<std::pair<std::size_t, std::size_t>> split(std::size_t n, std::size_t cl) {
    std::vector<std::pair<std::size_t, std::size_t>> v;
    for (std::size_t i = 0; i < n; i += cl) v.emplace_back(i, std::min(i + cl, n));
    return v;
}

// Сколько свободных слотов оставляем векторному ядру под «перелив».
constexpr std::size_t kTailGuard = 16;

// Записывает в dst РОВНО dst.size() элементов и ни байтом больше.
//
// AVX2-ядро делает vmovdqu на 8 лейнов, а курсор двигает на popcnt — то есть
// до 7 элементов выливается за курсор. При точной нарезке выхода по
// префикс-сумме этот перелив залез бы в зону соседнего потока — гонка.
// Отрезаем с конца чанка хвост, содержащий >= kTailGuard совпадений,
// и дописываем его скалярно — тогда у ядра всегда есть запас впереди.
void fill_exact(std::span<const std::int32_t> c, std::int32_t thr,
                std::span<std::int32_t> dst) {
    std::size_t found = 0;
    std::size_t sp    = c.size();
    while (sp > 0 && found < kTailGuard) {
        --sp;
        if (c[sp] > thr) ++found;
    }

    std::size_t body_end = 0, w = 0;
    if (found >= kTailGuard) {
        body_end = sp;
        w        = sve::filter_into_i32(c.subspan(0, sp), thr, dst);
    }
    for (std::size_t i = body_end; i < c.size(); ++i)
        if (c[i] > thr) dst[w++] = c[i];
}

}  // namespace

std::size_t threads() noexcept {
    static const std::size_t t = [] () -> std::size_t {
        if (const char* e = std::getenv("SVE_THREADS")) {
            const long v = std::strtol(e, nullptr, 10);
            if (v >= 1) return static_cast<std::size_t>(v);
        }
        const unsigned hc = std::thread::hardware_concurrency();
        return hc ? hc : 1u;
    }();
    return t;
}

std::size_t count_gt_i32(std::span<const std::int32_t> d, std::int32_t thr) {
    const std::size_t t = threads();
    if (t <= 1 || d.size() < kMinParallel) return sve::count_gt_i32(d, thr);

    const auto           parts = split(d.size(), chunk_len(d.size(), t));
    std::vector<std::size_t> res(parts.size());
    std::vector<std::thread> ws;
    ws.reserve(parts.size());

    for (std::size_t k = 0; k < parts.size(); ++k)
        ws.emplace_back([&, k] {
            res[k] = sve::count_gt_i32(d.subspan(parts[k].first, parts[k].second - parts[k].first), thr);
        });
    for (auto& w : ws) w.join();

    std::size_t total = 0;
    for (auto v : res) total += v;
    return total;
}

std::size_t count_gt_f32(std::span<const float> d, float thr) {
    const std::size_t t = threads();
    if (t <= 1 || d.size() < kMinParallel) return sve::count_gt_f32(d, thr);

    const auto           parts = split(d.size(), chunk_len(d.size(), t));
    std::vector<std::size_t> res(parts.size());
    std::vector<std::thread> ws;
    ws.reserve(parts.size());

    for (std::size_t k = 0; k < parts.size(); ++k)
        ws.emplace_back([&, k] {
            res[k] = sve::count_gt_f32(d.subspan(parts[k].first, parts[k].second - parts[k].first), thr);
        });
    for (auto& w : ws) w.join();

    std::size_t total = 0;
    for (auto v : res) total += v;
    return total;
}

// Сложение i64 ассоциативно => результат бит-в-бит такой же, как у 1 потока.
// Для float такой гарантии нет: сумма зависит от порядка.
std::int64_t sum_i32(std::span<const std::int32_t> d) {
    const std::size_t t = threads();
    if (t <= 1 || d.size() < kMinParallel) return sve::sum_i32(d);

    const auto            parts = split(d.size(), chunk_len(d.size(), t));
    std::vector<std::int64_t> res(parts.size());
    std::vector<std::thread>  ws;
    ws.reserve(parts.size());

    for (std::size_t k = 0; k < parts.size(); ++k)
        ws.emplace_back([&, k] {
            res[k] = sve::sum_i32(d.subspan(parts[k].first, parts[k].second - parts[k].first));
        });
    for (auto& w : ws) w.join();

    std::int64_t total = 0;
    for (auto v : res) total += v;
    return total;
}

// Возвращает МИНИМАЛЬНЫЙ индекс по всем чанкам — результат детерминирован
// и совпадает с однопоточным, а не «кто первый нашёл».
std::optional<std::size_t> find_i32(std::span<const std::int32_t> d, std::int32_t needle) {
    const std::size_t t = threads();
    if (t <= 1 || d.size() < kMinParallel) return sve::find_i32(d, needle);

    const auto parts = split(d.size(), chunk_len(d.size(), t));
    std::vector<std::optional<std::size_t>> res(parts.size());
    std::vector<std::thread> ws;
    ws.reserve(parts.size());

    for (std::size_t k = 0; k < parts.size(); ++k)
        ws.emplace_back([&, k] {
            const auto [b, e] = parts[k];
            if (auto r = sve::find_i32(d.subspan(b, e - b), needle)) res[k] = b + *r;
        });
    for (auto& w : ws) w.join();

    for (const auto& r : res)
        if (r) return r;  // parts упорядочены по возрастанию => первый непустой и есть минимум
    return std::nullopt;
}

// Пакетный отбор в два прохода, без блокировок и атомиков:
//   1. чтение: считаем выходную длину каждого чанка и префикс-сумму;
//   2. запись: каждый поток кладёт данные сразу на финальное место.
// Операция write-bound и на замерах медленнее однопоточной версии, см. README §4c.
std::size_t filter_into_i32(std::span<const std::int32_t> d, std::int32_t thr,
                            std::span<std::int32_t> out) {
    const std::size_t t = threads();
    if (t <= 1 || d.size() < kMinParallel) return sve::filter_into_i32(d, thr, out);

    const auto            parts = split(d.size(), chunk_len(d.size(), t));
    std::vector<std::size_t> cnt(parts.size());
    std::vector<std::thread> ws;
    ws.reserve(parts.size());

    // ПРОХОД 1 (только чтение): сколько выдаст каждый чанк.
    for (std::size_t k = 0; k < parts.size(); ++k)
        ws.emplace_back([&, k] {
            const auto [b, e] = parts[k];
            cnt[k] = sve::count_gt_i32(d.subspan(b, e - b), thr);
        });
    for (auto& w : ws) w.join();
    ws.clear();

    std::vector<std::size_t> prefix(parts.size() + 1, 0);
    for (std::size_t k = 0; k < parts.size(); ++k) prefix[k + 1] = prefix[k] + cnt[k];

    // Проход 2: запись по готовым смещениям, зоны потоков не пересекаются.
    for (std::size_t k = 0; k < parts.size(); ++k)
        ws.emplace_back([&, k] {
            const auto [b, e] = parts[k];
            fill_exact(d.subspan(b, e - b), thr, out.subspan(prefix[k], cnt[k]));
        });
    for (auto& w : ws) w.join();

    return prefix.back();
}

}  // namespace sve::par