Vector Class Discussion

 
thread Searching through int array with SSE2 - Christoph Rupp - 2014-04-09
reply Searching through int array with SSE2 - Agner - 2014-04-09
last reply Searching through int array with SSE2 - Agner - 2014-04-23
 
Searching through int array with SSE2
Author:  Date: 2014-04-09 08:12
Hi,

I want to perform a linear search through an integer array using SIMD instructions.

my idea is to iterate over the array and compare 4 integers in one call. My function should return the index of the matching element in the array. However, the Vec4i operator == does not return an index, only a vector of bools:

Vec4i a(10, 11, 12, 13);
Vec4i b(14, 13, 12, 11);
Vec4ib c = a == b;
// c = (false, false, true, false)

In order to get my index, I have to loop over the returned vector and check which element is true. Is there any way to avoid this overhead? i.e. the functions here (https://github.com/schani/linbin/blob/master/linear-sentinel-simd.h) use __builtin_ia32_pmovmskb128 and __builtin_ctz to calculate the index. And this paper here (http://openproceedings.org/EDBT/2014/paper_107.pdf) recommends popcount.

Thanks a lot,
Christoph

   
Searching through int array with SSE2
Author: Agner Date: 2014-04-09 10:52
You can use
if (horizontal_or(c))
to check if any element of c is true. Then use
int index = _mm_movemask_epi8(c);
to check which elements of c are true. index will have one bit for each byte of c that is true, i.e. 4 bits for each dword. Maybe I will make a function for this in a future version.
   
Searching through int array with SSE2
Author: Agner Date: 2014-04-23 04:36
Version 1.12 of the vector class library now has the function horizontal_find_first which I think is doing exactly what you want.