⚙️ The optimization

Like I mentioned in#5346, bothstd::search_n andranges::search_n make steps byn elements, and avoid going back for a good input (where there are few potential matches), so for largen values vectorization wouldn't be an improvement.

Still for smalln, such that vector register width is larger thann, 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>>1match &= match>>2match &= 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 ofn 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 onn. To save one variable (general purpose register), we rely onn=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 withlzcnt/tzcnt, this turned out to be not faster.

The fallback is used for tails and too largen values. For tails it useslzcnt with inverted carry value to have smooth transition from potential partial match in vectors to the scalar part. The fallback recreatesranges::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 usingpcmpestri. I'd expect either to be of advantage forn 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 ofint 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️⃣ Specialn=1 case

We need to handle this case as justfind 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 revertingUsefind forsearch_n when n=1 #5346 optimization
2. Keep handling it in header

With removaln=1 case from headers we get:

• Better throughput
• Simpler header implementation

With keepingn=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 recognizesfind 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, differentn, 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 theTwoZones case inherited from ##5346 , it hasDenseSmallSequences.

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 ton-1 interrupted by a single mismatch character.

The vectorization improvement is more forDenseSmallSequences, but we should probably care aboutTwoZones 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.