str::contains is very slow for substring checks

[netvl]

Originally found in SO question.

This Rust code

fn main(){

    let needle   = (0..100).map(|_| "b").collect::<String>();
    let heystack = (0..100_000).map(|_| "a").collect::<String>();

    println!("Data ready.");

    for _ in 0..1_000_000 {
        if heystack.contains( &needle ) {
            // Stuff...
        }
    }

}

Executes for up to three minutes on my machine (even with -C opt-level=3), while the equivalent Ruby or Python code:

needle   = 'b' * 100
heystack = 'a' * 100_000

puts 'Data ready.'

1_000_000.times do
    heystack.include? needle
end

finishes in several seconds. Java variant finishes almost instantly (but that seems to be due to JIT optimizations).

It looks like that pattern searching for substrings could be severely optimized.

[bluss]

StrSearcher has a lot of panic branches that can probably avoided (slicing and unwrapping that will never happen).

[ArtemGr]

I wonder wether LLVM can move the comparison out of the loop and if not, why?

[huonw]

I think this is fundamentally algorithmic problem, since StrSearcher is performing a naive string search at the moment. Eliminating unnecessary panics etc should probably wait until that problem is resolved (I could be wrong).

[bluss]

Oh wow, I thought that was something that we had already fixed.

[gereeter]

The algorithmic problem was fixed, but this fix got disabled in the switch to the pattern API. The two-way search code is still present as dead code.

[DanielKeep]

For comparison, I just did a straight translation of a C implementation of BMH. Results for the test in the SO question were:

test tests::boyermoore_horspool_memmem::case_tasos  ... bench:      5241 ns/iter (+/- 222)
test tests::naive::case_tasos                       ... bench:   1567384 ns/iter (+/- 64776)
test tests::std_str_find::case_tasos                ... bench:    864885 ns/iter (+/- 45622)

Where naive is just a 100% naive char-by-char search.

[alexcrichton]

triage: I-nominated

[bluss]

@DanielKeep Can it be adapted to the pattern API?

[DanielKeep]

@bluss I don't see why not; the signature is just (&str, &str) -> Option<usize>, but given that there's already a (not being used) higher-performance searcher in the stdlib, it'd probably make more sense to restore that first and then consider further improvements independently. So long as what's there isn't pathologically bad, it'll still be a considerable improvement. :)

(Not that my BMH implementation is likely to be an improvement: it was literally just copy, pasted, and translated from the C reference code. Hell, it uses... indexing. I was in a hurry. :P)

[Kimundi]

Yeah, after implementing the pattern API I haven't found the time to reintegrate the old fast searcher code yet. Part of the issue why I haven't done it directly is that the fast string searcher only supports single ended search, while with the Pattern API you'd want double ended search.

One way to resolve this is to just hack the naive and the fast search together into a hybrid that uses the fast search for forward iteration (which is all that happened before anyway), and the naive for backwards iteration, but due to me not fully understanding the fast algorithm I was reluctant to do that as part of the original patch.

Wouldn't harm to just do this now and see if any bugs appear though...

[alexcrichton]

triage: P-medium

[bluss]

This is allegedly a very interesting improvement upon our two-way search algorithm. http://drops.dagstuhl.de/opus/volltexte/2011/3355/