⚙️ The optimization

Like I mentioned in #5346, both std::search_n and ranges::search_n make steps by n elements, and avoid going back for a good input (where there are few potential matches), so for large n values vectorization wouldn't be an improvement.

Still for small n, such that vector register width is larger than n, and therefore, the vector step is bigger, it is possible to vectorize in a way that would be faster even for an input with few matches. For more matches, such vectorization will have more advantage, as it would not need to go back.

The approach is to compare elements, get bit mask, and look for contiguous set of ones of proper length. @Alcaro suggested:

you can do things like

match &= match>>1
match &= match>>2
match &= match>>3

to find 7 consecutive 1s, but that probably does something ruinous to instruction parallelism and may cost more than it saves

Turns out this is efficient enough for AVX2 with the values of n up twice smaller than AVX register size in elements. Despite there seems to be indeed high cost of ruined parallelism, I cannot find anything faster.

The shift values are computed based on n. To save one variable (general purpose register), we rely on n=1 to be handled separately, and assume at least one shift to happen.

To deal with matches on vector register boundary, the bitmask is concatenated with the previous one. AVX bitmask is 32 bits for 32 bytes of AVX value, doubled it is 64 bit, still fits x64 register perfectly. The alternative to concatenation could be handling the boundary case with lzcnt/tzcnt, this turned out to be not faster.

The fallback is used for tails and too large n values. For tails it uses lzcnt with inverted carry value to have smooth transition from potential partial match in vectors to the scalar part. The fallback recreates ranges::search_n in <algorithm>, with slight variation.

🥔 Down-level architectures support

SSE4.2 version is implementable in both senses of backporting the current approach to SSE and using pcmpestri. I'd expect either to be of advantage for n values twice smaller than SSE register. Just feel like should not bother trying that.

x86 version works the same way as x64. However, unlike many other vectorization algorithms, this one relies a lot on general-purpose 64 bit integer ops. To mitigate the impact __ull_rshift is used instead of the plain shift. This intrinsic usage doesn't impact 64-bit code, but makes 32-bit codegen better (at the expense of not handling huge shifts, which we don't need anyway). The shift values are of int type to match the intrinsic parameter type.

Still, the efficiency on x86 is questionable (see benchmark results below). Apart from having shifts in multiple instructions, it is apparently due to general purpose registers deficit. The compiler isn't being helpful here too, some register spills look superfluous.

For 32-bit and 64-bit elements, it is possible to use the floating point bit mask, instead of integer bit mask, like in #4987/#5092. This will save bit width. But apart from the mysterious "bypass delay" (integers and floats instructions mix potential penalty), it will also make the bit magic more complicated, more dependent on element width, and still won't reduce the bit width for 8-bit and 16-bit elements, so this doesn't seem to be worth doing.

We could just skip x86. But we don't have precedent of having vectorization for x64, but not having it for x86, so I didn't want to introduce one.

1️⃣ Special n=1 case

We need to handle this case as just find vectorization. find vectorization is more efficient than this one, plus the assumption that the shift happens at least once saves a variable/register.

The question is where we should handle this:

1. Only in separately compiled code
2. Only in headers
3. Both in headers and in separately compiled code

The latter two are indistinguishable in practice, so the real question is, if we should:

1. Handle it in separately compiled code, effectively reverting Use find for search_n when n=1 #5346 optimization
2. Keep handling it in header

With removal n=1 case from headers we get:

• Better throughput
• Simpler header implementation

With keeping n=1 case in headers we get:

• Some non-vectorization optimization for non-vector element types (I believe it is noticeable, but not like multiple times)
• Some auto-vectorization from Clang and probably MSVC in future (Clang recognizes find pattern)
• memchr for corresponding type and disabled vectorization mode

✅ Test coverage

To cover the variety of possibilities, the randomized test should try different input lengths, different n, and different actual matches lengths (including too long matches, too short matches, and different gap between matches). This has to have long run time, so it deserves a dedicated test.

The test coverage is not only useful for vectorization, it also compensates missing non-vectorization coverage, asked in #933.

This PR still doesn't fully address #933 as it is asked because:

• It does not cover the forward-only iterator branches
• It does not have features, like nice error case print, or seed parameter acceptance

I'm not sure how much these features are required, though. If they are required, further work to complete #933 would certainly need a different PR.

🏁 Benchmarks

In addition to the TwoZones case inherited from ##5346 , it has DenseSmallSequences.

These two are close to normal case and worst case respectively.

TwoZones (Zones in the table below) has half of range with mismatch character and half of rangers with match character. So the search should quickly proceed to the match part then check the first match which is successful.

DenseSmallSequences (Dense in the table below) has too short matches of random with from 0 to n-1 interrupted by a single mismatch character.

The vectorization improvement is more for DenseSmallSequences, but we should probably care about TwoZones somewhat more. If worst case is a priority, we can lift threshold for the vectorization twice.

⏱️ Benchmark results

🥈 Results interpretation

For x64 and for the vectorized n there is a certain improvement for Zones. For Dense the improvement is even greater.

The non-vectorized cases vary a lot, The fallback happen to be faster than header implementation often, but not always. Out of the header implementations, surprisingly, the ranges one is slower for Zones case.

The x86 results are not very good, but not too bad either.

The table contains a lot of rows, but I don't see a reasonable way to reduce it without losing important information.