линейный поиск через uint64[] с SSE

Я предлагаю НЕ использовать встроенные встроенные функции и неявные векторы. Это имеет смысл только в том случае, если вы не используете встроенные функции, отличные от 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);

(Теперь вы можете считать конечные нули, как и раньше).