линейный поиск через uint64 [] с SSE
я пытаюсь реализовать линейный поиск по массиву uint64 с использованием SSE
инструкции. У меня все работает для uint16 и uint32, но я получаю компилятор
ошибки для кода uint64 (linux, gcc — см. спецификации в конце).
Я пытаюсь сравнить 2х2 64-битные числа, а затем как-то перевести результат
в индексе для моего массива. Это хорошо работает с uint32 (кредиты идут в
http://schani.wordpress.com/2010/04/30/linear-vs-binary-search/):
#include <xmmintrin.h>
#include <smmintrin.h>
typedef ham_u64_t vec2uint64 __attribute__ ((vector_size (16)));
typedef ham_u32_t vec4uint32 __attribute__ ((vector_size (16)));
typedef float vec4float __attribute__ ((vector_size (16)));
typedef ham_u16_t vec8uint16 __attribute__ ((vector_size (16)));
typedef ham_u8_t vec16uint8 __attribute__ ((vector_size (16)));
// ...
vec4uint32 v1 = _mm_loadu_si128((const __m128i *)&data[start + i + 0]);
vec4uint32 v2 = _mm_loadu_si128((const __m128i *)&data[start + i + 4]);
vec4uint32 v3 = _mm_loadu_si128((const __m128i *)&data[start + i + 8]);
vec4uint32 v4 = _mm_loadu_si128((const __m128i *)&data[start + i + 12]);
vec4uint32 cmp0 = _mm_cmpeq_epi32(key4, v1);
vec4uint32 cmp1 = _mm_cmpeq_epi32(key4, v2);
vec4uint32 cmp2 = _mm_cmpeq_epi32(key4, v3);
vec4uint32 cmp3 = _mm_cmpeq_epi32(key4, v4);
vec8uint16 pack01 = __builtin_ia32_packssdw128(cmp0, cmp1);
vec8uint16 pack23 = __builtin_ia32_packssdw128(cmp2, cmp3);
vec16uint8 pack0123 = __builtin_ia32_packsswb128(pack01, pack23);
int res = __builtin_ia32_pmovmskb128(pack0123);
if (res > 0) {
int czt = __builtin_ctz(~res + 1);
return (start + i + czt);
}
Вот что я придумал для uint64. Сравнение работает, я просто
не знаю, что делать с результатами, и вызов __builtin_ia32_packssdw ()
не компилируется:
vec2uint64 v1 = _mm_loadu_si128((const __m128i *)&data[start + i + 0]);
vec2uint64 v2 = _mm_loadu_si128((const __m128i *)&data[start + i + 2]);
vec2uint64 cmp0 = _mm_cmpeq_epi64(key2, v1);
vec2uint64 cmp1 = _mm_cmpeq_epi64(key2, v2);
vec4uint32 pack01 = __builtin_ia32_packssdw(cmp0, cmp1); // error
vec4uint32 pack23 = _mm_set1_epi32(0);
vec16uint8 pack0123 = __builtin_ia32_packsswb128(pack01, pack23);
int res = __builtin_ia32_pmovmskb128(pack0123);
if (res > 0) {
int czt = __builtin_ctz(~res + 1);
return (start + i + czt);
}
Ошибка говорит:
error: cannot convert 'vec1uint64 {aka __vector(2) long unsigned int}'
to '__vector(2) int' for argument '1' to '__vector(4) short int
__builtin_ia32_packssdw(__vector(2) int, __vector(2) int)'
(Типовые определения для vec2uint64 находятся вверху, в коде для uint32.)
Моя среда:
Linux ws4484 3.5.0-48-generic #72~precise1-Ubuntu SMP Tue Mar 11 20:09:08 UTC 2014 x86_64 x86_64 x86_64 GNU/Linux
gcc version 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)
Мой вопрос не только в том, как я могу исправить ошибку компилятора, но если у кого-то есть лучшая идея получить индекс массива с соответствием, возможно, без целого
упаковка вещь?
Заранее спасибо!
Решение
Я предлагаю НЕ использовать встроенные внутренние и неявные векторы. Это имеет смысл, только если вы не используете встроенные функции, не относящиеся к GCC (например, _mm_cmpeq_epi32), и хотите использовать только GCC. Вы можете делать то, что вы хотите, как это
__m128i key2 = _mm_set1_epi64x(key);
__m128i v1 = _mm_loadu_si128((const __m128i *)&data[start + i + 0]);
__m128i v2 = _mm_loadu_si128((const __m128i *)&data[start + i + 2]);
__m128i cmp0 = _mm_cmpeq_epi64(key2, v1);
__m128i cmp1 = _mm_cmpeq_epi64(key2, v2);
__m128i low2 = _mm_shuffle_epi32(cmp0,0xD8);
__m128i high2 = _mm_shuffle_epi32(cmp1,0xD8);
__m128i pack = _mm_unpacklo_epi64(low2,high2);
__m128i pack01 = _mm_packs_epi32(pack, _mm_setzero_si128());
__m128i pack0123 = _mm_packs_epi16(pack01, _mm_setzero_si128());
int res = _mm_movemask_epi8(pack0123);
Возможно, вы найдете более эффективную версию, которая позволяет избежать упаковки, но тогда вам придется использовать другую функцию, чем __builtin_ctz,
Для 32-битных целых я предлагаю
__m128i key4 = _mm_set1_epi32(key);
__m128i v1 = _mm_loadu_si128((const __m128i *)&data[start + i + 0]);
__m128i v2 = _mm_loadu_si128((const __m128i *)&data[start + i + 4]);
__m128i v3 = _mm_loadu_si128((const __m128i *)&data[start + i + 8]);
__m128i v4 = _mm_loadu_si128((const __m128i *)&data[start + i + 12]);
__m128i cmp0 = _mm_cmpeq_epi32(key4, v1);
__m128i cmp1 = _mm_cmpeq_epi32(key4, v2);
__m128i cmp2 = _mm_cmpeq_epi32(key4, v3);
__m128i cmp3 = _mm_cmpeq_epi32(key4, v4);
__m128i pack01 = _mm_packs_epi32(cmp0, cmp1);
__m128i pack23 = _mm_packs_epi32(cmp2, cmp3);
__m128i pack0123 = _mm_packs_epi16(pack01, pack23);
int res = _mm_movemask_epi8(pack0123);
Другие решения
Это полное решение для поиска 64-битных значений для соответствия. В этом случае значение (namehash) является членом структуры. Эта процедура сравнивает 8 64-битных значений на каждой итерации и предоставляет соответствующий структурный индекс.
//ptr is a struct array
__m128i key2 = _mm_set1_epi64x(k); //k is the 64 bit search key
for(;;)
{
if(!ptr[i].namehash)return NULL;
__m128i v1 = _mm_set_epi64x (ptr[i+1].namehash,ptr[i].namehash);
__m128i v2 = _mm_set_epi64x (ptr[i+3].namehash,ptr[i+2].namehash);
__m128i v3 = _mm_set_epi64x (ptr[i+5].namehash,ptr[i+4].namehash);
__m128i v4 = _mm_set_epi64x (ptr[i+7].namehash,ptr[i+6].namehash);
__m128i cmp0 = _mm_cmpeq_epi64(key2, v1);
__m128i cmp1 = _mm_cmpeq_epi64(key2, v2);
__m128i cmp2 = _mm_cmpeq_epi64(key2, v3);
__m128i cmp3 = _mm_cmpeq_epi64(key2, v4);
__m128i L0 = _mm_shuffle_epi32(cmp0,0xD8);
__m128i H1 = _mm_shuffle_epi32(cmp1,0xD8);
__m128i L2 = _mm_shuffle_epi32(cmp2,0xD8);
__m128i H3 = _mm_shuffle_epi32(cmp3,0xD8);
__m128i pack0 = _mm_unpacklo_epi64(L0,H1);
__m128i pack1 = _mm_unpacklo_epi64(L2,H3);
__m128i pack01 = _mm_packs_epi32(pack0,pack1);
__m128i pack0123 = _mm_packs_epi16(pack01, _mm_setzero_si128());
res = _mm_movemask_epi8(pack0123);
if(res > 0)break;
i+=8;
}
int index = i + __builtin_ctz(res); //The struct table index to the matching struct.
ВАЖНО: длина массива структуры должна быть кратна 8, по крайней мере, с 1 завершающим элементом NULL
В качестве альтернативы, если для каждой итерации требуется только 2 64-битных сравнения, вышеприведенное можно значительно упростить до:
for(;;)
{
if(!ptr[i].namehash)return NULL;
__m128i v1 = _mm_set_epi64x (ptr[i+1].namehash,ptr[i].namehash);
__m128i cmp0 = _mm_cmpeq_epi64(key2, v1);
res = _mm_movemask_epi8(cmp0);
if(res > 0)break;
i+=2;
}
int ctz = __builtin_ctz(res);
int index = i + (ctz>>5); //The struct table index to the matching struct.
Я не могу найти никаких инструкций для преобразования 64-разрядного целого числа в 32-разрядное целое число, которое вам необходимо затем использовать packssdw и т. Д. Он становится довольно длинным и грязным, но должен работать:
Итак, я думаю, что решение заключается в использовании битовой маски (биты 0, 1, 2, 3:
Они идут до цикла:
vec2uint64 mask0 = { 2, 1 };
vec2uint64 mask1 = { 8, 4 };
vec2uint64 zero = { 0, 0 };
Внутри петли:
vec2uint64 res0 = _mm_and_si128(cmp0, mask0);
vec2uint64 res1 = _mm_and_si128(cmp1, mask1);
vec2uint64 res2 = _mm_or_si128(res0, res1);
Затем нам нужно переместить верхнюю часть в нижнюю часть новой переменной:
vec2uint64 hi0 = _mm_unpackhi_epi64(res0, zero);
vec2uint64 hi1 = _mm_unpackhi_epi64(res1, zero);
vec2uint64 hi2 = _mm_or_si128(hi0, hi1);
vec2uint64 res3 = _mm_or_si128(res2, hi2);
Теперь младшие 64 бита [ну, младшие 4 бита, остальные равны нулю] res — это битовая маска, одно из значений которой соответствует.
int res = _mm_cvtsi128_si32(res3);
(Теперь вы можете посчитать конечные нули, как раньше).