4 ms·
which are slow. If you wanna count the number of occurrences of a certain character in a string, you ultimately have to use popcount on an ordinary register, t
by stabbles 3y ago
which are slow.
If you wanna count the number of occurrences of a certain character in a string, you ultimately have to use popcount on an ordinary register, there's no corresponding SIMD instruction (at least in <= AVX2). Something along the lines of:
__builtin_popcount(_mm256_movemask_epi8(_mm256_cmpeq_epi8(haystack, needle)));
So, if you wanna avoid horizontal reductions, you better sum the result of _mm256_cmpeq_epi8 and effectively keep track of 32 counters of 1 byte integers.
Meaning that you have an outer loop over the string, and a fixed-length inner loop of 255 iterations in which you accumulate counts, and after the inner loop a horizontal sum.
Then you go from 1 horizontal operation per iteration, to 1 horizontal operations per 255 iterations.
- ack_complete 3y agoThere is actually such an instruction, psadbw (_mm_sad_epu8). It's not any noticeably faster for the scenario you describe since it only affects the outer loop, but it does avoid needing the popcnt instruction since psadbw only requires SSE2.
- 10000truths 3y agoWith AVX512, you can use masking and the vpopcntb instruction to avoid moving values between GPRs and vector registers until the very end: uint64_t count_occurrences(const __m512i* vec_string, size_t num_vecs, char target) { __m512i count_vec = _mm512_set1_epi64(0); __m512i target_vec = _mm512_set1_epi8(target); __m512i increment_vec = _mm512_set1_epi8(1); for(size_t i = 0; i < num_vecs; ++i) { __mmask64 cmp_mask = _mm512_cmpeq_epu8_mask(target_vec, vec_string[i]); count_vec += _mm512_maskz_popcnt_epi8(cmp_mask, increment_vec); } return _mm512_reduce_add_epi64(count_vec); }