Код AVX2 для поиска первого самого длинного совпадения 4-байтовой строки среди 8 4-байтовых целей
Мне нужен самый быстрый (т.е. безветвистый, минимизирующий операции) код AVX2, эквивалентный этому:
prevlen = 0
for i=0..7:
len = matched_bytes(target[i], src)
if len > prevlen:
prevlen = len
index = i
где target[i] и src — 4-байтовые строки, а matched_bytes возвращает 0..4 — количество равных младших байтов:
def matched_bytes(target, src):
return lzcnt(target ^ src) / 8
Код ниже принимает 15 команд. Я могу жить без лучшей длины, индекса достаточно для некоторых моих случаев использования.
Можно ли это сделать меньшим количеством команд? Меня меньше волнуют задержки или несправедливое использование ALU, поскольку это часть более крупного кода.
byte_eq = pmovmskb( pcmpeqb( broadcast(src), targets))
// bit 4*i set if byte1..4 is equal
byte_eq1 = flags
byte_eq2 = flags >> 1
byte_eq3 = flags >> 2
byte_eq4 = flags >> 3
// bit 4*i set if at least 1..4 bytes are equal
len1 = byte_eq1 & 0x11111111
len2 = len1 & byte_eq2
len3 = len2 & byte_eq3
len4 = len3 & byte_eq4
// Just one CMOV after the corresponding assignment, interleaved with the previous block
if (len2==0) len2 = len1
if (len3==0) len3 = len2
if (len4==0) len4 = len3
index = lzcnt(len4) / 4
// if len4==0 then no match was found
Ответы 2
Упакуйте маски сравнения u8x4 до 16 бит, а затем используйте PHMINPOSUW.
#include <smmintrin.h> // SSE4.1 intrinsics
#include <stdint.h>
#include <stdio.h>
void fn (uint32_t* arr, uint32_t val) {
const __m128i neg1 = _mm_set1_epi32(-1);
__m128i search_value = _mm_set1_epi32(val);
__m128i row0 = _mm_loadu_si128((__m128i*)&arr[0]);
__m128i row1 = _mm_loadu_si128((__m128i*)&arr[4]);
__m128i matched_bytes0 = _mm_cmpeq_epi8(row0, search_value);
__m128i matched_bytes1 = _mm_cmpeq_epi8(row1, search_value);
__m128i packed = _mm_packs_epi16(matched_bytes0, matched_bytes1);
__m128i t1mskc = _mm_or_si128(_mm_xor_si128(packed, neg1), _mm_sub_epi16(packed, neg1));
__m128i best_match = _mm_minpos_epu16(t1mskc);
uint32_t match_desc = (uint32_t)_mm_cvtsi128_si32(best_match);
uint32_t match_index = match_desc >> 16;
uint32_t match_length = __builtin_ctzl(match_desc | 0x10000) >> 2;
printf("index: %d, length: %d\n", match_index, match_length);
}
16-битный входной элемент на этапе упаковки представляет собой пару результатов сравнения 0 или -1. Они интерпретируются как 16-битные целые числа со знаком и насыщаются до 8-битных знаков со знаком от -128 (0x80) до +127 (0x7f).
input vpacksswb result
0xffff 0xff (-1)
0xff00 0x80 (large negative: saturates)
0x00ff 0x7f (large positive: saturates)
0x0000 0x00 (0)
Этот шаг сохраняет порядок при интерпретации байта результата как беззнакового.
При дальнейшей обработке, включающей 16-битное вычитание SIMD (пар байтов результата пакета), мы подготавливаем входные данные для phminposuw так, что 4-байтовое совпадение дает наименьшее 16-битное значение без знака, а самое короткое (без совпадения) дает наибольшее , при этом остальные три возможности также в порядке.
Неочевидно, почему именно использование знаковой насыщенности работает. Возможные входные данные: 0xffff / 0xff00 / 0x00ff / 0x0000, и мы получаем соответственно 0xff / 0x80 / 0x7f / 0x00. Интересно, что порядок сохраняется, если интерпретироваться как беззнаковый!
ух ты! просто вау!! Питер, спасибо за дальнейшее объяснение, моя первая мысль была о том, что _mm_packs_epi16 просто теряет необходимую информацию.
Вдохновленный ответом Акрита, я разработал еще один подход к проблеме:
// byte_eq.bit[i*4+j] = (src[j] == targets[i][j])
byte_eq = pmovmskb( pcmpeqb( broadcast(src), targets))
// Convert 8 nibbles into 8 bytes
byte_eq |= (byte_eq << 28)
byte_eq &= 0x0F0F0F0F0F0F0F0F
// Map byte-eq masks to proper match lengths
match_lens = pshufb(MAP_NIBBLE_MASK_TO_LENGTH, movd(byte_eq))
// Reorder bytes and extend them to 2-byte words
16bit_match_lens = pshufb(match_lens, REORDER_AND_EXTEND)
// Time to call PHMINPOSUW
Плюсы (по сравнению с решением Акрита):
- возвращает реальную длину совпадения, а не значение для расшифровки
Минусы:
- на 2 операции дольше
- требуется AVX2, а не SSE 4.1
- задержка вычислений кажется намного выше, каждая операция зависит от результата предыдущей
В качестве сноски к этому хорошему ответу, причина, по которой он использует два 128-битных вектора, даже когда доступен AVX2: не существует 256-битной версии
phminposuw, только 128-битная версия AVX1vphminposuw. 256-битное сравнение/извлечение в подачуvpacksswb, вероятно, дороже, чем 2x сравнения (оба с операндами из памяти для загрузки). Возможно, пропускная способность практически одинаковая, и, возможно, используется больше внутренних операций (дополнительная нагрузка), но хуже задержка/меньше ILP.