Source code
Revision control
Copy as Markdown
Other Tools
use core::{
fmt::Debug,
panic::{RefUnwindSafe, UnwindSafe},
};
use alloc::sync::Arc;
use crate::packed::{ext::Pointer, pattern::Patterns, teddy::generic::Match};
/// A builder for constructing a Teddy matcher.
///
/// The builder primarily permits fine grained configuration of the Teddy
/// matcher. Most options are made only available for testing/benchmarking
/// purposes. In reality, options are automatically determined by the nature
/// and number of patterns given to the builder.
#[derive(Clone, Debug)]
pub(crate) struct Builder {
/// When none, this is automatically determined. Otherwise, `false` means
/// slim Teddy is used (8 buckets) and `true` means fat Teddy is used
/// (16 buckets). Fat Teddy requires AVX2, so if that CPU feature isn't
/// available and Fat Teddy was requested, no matcher will be built.
only_fat: Option<bool>,
/// When none, this is automatically determined. Otherwise, `false` means
/// that 128-bit vectors will be used (up to SSSE3 instructions) where as
/// `true` means that 256-bit vectors will be used. As with `fat`, if
/// 256-bit vectors are requested and they aren't available, then a
/// searcher will not be built.
only_256bit: Option<bool>,
/// When true (the default), the number of patterns will be used as a
/// heuristic for refusing construction of a Teddy searcher. The point here
/// is that too many patterns can overwhelm Teddy. But this can be disabled
/// in cases where the caller knows better.
heuristic_pattern_limits: bool,
}
impl Default for Builder {
fn default() -> Builder {
Builder::new()
}
}
impl Builder {
/// Create a new builder for configuring a Teddy matcher.
pub(crate) fn new() -> Builder {
Builder {
only_fat: None,
only_256bit: None,
heuristic_pattern_limits: true,
}
}
/// Build a matcher for the set of patterns given. If a matcher could not
/// be built, then `None` is returned.
///
/// Generally, a matcher isn't built if the necessary CPU features aren't
/// available, an unsupported target or if the searcher is believed to be
/// slower than standard techniques (i.e., if there are too many literals).
pub(crate) fn build(&self, patterns: Arc<Patterns>) -> Option<Searcher> {
self.build_imp(patterns)
}
/// Require the use of Fat (true) or Slim (false) Teddy. Fat Teddy uses
/// 16 buckets where as Slim Teddy uses 8 buckets. More buckets are useful
/// for a larger set of literals.
///
/// `None` is the default, which results in an automatic selection based
/// on the number of literals and available CPU features.
pub(crate) fn only_fat(&mut self, yes: Option<bool>) -> &mut Builder {
self.only_fat = yes;
self
}
/// Request the use of 256-bit vectors (true) or 128-bit vectors (false).
/// Generally, a larger vector size is better since it either permits
/// matching more patterns or matching more bytes in the haystack at once.
///
/// `None` is the default, which results in an automatic selection based on
/// the number of literals and available CPU features.
pub(crate) fn only_256bit(&mut self, yes: Option<bool>) -> &mut Builder {
self.only_256bit = yes;
self
}
/// Request that heuristic limitations on the number of patterns be
/// employed. This useful to disable for benchmarking where one wants to
/// explore how Teddy performs on large number of patterns even if the
/// heuristics would otherwise refuse construction.
///
/// This is enabled by default.
pub(crate) fn heuristic_pattern_limits(
&mut self,
yes: bool,
) -> &mut Builder {
self.heuristic_pattern_limits = yes;
self
}
fn build_imp(&self, patterns: Arc<Patterns>) -> Option<Searcher> {
let patlimit = self.heuristic_pattern_limits;
// There's no particular reason why we limit ourselves to little endian
// here, but it seems likely that some parts of Teddy as they are
// currently written (e.g., the uses of `trailing_zeros`) are likely
// wrong on non-little-endian targets. Such things are likely easy to
// fix, but at the time of writing (2023/09/18), I actually do not know
// how to test this code on a big-endian target. So for now, we're
// conservative and just bail out.
if !cfg!(target_endian = "little") {
debug!("skipping Teddy because target isn't little endian");
return None;
}
// Too many patterns will overwhelm Teddy and likely lead to slow
// downs, typically in the verification step.
if patlimit && patterns.len() > 64 {
debug!("skipping Teddy because of too many patterns");
return None;
}
#[cfg(all(target_arch = "x86_64", target_feature = "sse2"))]
{
use self::x86_64::{FatAVX2, SlimAVX2, SlimSSSE3};
let mask_len = core::cmp::min(4, patterns.minimum_len());
let beefy = patterns.len() > 32;
let has_avx2 = self::x86_64::is_available_avx2();
let has_ssse3 = has_avx2 || self::x86_64::is_available_ssse3();
let use_avx2 = if self.only_256bit == Some(true) {
if !has_avx2 {
debug!(
"skipping Teddy because avx2 was demanded but unavailable"
);
return None;
}
true
} else if self.only_256bit == Some(false) {
if !has_ssse3 {
debug!(
"skipping Teddy because ssse3 was demanded but unavailable"
);
return None;
}
false
} else if !has_ssse3 && !has_avx2 {
debug!(
"skipping Teddy because ssse3 and avx2 are unavailable"
);
return None;
} else {
has_avx2
};
let fat = match self.only_fat {
None => use_avx2 && beefy,
Some(false) => false,
Some(true) if !use_avx2 => {
debug!(
"skipping Teddy because fat was demanded, but fat \
Teddy requires avx2 which is unavailable"
);
return None;
}
Some(true) => true,
};
// Just like for aarch64, it's possible that too many patterns will
// overhwelm Teddy. Unlike aarch64 though, we have Fat teddy which
// helps things scale a bit more by spreading patterns over more
// buckets.
//
// These thresholds were determined by looking at the measurements
// for the rust/aho-corasick/packed/leftmost-first and
// rust/aho-corasick/dfa/leftmost-first engines on the `teddy/`
// benchmarks.
if patlimit && mask_len == 1 && patterns.len() > 16 {
debug!(
"skipping Teddy (mask len: 1) because there are \
too many patterns",
);
return None;
}
match (mask_len, use_avx2, fat) {
(1, false, _) => {
debug!("Teddy choice: 128-bit slim, 1 byte");
SlimSSSE3::<1>::new(&patterns)
}
(1, true, false) => {
debug!("Teddy choice: 256-bit slim, 1 byte");
SlimAVX2::<1>::new(&patterns)
}
(1, true, true) => {
debug!("Teddy choice: 256-bit fat, 1 byte");
FatAVX2::<1>::new(&patterns)
}
(2, false, _) => {
debug!("Teddy choice: 128-bit slim, 2 bytes");
SlimSSSE3::<2>::new(&patterns)
}
(2, true, false) => {
debug!("Teddy choice: 256-bit slim, 2 bytes");
SlimAVX2::<2>::new(&patterns)
}
(2, true, true) => {
debug!("Teddy choice: 256-bit fat, 2 bytes");
FatAVX2::<2>::new(&patterns)
}
(3, false, _) => {
debug!("Teddy choice: 128-bit slim, 3 bytes");
SlimSSSE3::<3>::new(&patterns)
}
(3, true, false) => {
debug!("Teddy choice: 256-bit slim, 3 bytes");
SlimAVX2::<3>::new(&patterns)
}
(3, true, true) => {
debug!("Teddy choice: 256-bit fat, 3 bytes");
FatAVX2::<3>::new(&patterns)
}
(4, false, _) => {
debug!("Teddy choice: 128-bit slim, 4 bytes");
SlimSSSE3::<4>::new(&patterns)
}
(4, true, false) => {
debug!("Teddy choice: 256-bit slim, 4 bytes");
SlimAVX2::<4>::new(&patterns)
}
(4, true, true) => {
debug!("Teddy choice: 256-bit fat, 4 bytes");
FatAVX2::<4>::new(&patterns)
}
_ => {
debug!("no supported Teddy configuration found");
None
}
}
}
#[cfg(target_arch = "aarch64")]
{
use self::aarch64::SlimNeon;
let mask_len = core::cmp::min(4, patterns.minimum_len());
if self.only_256bit == Some(true) {
debug!(
"skipping Teddy because 256-bits were demanded \
but unavailable"
);
return None;
}
if self.only_fat == Some(true) {
debug!(
"skipping Teddy because fat was demanded but unavailable"
);
}
// Since we don't have Fat teddy in aarch64 (I think we'd want at
// least 256-bit vectors for that), we need to be careful not to
// allow too many patterns as it might overwhelm Teddy. Generally
// speaking, as the mask length goes up, the more patterns we can
// handle because the mask length results in fewer candidates
// generated.
//
// These thresholds were determined by looking at the measurements
// for the rust/aho-corasick/packed/leftmost-first and
// rust/aho-corasick/dfa/leftmost-first engines on the `teddy/`
// benchmarks.
match mask_len {
1 => {
if patlimit && patterns.len() > 16 {
debug!(
"skipping Teddy (mask len: 1) because there are \
too many patterns",
);
}
debug!("Teddy choice: 128-bit slim, 1 byte");
SlimNeon::<1>::new(&patterns)
}
2 => {
if patlimit && patterns.len() > 32 {
debug!(
"skipping Teddy (mask len: 2) because there are \
too many patterns",
);
}
debug!("Teddy choice: 128-bit slim, 2 bytes");
SlimNeon::<2>::new(&patterns)
}
3 => {
if patlimit && patterns.len() > 48 {
debug!(
"skipping Teddy (mask len: 3) because there are \
too many patterns",
);
}
debug!("Teddy choice: 128-bit slim, 3 bytes");
SlimNeon::<3>::new(&patterns)
}
4 => {
debug!("Teddy choice: 128-bit slim, 4 bytes");
SlimNeon::<4>::new(&patterns)
}
_ => {
debug!("no supported Teddy configuration found");
None
}
}
}
#[cfg(not(any(
all(target_arch = "x86_64", target_feature = "sse2"),
target_arch = "aarch64"
)))]
{
None
}
}
}
/// A searcher that dispatches to one of several possible Teddy variants.
#[derive(Clone, Debug)]
pub(crate) struct Searcher {
/// The Teddy variant we use. We use dynamic dispatch under the theory that
/// it results in better codegen then a enum, although this is a specious
/// claim.
///
/// This `Searcher` is essentially a wrapper for a `SearcherT` trait
/// object. We just make `memory_usage` and `minimum_len` available without
/// going through dynamic dispatch.
imp: Arc<dyn SearcherT>,
/// Total heap memory used by the Teddy variant.
memory_usage: usize,
/// The minimum haystack length this searcher can handle. It is intended
/// for callers to use some other search routine (such as Rabin-Karp) in
/// cases where the haystack (or remainer of the haystack) is too short.
minimum_len: usize,
}
impl Searcher {
/// Look for the leftmost occurrence of any pattern in this search in the
/// given haystack starting at the given position.
///
/// # Panics
///
/// This panics when `haystack[at..].len()` is less than the minimum length
/// for this haystack.
#[inline(always)]
pub(crate) fn find(
&self,
haystack: &[u8],
at: usize,
) -> Option<crate::Match> {
// SAFETY: The Teddy implementations all require a minimum haystack
// length, and this is required for safety. Therefore, we assert it
// here in order to make this method sound.
assert!(haystack[at..].len() >= self.minimum_len);
let hayptr = haystack.as_ptr();
// SAFETY: Construction of the searcher guarantees that we are able
// to run it in the current environment (i.e., we won't get an AVX2
// searcher on a x86-64 CPU without AVX2 support). Also, the pointers
// are valid as they are derived directly from a borrowed slice.
let teddym = unsafe {
self.imp.find(hayptr.add(at), hayptr.add(haystack.len()))?
};
let start = teddym.start().as_usize().wrapping_sub(hayptr.as_usize());
let end = teddym.end().as_usize().wrapping_sub(hayptr.as_usize());
let span = crate::Span { start, end };
// OK because we won't permit the construction of a searcher that
// could report a pattern ID bigger than what can fit in the crate-wide
// PatternID type.
let pid = crate::PatternID::new_unchecked(teddym.pattern().as_usize());
let m = crate::Match::new(pid, span);
Some(m)
}
/// Returns the approximate total amount of heap used by this type, in
/// units of bytes.
#[inline(always)]
pub(crate) fn memory_usage(&self) -> usize {
self.memory_usage
}
/// Returns the minimum length, in bytes, that a haystack must be in order
/// to use it with this searcher.
#[inline(always)]
pub(crate) fn minimum_len(&self) -> usize {
self.minimum_len
}
}
/// A trait that provides dynamic dispatch over the different possible Teddy
/// variants on the same algorithm.
///
/// On `x86_64` for example, it isn't known until runtime which of 12 possible
/// variants will be used. One might use one of the four slim 128-bit vector
/// variants, or one of the four 256-bit vector variants or even one of the
/// four fat 256-bit vector variants.
///
/// Since this choice is generally made when the Teddy searcher is constructed
/// and this choice is based on the patterns given and what the current CPU
/// supports, it follows that there must be some kind of indirection at search
/// time that "selects" the variant chosen at build time.
///
/// There are a few different ways to go about this. One approach is to use an
/// enum. It works fine, but in my experiments, this generally results in worse
/// codegen. Another approach, which is what we use here, is dynamic dispatch
/// via a trait object. We basically implement this trait for each possible
/// variant, select the variant we want at build time and convert it to a
/// trait object for use at search time.
///
/// Another approach is to use function pointers and stick each of the possible
/// variants into a union. This is essentially isomorphic to the dynamic
/// dispatch approach, but doesn't require any allocations. Since this crate
/// requires `alloc`, there's no real reason (AFAIK) to go down this path. (The
/// `memchr` crate does this.)
trait SearcherT:
Debug + Send + Sync + UnwindSafe + RefUnwindSafe + 'static
{
/// Execute a search on the given haystack (identified by `start` and `end`
/// raw pointers).
///
/// # Safety
///
/// Essentially, the `start` and `end` pointers must be valid and point
/// to a haystack one can read. As long as you derive them from, for
/// example, a `&[u8]`, they should automatically satisfy all of the safety
/// obligations:
///
/// * Both `start` and `end` must be valid for reads.
/// * Both `start` and `end` must point to an initialized value.
/// * Both `start` and `end` must point to the same allocated object and
/// must either be in bounds or at most one byte past the end of the
/// allocated object.
/// * Both `start` and `end` must be _derived from_ a pointer to the same
/// object.
/// * The distance between `start` and `end` must not overflow `isize`.
/// * The distance being in bounds must not rely on "wrapping around" the
/// address space.
/// * It must be the case that `start <= end`.
/// * `end - start` must be greater than the minimum length for this
/// searcher.
///
/// Also, it is expected that implementations of this trait will tag this
/// method with a `target_feature` attribute. Callers must ensure that
/// they are executing this method in an environment where that attribute
/// is valid.
unsafe fn find(&self, start: *const u8, end: *const u8) -> Option<Match>;
}
#[cfg(all(target_arch = "x86_64", target_feature = "sse2"))]
mod x86_64 {
use core::arch::x86_64::{__m128i, __m256i};
use alloc::sync::Arc;
use crate::packed::{
ext::Pointer,
pattern::Patterns,
teddy::generic::{self, Match},
};
use super::{Searcher, SearcherT};
#[derive(Clone, Debug)]
pub(super) struct SlimSSSE3<const BYTES: usize> {
slim128: generic::Slim<__m128i, BYTES>,
}
// Defines SlimSSSE3 wrapper functions for 1, 2, 3 and 4 bytes.
macro_rules! slim_ssse3 {
($len:expr) => {
impl SlimSSSE3<$len> {
/// Creates a new searcher using "slim" Teddy with 128-bit
/// vectors. If SSSE3 is not available in the current
/// environment, then this returns `None`.
pub(super) fn new(
patterns: &Arc<Patterns>,
) -> Option<Searcher> {
if !is_available_ssse3() {
return None;
}
Some(unsafe { SlimSSSE3::<$len>::new_unchecked(patterns) })
}
/// Creates a new searcher using "slim" Teddy with 256-bit
/// vectors without checking whether SSSE3 is available or not.
///
/// # Safety
///
/// Callers must ensure that SSSE3 is available in the current
/// environment.
#[target_feature(enable = "ssse3")]
unsafe fn new_unchecked(patterns: &Arc<Patterns>) -> Searcher {
let slim128 = generic::Slim::<__m128i, $len>::new(
Arc::clone(patterns),
);
let memory_usage = slim128.memory_usage();
let minimum_len = slim128.minimum_len();
let imp = Arc::new(SlimSSSE3 { slim128 });
Searcher { imp, memory_usage, minimum_len }
}
}
impl SearcherT for SlimSSSE3<$len> {
#[target_feature(enable = "ssse3")]
#[inline]
unsafe fn find(
&self,
start: *const u8,
end: *const u8,
) -> Option<Match> {
// SAFETY: All obligations except for `target_feature` are
// passed to the caller. Our use of `target_feature` is
// safe because construction of this type requires that the
// requisite target features are available.
self.slim128.find(start, end)
}
}
};
}
slim_ssse3!(1);
slim_ssse3!(2);
slim_ssse3!(3);
slim_ssse3!(4);
#[derive(Clone, Debug)]
pub(super) struct SlimAVX2<const BYTES: usize> {
slim128: generic::Slim<__m128i, BYTES>,
slim256: generic::Slim<__m256i, BYTES>,
}
// Defines SlimAVX2 wrapper functions for 1, 2, 3 and 4 bytes.
macro_rules! slim_avx2 {
($len:expr) => {
impl SlimAVX2<$len> {
/// Creates a new searcher using "slim" Teddy with 256-bit
/// vectors. If AVX2 is not available in the current
/// environment, then this returns `None`.
pub(super) fn new(
patterns: &Arc<Patterns>,
) -> Option<Searcher> {
if !is_available_avx2() {
return None;
}
Some(unsafe { SlimAVX2::<$len>::new_unchecked(patterns) })
}
/// Creates a new searcher using "slim" Teddy with 256-bit
/// vectors without checking whether AVX2 is available or not.
///
/// # Safety
///
/// Callers must ensure that AVX2 is available in the current
/// environment.
#[target_feature(enable = "avx2")]
unsafe fn new_unchecked(patterns: &Arc<Patterns>) -> Searcher {
let slim128 = generic::Slim::<__m128i, $len>::new(
Arc::clone(&patterns),
);
let slim256 = generic::Slim::<__m256i, $len>::new(
Arc::clone(&patterns),
);
let memory_usage =
slim128.memory_usage() + slim256.memory_usage();
let minimum_len = slim128.minimum_len();
let imp = Arc::new(SlimAVX2 { slim128, slim256 });
Searcher { imp, memory_usage, minimum_len }
}
}
impl SearcherT for SlimAVX2<$len> {
#[target_feature(enable = "avx2")]
#[inline]
unsafe fn find(
&self,
start: *const u8,
end: *const u8,
) -> Option<Match> {
// SAFETY: All obligations except for `target_feature` are
// passed to the caller. Our use of `target_feature` is
// safe because construction of this type requires that the
// requisite target features are available.
let len = end.distance(start);
if len < self.slim256.minimum_len() {
self.slim128.find(start, end)
} else {
self.slim256.find(start, end)
}
}
}
};
}
slim_avx2!(1);
slim_avx2!(2);
slim_avx2!(3);
slim_avx2!(4);
#[derive(Clone, Debug)]
pub(super) struct FatAVX2<const BYTES: usize> {
fat256: generic::Fat<__m256i, BYTES>,
}
// Defines SlimAVX2 wrapper functions for 1, 2, 3 and 4 bytes.
macro_rules! fat_avx2 {
($len:expr) => {
impl FatAVX2<$len> {
/// Creates a new searcher using "slim" Teddy with 256-bit
/// vectors. If AVX2 is not available in the current
/// environment, then this returns `None`.
pub(super) fn new(
patterns: &Arc<Patterns>,
) -> Option<Searcher> {
if !is_available_avx2() {
return None;
}
Some(unsafe { FatAVX2::<$len>::new_unchecked(patterns) })
}
/// Creates a new searcher using "slim" Teddy with 256-bit
/// vectors without checking whether AVX2 is available or not.
///
/// # Safety
///
/// Callers must ensure that AVX2 is available in the current
/// environment.
#[target_feature(enable = "avx2")]
unsafe fn new_unchecked(patterns: &Arc<Patterns>) -> Searcher {
let fat256 = generic::Fat::<__m256i, $len>::new(
Arc::clone(&patterns),
);
let memory_usage = fat256.memory_usage();
let minimum_len = fat256.minimum_len();
let imp = Arc::new(FatAVX2 { fat256 });
Searcher { imp, memory_usage, minimum_len }
}
}
impl SearcherT for FatAVX2<$len> {
#[target_feature(enable = "avx2")]
#[inline]
unsafe fn find(
&self,
start: *const u8,
end: *const u8,
) -> Option<Match> {
// SAFETY: All obligations except for `target_feature` are
// passed to the caller. Our use of `target_feature` is
// safe because construction of this type requires that the
// requisite target features are available.
self.fat256.find(start, end)
}
}
};
}
fat_avx2!(1);
fat_avx2!(2);
fat_avx2!(3);
fat_avx2!(4);
#[inline]
pub(super) fn is_available_ssse3() -> bool {
#[cfg(not(target_feature = "sse2"))]
{
false
}
#[cfg(target_feature = "sse2")]
{
#[cfg(target_feature = "ssse3")]
{
true
}
#[cfg(not(target_feature = "ssse3"))]
{
#[cfg(feature = "std")]
{
std::is_x86_feature_detected!("ssse3")
}
#[cfg(not(feature = "std"))]
{
false
}
}
}
}
#[inline]
pub(super) fn is_available_avx2() -> bool {
#[cfg(not(target_feature = "sse2"))]
{
false
}
#[cfg(target_feature = "sse2")]
{
#[cfg(target_feature = "avx2")]
{
true
}
#[cfg(not(target_feature = "avx2"))]
{
#[cfg(feature = "std")]
{
std::is_x86_feature_detected!("avx2")
}
#[cfg(not(feature = "std"))]
{
false
}
}
}
}
}
#[cfg(target_arch = "aarch64")]
mod aarch64 {
use core::arch::aarch64::uint8x16_t;
use alloc::sync::Arc;
use crate::packed::{
pattern::Patterns,
teddy::generic::{self, Match},
};
use super::{Searcher, SearcherT};
#[derive(Clone, Debug)]
pub(super) struct SlimNeon<const BYTES: usize> {
slim128: generic::Slim<uint8x16_t, BYTES>,
}
// Defines SlimSSSE3 wrapper functions for 1, 2, 3 and 4 bytes.
macro_rules! slim_neon {
($len:expr) => {
impl SlimNeon<$len> {
/// Creates a new searcher using "slim" Teddy with 128-bit
/// vectors. If SSSE3 is not available in the current
/// environment, then this returns `None`.
pub(super) fn new(
patterns: &Arc<Patterns>,
) -> Option<Searcher> {
Some(unsafe { SlimNeon::<$len>::new_unchecked(patterns) })
}
/// Creates a new searcher using "slim" Teddy with 256-bit
/// vectors without checking whether SSSE3 is available or not.
///
/// # Safety
///
/// Callers must ensure that SSSE3 is available in the current
/// environment.
#[target_feature(enable = "neon")]
unsafe fn new_unchecked(patterns: &Arc<Patterns>) -> Searcher {
let slim128 = generic::Slim::<uint8x16_t, $len>::new(
Arc::clone(patterns),
);
let memory_usage = slim128.memory_usage();
let minimum_len = slim128.minimum_len();
let imp = Arc::new(SlimNeon { slim128 });
Searcher { imp, memory_usage, minimum_len }
}
}
impl SearcherT for SlimNeon<$len> {
#[target_feature(enable = "neon")]
#[inline]
unsafe fn find(
&self,
start: *const u8,
end: *const u8,
) -> Option<Match> {
// SAFETY: All obligations except for `target_feature` are
// passed to the caller. Our use of `target_feature` is
// safe because construction of this type requires that the
// requisite target features are available.
self.slim128.find(start, end)
}
}
};
}
slim_neon!(1);
slim_neon!(2);
slim_neon!(3);
slim_neon!(4);
}