Improve substring search performance for corner cases

[bluss]

I've subjected jetscii 0.3.1 to a benchmark suite of just a few pathological examples for substring search.

_jetscii benches very well_, there's just evidence of pathlogical cases

Result (may be noisy, i.e. individual benchmarks may be flukes)

• find - str::find with &str pattern
• rfind - str::rfind with &str pattern
• jetscii_find str::find with Substring pattern
• pcmp_find experimental function twsearch::pcmp::find, an incomplete, incorrect two-way search
• regex_find using regex

test bad_naive::find                                      ... bench:         274 ns/iter (+/- 19) = 270 MB/s
test bad_naive::jetscii_find                              ... bench:         504 ns/iter (+/- 118) = 146 MB/s
test bad_naive::pcmp_find                                 ... bench:          96 ns/iter (+/- 1) = 770 MB/s
test bad_naive::regex_find                                ... bench:       1,077 ns/iter (+/- 89) = 68 MB/s
test bad_naive::rfind                                     ... bench:         231 ns/iter (+/- 16) = 320 MB/s
test bad_naive_reversed::find                             ... bench:         175 ns/iter (+/- 9) = 422 MB/s
test bad_naive_reversed::jetscii_find                     ... bench:          54 ns/iter (+/- 4) = 1370 MB/s
test bad_naive_reversed::pcmp_find                        ... bench:          43 ns/iter (+/- 4) = 1720 MB/s
test bad_naive_reversed::regex_find                       ... bench:          36 ns/iter (+/- 3) = 2055 MB/s
test bad_naive_reversed::rfind                            ... bench:         367 ns/iter (+/- 54) = 201 MB/s
test pathological_aa_100k::find                           ... bench:       3,084 ns/iter (+/- 149) = 32425 MB/s
test pathological_aa_100k::jetscii_find                   ... bench:      24,116 ns/iter (+/- 1,041) = 4146 MB/s
test pathological_aa_100k::pcmp_find                      ... bench:      27,241 ns/iter (+/- 2,031) = 3670 MB/s
test pathological_aa_100k::regex_find                     ... bench:       4,453 ns/iter (+/- 262) = 22456 MB/s
test pathological_aa_100k::rfind                          ... bench:       2,824 ns/iter (+/- 207) = 35410 MB/s
test pathological_aab_100k::find                          ... bench:     889,518 ns/iter (+/- 55,787) = 337 MB/s
test pathological_aab_100k::jetscii_find                  ... bench:     265,300 ns/iter (+/- 15,265) = 1130 MB/s
test pathological_aab_100k::pcmp_find                     ... bench:     183,135 ns/iter (+/- 11,808) = 1638 MB/s
test pathological_aab_100k::regex_find                    ... bench:   3,750,744 ns/iter (+/- 392,444) = 79 MB/s
test pathological_aab_100k::rfind                         ... bench:     859,327 ns/iter (+/- 104,678) = 348 MB/s
test pathological_two_way_10k::find                       ... bench:     107,896 ns/iter (+/- 48,497) = 278 MB/s
test pathological_two_way_10k::jetscii_find               ... bench:       7,406 ns/iter (+/- 1,072) = 4050 MB/s
test pathological_two_way_10k::pcmp_find                  ... bench:      19,444 ns/iter (+/- 22,302) = 1542 MB/s
test pathological_two_way_10k::regex_find                 ... bench:       1,329 ns/iter (+/- 2,413) = 22573 MB/s
test pathological_two_way_10k::rfind                      ... bench:       2,463 ns/iter (+/- 4,146) = 12180 MB/s
test pathological_two_way_20k::find                       ... bench:     305,465 ns/iter (+/- 505,176) = 327 MB/s
test pathological_two_way_20k::jetscii_find               ... bench:      25,179 ns/iter (+/- 39,142) = 3971 MB/s
test pathological_two_way_20k::pcmp_find                  ... bench:      64,983 ns/iter (+/- 113,250) = 1538 MB/s
test pathological_two_way_20k::regex_find                 ... bench:       6,175 ns/iter (+/- 12,215) = 16194 MB/s
test pathological_two_way_20k::rfind                      ... bench:       3,673 ns/iter (+/- 6,390) = 27225 MB/s
test pathological_two_way_20k_reversed::find              ... bench:       2,492 ns/iter (+/- 4,523) = 24077 MB/s
test pathological_two_way_20k_reversed::jetscii_find      ... bench:      45,084 ns/iter (+/- 80,989) = 1330 MB/s
test pathological_two_way_20k_reversed::pcmp_find         ... bench:      39,623 ns/iter (+/- 65,178) = 1514 MB/s
test pathological_two_way_20k_reversed::regex_find        ... bench:     406,637 ns/iter (+/- 730,079) = 147 MB/s
test pathological_two_way_20k_reversed::rfind             ... bench:     155,639 ns/iter (+/- 284,944) = 385 MB/s
test short_long::find                                     ... bench:       3,924 ns/iter (+/- 4,175) = 650 MB/s
test short_long::jetscii_find                             ... bench:         676 ns/iter (+/- 1,291) = 3773 MB/s
test short_long::pcmp_find                                ... bench:         810 ns/iter (+/- 1,531) = 3149 MB/s
test short_long::regex_find                               ... bench:       2,821 ns/iter (+/- 748) = 904 MB/s
test short_long::rfind                                    ... bench:       2,253 ns/iter (+/- 3,445) = 1132 MB/s
test short_short::find                                    ... bench:          68 ns/iter (+/- 119) = 823 MB/s
test short_short::jetscii_find                            ... bench:         109 ns/iter (+/- 127) = 513 MB/s
test short_short::pcmp_find                               ... bench:          43 ns/iter (+/- 69) = 1302 MB/s
test short_short::regex_find                              ... bench:          54 ns/iter (+/- 122) = 1037 MB/s
test short_short::rfind                                   ... bench:         125 ns/iter (+/- 160) = 448 MB/s

Conclusions:

• jetscii 0.3.1 has algorithmic trouble, probably O(n²) problematics, see testcase bad_naive
• Both jetscii and pcmp are losing to the byteset optimization in libstd's StrSearcher, see testcase pathological_aa_100k

Benchmark source, very messy crate

[bluss]

I realized the bad_naive testcase was a bit short -- the needle below 16 bytes. A proper testcase is a worse pathological case for jetscii!

haystack: (0..100_000).map(|_| "a").collect::<String>()
needle: (0..100).map(|_| "a").collect::<String>() + "b"

test bad_naive_long::find                                 ... bench:     299,292 ns/iter (+/- 37,567) = 334 MB/s
test bad_naive_long::jetscii_find                         ... bench:  10,303,063 ns/iter (+/- 194,054) = 9 MB/s
test bad_naive_long::pcmp_find                            ... bench:      23,807 ns/iter (+/- 225) = 4200 MB/s

as consolation, regex is even worse..

[shepmaster]

Awesome, thanks for this! I'm certainly not surprised that there are pathological cases, but having them pointed out in test cases is even nicer.

One thing I assume will help is to not increment by one byte on a false positive. Any highlights of normal things to avoid before I read your tests and the standard lib implementation?

[shepmaster]

9 MB/s

Ouch. Lots to fix!

[bluss]

To avoid all algorithmic trouble, employ a substring search algorithm, i.e. some system to make sure it advances enough per trial. Here's an nice overview http://www-igm.univ-mlv.fr/~lecroq/string/

I don't know enough to have specific advice. I'm obviously trying to impl the two way algorithm with pcmp_find, but I'm not sure it's the best algorithm to pick for SSE4.2 substring search.

[bluss]

The MB/s is bytes of haystack searched per second, of course. Most of the testcases don't match, so they effectively search it all.

[shepmaster]

One thought is that the pcmpestrm instruction should be able to tell which byte fails strcmp, which I believe can be used to stride further.

[bluss]

absolutely, that's what you need to to for the two way algorithm.

Without the factorization that two-way does of the needle, I don't think you can step to the failed match position in general.

Not sure I can recommend diving into string search algorithms. 😄 My revival PR of two-way for libstd took me a week of work, and I didn't even implement it from scratch

[bluss]

That said, I think the pcmp_find is part way there. But I'd consider a different algorithm entirely maybe. Maybe Boyer-Moore-Horspool?

[shepmaster]

a different algorithm

Yeah, I'll skim through and see if anything jumps out as a key match. One nice thing is that you and I can collaborate on ideas and compete on implementations, and everyone wins!

[bluss]

Note that the byteset optimization is why str::find is so fast in the substring benchmark in your Readme. If you add an a anywhere in the needle, that optimization won't work.

[ArtemGr]

Have you seen strstr_sse42 in http://www.strchr.com/strcmp_and_strlen_using_sse_4.2?

[bluss]

@ArtemGr that's a quadratic algorithm too (it's a naive search)

; continue searching from the next byte

[ArtemGr]

I wondered if the next byte meant the one after the 15 already checked. Duh, at least I tried. )

BTW, you ever run those benchmars with native optimizations on (target=native)?

[bluss]

I didn't think about it. The pcmpestri instruction is emitted anyway since it's in an explicit asm!() block, so I'm not sure what could improve.

[ArtemGr]

The pcmpestri instruction is emitted anyway since it's in an explicit asm!() block, so I'm not sure what could improve.

The SSE version won't improve, but the non-SSE versions might. We could see how LLVM fares against manual assembly. Without "target=native" it can't compete.