SIMD найти первый элемент больше x
Я учусь использовать SIMD в C++, и это моя попытка реализовать версию SIMD «найти первый элемент, больший или равный X».
Мои вопросы:
- Можно ли заменить
reinterpret_castкаким-нибудь внутренним? - Лучше ли убедиться, что содержимое
reinterpret_castвыровнено, начиная аналогичным образом до конца и используя логику, отличную от simd, для элементов до первого выровненного короткого фрагмента?
// reference function of desired behavior
inline auto find_first_greater_or_equal_simple(const std::vector<short>& v, short insert)
{
for (auto it = v.begin(), end = v.end(); it != end; ++it)
{
if (*it >= insert) return it;
}
return v.end();
}
// simd version
inline auto find_first_greater_or_equal_simd(const std::vector<short>& v, short insert)
{
const __m512i target = _mm512_set1_epi16(insert);
auto it = v.begin();
const auto end = v.end();
const auto end_simd = it + 32 * ((end - it) / 32);
__mmask32 cmpge_mask{};
for (; it != end_simd &&
!(cmpge_mask = _mm512_cmpge_epi16_mask(*reinterpret_cast<const __m512i*>(&*it), target));
it += 32)
{}
if (cmpge_mask)
{
unsigned long local_idx;
_BitScanForward(&local_idx, cmpge_mask); // todo: __builtin_ctz
return it + local_idx;
}
for (; it != end; ++it)
{
if (*it >= insert) return it;
}
return v.end();
}
@PeterCordes Компилятор может генерировать tzcnt для _BitScanForward, если это позволяет целевой процессор (и он это делает, когда включен AVX-512). gcc делает именно это, например, для __builtin_ctz.
@AndreySemachev: Нет, _BitScanForward является свойством bsf, в частности (felixcloutier.com/x86/bsf ). Как обычно, MSVC воспринимает это буквально, не используя tzcnt с -arch:AVX2 или -arch:AVX512 godbolt.org/z/K9T8Tc9rb (-arch:AVX2 MSVC действительно подразумевает BMI1+2, как вы можете видеть из этого, используя tzcnt для std::countr_zero. MSVC лечит «AVX2» так же, как GCC/Clang обрабатывает -march=x86-64-v3, но MSVC не оптимизирует внутренние функции.) Конечно, GCC или Clang оптимизируют __builtin_ctz до наилучшего доступного asm, но это не переносится на MSVC.
@PeterCordes В спецификации _BitScanForward не упоминается bsf. Фактически, встроенная функция также поддерживается в ARM. Тот факт, что MSVC не генерирует tzcnt для него, когда это возможно, является вопросом качества и может быть сообщен разработчикам компилятора как пропущенная оптимизация.
@AndreySemachev: Ой, странно. Intel документирует это как встроенную функцию bsf. intel.com/content/www/us/en/docs/intrinsics-guide/… . К счастью, это все спорный вопрос, если доступен C++20 std::countr_zero или если вы уже используете функции x86-64-v3 и можете использовать _tzcnt_u32. Или, если вы знаете, что ваш ввод не равен нулю, вы можете использовать _tzcnt_u32, даже если он может работать как bsf, если вы используете MSVC или classic-ICC, которые позволяют вам использовать встроенные функции для расширений, которые вы не включили.
Ответы 1
Обычно я просто использую математику указателей с внутренними функциями SIMD или &v[i], а не итераторами .begin()/.end(). Использование SIMD зависит от непрерывного хранения элементов, поэтому мы не получаем какой-либо общности для коллекций, в которых итератор не эквивалентен const int*.
Ваш reinterpret_castэквивалентен_mm512_load_si512(it), что является версией, требующей выравнивания. (В оптимизированных сборках компилятор складывает нагрузку в операнд источника памяти для vpcmpd, который не обеспечивает выравнивание.) Если ваш указатель не выровнен, используйте _mm512_loadu_si512.
Для векторов шириной менее 512 встроенные функции загрузки/сохранения __m128i/ __m256i имеют менее удобные определения, которые не принимают аргументы void*, поэтому вам понадобится _mm256_loadu_si256( (const __m256i*) ptr_expression ). Intel перешла на void* для встроенных функций, представленных примерно с 2015 года, которые включают в себя все новое с AVX-512, но не изменили задним числом старые встроенные функции, поэтому нам все еще нужны эти шумные приведения повсюду для работы с целочисленными векторами.
Да, особенно на процессорах Intel рекомендуется выравнивать указатели при использовании 512-битных векторов. В идеале вы можете просто использовать выровненный распределитель для вашего std::vector, чтобы данные всегда были выровнены. (Если вы всегда проверяете только начало std::vector, а не какую-то отправную точку в середине.) Или если ваши данные обычно выровнены, причем достаточно часто, чтобы не оправдать дополнительные затраты на выравнивание при запуске.
Но в этом случае можно очень дешево справиться с возможным несовпадением: проверьте первый вектор, затем выровняйте указатель. Первый выровненный вектор будет частично перекрывать первый вектор, если он не был выровнен, но это нормально; вам не нужно избегать двойной проверки одного и того же элемента, поскольку вы не суммируете или что-то в этом роде. Этот трюк также работает для циклов копирования и изменения, таких как dst[i] = f(src[i]), где вы никогда не вызываете его с dst==src для работы на месте.
Тот же прием можно использовать для обработки конца массива, если общий размер массива равен хотя бы одному вектору. Если небольшие массивы не являются редкостью в вашем предполагаемом варианте использования, рассмотрите для очистки 128-битные или 256-битные векторы, что потенциально позволит использовать этот трюк. Или дополните или выровняйте массивы, чтобы их можно было безопасно читать после конца, маскируя потенциальные совпадения (установленные биты маски) из прошлого, где массив должен был заканчиваться. (бжи для этого годится, _bzhi_u32)
Учитывая AVX-512, у вас определенно есть ИМТ2 для _tzcnt_u32, поэтому используйте его вместо встроенных функций, специфичных для компилятора, для BSF. Или используйте C++20 std::countr_zero
Учитывая AVX-512, у вас определенно есть ИМТ2 для
_tzcnt_u32, поэтому используйте его вместо встроенных функций, специфичных для компилятора, для BSF. Или используйте C++20std::countr_zero