Быстрый подсчет количества равных байтов между двумя массивами
Я написал функцию int compare_16bytes(__m128i lhs, __m128i rhs) чтобы сравнить два 16-байтовых числа с использованием инструкций SSE: эта функция возвращает количество байтов, равных после выполнения сравнения.
Теперь я хотел бы использовать вышеупомянутую функцию для сравнения двух байтовых массивов произвольной длины: длина не может быть кратна 16 байтам, поэтому мне нужно разобраться с этой проблемой. Как я могу завершить реализацию функции ниже? Как я могу улучшить функцию ниже?
int fast_compare(const char* s, const char* t, int length)
{
int result = 0;
const char* sPtr = s;
const char* tPtr = t;
while(...)
{
const __m128i* lhs = (const __m128i*)sPtr;
const __m128i* rhs = (const __m128i*)tPtr;
// compare the next 16 bytes of s and t
result += compare_16bytes(*lhs,*rhs);
sPtr += 16;
tPtr += 16;
}
return result;
}
Решение
Как говорит @Mysticial в комментариях выше, сравнивайте и суммируйте по вертикали, а затем просто суммируйте по горизонтали в конце основного цикла:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <emmintrin.h>
// reference implementation
int fast_compare_ref(const char *s, const char *t, int length)
{
int result = 0;
int i;
for (i = 0; i < length; ++i)
{
if (s[i] == t[i])
result++;
}
return result;
}
// optimised implementation
int fast_compare(const char *s, const char *t, int length)
{
int result = 0;
int i;
__m128i vsum = _mm_set1_epi32(0);
for (i = 0; i < length - 15; i += 16)
{
__m128i vs, vt, v, vh, vl, vtemp;
vs = _mm_loadu_si128((__m128i *)&s[i]); // load 16 chars from input
vt = _mm_loadu_si128((__m128i *)&t[i]);
v = _mm_cmpeq_epi8(vs, vt); // compare
vh = _mm_unpackhi_epi8(v, v); // unpack compare result into 2 x 8 x 16 bit vectors
vl = _mm_unpacklo_epi8(v, v);
vtemp = _mm_madd_epi16(vh, vh); // accumulate 16 bit vectors into 4 x 32 bit partial sums
vsum = _mm_add_epi32(vsum, vtemp);
vtemp = _mm_madd_epi16(vl, vl);
vsum = _mm_add_epi32(vsum, vtemp);
}
// get sum of 4 x 32 bit partial sums
vsum = _mm_add_epi32(vsum, _mm_srli_si128(vsum, 8));
vsum = _mm_add_epi32(vsum, _mm_srli_si128(vsum, 4));
result = _mm_cvtsi128_si32(vsum);
// handle any residual bytes ( < 16)
if (i < length)
{
result += fast_compare_ref(&s[i], &t[i], length - i);
}
return result;
}
// test harness
int main(void)
{
const int n = 1000000;
char *s = malloc(n);
char *t = malloc(n);
int i, result_ref, result;
srand(time(NULL));
for (i = 0; i < n; ++i)
{
s[i] = rand();
t[i] = rand();
}
result_ref = fast_compare_ref(s, t, n);
result = fast_compare(s, t, n);
printf("result_ref = %d, result = %d\n", result_ref, result);;
return 0;
}
Скомпилируйте и запустите приведенный выше тестовый жгут:
$ gcc -Wall -O3 -msse3 fast_compare.c -o fast_compare
$ ./fast_compare
result_ref = 3955, result = 3955
$ ./fast_compare
result_ref = 3947, result = 3947
$ ./fast_compare
result_ref = 3945, result = 3945
Обратите внимание, что есть один, возможно, неочевидный трюк в приведенном выше коде SSE, где мы используем _mm_madd_epi16 распаковать и накопить 16 бит 0/-1 значения до 32-битных частичных сумм. Мы пользуемся тем фактом, что -1*-1 = 1 (а также 0*0 = 0 конечно) — мы не делаем здесь умножение, просто распаковываем и суммируем в одной инструкции.
ОБНОВЛЕНИЕ: как отмечено в комментариях ниже, это решение не является оптимальным — я просто выбрал довольно оптимальное 16-битное решение и добавил распаковку с 8-битной до 16-битной, чтобы она работала для 8-битных данных. Однако для 8-битных данных существуют более эффективные методы, например, с помощью psadbw/_mm_sad_epu8. Я оставлю этот ответ здесь для потомков, и для всех, кто захочет делать подобные вещи с 16-битными данными, но на самом деле одним из других ответов, который не требует распаковки входных данных, должен быть принятый ответ.
Другие решения
Использование частичных сумм в 16 элементах uint8 может повысить производительность.
Я разделил цикл на внутренний цикл и внешний цикл.
Внутренний цикл суммирует элементы uint8 (каждый элемент uint8 может суммировать до 255 «1» с).
Небольшая хитрость: _mm_cmpeq_epi8 устанавливает равные элементы в 0xFF и (char) 0xFF = -1, так что вы можете вычесть результат из суммы (вычтите -1 для сложения 1).
Вот моя оптимизированная версия для fast_compare:
int fast_compare2(const char *s, const char *t, int length)
{
int result = 0;
int inner_length = length;
int i;
int j = 0;
//Points beginning of 4080 elements block.
const char *s0 = s;
const char *t0 = t;__m128i vsum = _mm_setzero_si128();
//Outer loop sum result of 4080 sums.
for (i = 0; i < length; i += 4080)
{
__m128i vsum_uint8 = _mm_setzero_si128(); //16 uint8 sum elements (each uint8 element can sum up to 255).
__m128i vh, vl, vhl, vhl_lo, vhl_hi;
//Points beginning of 4080 elements block.
s0 = s + i;
t0 = t + i;
if (i + 4080 <= length)
{
inner_length = 4080;
}
else
{
inner_length = length - i;
}
//Inner loop - sum up to 4080 (compared) results.
//Each uint8 element can sum up to 255. 16 uint8 elements can sum up to 255*16 = 4080 (compared) results.
//////////////////////////////////////////////////////////////////////////
for (j = 0; j < inner_length-15; j += 16)
{
__m128i vs, vt, v;
vs = _mm_loadu_si128((__m128i *)&s0[j]); // load 16 chars from input
vt = _mm_loadu_si128((__m128i *)&t0[j]);
v = _mm_cmpeq_epi8(vs, vt); // compare - set to 0xFF where equal, and 0 otherwise.
//Consider this: (char)0xFF = (-1)
vsum_uint8 = _mm_sub_epi8(vsum_uint8, v); //Subtract the comparison result - subtract (-1) where equal.
}
//////////////////////////////////////////////////////////////////////////
vh = _mm_unpackhi_epi8(vsum_uint8, _mm_setzero_si128()); // unpack result into 2 x 8 x 16 bit vectors
vl = _mm_unpacklo_epi8(vsum_uint8, _mm_setzero_si128());
vhl = _mm_add_epi16(vh, vl); //Sum high and low as uint16 elements.
vhl_hi = _mm_unpackhi_epi16(vhl, _mm_setzero_si128()); //unpack sum of vh an vl into 2 x 4 x 32 bit vectors
vhl_lo = _mm_unpacklo_epi16(vhl, _mm_setzero_si128()); //unpack sum of vh an vl into 2 x 4 x 32 bit vectors
vsum = _mm_add_epi32(vsum, vhl_hi);
vsum = _mm_add_epi32(vsum, vhl_lo);
}
// get sum of 4 x 32 bit partial sums
vsum = _mm_add_epi32(vsum, _mm_srli_si128(vsum, 8));
vsum = _mm_add_epi32(vsum, _mm_srli_si128(vsum, 4));
result = _mm_cvtsi128_si32(vsum);
// handle any residual bytes ( < 16)
if (j < inner_length)
{
result += fast_compare_ref(&s0[j], &t0[j], inner_length - j);
}
return result;
}
Самый быстрый способ для больших входов — это ответ Rotem, где внутренний цикл pcmpeqb / psubb, получая суммирование по горизонтали перед переполнением любого байтового элемента векторного аккумулятора. Сделать сумму неподписанных байтов с psadbw против нулевого вектора.
Без развертывания / вложенных циклов, лучший вариант, вероятно,
pcmpeqb -> vector of 0 or 0xFF elements
psadbw -> two 64bit sums of (0*no_matches + 0xFF*matches)
paddq -> accumulate the psadbw result in a vector accumulator
#outside the loop:
horizontal sum
divide the result by 255
Если у вас нет большого давления регистра в вашей петле, psadbw против вектора 0x7f вместо всего ноль.
psadbw(0x00, set1(0x7f))=>sum += 0x7fpsadbw(0xff, set1(0x7f))=>sum += 0x80
Таким образом, вместо деления на 255 (что компилятор должен делать эффективно без фактического div), вам просто нужно вычесть n * 0x7f, где n это количество элементов.
Также обратите внимание, что paddq медленно на пре-Нехалеме и Атоме, так что вы можете использовать paddd (_mm_add_epi32) если вы не ожидаете, что число 128 * превысит 32-битное целое число.
Это очень хорошо сравнивается с Полом Р. pcmpeqb / 2x punpck / 2x pmaddwd / 2x paddw,
Целочисленное сравнение в SSE дает байты, которые являются либо всеми нулями, либо всеми. Если вы хотите посчитать, вам сначала нужно сместить вправо (не арифметически) результат сравнения на 7, а затем добавить к вектору результатов.
В конце вам все равно нужно уменьшить результирующий вектор путем суммирования его элементов. Это сокращение должно быть сделано в скалярном коде или с помощью последовательности добавления / сдвига. Обычно эту часть не стоит беспокоить.