c++: table lookup vectorizable for small lookup-table

Question

我想用 SIMD 内部函数向量化以下代码片段，这可能吗？

unsigned char chain[3][3] = { 
            3,  2, 1,    //  y    --> x
            4, -1, 0,    //  | 
            5,  6, 7     //  |
            };           //  v    

std::vector<int> x;
std::vector<int> y;    
//initialize x, y

std::vector<int> chain_code(x.size());

for(std::size_t i = 0; i < x.size(); ++i
     chain_code[i] = chain[x[i]][y[i]];

编辑：

支持：SSE - SSE4.2 和 AVX

架构师：Sandy Bridge i5 2500

Answer 1

如果您将 x、y、chain_node 设为 8 位整数（而不是 32 位整数），那么您可以一次处理 16 个值。这是使用 SSSE3 的代码：

std::vector<uint8_t> x;
std::vector<uint8_t> y;    
...
int n = x.size();
std::vector<uint8_t> chain_code(n);

//initialize table register
__m128i table = _mm_setr_epi8(
    chain[0][0], chain[0][1], chain[0][2], 99,
    chain[1][0], chain[1][1], chain[1][2], 99,
    chain[2][0], chain[2][1], chain[2][2], 99,
    99, 99, 99, 99
);

int b = (n / 16) * 16;
for (int i = 0; i < b; i += 16) {
    //load 16 X/Y bytes
    __m128i regX = _mm_loadu_si128((__m128i*)&x[i]);
    __m128i regY = _mm_loadu_si128((__m128i*)&y[i]);
    //shift all X values left by 2 bits (as 16-bit integers)
    __m128i regX4 = _mm_slli_epi16(regX, 2);
    //calculate linear indices (x * 4 + y)
    __m128i indices = _mm_add_epi8(regX4, regY);
    //perform 16 lookups
    __m128i res = _mm_shuffle_epi8(table, indices);
    //store results
    _mm_storeu_si128((__m128i*)&chain_code[i], res);
}
for (int i = b; i < n; i++)
    chain_code[i] = chain[x[i]][y[i]];

此代码的完整工作版本是 here。生成的程序集非常简单（MSVC2013 x64）：

movdqu  xmm1, XMMWORD PTR [rdi+rax]
movdqu  xmm0, XMMWORD PTR [rax]
psllw   xmm1, 2
paddb   xmm1, xmm0
movdqa  xmm0, xmm6
pshufb  xmm0, xmm1
movdqu  XMMWORD PTR [rsi+rax], xmm0

P.S。我猜你会遇到 std::vector 容器的各种性能问题。也许未对齐的访问不再昂贵，但用零填充向量肯定会发生。而且它可能比矢量化代码花费更多时间。

c++: table lookup vectorizable for small lookup-table

c++: Is table lookup vectorizable for small lookup-table

c++

x86

sse

simd

avx