str::find(char) is slower than it ought ot be

[mystor]

If you try to find a specific character in a string, it performs significantly worse than the theoretical optimal implementation built on memchr.

For example, consider the following benchmark. On my laptop the find method runs at about 90ns/iter, and the memchr method runs at 4ns/iter. I would imagine that we should optimize them such that they are the same.

#![feature(test)]
extern crate memchr;
extern crate test;

use test::{black_box, Bencher};

const DEMO_STRING: &str = "this is a string with a decent number of ascii characters and \n there is a new line in the middle which it should find";

#[bench]
fn bench_find(b: &mut Bencher) {
    b.iter(|| {
        let s = test::black_box(DEMO_STRING);
        s.find('\n')
    });
}

#[bench]
fn bench_memchr(b: &mut Bencher) {
    b.iter(|| {
        let s = test::black_box(DEMO_STRING);
        memchr::memchr(b'\n', s.as_bytes())
    });
}

[ExpHP]

Another benchmark, the intent being to eliminate just the cost of the unnecessary utf8 decoding (that I assume is happening). This gives a meager 60% reduction in time.

#[bench]
fn bench_byte_find(b: &mut Bencher) {
    b.iter(|| {
        let s = test::black_box(DEMO_STRING);
        s.bytes().position(|b| b == b'\n')
    });
}

running 3 tests
test bench_byte_find ... bench:          35 ns/iter (+/- 2)
test bench_find      ... bench:          88 ns/iter (+/- 2)
test bench_memchr    ... bench:           5 ns/iter (+/- 0)

[Manishearth]

I have fixes. We have two problems.

One is that [u8]::contains doesn't use memchr, which affects str::contains.

The other is that we reuse the same Searcher code for char, [char], and Fn(char) -> bool; we should have a simpler custom impl for char.

[Manishearth]

#46713 fixes [u8]::contains but not the rest (however it sets the stage for this fix)

[ExpHP]

I wonder if similar concerns apply for &str patterns. From the way UTF-8 is designed, I expect that a dumb non-unicode-aware strstr-like implementation is in fact a valid way to implement &str patterns.

(and then as a bonus, we can get non-ASCII char patterns by encoding the char to &str)

[Manishearth]

Yes, this is true. I need to think about that more.

There is a question of how useful that will be -- for most multibyte utf8 text the first byte is quite common. But it should still be faster to do the dumb memchr-based thing instead of actually iterating chars.

[ExpHP]

Comparison to GNU libc strstr, x86-64

Of course, not 100% apples to oranges since C strings are null-terminated

#![feature(test)]
extern crate libc;
extern crate test;

use libc::c_char;
use std::ffi::{CString};
use test::{black_box, Bencher};

const NEEDLE: &str = "there";
const HAYSTACK: &str = "this is a string with a decent number of ascii characters and \n there is a new line in the middle which it should find";

fn strstr(haystack: *const c_char, needle: *const c_char) -> Option<usize> {
    let found = unsafe { libc::strstr(haystack, needle) };

    if found.is_null() { None }
    else { Some(found as usize - haystack as usize) }
}

#[bench]
fn bench_find(b: &mut Bencher) {
    b.iter(|| {
        let haystack = test::black_box(HAYSTACK);
        let needle = test::black_box(NEEDLE);
        haystack.find(needle)
    });
}

#[bench]
fn bench_strstr(b: &mut Bencher) {
    let haystack = CString::new(HAYSTACK).unwrap();
    let haystack = haystack.as_ptr();
    let needle = CString::new(NEEDLE).unwrap();
    let needle = needle.as_ptr();
    b.iter(|| {
        let haystack = test::black_box(haystack);
        let needle = test::black_box(needle);
        strstr(haystack, needle)
    });
}

test bench_find   ... bench:          56 ns/iter (+/- 1)
test bench_strstr ... bench:          19 ns/iter (+/- 0)

[kennytm]

Duplicate of #41993?

[mystor]

Duplicate of #41993?

I think this is probably related, but not exactly a duplicate. The code s.find("\n") is faster than s.find('\n'), but both are still significantly slower than memchr.

[Manishearth]

#46735