❔ Why ranges approach

We have three outcomes of comparison of elements pair:

1. Haystack element less. Advance only haystack
2. Needle element less. We found mismatch, return false
3. Elements equal. Advance haystack and needle

Out of these outcomes, we can get one in one branch, the rest will be two branches.
Since we have "less" predicate, we can't have equal in one branch.

Out of haystack less and needle less, the current std:: algorithm favors needle less, and the ranges algorithm favors haystack less.
Favoring haystack less optimizes long algorithm run, where haystack is way bigger than needle.
Favoring needle less optimizes early return, which is not so useful, as it happens only once per algorithm run.

🏁 Benchmarks

Not sure what is common case of includes, trying these three:
(0) Needle is seen contiguously in haystack
(1) Needle is seen not completely contiguously in haystack, but still compact (stride is geometric distribution)
(2) Needle is spread in haystack with almost the same stride (plus-minus one)
(3) Needle is sampled randomly from haystack

All these are multiplied by
(1) The needle is actually found
(0) The middle element of the needle does not match anything in haystack

I think these combinations are enough to explore the algorithm performance properties

Benchmark results show being affected by codegen gremlin, and expectedly 300/290 cases are less faster and more slower.
But overall looks like an improvement.

📜 Benchmark results

⚠️ mixed result with improvements over 2.0 sometimes, but degradation below 0.3 sometimes too ⚠️

⚠️ whole benchmark runs long ⚠️