CODEWITHSUNDEEP
c++x86ssesimdavx
user1235183
user1235183

Reputation: 3072

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

I want to vectorize the following snippet of code with SIMD intrinsics is this possible?

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]];

EDIT:

Support for: SSE - SSE4.2 and AVX

Architectur: Sandy Bridge i5 2500

Upvotes: 2

Views: 2446

Answers (1)

stgatilov
stgatilov

Reputation: 5533

If you make your x, y, chain_node 8-bit integers (instead of 32-bit ones), then you can process 16 values at once. Here is the code using 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]];

The fully working version of this code is here. Generated assembly is quite simple (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. I guess you'll have various performance issues with std::vector containers. Perhaps unaligned accesses are no longer expensive, but filling vector with zeros will certainly happen. And it can take more time than the vectorized code.

Upvotes: 7

Related Questions