Stream compaction на NEON. Векторизуем copy_if

В сфере искусственного интеллекта произошло заметное событие. a_eridani 38 минут назад Stream compaction на NEON. Векторизуем copy_if Средний 7 мин 1. 7K C++ * Assembler * Алгоритмы * Компиляторы * Туториал Из песочницы ЗадачаДаны массивы a и out.

Нужно записать в out подряд, без пробелов, только те элементы a, которые удовлетворяют заданному условию. В статье — условие a > threshold, a ∈ (0, 1), threshold ∈ {0, 0. Почему компилятор сдаетсяОдин if внутри цикла копирования роняет скорость с 112 до 2.

Технические детали

Компилятор не может векторизовать — в NEON нет подходящей для этого инструкции. Статья о том, как собрать ее. auto copy_if(const float* a, float* out, size_t n) { size_t j = 0; for (size_t i = 0; i < n; ++i) { if (a > 0) out = a; } return j; } В задаче copy_if выходной курсор (в коде - j) зависит от данных, поэтому, чтобы компилятор векторизовал, нужна compress-инструкция (собирает выбранные элементы регистра подряд в его начало, без дырок), а в NEON ее нет, поэтому компилятор сдается:clang++ -O3 -Rpass-analysis=loop-vectorize -std=c++23 main.

cpp:5:5: remark: loop not vectorized: value that could not be identified as reduction is used outside the loop 5 | for (size_t i = 0; i < n; ++i) { | ^ main. cpp:6:23: remark: loop not vectorized: cannot identify array bounds 6 | if (a > 0) out = a; Векторизатор clang умеет классифицировать j либо как induction (фиксированный шаг), либо как reduction (свертка). j не является ни тем, ни другим — он курсор, зависящий от данных.

Компилятор не умеет векторизовать такой вид курсоров. Вторая ремарка отсюда же: он не может вычислить диапазон обращений к out. Замер: две проблемы скаляравсе замеры: Apple M5; clang++ -O3 -std=c++23 -march=native; GB/s = (2n * 4 байта) / время, минимум из 3e9 / n прогонов; cache: n=1e5, DRAM: n=1e7Функцияms (cache)GB/s (cache)ms (DRAM)GB/s (DRAM)copy a0.

Отраслевые последствия

71112copy a if a > 00. 4133copy a if a > 0. 6copy a if a > 10.

3933“copy a” — тот же цикл, но без условия, его компилятор векторизует. Вся разница с ним в одном if. Данные те же, меняется только предсказуемость ветки:> 0 (всегда true) и > 1 (всегда false): branch predictor не промахивается → 33 GB/s.

Из-за отсутствия векторизации скорость падает в 3 раза> 0. 5 (50/50): промах на каждом втором → 3 GB/sТрюк исправит обе эти проблемы. Трюк 1: эмулируем compressДальше считаем n кратным ширине регистра; хвост — отдельная тема, к трюку отношения не имеет.

Этот прогресс даёт важные сигналы о будущем отрасли, и технологический мир внимательно наблюдает.