在 C++ 中对整数数组进行线性搜索时，SSE 比较无法按预期工作

Question

我有以下代码旨在使用 C++ 中的流式 SIMD 扩展对数组执行线性搜索：

#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();
}

它有效，但主函数中的示例应该 return 假，因为 128 不在 example_array 中，但 sse2_search_array 似乎总是 return 真，并且示例中 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 内在函数而不是写入本地数组来为您选择。

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。也许你的意思是 "byte"?

如果您确实想搜索 int 的数组，请使用 _mm_set1_epi32(key) 和 _mm_cmpeq_epi32。一个 16 字节的向量包含四个 int。 movemask结果仍然是基于字节的，但是结果中的每组4位都是相同的。

另见 sse tag wiki and the x86 tag wiki for useful links. The c++ 标签 wiki 有很多关于一般语言的好东西，因为你说你也是新手。

IDK 为什么你会得到键=128 的点击；这似乎没有意义，除非你的代码有更多我没有注意到的错误。

您的调试器应该能够向您显示 __m128i 变量中的内容。将一些临时变量存储在变量中将使使用 C++ 源代码级调试器更容易查看它们，而不是单步执行 asm 代码。

在 C++ 中对整数数组进行线性搜索时，SSE 比较无法按预期工作

SSE comparisons not working as intended while doing a linear search over an array of integers in c++

c++

sse

linear-search