diff options
Diffstat (limited to 'vendor/memchr/src/memmem/searcher.rs')
| -rw-r--r-- | vendor/memchr/src/memmem/searcher.rs | 1030 |
1 files changed, 0 insertions, 1030 deletions
diff --git a/vendor/memchr/src/memmem/searcher.rs b/vendor/memchr/src/memmem/searcher.rs deleted file mode 100644 index 98b9bd6..0000000 --- a/vendor/memchr/src/memmem/searcher.rs +++ /dev/null @@ -1,1030 +0,0 @@ -use crate::arch::all::{ - packedpair::{HeuristicFrequencyRank, Pair}, - rabinkarp, twoway, -}; - -#[cfg(target_arch = "aarch64")] -use crate::arch::aarch64::neon::packedpair as neon; -#[cfg(target_arch = "wasm32")] -use crate::arch::wasm32::simd128::packedpair as simd128; -#[cfg(all(target_arch = "x86_64", target_feature = "sse2"))] -use crate::arch::x86_64::{ - avx2::packedpair as avx2, sse2::packedpair as sse2, -}; - -/// A "meta" substring searcher. -/// -/// To a first approximation, this chooses what it believes to be the "best" -/// substring search implemnetation based on the needle at construction time. -/// Then, every call to `find` will execute that particular implementation. To -/// a second approximation, multiple substring search algorithms may be used, -/// depending on the haystack. For example, for supremely short haystacks, -/// Rabin-Karp is typically used. -/// -/// See the documentation on `Prefilter` for an explanation of the dispatching -/// mechanism. The quick summary is that an enum has too much overhead and -/// we can't use dynamic dispatch via traits because we need to work in a -/// core-only environment. (Dynamic dispatch works in core-only, but you -/// need `&dyn Trait` and we really need a `Box<dyn Trait>` here. The latter -/// requires `alloc`.) So instead, we use a union and an appropriately paired -/// free function to read from the correct field on the union and execute the -/// chosen substring search implementation. -#[derive(Clone)] -pub(crate) struct Searcher { - call: SearcherKindFn, - kind: SearcherKind, - rabinkarp: rabinkarp::Finder, -} - -impl Searcher { - /// Creates a new "meta" substring searcher that attempts to choose the - /// best algorithm based on the needle, heuristics and what the current - /// target supports. - #[inline] - pub(crate) fn new<R: HeuristicFrequencyRank>( - prefilter: PrefilterConfig, - ranker: R, - needle: &[u8], - ) -> Searcher { - let rabinkarp = rabinkarp::Finder::new(needle); - if needle.len() <= 1 { - return if needle.is_empty() { - trace!("building empty substring searcher"); - Searcher { - call: searcher_kind_empty, - kind: SearcherKind { empty: () }, - rabinkarp, - } - } else { - trace!("building one-byte substring searcher"); - debug_assert_eq!(1, needle.len()); - Searcher { - call: searcher_kind_one_byte, - kind: SearcherKind { one_byte: needle[0] }, - rabinkarp, - } - }; - } - let pair = match Pair::with_ranker(needle, &ranker) { - Some(pair) => pair, - None => return Searcher::twoway(needle, rabinkarp, None), - }; - debug_assert_ne!( - pair.index1(), - pair.index2(), - "pair offsets should not be equivalent" - ); - #[cfg(all(target_arch = "x86_64", target_feature = "sse2"))] - { - if let Some(pp) = avx2::Finder::with_pair(needle, pair) { - if do_packed_search(needle) { - trace!("building x86_64 AVX2 substring searcher"); - let kind = SearcherKind { avx2: pp }; - Searcher { call: searcher_kind_avx2, kind, rabinkarp } - } else if prefilter.is_none() { - Searcher::twoway(needle, rabinkarp, None) - } else { - let prestrat = Prefilter::avx2(pp, needle); - Searcher::twoway(needle, rabinkarp, Some(prestrat)) - } - } else if let Some(pp) = sse2::Finder::with_pair(needle, pair) { - if do_packed_search(needle) { - trace!("building x86_64 SSE2 substring searcher"); - let kind = SearcherKind { sse2: pp }; - Searcher { call: searcher_kind_sse2, kind, rabinkarp } - } else if prefilter.is_none() { - Searcher::twoway(needle, rabinkarp, None) - } else { - let prestrat = Prefilter::sse2(pp, needle); - Searcher::twoway(needle, rabinkarp, Some(prestrat)) - } - } else if prefilter.is_none() { - Searcher::twoway(needle, rabinkarp, None) - } else { - // We're pretty unlikely to get to this point, but it is - // possible to be running on x86_64 without SSE2. Namely, it's - // really up to the OS whether it wants to support vector - // registers or not. - let prestrat = Prefilter::fallback(ranker, pair, needle); - Searcher::twoway(needle, rabinkarp, prestrat) - } - } - #[cfg(target_arch = "wasm32")] - { - if let Some(pp) = simd128::Finder::with_pair(needle, pair) { - if do_packed_search(needle) { - trace!("building wasm32 simd128 substring searcher"); - let kind = SearcherKind { simd128: pp }; - Searcher { call: searcher_kind_simd128, kind, rabinkarp } - } else if prefilter.is_none() { - Searcher::twoway(needle, rabinkarp, None) - } else { - let prestrat = Prefilter::simd128(pp, needle); - Searcher::twoway(needle, rabinkarp, Some(prestrat)) - } - } else if prefilter.is_none() { - Searcher::twoway(needle, rabinkarp, None) - } else { - let prestrat = Prefilter::fallback(ranker, pair, needle); - Searcher::twoway(needle, rabinkarp, prestrat) - } - } - #[cfg(target_arch = "aarch64")] - { - if let Some(pp) = neon::Finder::with_pair(needle, pair) { - if do_packed_search(needle) { - trace!("building aarch64 neon substring searcher"); - let kind = SearcherKind { neon: pp }; - Searcher { call: searcher_kind_neon, kind, rabinkarp } - } else if prefilter.is_none() { - Searcher::twoway(needle, rabinkarp, None) - } else { - let prestrat = Prefilter::neon(pp, needle); - Searcher::twoway(needle, rabinkarp, Some(prestrat)) - } - } else if prefilter.is_none() { - Searcher::twoway(needle, rabinkarp, None) - } else { - let prestrat = Prefilter::fallback(ranker, pair, needle); - Searcher::twoway(needle, rabinkarp, prestrat) - } - } - #[cfg(not(any( - all(target_arch = "x86_64", target_feature = "sse2"), - target_arch = "wasm32", - target_arch = "aarch64" - )))] - { - if prefilter.is_none() { - Searcher::twoway(needle, rabinkarp, None) - } else { - let prestrat = Prefilter::fallback(ranker, pair, needle); - Searcher::twoway(needle, rabinkarp, prestrat) - } - } - } - - /// Creates a new searcher that always uses the Two-Way algorithm. This is - /// typically used when vector algorithms are unavailable or inappropriate. - /// (For example, when the needle is "too long.") - /// - /// If a prefilter is given, then the searcher returned will be accelerated - /// by the prefilter. - #[inline] - fn twoway( - needle: &[u8], - rabinkarp: rabinkarp::Finder, - prestrat: Option<Prefilter>, - ) -> Searcher { - let finder = twoway::Finder::new(needle); - match prestrat { - None => { - trace!("building scalar two-way substring searcher"); - let kind = SearcherKind { two_way: finder }; - Searcher { call: searcher_kind_two_way, kind, rabinkarp } - } - Some(prestrat) => { - trace!( - "building scalar two-way \ - substring searcher with a prefilter" - ); - let two_way_with_prefilter = - TwoWayWithPrefilter { finder, prestrat }; - let kind = SearcherKind { two_way_with_prefilter }; - Searcher { - call: searcher_kind_two_way_with_prefilter, - kind, - rabinkarp, - } - } - } - } - - /// Searches the given haystack for the given needle. The needle given - /// should be the same as the needle that this finder was initialized - /// with. - /// - /// Inlining this can lead to big wins for latency, and #[inline] doesn't - /// seem to be enough in some cases. - #[inline(always)] - pub(crate) fn find( - &self, - prestate: &mut PrefilterState, - haystack: &[u8], - needle: &[u8], - ) -> Option<usize> { - if haystack.len() < needle.len() { - None - } else { - // SAFETY: By construction, we've ensured that the function - // in `self.call` is properly paired with the union used in - // `self.kind`. - unsafe { (self.call)(self, prestate, haystack, needle) } - } - } -} - -impl core::fmt::Debug for Searcher { - fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { - f.debug_struct("Searcher") - .field("call", &"<searcher function>") - .field("kind", &"<searcher kind union>") - .field("rabinkarp", &self.rabinkarp) - .finish() - } -} - -/// A union indicating one of several possible substring search implementations -/// that are in active use. -/// -/// This union should only be read by one of the functions prefixed with -/// `searcher_kind_`. Namely, the correct function is meant to be paired with -/// the union by the caller, such that the function always reads from the -/// designated union field. -#[derive(Clone, Copy)] -union SearcherKind { - empty: (), - one_byte: u8, - two_way: twoway::Finder, - two_way_with_prefilter: TwoWayWithPrefilter, - #[cfg(all(target_arch = "x86_64", target_feature = "sse2"))] - sse2: crate::arch::x86_64::sse2::packedpair::Finder, - #[cfg(all(target_arch = "x86_64", target_feature = "sse2"))] - avx2: crate::arch::x86_64::avx2::packedpair::Finder, - #[cfg(target_arch = "wasm32")] - simd128: crate::arch::wasm32::simd128::packedpair::Finder, - #[cfg(target_arch = "aarch64")] - neon: crate::arch::aarch64::neon::packedpair::Finder, -} - -/// A two-way substring searcher with a prefilter. -#[derive(Copy, Clone, Debug)] -struct TwoWayWithPrefilter { - finder: twoway::Finder, - prestrat: Prefilter, -} - -/// The type of a substring search function. -/// -/// # Safety -/// -/// When using a function of this type, callers must ensure that the correct -/// function is paired with the value populated in `SearcherKind` union. -type SearcherKindFn = unsafe fn( - searcher: &Searcher, - prestate: &mut PrefilterState, - haystack: &[u8], - needle: &[u8], -) -> Option<usize>; - -/// Reads from the `empty` field of `SearcherKind` to handle the case of -/// searching for the empty needle. Works on all platforms. -/// -/// # Safety -/// -/// Callers must ensure that the `searcher.kind.empty` union field is set. -unsafe fn searcher_kind_empty( - _searcher: &Searcher, - _prestate: &mut PrefilterState, - _haystack: &[u8], - _needle: &[u8], -) -> Option<usize> { - Some(0) -} - -/// Reads from the `one_byte` field of `SearcherKind` to handle the case of -/// searching for a single byte needle. Works on all platforms. -/// -/// # Safety -/// -/// Callers must ensure that the `searcher.kind.one_byte` union field is set. -unsafe fn searcher_kind_one_byte( - searcher: &Searcher, - _prestate: &mut PrefilterState, - haystack: &[u8], - _needle: &[u8], -) -> Option<usize> { - let needle = searcher.kind.one_byte; - crate::memchr(needle, haystack) -} - -/// Reads from the `two_way` field of `SearcherKind` to handle the case of -/// searching for an arbitrary needle without prefilter acceleration. Works on -/// all platforms. -/// -/// # Safety -/// -/// Callers must ensure that the `searcher.kind.two_way` union field is set. -unsafe fn searcher_kind_two_way( - searcher: &Searcher, - _prestate: &mut PrefilterState, - haystack: &[u8], - needle: &[u8], -) -> Option<usize> { - if rabinkarp::is_fast(haystack, needle) { - searcher.rabinkarp.find(haystack, needle) - } else { - searcher.kind.two_way.find(haystack, needle) - } -} - -/// Reads from the `two_way_with_prefilter` field of `SearcherKind` to handle -/// the case of searching for an arbitrary needle with prefilter acceleration. -/// Works on all platforms. -/// -/// # Safety -/// -/// Callers must ensure that the `searcher.kind.two_way_with_prefilter` union -/// field is set. -unsafe fn searcher_kind_two_way_with_prefilter( - searcher: &Searcher, - prestate: &mut PrefilterState, - haystack: &[u8], - needle: &[u8], -) -> Option<usize> { - if rabinkarp::is_fast(haystack, needle) { - searcher.rabinkarp.find(haystack, needle) - } else { - let TwoWayWithPrefilter { ref finder, ref prestrat } = - searcher.kind.two_way_with_prefilter; - let pre = Pre { prestate, prestrat }; - finder.find_with_prefilter(Some(pre), haystack, needle) - } -} - -/// Reads from the `sse2` field of `SearcherKind` to execute the x86_64 SSE2 -/// vectorized substring search implementation. -/// -/// # Safety -/// -/// Callers must ensure that the `searcher.kind.sse2` union field is set. -#[cfg(all(target_arch = "x86_64", target_feature = "sse2"))] -unsafe fn searcher_kind_sse2( - searcher: &Searcher, - _prestate: &mut PrefilterState, - haystack: &[u8], - needle: &[u8], -) -> Option<usize> { - let finder = &searcher.kind.sse2; - if haystack.len() < finder.min_haystack_len() { - searcher.rabinkarp.find(haystack, needle) - } else { - finder.find(haystack, needle) - } -} - -/// Reads from the `avx2` field of `SearcherKind` to execute the x86_64 AVX2 -/// vectorized substring search implementation. -/// -/// # Safety -/// -/// Callers must ensure that the `searcher.kind.avx2` union field is set. -#[cfg(all(target_arch = "x86_64", target_feature = "sse2"))] -unsafe fn searcher_kind_avx2( - searcher: &Searcher, - _prestate: &mut PrefilterState, - haystack: &[u8], - needle: &[u8], -) -> Option<usize> { - let finder = &searcher.kind.avx2; - if haystack.len() < finder.min_haystack_len() { - searcher.rabinkarp.find(haystack, needle) - } else { - finder.find(haystack, needle) - } -} - -/// Reads from the `simd128` field of `SearcherKind` to execute the wasm32 -/// simd128 vectorized substring search implementation. -/// -/// # Safety -/// -/// Callers must ensure that the `searcher.kind.simd128` union field is set. -#[cfg(target_arch = "wasm32")] -unsafe fn searcher_kind_simd128( - searcher: &Searcher, - _prestate: &mut PrefilterState, - haystack: &[u8], - needle: &[u8], -) -> Option<usize> { - let finder = &searcher.kind.simd128; - if haystack.len() < finder.min_haystack_len() { - searcher.rabinkarp.find(haystack, needle) - } else { - finder.find(haystack, needle) - } -} - -/// Reads from the `neon` field of `SearcherKind` to execute the aarch64 neon -/// vectorized substring search implementation. -/// -/// # Safety -/// -/// Callers must ensure that the `searcher.kind.neon` union field is set. -#[cfg(target_arch = "aarch64")] -unsafe fn searcher_kind_neon( - searcher: &Searcher, - _prestate: &mut PrefilterState, - haystack: &[u8], - needle: &[u8], -) -> Option<usize> { - let finder = &searcher.kind.neon; - if haystack.len() < finder.min_haystack_len() { - searcher.rabinkarp.find(haystack, needle) - } else { - finder.find(haystack, needle) - } -} - -/// A reverse substring searcher. -#[derive(Clone, Debug)] -pub(crate) struct SearcherRev { - kind: SearcherRevKind, - rabinkarp: rabinkarp::FinderRev, -} - -/// The kind of the reverse searcher. -/// -/// For the reverse case, we don't do any SIMD acceleration or prefilters. -/// There is no specific technical reason why we don't, but rather don't do it -/// because it's not clear it's worth the extra code to do so. If you have a -/// use case for it, please file an issue. -/// -/// We also don't do the union trick as we do with the forward case and -/// prefilters. Basically for the same reason we don't have prefilters or -/// vector algorithms for reverse searching: it's not clear it's worth doing. -/// Please file an issue if you have a compelling use case for fast reverse -/// substring search. -#[derive(Clone, Debug)] -enum SearcherRevKind { - Empty, - OneByte { needle: u8 }, - TwoWay { finder: twoway::FinderRev }, -} - -impl SearcherRev { - /// Creates a new searcher for finding occurrences of the given needle in - /// reverse. That is, it reports the last (instead of the first) occurrence - /// of a needle in a haystack. - #[inline] - pub(crate) fn new(needle: &[u8]) -> SearcherRev { - let kind = if needle.len() <= 1 { - if needle.is_empty() { - trace!("building empty reverse substring searcher"); - SearcherRevKind::Empty - } else { - trace!("building one-byte reverse substring searcher"); - debug_assert_eq!(1, needle.len()); - SearcherRevKind::OneByte { needle: needle[0] } - } - } else { - trace!("building scalar two-way reverse substring searcher"); - let finder = twoway::FinderRev::new(needle); - SearcherRevKind::TwoWay { finder } - }; - let rabinkarp = rabinkarp::FinderRev::new(needle); - SearcherRev { kind, rabinkarp } - } - - /// Searches the given haystack for the last occurrence of the given - /// needle. The needle given should be the same as the needle that this - /// finder was initialized with. - #[inline] - pub(crate) fn rfind( - &self, - haystack: &[u8], - needle: &[u8], - ) -> Option<usize> { - if haystack.len() < needle.len() { - return None; - } - match self.kind { - SearcherRevKind::Empty => Some(haystack.len()), - SearcherRevKind::OneByte { needle } => { - crate::memrchr(needle, haystack) - } - SearcherRevKind::TwoWay { ref finder } => { - if rabinkarp::is_fast(haystack, needle) { - self.rabinkarp.rfind(haystack, needle) - } else { - finder.rfind(haystack, needle) - } - } - } - } -} - -/// Prefilter controls whether heuristics are used to accelerate searching. -/// -/// A prefilter refers to the idea of detecting candidate matches very quickly, -/// and then confirming whether those candidates are full matches. This -/// idea can be quite effective since it's often the case that looking for -/// candidates can be a lot faster than running a complete substring search -/// over the entire input. Namely, looking for candidates can be done with -/// extremely fast vectorized code. -/// -/// The downside of a prefilter is that it assumes false positives (which are -/// candidates generated by a prefilter that aren't matches) are somewhat rare -/// relative to the frequency of full matches. That is, if a lot of false -/// positives are generated, then it's possible for search time to be worse -/// than if the prefilter wasn't enabled in the first place. -/// -/// Another downside of a prefilter is that it can result in highly variable -/// performance, where some cases are extraordinarily fast and others aren't. -/// Typically, variable performance isn't a problem, but it may be for your use -/// case. -/// -/// The use of prefilters in this implementation does use a heuristic to detect -/// when a prefilter might not be carrying its weight, and will dynamically -/// disable its use. Nevertheless, this configuration option gives callers -/// the ability to disable prefilters if you have knowledge that they won't be -/// useful. -#[derive(Clone, Copy, Debug)] -#[non_exhaustive] -pub enum PrefilterConfig { - /// Never used a prefilter in substring search. - None, - /// Automatically detect whether a heuristic prefilter should be used. If - /// it is used, then heuristics will be used to dynamically disable the - /// prefilter if it is believed to not be carrying its weight. - Auto, -} - -impl Default for PrefilterConfig { - fn default() -> PrefilterConfig { - PrefilterConfig::Auto - } -} - -impl PrefilterConfig { - /// Returns true when this prefilter is set to the `None` variant. - fn is_none(&self) -> bool { - matches!(*self, PrefilterConfig::None) - } -} - -/// The implementation of a prefilter. -/// -/// This type encapsulates dispatch to one of several possible choices for a -/// prefilter. Generally speaking, all prefilters have the same approximate -/// algorithm: they choose a couple of bytes from the needle that are believed -/// to be rare, use a fast vector algorithm to look for those bytes and return -/// positions as candidates for some substring search algorithm (currently only -/// Two-Way) to confirm as a match or not. -/// -/// The differences between the algorithms are actually at the vector -/// implementation level. Namely, we need different routines based on both -/// which target architecture we're on and what CPU features are supported. -/// -/// The straight-forwardly obvious approach here is to use an enum, and make -/// `Prefilter::find` do case analysis to determine which algorithm was -/// selected and invoke it. However, I've observed that this leads to poor -/// codegen in some cases, especially in latency sensitive benchmarks. That is, -/// this approach comes with overhead that I wasn't able to eliminate. -/// -/// The second obvious approach is to use dynamic dispatch with traits. Doing -/// that in this context where `Prefilter` owns the selection generally -/// requires heap allocation, and this code is designed to run in core-only -/// environments. -/// -/// So we settle on using a union (that's `PrefilterKind`) and a function -/// pointer (that's `PrefilterKindFn`). We select the right function pointer -/// based on which field in the union we set, and that function in turn -/// knows which field of the union to access. The downside of this approach -/// is that it forces us to think about safety, but the upside is that -/// there are some nice latency improvements to benchmarks. (Especially the -/// `memmem/sliceslice/short` benchmark.) -/// -/// In cases where we've selected a vector algorithm and the haystack given -/// is too short, we fallback to the scalar version of `memchr` on the -/// `rarest_byte`. (The scalar version of `memchr` is still better than a naive -/// byte-at-a-time loop because it will read in `usize`-sized chunks at a -/// time.) -#[derive(Clone, Copy)] -struct Prefilter { - call: PrefilterKindFn, - kind: PrefilterKind, - rarest_byte: u8, - rarest_offset: u8, -} - -impl Prefilter { - /// Return a "fallback" prefilter, but only if it is believed to be - /// effective. - #[inline] - fn fallback<R: HeuristicFrequencyRank>( - ranker: R, - pair: Pair, - needle: &[u8], - ) -> Option<Prefilter> { - /// The maximum frequency rank permitted for the fallback prefilter. - /// If the rarest byte in the needle has a frequency rank above this - /// value, then no prefilter is used if the fallback prefilter would - /// otherwise be selected. - const MAX_FALLBACK_RANK: u8 = 250; - - trace!("building fallback prefilter"); - let rarest_offset = pair.index1(); - let rarest_byte = needle[usize::from(rarest_offset)]; - let rarest_rank = ranker.rank(rarest_byte); - if rarest_rank > MAX_FALLBACK_RANK { - None - } else { - let finder = crate::arch::all::packedpair::Finder::with_pair( - needle, - pair.clone(), - )?; - let call = prefilter_kind_fallback; - let kind = PrefilterKind { fallback: finder }; - Some(Prefilter { call, kind, rarest_byte, rarest_offset }) - } - } - - /// Return a prefilter using a x86_64 SSE2 vector algorithm. - #[cfg(all(target_arch = "x86_64", target_feature = "sse2"))] - #[inline] - fn sse2(finder: sse2::Finder, needle: &[u8]) -> Prefilter { - trace!("building x86_64 SSE2 prefilter"); - let rarest_offset = finder.pair().index1(); - let rarest_byte = needle[usize::from(rarest_offset)]; - Prefilter { - call: prefilter_kind_sse2, - kind: PrefilterKind { sse2: finder }, - rarest_byte, - rarest_offset, - } - } - - /// Return a prefilter using a x86_64 AVX2 vector algorithm. - #[cfg(all(target_arch = "x86_64", target_feature = "sse2"))] - #[inline] - fn avx2(finder: avx2::Finder, needle: &[u8]) -> Prefilter { - trace!("building x86_64 AVX2 prefilter"); - let rarest_offset = finder.pair().index1(); - let rarest_byte = needle[usize::from(rarest_offset)]; - Prefilter { - call: prefilter_kind_avx2, - kind: PrefilterKind { avx2: finder }, - rarest_byte, - rarest_offset, - } - } - - /// Return a prefilter using a wasm32 simd128 vector algorithm. - #[cfg(target_arch = "wasm32")] - #[inline] - fn simd128(finder: simd128::Finder, needle: &[u8]) -> Prefilter { - trace!("building wasm32 simd128 prefilter"); - let rarest_offset = finder.pair().index1(); - let rarest_byte = needle[usize::from(rarest_offset)]; - Prefilter { - call: prefilter_kind_simd128, - kind: PrefilterKind { simd128: finder }, - rarest_byte, - rarest_offset, - } - } - - /// Return a prefilter using a aarch64 neon vector algorithm. - #[cfg(target_arch = "aarch64")] - #[inline] - fn neon(finder: neon::Finder, needle: &[u8]) -> Prefilter { - trace!("building aarch64 neon prefilter"); - let rarest_offset = finder.pair().index1(); - let rarest_byte = needle[usize::from(rarest_offset)]; - Prefilter { - call: prefilter_kind_neon, - kind: PrefilterKind { neon: finder }, - rarest_byte, - rarest_offset, - } - } - - /// Return a *candidate* position for a match. - /// - /// When this returns an offset, it implies that a match could begin at - /// that offset, but it may not. That is, it is possible for a false - /// positive to be returned. - /// - /// When `None` is returned, then it is guaranteed that there are no - /// matches for the needle in the given haystack. That is, it is impossible - /// for a false negative to be returned. - /// - /// The purpose of this routine is to look for candidate matching positions - /// as quickly as possible before running a (likely) slower confirmation - /// step. - #[inline] - fn find(&self, haystack: &[u8]) -> Option<usize> { - // SAFETY: By construction, we've ensured that the function in - // `self.call` is properly paired with the union used in `self.kind`. - unsafe { (self.call)(self, haystack) } - } - - /// A "simple" prefilter that just looks for the occurrence of the rarest - /// byte from the needle. This is generally only used for very small - /// haystacks. - #[inline] - fn find_simple(&self, haystack: &[u8]) -> Option<usize> { - // We don't use crate::memchr here because the haystack should be small - // enough that memchr won't be able to use vector routines anyway. So - // we just skip straight to the fallback implementation which is likely - // faster. (A byte-at-a-time loop is only used when the haystack is - // smaller than `size_of::<usize>()`.) - crate::arch::all::memchr::One::new(self.rarest_byte) - .find(haystack) - .map(|i| i.saturating_sub(usize::from(self.rarest_offset))) - } -} - -impl core::fmt::Debug for Prefilter { - fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { - f.debug_struct("Prefilter") - .field("call", &"<prefilter function>") - .field("kind", &"<prefilter kind union>") - .field("rarest_byte", &self.rarest_byte) - .field("rarest_offset", &self.rarest_offset) - .finish() - } -} - -/// A union indicating one of several possible prefilters that are in active -/// use. -/// -/// This union should only be read by one of the functions prefixed with -/// `prefilter_kind_`. Namely, the correct function is meant to be paired with -/// the union by the caller, such that the function always reads from the -/// designated union field. -#[derive(Clone, Copy)] -union PrefilterKind { - fallback: crate::arch::all::packedpair::Finder, - #[cfg(all(target_arch = "x86_64", target_feature = "sse2"))] - sse2: crate::arch::x86_64::sse2::packedpair::Finder, - #[cfg(all(target_arch = "x86_64", target_feature = "sse2"))] - avx2: crate::arch::x86_64::avx2::packedpair::Finder, - #[cfg(target_arch = "wasm32")] - simd128: crate::arch::wasm32::simd128::packedpair::Finder, - #[cfg(target_arch = "aarch64")] - neon: crate::arch::aarch64::neon::packedpair::Finder, -} - -/// The type of a prefilter function. -/// -/// # Safety -/// -/// When using a function of this type, callers must ensure that the correct -/// function is paired with the value populated in `PrefilterKind` union. -type PrefilterKindFn = - unsafe fn(strat: &Prefilter, haystack: &[u8]) -> Option<usize>; - -/// Reads from the `fallback` field of `PrefilterKind` to execute the fallback -/// prefilter. Works on all platforms. -/// -/// # Safety -/// -/// Callers must ensure that the `strat.kind.fallback` union field is set. -unsafe fn prefilter_kind_fallback( - strat: &Prefilter, - haystack: &[u8], -) -> Option<usize> { - strat.kind.fallback.find_prefilter(haystack) -} - -/// Reads from the `sse2` field of `PrefilterKind` to execute the x86_64 SSE2 -/// prefilter. -/// -/// # Safety -/// -/// Callers must ensure that the `strat.kind.sse2` union field is set. -#[cfg(all(target_arch = "x86_64", target_feature = "sse2"))] -unsafe fn prefilter_kind_sse2( - strat: &Prefilter, - haystack: &[u8], -) -> Option<usize> { - let finder = &strat.kind.sse2; - if haystack.len() < finder.min_haystack_len() { - strat.find_simple(haystack) - } else { - finder.find_prefilter(haystack) - } -} - -/// Reads from the `avx2` field of `PrefilterKind` to execute the x86_64 AVX2 -/// prefilter. -/// -/// # Safety -/// -/// Callers must ensure that the `strat.kind.avx2` union field is set. -#[cfg(all(target_arch = "x86_64", target_feature = "sse2"))] -unsafe fn prefilter_kind_avx2( - strat: &Prefilter, - haystack: &[u8], -) -> Option<usize> { - let finder = &strat.kind.avx2; - if haystack.len() < finder.min_haystack_len() { - strat.find_simple(haystack) - } else { - finder.find_prefilter(haystack) - } -} - -/// Reads from the `simd128` field of `PrefilterKind` to execute the wasm32 -/// simd128 prefilter. -/// -/// # Safety -/// -/// Callers must ensure that the `strat.kind.simd128` union field is set. -#[cfg(target_arch = "wasm32")] -unsafe fn prefilter_kind_simd128( - strat: &Prefilter, - haystack: &[u8], -) -> Option<usize> { - let finder = &strat.kind.simd128; - if haystack.len() < finder.min_haystack_len() { - strat.find_simple(haystack) - } else { - finder.find_prefilter(haystack) - } -} - -/// Reads from the `neon` field of `PrefilterKind` to execute the aarch64 neon -/// prefilter. -/// -/// # Safety -/// -/// Callers must ensure that the `strat.kind.neon` union field is set. -#[cfg(target_arch = "aarch64")] -unsafe fn prefilter_kind_neon( - strat: &Prefilter, - haystack: &[u8], -) -> Option<usize> { - let finder = &strat.kind.neon; - if haystack.len() < finder.min_haystack_len() { - strat.find_simple(haystack) - } else { - finder.find_prefilter(haystack) - } -} - -/// PrefilterState tracks state associated with the effectiveness of a -/// prefilter. It is used to track how many bytes, on average, are skipped by -/// the prefilter. If this average dips below a certain threshold over time, -/// then the state renders the prefilter inert and stops using it. -/// -/// A prefilter state should be created for each search. (Where creating an -/// iterator is treated as a single search.) A prefilter state should only be -/// created from a `Freqy`. e.g., An inert `Freqy` will produce an inert -/// `PrefilterState`. -#[derive(Clone, Copy, Debug)] -pub(crate) struct PrefilterState { - /// The number of skips that has been executed. This is always 1 greater - /// than the actual number of skips. The special sentinel value of 0 - /// indicates that the prefilter is inert. This is useful to avoid - /// additional checks to determine whether the prefilter is still - /// "effective." Once a prefilter becomes inert, it should no longer be - /// used (according to our heuristics). - skips: u32, - /// The total number of bytes that have been skipped. - skipped: u32, -} - -impl PrefilterState { - /// The minimum number of skip attempts to try before considering whether - /// a prefilter is effective or not. - const MIN_SKIPS: u32 = 50; - - /// The minimum amount of bytes that skipping must average. - /// - /// This value was chosen based on varying it and checking - /// the microbenchmarks. In particular, this can impact the - /// pathological/repeated-{huge,small} benchmarks quite a bit if it's set - /// too low. - const MIN_SKIP_BYTES: u32 = 8; - - /// Create a fresh prefilter state. - #[inline] - pub(crate) fn new() -> PrefilterState { - PrefilterState { skips: 1, skipped: 0 } - } - - /// Update this state with the number of bytes skipped on the last - /// invocation of the prefilter. - #[inline] - fn update(&mut self, skipped: usize) { - self.skips = self.skips.saturating_add(1); - // We need to do this dance since it's technically possible for - // `skipped` to overflow a `u32`. (And we use a `u32` to reduce the - // size of a prefilter state.) - self.skipped = match u32::try_from(skipped) { - Err(_) => core::u32::MAX, - Ok(skipped) => self.skipped.saturating_add(skipped), - }; - } - - /// Return true if and only if this state indicates that a prefilter is - /// still effective. - #[inline] - fn is_effective(&mut self) -> bool { - if self.is_inert() { - return false; - } - if self.skips() < PrefilterState::MIN_SKIPS { - return true; - } - if self.skipped >= PrefilterState::MIN_SKIP_BYTES * self.skips() { - return true; - } - - // We're inert. - self.skips = 0; - false - } - - /// Returns true if the prefilter this state represents should no longer - /// be used. - #[inline] - fn is_inert(&self) -> bool { - self.skips == 0 - } - - /// Returns the total number of times the prefilter has been used. - #[inline] - fn skips(&self) -> u32 { - // Remember, `0` is a sentinel value indicating inertness, so we - // always need to subtract `1` to get our actual number of skips. - self.skips.saturating_sub(1) - } -} - -/// A combination of prefilter effectiveness state and the prefilter itself. -#[derive(Debug)] -pub(crate) struct Pre<'a> { - /// State that tracks the effectiveness of a prefilter. - prestate: &'a mut PrefilterState, - /// The actual prefilter. - prestrat: &'a Prefilter, -} - -impl<'a> Pre<'a> { - /// Call this prefilter on the given haystack with the given needle. - #[inline] - pub(crate) fn find(&mut self, haystack: &[u8]) -> Option<usize> { - let result = self.prestrat.find(haystack); - self.prestate.update(result.unwrap_or(haystack.len())); - result - } - - /// Return true if and only if this prefilter should be used. - #[inline] - pub(crate) fn is_effective(&mut self) -> bool { - self.prestate.is_effective() - } -} - -/// Returns true if the needle has the right characteristics for a vector -/// algorithm to handle the entirety of substring search. -/// -/// Vector algorithms can be used for prefilters for other substring search -/// algorithms (like Two-Way), but they can also be used for substring search -/// on their own. When used for substring search, vector algorithms will -/// quickly identify candidate match positions (just like in the prefilter -/// case), but instead of returning the candidate position they will try to -/// confirm the match themselves. Confirmation happens via `memcmp`. This -/// works well for short needles, but can break down when many false candidate -/// positions are generated for large needles. Thus, we only permit vector -/// algorithms to own substring search when the needle is of a certain length. -#[inline] -fn do_packed_search(needle: &[u8]) -> bool { - /// The minimum length of a needle required for this algorithm. The minimum - /// is 2 since a length of 1 should just use memchr and a length of 0 isn't - /// a case handled by this searcher. - const MIN_LEN: usize = 2; - - /// The maximum length of a needle required for this algorithm. - /// - /// In reality, there is no hard max here. The code below can handle any - /// length needle. (Perhaps that suggests there are missing optimizations.) - /// Instead, this is a heuristic and a bound guaranteeing our linear time - /// complexity. - /// - /// It is a heuristic because when a candidate match is found, memcmp is - /// run. For very large needles with lots of false positives, memcmp can - /// make the code run quite slow. - /// - /// It is a bound because the worst case behavior with memcmp is - /// multiplicative in the size of the needle and haystack, and we want - /// to keep that additive. This bound ensures we still meet that bound - /// theoretically, since it's just a constant. We aren't acting in bad - /// faith here, memcmp on tiny needles is so fast that even in pathological - /// cases (see pathological vector benchmarks), this is still just as fast - /// or faster in practice. - /// - /// This specific number was chosen by tweaking a bit and running - /// benchmarks. The rare-medium-needle, for example, gets about 5% faster - /// by using this algorithm instead of a prefilter-accelerated Two-Way. - /// There's also a theoretical desire to keep this number reasonably - /// low, to mitigate the impact of pathological cases. I did try 64, and - /// some benchmarks got a little better, and others (particularly the - /// pathological ones), got a lot worse. So... 32 it is? - const MAX_LEN: usize = 32; - MIN_LEN <= needle.len() && needle.len() <= MAX_LEN -} |