memmem::find performance regression since 2.6.0

[Ambyjkl]

I noticed when updating memchr and that memmem::find was considerably slower, and digging deeper found that memmem::Finder takes considerably longer to build in versions 2.6.0 and above. The good thing is this revealed some opportunities for caching and reusing existing Finder instances, but there are still cases where I have a fresh one-time needle to search in the haystack and hence I cannot cache. Comparing the commits between 2.5.0 and 2.6.0 revealed that the major suspects as being e49a1b8 00c6372 93662e7, with the first and the last ones being the biggest. Here are the benchmark results of simulating real-world usage in my application

Summary
  /tmp/m-2.5.0 ran
    1.19 ± 0.02 times faster than /tmp/m-54c893176860c15cb41be03412ab0bc30f20df25
    1.20 ± 0.02 times faster than /tmp/m-e49a1b89ea8c7617de2e3447c356f7813d0a88e9
    1.20 ± 0.02 times faster than /tmp/m-7af67ce25998d7e91c349f39eb3e38efcc5d5e8f
    1.21 ± 0.01 times faster than /tmp/m-00c6372daa25224a3a8698f0d0a3b222bb8b0795
    1.28 ± 0.01 times faster than /tmp/m-93662e796001b795283ec6badb59a17b4b5492cc

and here is a microbenchmark just running memmem::find in a loop to get the net perf regression

fn main() {
    for _ in 0..1000000 {
        memchr::memmem::find(b"123456789012374890172390417230941723401723490293084570293457890234589023478", b"testadfjgadfaopisdfjoipasdf");
    }
}

Summary
  target/release/2.5.0 ran
    3.31 ± 0.20 times faster than target/release/2.6.0

Which comes out to ~3.3x. Here are the flamegraphs

2.6.0:

2.5.0: