SSE сравнения не работает, как предполагалось, делая линейный поиск по массив целых чисел в C++

Question

У меня есть следующий код предназначен для выполнения линейного поиска через массив с использованием потоковых расширений SIMD в C++:

#include <iostream> 
#include <emmintrin.h> 

using namespace std; 

bool sse2_search_array(int* arr, int size, int key) { 
    int iterations; 
    if (size % 16 == 0) { 
     iterations = size/16; 
    } 
    else { 
     iterations = size/16 + 1; 
    } 
    __m128i* arr_ = reinterpret_cast<__m128i*>(arr); /*Cast to corresponding int type for 128 bit registers. Each __m128i 
           occupies 8 bits, so 16 integers can be processed simultaneously.*/ 
    __declspec(align(16)) int key_arr[16]; 
    fill_n(key_arr, 16, key); /*fill key array with 16 keys (for SSE comparisons)*/ 
    __m128i* key_arr_ = reinterpret_cast<__m128i*>(key_arr); 

    int result; 
    /*Actual search begins here.*/ 
    for (int i = 0; i < iterations; i++, arr_++) { 
     result = _mm_movemask_epi8(_mm_cmpeq_epi8(*key_arr_, *arr_)); /*Comparison of 2 16 bit arrays simultaneously.*/ 
     cout << "result: " << result << endl; 
     if (result != 0) { return true; } 
    } 
    return false; 

} 

int main() { 
    __declspec(align(16)) int example_array[16] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6 }; 

    cout << "found: " << sse2_search_array(example_array, 16, 128); 
    cin.get(); 
} 

It работает, но пример в основной функции должен возвращать значение false, поскольку 128 не находится в example_array, но sse2_search_array всегда возвращает true, а значение result в примере равно 1110111011101110b или 61166, и это не имеет смысла для меня, потому что я ожидая, что это будет 0. Так может кто-нибудь сказать мне, в чем проблема, и как я могу это исправить? Я не очень разбираюсь в C++ и мало знаю SSE.

Answer 1

две основные проблемы:

Никогда не заполнить массив скретч просто так что вы можете загрузить его в качестве вектора:

__declspec(align(16)) int key_arr[16]; 
fill_n(key_arr, 16, key); /*fill key array with 16 keys (for SSE comparisons)*/ 
__m128i* key_arr_ = reinterpret_cast<__m128i*>(key_arr); 

Вместо этого используйте __m128i keyvec = _mm_set1_epi8(key);. Есть много более быстрые способы передачи байта ко всем позициям вектора, чем выполнение 16 скалярных хранилищ в память, а затем векторная нагрузка (которая будет страдать от хранилища в магазине). Пусть компилятор выбирает для вас, используя _mm_set intrinsics, вместо того, чтобы писать в локальные массивы.

---

int составляет 4 байта (на всех современных компиляторов x86), но, по-видимому хотите работать с массивами однобайтными элементов, так как вы используете _mm_cmpeq_epi8. Ваш example_array фактически длиной 16 * 4 байта:

__declspec(align(16)) int example_array[16] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6 }; 
// equivalent byte array (on little-endian x86): 
uint8_t byte_array[16*sizeof(int)] = { 1,0,0,0, 2,0,0,0, 3,0,0,0, ... }; 

Ваши комментарии часто совершенно неправильно, например, Comparison of 2 16 bit arrays simultaneously. Возможно, вы имели в виду «байт»?

---

Если вы действительно хотите найти массивы из int, используйте _mm_set1_epi32(key) и _mm_cmpeq_epi32. 16-байтовый вектор содержит четыре int с. Результат movemask все еще основан на байтах, но каждая группа из 4 бит в результате будет одинаковой.

См. Также sse tag wiki и x86 тег wiki для полезных ссылок. В теге wiki c++ есть много хорошего материала для языка в целом, так как вы сказали, что новичок в этом.

---

IDK почему вы получаете хиты для ключа = 128; что, похоже, не имеет смысла, если в коде нет еще неправильного кода, которого я не заметил.

Ваш отладчик должен быть в состоянии показать вам, что находится в ваших __m128i переменных. Хранение некоторых временных переменных в переменных упростит просмотр их с помощью отладчика исходного уровня на C++ вместо однократного ввода кода asm.