simdsieve

Part of Santh - open source Rust security and infrastructure tooling.

A SIMD-accelerated multi-pattern pre-filtering engine with zero-allocation streaming iteration. Scans byte haystacks for up to 16 patterns simultaneously using the widest SIMD instructions available.

What It Does

simdsieve is a first-pass candidate filter for substring search:

1. Prefix Extraction: Takes the first 1-4 bytes of each pattern
2. SIMD Filtering: Scans haystack in 32-128 byte blocks, finding positions where prefixes match using vectorized comparison
3. Verification: Confirms full pattern matches before yielding
4. Zero False Positives: Every yielded offset is a verified match start

Use this when you need to quickly filter large data streams for multiple patterns before applying more expensive analysis.

Architecture

* Single-byte pattern on modern x86_64. Multi-byte patterns scale linearly with prefix length.

Backend Selection

The optimal backend is auto-selected at construction time:

1. AVX-512: If avx512f and avx512bw CPU features are detected
2. AVX2: If avx2 is detected
3. NEON: On aarch64 targets (guaranteed by the architecture)
4. Scalar: Portable fallback for all other platforms

Dual-Pump Processing

AVX-512, AVX2, and NEON use "dual-pump" processing where each logical block is split into two halves processed together. This hides load latency by interleaving independent operations across both load ports.

Design Limits

• 16 patterns maximum: Unrolled register layout saturates execution ports
• 4-byte prefix: First 4 bytes used for SIMD filtering; full pattern for verification
• ASCII case-insensitive: Only a-z folded; non-ASCII compared verbatim

Usage

Add to Cargo.toml:

[dependencies]
simdsieve = "0.1"

Basic exact matching:

use simdsieve::SimdSieve;

let haystack = b"The quick brown fox jumps over the lazy dog";
let patterns: &[&[u8]] = &[b"fox", b"dog"];

let sieve = SimdSieve::new(haystack, patterns).unwrap();
let matches: Vec<usize> = sieve.collect();

assert_eq!(matches, vec![16, 40]); // Positions of "fox" and "dog"

Case-insensitive matching:

use simdsieve::SimdSieve;

let haystack = b"Hello World HELLO";
let patterns: &[&[u8]] = &[b"hello"];

let sieve = SimdSieve::new_case_insensitive(haystack, patterns).unwrap();
let matches: Vec<usize> = sieve.collect();

assert_eq!(matches, vec![0, 12]); // Matches "Hello" and "HELLO"

Density estimation (without full verification):

use simdsieve::SimdSieve;

let haystack = b"aaaaaa";
let patterns: &[&[u8]] = &[b"a"];

let count = SimdSieve::estimate_match_count(haystack, patterns, false);
assert_eq!(count, 6); // One prefix hit at each position

Compile-Once Haystack Scanning (CompiledSieve)

When scanning multiple haystacks with the same set of patterns (e.g. in a hot scanner loop, packet inspector, or log processor), calling SimdSieve::new(haystack, patterns) on every haystack incurs pattern validation, deduplication, runtime feature detection, and boxed SIMD filter allocation on each call.

Use [CompiledSieve] to compile the SIMD filter once up front and rebind haystacks with zero memory allocation and zero filter recompilation:

use simdsieve::CompiledSieve;

// Compile pattern set once (up to 16 patterns)
let compiled = CompiledSieve::new(&[b"GET", b"/admin", b"POST"]).unwrap();

let haystacks = [
    b"GET /admin HTTP/1.1\r\n".as_slice(),
    b"POST /api/v1 HTTP/1.1\r\n".as_slice(),
    b"GET /index.html HTTP/1.1\r\n".as_slice(),
];

// Rebind haystack per scan with zero heap allocation or filter rebuild
for haystack in haystacks {
    let matches: Vec<usize> = compiled.scan(haystack).collect();
    println!("Matches: {matches:?}");
}

For pattern sets larger than 16, use [CompiledMultiSieve]:

use simdsieve::CompiledMultiSieve;

let patterns: Vec<Vec<u8>> = (0..32).map(|i| format!("pattern_{i}").into_bytes()).collect();
let pattern_refs: Vec<&[u8]> = patterns.iter().map(Vec::as_slice).collect();

let compiled_multi = CompiledMultiSieve::new(&pattern_refs).unwrap();

for haystack in haystacks {
    let matches: Vec<usize> = compiled_multi.candidates(haystack).collect();
}

Construction Cost & 16-Pattern Cap

• 16-Pattern Cap per Filter: Single SIMD filters (SimdSieve / CompiledSieve) accept up to 16 patterns simultaneously, matching hardware SIMD register layouts. Pattern sets exceeding 16 automatically partition into 16-element chunks via MultiSieve or CompiledMultiSieve with $k$-way merge iteration.
• Construction Overhead: SimdSieve::new executes CPU feature detection (std::is_x86_feature_detected!), pattern deduplication, and heap allocation of aligned backend filters (Box<Filter>). CompiledSieve::new absorbs this cost once; subsequent .scan(haystack) calls rebind haystack pointers on stack memory without heap allocations.

Iterator Behavior

SimdSieve implements Iterator<Item = usize> and FusedIterator:

• Yields match offsets in ascending order
• After returning None, all subsequent calls return None
• Zero heap allocation during iteration
• Thread-safe: Send and Sync (immutable iterator)

Error Handling

Construction can fail with SimdSieveError:

• EmptyPatternSet: No patterns provided
• PatternLimitExceeded(usize): More than 16 patterns provided

use simdsieve::{SimdSieve, SimdSieveError};

let result = SimdSieve::new(b"haystack", &[]);
assert!(matches!(result, Err(SimdSieveError::EmptyPatternSet)));

Platform Support

Safety

simdsieve contains a small amount of unsafe code confined to platform-specific backend modules. Every unsafe block has been audited for soundness:

• SIMD loads use unaligned load intrinsics (loadu), safe for any valid pointer alignment.
• Block bounds are verified before each SIMD call; multi-byte prefixes require block_len >= block_size + max_prefix_len - 1 trailing bytes.
• Target features are detected at construction; #[target_feature] gates prevent executing unsupported instructions.
• No uninitialized memory is read; SIMD struct arrays are zero-initialized.
• unsafe_op_in_unsafe_fn is forbidden at the crate level.

Performance Tuning

When to Use This Crate

✅ Good for:

• Filtering large streams (>1MB) for multiple patterns
• Finding candidate positions for regex engines
• Log analysis with multiple fixed-string patterns
• Network packet inspection with signature matching

❌ Not ideal for:

• Single small haystacks (<1KB)
• Patterns longer than 4 bytes that differ only after position 4
• Pattern sets that share a long common prefix against uniform haystacks (this shifts the bottleneck from SIMD filtering to byte-by-byte verification, resulting in O(n × pattern_count) work)
• When you need capture groups or regex features

Prefetching

The engine automatically issues prefetch hints 512 bytes ahead. This value (8 cache lines) balances:

• Enough lookahead to hide memory latency on modern CPUs
• Not so much that we evict useful data from cache

Pattern Selection

For best performance:

• Use patterns with distinct first bytes when possible
• Place more frequent patterns earlier in the pattern list
• For case-insensitive mode, use lowercase in patterns

Benchmarks

Run benchmarks with:

cargo bench

Example throughput on AMD EPYC 9R14 (AVX-512):

License

Licensed under the MIT License. See LICENSE for details.

Contributing

Contributions welcome! Areas of interest:

• WebAssembly SIMD backend
• Additional benchmarks and fuzz targets
• New verification strategies

Please ensure:

• cargo test passes
• cargo clippy -- -D warnings is clean
• cargo fmt --check passes
• New code has module-level and item-level documentation