Сравнения SSE не работают должным образом при выполнении линейного поиска по массиву целых чисел в переполнении стека

Question

Сравнения SSE не работают должным образом при выполнении линейного поиска по массиву целых чисел в переполнении стека

У меня есть следующий код, предназначенный для выполнения линейного поиска по массиву с использованием потоковых 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();
}

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

1

c++linear-search sse

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

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

__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 встроенные вместо записи в локальные массивы.

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-байтовый вектор содержит четыре ints. Результат маски перемещения по-прежнему основан на байтах, но каждая группа из 4 битов в результате будет одинаковой.

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

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

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

3