❓ Questionable improvement

Not sure if this is good, because it optimizes best cases, whereas pessimizing some worse cases.
Unlike std::search vectorization:

• The set of worse cases seems larger.
• For std::search there's intuitive understanding of an "usual" case: it is "usual" language text search. The "usual" case for includes is not known.

½ Half-vectorization approach

• Iterate haystack by vector-sized units
• Skip the whole vector, if all elements are less than the current needle element
• Skip the vector part is some elements are less than the current needle element
• Proceed the rest of the current vector in a scalar way

😾 Which full vectorization approaches considered and failed

Generally, any of these aproaches result in major slowdown for the following case:

• Hay: 0,0,1,1,2,2,...999,999
• Needle: 0,1,2,...999

The approaches considered:

• Compare the needle for equality using vector comparison, skip all equal elements. This ends up being close to scalar but using inefficient instructions, when the needle is large and spread nearly equally
• Use *cmpestr* in any-to-any match mode. Could possibly have worked if there were no duplicates to consider
• Use remove/unique approach in a loop. When the needle is large and spread nearly equally, it takes up to half vector size iterations, which is very slow

⏱️ Benchmark results