# simd-vector-engine
Вычислительное ядро для пакетной обработки массивов `i32` и `f32` на AVX-512, AVX2 и NEON,
с рантайм-диспетчеризацией и многопоточным слоем. Две независимые реализации — Rust и C++20 —
с одинаковым API и общим бенчмарком.
Поддерживаемые операции:
| Подсчёт по предикату | `count_gt_i32(data, threshold) -> usize` |
| То же для float | `count_gt_f32(data, threshold) -> usize` |
| Агрегация | `sum_i32(data) -> i64` |
| Поиск первого вхождения | `find_i32(data, needle) -> Option<usize>` |
| Пакетный отбор (compaction) | `filter_into_i32(data, threshold, out) -> usize` |
Протестировано на Intel Core i5-11400F (Rocket Lake, 6C/12T, AVX-512, DDR4 dual-channel),
Windows 11 + MSVC 19.51, Rust 1.97.
## Архитектура
Четыре слоя, снизу вверх:
1. **Детекция CPU** (`src/cpu.rs`, `cpp/src/cpu.cpp`) — CPUID + XGETBV один раз за процесс,
результат кэшируется.
2. **Ядра** (`src/kernels/`, `cpp/src/kernels_*.cpp`) — по файлу на ISA: scalar, AVX2, AVX-512, NEON.
3. **Диспетчер** (`src/engine.rs`, `cpp/src/dispatch.cpp`) — безопасный фасад, весь `unsafe` здесь.
4. **Многопоточность** (`src/parallel.rs`, `cpp/src/parallel.cpp`) — тот же контракт,
работа разделена между ядрами.
```
src/ cpp/
cpu.rs include/sve/sve.hpp
aligned.rs src/cpu.cpp
kernels/ src/dispatch.cpp
scalar.rs src/parallel.cpp
avx2.rs src/kernels_scalar.cpp
avx512.rs src/kernels_avx2.cpp
neon.rs src/kernels_avx512.cpp
engine.rs src/kernels_neon.cpp
parallel.rs src/bench.cpp
bin/bench.rs CMakeLists.txt
```
### Детекция инструкций
Проверки битов CPUID недостаточно. Операционная система должна ещё сохранять
широкие регистры при переключении контекста, иначе значения будут портиться молча.
Поэтому проверяются и биты XCR0 через XGETBV:
* `XCR0[2:1] == 11b` — OS сохраняет YMM, можно AVX/AVX2;
* `XCR0[7:5] == 111b` дополнительно — OS сохраняет ZMM и масковые регистры, можно AVX-512.
Цепочка выбора: AVX-512 -> AVX2 -> NEON (ARM) -> скаляр.
Переопределить можно переменной `SVE_ISA=scalar|avx2|avx512|neon` — только в сторону
ослабления, включить неподдерживаемый набор нельзя.
### Выравнивание
`AlignedVec` выделяет память по границе 64 байта. На выровненных данных ядра берут
`vmovdqa`/`vmovdqa64`, иначе `vmovdqu`. Флаг вычисляется один раз до цикла:
aligned-загрузка по невыровненному адресу даёт `#GP`, а не замедление.
На современных ядрах выигрыш от aligned-варианта небольшой, но выравнивание важно само по себе:
512-битный доступ без него гарантированно рвёт кэш-линию и требует двух обращений к L1.
### Структура циклов
Все ядра развёрнуты на 4 вектора с независимыми аккумуляторами. У `vpaddd` латентность 1 такт
при пропускной способности 2-3 инструкции за такт; с одним аккумулятором цикл упёрся бы
в loop-carried dependency вместо памяти.
Сравнение даёт маску 0/-1, поэтому подсчёт делается через `acc -= mask` — одна инструкция
без ветвлений. В AVX-512 сравнение возвращает `__mmask16`, и шаг с `movemask` отпадает.
### Пакетный отбор
Самая интересная операция — единственная, где скалярная версия страдает не от ширины
регистра, а от непредсказуемого ветвления (`if (x > thr)` при ~50% срабатываний —
почти гарантированный промах предсказателя, ~15-20 тактов штрафа).
* AVX-512: `vpcompressd` пишет отмеченные маской лейны плотно, одной инструкцией.
* AVX2: аналога нет, используется `vpermd` с таблицей перестановок на 256 масок (8 КБ,
строится в compile-time).
* NEON: в базовом наборе compaction нет (появляется только в SVE2), поэтому векторно
пропускаются пустые блоки, а запись внутри непустых скалярная.
Важный нюанс AVX2-версии: `vmovdqu` пишет все 8 лейнов, а курсор двигается на popcount,
то есть до 7 элементов мусора оказывается за возвращаемой границей. В одном потоке это
безвредно, в многопоточном слое была бы гонка, поэтому там хвост чанка дописывается
скалярно (`fill_exact`).
## Сборка
### Rust
```
cargo build --release
cargo test --release
cargo run --release --bin bench
```
Требуется Rust 1.89+. `-C target-cpu=native` не нужен и нежелателен: ISA выбирается
в рантайме, а с `native` компилятор сможет поставить широкие инструкции в сам диспетчер.
### C++20
```
cmake -S cpp -B cpp/build -G Ninja -DCMAKE_BUILD_TYPE=Release
cmake --build cpp/build
./cpp/build/bench
```
На Windows есть `build_cpp.bat` — он сам вызывает `vcvars64.bat` и cmake/ninja из поставки
Visual Studio. На Linux — `./build.sh` (режимы `all`, `cpp`, `rust`, `run`).
Флаги ISA в CMake заданы пофайлово (`/arch:AVX512`, `-mavx512f` и т.д.), а не глобально.
`-march=native` не используется по той же причине, что и `target-cpu=native` в Rust.
### Переменные окружения
| `SVE_ISA` | `scalar` / `avx2` / `avx512` / `neon` — принудительный бэкенд |
| `SVE_THREADS` | число потоков, по умолчанию — число логических ядер |
## Замеры
N = 100 000 000 элементов (400 МБ на массив), 3 повтора, берётся лучший.
Контрольные суммы всех бэкендов совпадают.
### Rust, один поток
| Фильтрация i32 | 29.93 мс | 17.12 мс | 18.21 мс | 1.75x |
| Агрегация i32 | 28.14 мс | 19.71 мс | 17.92 мс | 1.57x |
| Поиск (worst case) | 43.21 мс | 17.86 мс | 17.14 мс | 2.52x |
| Фильтрация f32 | 25.82 мс | 21.61 мс | 18.80 мс | 1.37x |
| Пакетный отбор | 340.13 мс | 34.30 мс | 35.80 мс | 9.92x |
### C++20, MSVC 19.51 /O2, один поток
Цифры близки к Rust на всех операциях; пакетный отбор на AVX-512 — 28.70 мс
(13.94 ГБ/с, 11.51x к скаляру). Разброс между языками в пределах 5-10% и объясняется
разницей в кодогене хвостов и прологов, а не самих ядер — интринсики одни и те же.
### Многопоточность (12 потоков)
| count i32 | 18.10 мс / 22.1 ГБ/с | 12.07 мс / 33.1 ГБ/с | 16.09 мс | 11.89 мс / 33.7 ГБ/с |
| sum i32 | 18.85 мс | 12.53 мс / 31.9 ГБ/с | 17.73 мс | 11.95 мс / 33.5 ГБ/с |
| find (worst) | 17.91 мс | 12.76 мс / 31.4 ГБ/с | 15.55 мс | 12.02 мс / 33.3 ГБ/с |
| count f32 | 19.95 мс | 12.82 мс / 31.2 ГБ/с | 16.30 мс | 11.93 мс / 33.5 ГБ/с |
| filter_into | 34.27 мс | 39.76 мс | 28.55 мс | 37.28 мс |
Потолок ~33.5 ГБ/с — это практически пропускная способность двухканального DDR4.
Дальше масштабироваться некуда ни шириной регистра, ни числом потоков.
Суммарно от скалярной версии в один поток до SIMD в 12 потоков: поиск 43.2 -> 12.8 мс (3.4x),
подсчёт i32 29.9 -> 12.1 мс (2.5x), подсчёт f32 25.8 -> 12.8 мс (2.0x).
### Отрицательный результат: параллельный `filter_into_i32`
Многопоточный пакетный отбор медленнее однопоточного (0.86x в Rust, 0.77x в C++).
Было пробовано две схемы:
1. Один проход, каждый поток пишет в свою зону, затем `copy_within` схлопывает дыры — 0.83x.
2. Два прохода: параллельный подсчёт, префикс-сумма, запись сразу на финальные места — 0.86x
(текущая).
Причина в том, что операция write-bound. Запись в память требует Read-For-Ownership:
перед записью кэш-линия сначала читается, так что реальный трафик около 800 МБ,
а не 600 МБ. Канал памяти уже насыщен одним потоком, и любой дополнительный проход
съедает весь выигрыш от многоядерности.
NT-запись (`_mm256_stream_si256`) здесь не применима: она требует выравнивания по 64 байта,
а курсор compaction встаёт на произвольные смещения. Поэтому для этой операции
рекомендуется однопоточный `engine::filter_into_i32`; многопоточный вариант оставлен для
случаев, когда результат потребляется почанково.
### Сравнение с baseline на std-итераторах
`cargo bench` гоняет criterion против того кода, который напишет человек без этой
библиотеки: `iter().filter().count()`, `iter().sum()`, `iter().position()`. LLVM
автовекторизует их сам, так что это не соломенное чучело.
16M элементов i32 (64 MiB), i5-11400F, медиана criterion:
| `count_gt_i32` | 6.94 мс / 9.01 GiB/s | 3.09 мс / 20.24 GiB/s | 2.43 мс / 25.73 GiB/s | **2.86x** |
| `sum_i32` | 4.09 мс / 15.27 GiB/s | 2.88 мс / 21.68 GiB/s | 2.43 мс / 25.73 GiB/s | **1.68x** |
| `find_i32` (худший случай) | 5.58 мс / 11.20 GiB/s | 2.82 мс / 22.19 GiB/s | — | **1.98x** |
| `filter_into_i32` | 66.95 мс / 0.93 GiB/s | 13.38 мс / 4.67 GiB/s | — | **5.01x** |
На `sum_i32` выигрыш маленький и так и должно быть: LLVM разворачивает цикл сам,
и обе версии быстро упираются в пропускную способность памяти. Главный разрыв —
на `filter_into_i32`: скалярный цикл ветвится на каждом элементе и ловит промахи
предсказателя, а `vpcompressd` упаковывает 16 элементов без единого ветвления.
## Кроссплатформенность
| CPUID | `__cpuidex` | `__cpuid_count` из `<cpuid.h>` |
| XGETBV | `_xgetbv` | inline asm `xgetbv` |
| Выровненная память | `_aligned_malloc` / `_aligned_free` | `std::aligned_alloc` / `std::free` |
| Флаги ISA | `/arch:AVX2`, `/arch:AVX512` | `-mavx2`, `-mavx512f -mavx512bw -mavx512dq -mavx512vl` |
| Оптимизация | `/O2 /Oi /GL /fp:fast` | `-O3 -fno-math-errno` |
| Потоки | `std::thread` | `std::thread` + `Threads::Threads` |
Rust-часть кроссплатформенна без `#[cfg]` по OS: `is_x86_feature_detected!` и
`std::alloc::alloc` с явным `Layout` работают одинаково везде. Разделение идёт только
по архитектуре (`target_arch`), не по платформе.
## Тесты
13 тестов в Rust: каждый SIMD-бэкенд сверяется со скалярной версией на длинах, не кратных
ширине вектора (100 003 и 1 000 003 элемента), чтобы ловить ошибки в хвостах.
Отдельно проверяется, что параллельный `find_i32` возвращает первое вхождение,
а не произвольное, и что параллельная сумма бит-в-бит совпадает с однопоточной.
CI собирает проект на ubuntu-latest (GCC) и windows-latest (MSVC): Rust-тесты плюс сборка C++.
## Ограничения
* NEON-ядра написаны и входят в сборку под aarch64, но на реальном ARM не замерялись.
* Поддерживаются только `i32` и `f32`; `i64`/`f64` потребуют отдельных ядер.
* `filter_into_i32` на AVX2 требует запаса в 7 элементов в выходном буфере.