Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save sophiawisdom/6762e4046f928ff2cd1fd1b25316e1b4 to your computer and use it in GitHub Desktop.
Save sophiawisdom/6762e4046f928ff2cd1fd1b25316e1b4 to your computer and use it in GitHub Desktop.
int vectorizedLinearSearch(unsigned int *array, int size, unsigned int searchNum) {
assert(((size >> 3) << 3) == size); // divisible by 8 for __m256i
__m256i searchVector = _mm256_set1_epi32(searchNum); // broadcast searchNum
for (int i = 0; i < size; i+=8) {
__m256i searchValue = _mm256_loadu_si256(&array[i]);
// Would be better if we could compare just a single 32 bit value, but just duplicating
// the 32 bit value is fine also.
__m256i eqMask = _mm256_cmpeq_epi32(searchVector, searchValue);
unsigned int intMask = _mm256_movemask_ps(eqMask);
if (_mm_popcnt_u32(intMask) != 0) {
// Get the lowest value found. Necessary to do this because multiple of the same number is fairly common.
for (int j = 0; j < 8; j++) {
if (intMask & (1 << j)) {
return i+j;
}
}
}
}
return -1;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment