Module prefilter 

Fast prefiltering algorithms, which run before Smith Waterman since in the typical case, a small percentage of the haystack will match the needle. Automatically used by the Matcher and match_list APIs.

Unordered algorithms are much faster than ordered algorithms, but allow for false positives. As a result, a backwards pass must be performed after Smith Waterman to verify the number of typos. But the faster prefilter outweighs this extra cost. The algorithm also checks both lowercase and uppercase needle chars in the same comparison (when AVX2 is available).

needle: "foo"
haystack: "Fo_o"

// assuming 4 and 8 byte SIMD widths for simplicity
// in reality, the widths are 16 and 32 bytes

needle[0]: [f, f, f, f, F, F, F, F]

haystack: [F, o, _, o]
// expand to 8 bytes by broadcasting lo to hi
haystack: [F, o, _, o, F, o, _, o]

needle == haystack
mask: [00, 00, 00, 00, FF, 00, 00, 00]
bitmask: 0b00001000 // movemask(mask)
bitmask > 0 // needle found in haystack, check next needle char

See the full implementation in src/prefilter/x86_64/avx2.rs. When 256-bit SIMD is not available (no AVX2 or ARM), we simply check the uppercase and lowercase separately.

The Prefilter struct chooses the fastest algorithm via runtime feature detection. SIMD algorithms only apply to haystack.len() >= 16. All algorithms assume that needle.len() > 0

Modules

scalar

x86_64

Enums

Prefilter

SIMD unordered prefiltering algorithm which allows for false positives. Chooses the fastest algorithm via runtime feature detection.