auto merge of #14135 : gereeter/rust/two-way-search, r=brson

This changes the previously naive string searching algorithm to a two-way search like glibc, which should be faster on average while still maintaining worst case linear time complexity. This fixes #14107. Note that I don't think this should be merged yet, as this is the only approach to speeding up search I've tried - it's worth considering options like Boyer-Moore or adding a bad character shift table to this. However, the benchmarks look quite good so far:

    test str::bench::bench_contains_bad_naive                   ... bench:       290 ns/iter (+/- 12)     from 1309 ns/iter (+/- 36)
    test str::bench::bench_contains_equal                       ... bench:       479 ns/iter (+/- 10)     from  137 ns/iter (+/- 2)
    test str::bench::bench_contains_short_long                  ... bench:      2844 ns/iter (+/- 105)    from 5473 ns/iter (+/- 14)
    test str::bench::bench_contains_short_short                 ... bench:        55 ns/iter (+/- 4)      from   57 ns/iter (+/- 6)

Except for the case specifically designed to be optimal for the naive case (`bench_contains_equal`), this gets as good or better performance as the previous code.

0 files changed, 0 insertions, 0 deletions