rust/library/core/src/str/pattern.rs, branch 1.75.0https://github.com/rust-lang/rust
http://git.dreamy.place/mirrors/rust/atom?h=1.75.02023-11-27T20:57:23+00:00feat: implement `DoubleEndedSearcher` for `CharArray[Ref]Searcher`2023-11-27T20:57:23+00:00Jan66554238+vaporoxx@users.noreply.github.com2023-05-24T20:27:10+00:00urn:sha1:1ce9a4cb0b6e49fe94f2b1e6bac5e3e87b150fd2
(cherry picked from commit c6ed532bef02e752ea881ab104cacc28e5d06738)
Re-format let-else per rustfmt update2023-07-13T01:49:27+00:00Mark Rousskovmark.simulacrum@gmail.com2023-07-13T01:49:27+00:00urn:sha1:cc907f80b95c6ec530c5ee1b05b044a468f07ecaFix some misleading and copy-pasted `Pattern` examples2023-05-15T06:03:50+00:00Scott McMurrayscottmcm@users.noreply.github.com2023-05-15T06:03:50+00:00urn:sha1:47232ade6151a8e7d2112e2dda0c7c5c930b0a31
These examples were listed twice and also were confusable with doing a substring match instead of a any-of-set match.
Fix typos in library2023-04-10T19:07:29+00:00DaniPopes57450786+DaniPopes@users.noreply.github.com2023-04-10T19:07:29+00:00urn:sha1:a0daf22b95ff1cd3f7ac55ea9370987535f3134dfix dupe word typos2022-12-05T08:42:36+00:00Rageking8tomleetyt@gmail.com2022-12-05T08:42:36+00:00urn:sha1:58110572fb23e0ad1944bdf3d8cdb3f84cb91aa2fix OOB access in SIMD impl of str.contains()2022-11-22T19:59:19+00:00The 8472git@infinite-source.de2022-11-22T19:59:19+00:00urn:sha1:3ed8fccff5295e1d92419e7c67502e434ff1e98f- convert from core::arch to core::simd2022-11-15T17:30:31+00:00The 8472git@infinite-source.de2022-11-03T22:31:00+00:00urn:sha1:a2b2010891224cbaf448d5d799b3c47c87e863be
- bump simd compare to 32bytes
- import small slice compare code from memmem crate
- try a few different probe bytes to avoid degenerate cases
- but special-case 2-byte needles
x86_64 SSE2 fast-path for str.contains(&str) and short needles2022-11-14T22:03:16+00:00The 8472git@infinite-source.de2022-10-30T20:47:04+00:00urn:sha1:3d4a8482b93313be4d6e8dc62030860fa2fc46ef
Based on Wojciech Muła's "SIMD-friendly algorithms for substring searching"[0]
The two-way algorithm is Big-O efficient but it needs to preprocess the needle
to find a "criticla factorization" of it. This additional work is significant
for short needles. Additionally it mostly advances needle.len() bytes at a time.
The SIMD-based approach used here on the other hand can advance based on its
vector width, which can exceed the needle length. Except for pathological cases,
but due to being limited to small needles the worst case blowup is also small.
benchmarks taken on a Zen2:
```
16CGU, OLD:
test str::bench_contains_short_short ... bench: 27 ns/iter (+/- 1)
test str::bench_contains_short_long ... bench: 667 ns/iter (+/- 29)
test str::bench_contains_bad_naive ... bench: 131 ns/iter (+/- 2)
test str::bench_contains_bad_simd ... bench: 130 ns/iter (+/- 2)
test str::bench_contains_equal ... bench: 148 ns/iter (+/- 4)
16CGU, NEW:
test str::bench_contains_short_short ... bench: 8 ns/iter (+/- 0)
test str::bench_contains_short_long ... bench: 135 ns/iter (+/- 4)
test str::bench_contains_bad_naive ... bench: 130 ns/iter (+/- 2)
test str::bench_contains_bad_simd ... bench: 292 ns/iter (+/- 1)
test str::bench_contains_equal ... bench: 3 ns/iter (+/- 0)
1CGU, OLD:
test str::bench_contains_short_short ... bench: 30 ns/iter (+/- 0)
test str::bench_contains_short_long ... bench: 713 ns/iter (+/- 17)
test str::bench_contains_bad_naive ... bench: 131 ns/iter (+/- 3)
test str::bench_contains_bad_simd ... bench: 130 ns/iter (+/- 3)
test str::bench_contains_equal ... bench: 148 ns/iter (+/- 6)
1CGU, NEW:
test str::bench_contains_short_short ... bench: 10 ns/iter (+/- 0)
test str::bench_contains_short_long ... bench: 111 ns/iter (+/- 0)
test str::bench_contains_bad_naive ... bench: 135 ns/iter (+/- 3)
test str::bench_contains_bad_simd ... bench: 274 ns/iter (+/- 2)
test str::bench_contains_equal ... bench: 4 ns/iter (+/- 0)
```
[0] http://0x80.pl/articles/simd-strfind.html#sse-avx2
Fix typo in `ReverseSearcher` docs2022-10-17T17:14:15+00:00Skysky@h4x5.dev2022-10-17T17:14:15+00:00urn:sha1:9a7e527e28448fcfe589ef4ce9c3d753382a6f20Add char array without ref Pattern impl2021-07-28T21:13:46+00:00Cameron Steffencam.steffen94@gmail.com2021-06-22T02:21:18+00:00urn:sha1:28f7890a29bd9531fb91295bc130a911820e9fb6