📜 Overview

AVX2 based search for all four element widths. Modeled on SSE4.2 8-bit and 16-bit approach.
Without pcmpestr* instruction, as it is not available for AVX vector width, traditional find-like approach is used instead.

Notable differences:

• pcmpestr* compares all fit characters, pcmpeq* compares only the first, so need to confirm the rest of characters even if the needle fits vector
• as a result, for search (forward search), the variable step is no longer better than the fixed step. See below
• pcmpeq* returns byte bitmask instead of element bitmask, so the mask is masked to make it contain only initial byte positions, also, some element size multiplications are not needed
• for 32-bit and 64-bit elements, AVX2 mask can be used to load partial value, instead of temporary buffer
• ^= (1 << _Pos) is used instead of _bittestandreset. Apparently, this is faster, and should have been used for SSE either

🚶 Fixed vs variable step

For SSE4.2, there are pcmpestri instruction that returns first or last match position, and pcmpestrm instruction that returns bitmask of matches. pcmpestri is faster, also pcmpestri is not affected by DevCom-10689455, unlike pcmpestrm.

Both of the instructions check all characters they can, not just the initial character of a potential match. With smaller needle they can end up making a full match, if the match start is closer to the beginning of the haystack part vector.

For search (the forward one), this makes it appealing to use only pcmpestri for matching, and if the match does not fit, make such step that pcmpestri would have matched, so it would be full match next time. If match is not confirmed, we have to do such step that we skip the unconfirmed match, but attempt to match immediately past it. This results in variable step, but generally faster progress if there are not too many apparent matches.

For find_end (the backward one) this does not work well, as the matches we need to prioritize are closer to the end, which would result in more matches we need to confirm with additional comparison, and still smaller step, so pcmpestri is clearly worse than pcmpestrm with fixed step.

For AVX2, we only match the first character, so there are no cases, where variable step is better.

🐌 Perf bug fix in SSE4.2 path

There was a confusion of elements/bytes in the SSE4.2 path of find_end remaining part check. The intention was to mask out the positions that were already checked. It worked correctly for 8-bit elements, but masked out too few bits for 16-bit element. Whereas the impact is very small, I'm fixing this here in a separate commit, to avoid inconsistencies and make the comparison of these branches easier

⏱️ Benchmark results