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 e49a1b89ea8c7617de2e3447c356f7813d0a88e9 00c6372daa25224a3a8698f0d0a3b222bb8b0795 93662e796001b795283ec6badb59a17b4b5492cc, 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: