frizbee

Frizbee's performance is evaluated across several datasets and scenarios, comparing it against Nucleo, FZF, and Iter. The benchmarks cover various character encodings (UTF-8 throughput for 2-byte and 3-byte characters), match scenarios (Partial Match, All Match, No Match, etc.), and sorting performance.

Key performance characteristics observed:

• High Throughput: Significant speedups in UTF-8 processing for Arabic (2-bytes) and Korean (3-bytes) datasets.
• Scenario Efficiency: High performance in 'No Match' and 'Partial Match' scenarios due to effective prefiltering.
• Parallelism: Significant speedups when using Parallel (x8) execution compared to Sequential execution in many datasets.

Frizbee uses a SIMD-accelerated prefiltering step to quickly discard haystacks that cannot match the needle.

Unlike other implementations (like Nucleo) that perform multiple sequential loads for each needle character, Frizbee loads the haystack chunk-by-chunk and uses bitmasks to skip already-matched prefixes. This significantly reduces the number of memory loads. Frizbee also identifies and skips prefixes/suffixes of the haystack that contain characters not present in the needle.

Frizbee implements the Smith-Waterman algorithm with affine gaps and row-wise parallelism via SIMD.

Key characteristics:

• Local Alignment: It finds the best local sequence alignment.
• Complexity: While the theoretical complexity is $O(nm)$, Frizbee optimizes this for small matrices (typically $m < 128$) using SIMD.
• Scoring Optimization: When the maximum score is $< 256$ (relative to needle length), Frizbee uses u8 scoring instead of the default u16, effectively doubling the SIMD width.
• Data Dependency: It uses a sequential layout where horizontal data dependencies are applied immediately to support affine gaps.

When analyzing or running benchmarks, Frizbee uses several distinct configuration modes that affect performance and matching behavior:

• Frizbee (Default): Uses Config::default(). This performs the fastest prefiltering because no typos are allowed.
• Iter: Uses the match_iter API to lazily match haystacks one at a time, similar to the default configuration.
• All Scores: Configured with max_typos: None. This retrieves scores for all items without any filtering.
• 1/2 Typos: Configured with max_typos: Some(1) or max_typos: Some(2). This uses a slower but effective prefilter that allows a small number of typos.
• 3 Typos: Configured with max_typos: Some(3). This skips prefiltering entirely because, in non-synthetic data, the prefilter would require up to 4 passes over the data without providing significant filtering benefits.

You can test the performance of Frizbee by running the included benchmarks. The benchmarks compare Frizbee's performance against different configurations and other tools like Nucleo and FZF. Note that the benchmark results provided in the documentation were generated on a Ryzen 9950x3D running NixOS 26.11.0.

# Use cargo to run the included benchmarks
cargo bench

For a simpler, albeit slightly slower, interface, you can use the FuzzyMatchExt trait to call .fuzzy_match() directly on an iterator of strings. To sort the resulting matches, use the radix_sort_matches function.

use frizbee::{iter::FuzzyMatchExt, Config, radix_sort_matches};

let haystacks = ["fooBar", "foo_bar", "prelude", "println!"];
let mut matches: Vec<_> = haystacks
    .iter()
    .fuzzy_match("fBr", &Config::default())
    .collect();

radix_sort_matches(&mut matches);

Frizbee supports multi-pattern matching using whitespace-separated queries. You can control the matching mode for each pattern using specific prefixes:

Example query: "foo !^bar" matches strings containing foo but not starting with bar.

use frizbee::{Config, Matcher};

let needle = "foo !^bar";
let haystacks = ["fooBar", "foo_bar", "barfoo", "prelude", "println!"];

let mut matcher = Matcher::from_query(needle, &Config::default());
let matches = matcher.match_list(&haystacks);

If you need different matching behaviors for different needles (for example, scaling allowed typos based on the length of the needle), use Pattern::parse_query to generate a collection of patterns, modify them, and then initialize a Matcher using Matcher::from_patterns.

use frizbee::{Config, Matcher, Pattern};

let haystacks = ["fooBar", "foo_bar", "barfoo", "prelude", "println!"];

let patterns = Pattern::parse_query("foo !^bar")
    .into_iter()
    .map(|pattern| {
        let max_typos = (pattern.needle.len() / 4) as u16;
        pattern.max_typos(Some(max_typos))
    })
    .collect::<Vec<_>>();

let mut matcher = Matcher::from_patterns(&patterns, &Config::default());
let matches = matcher.match_list(&haystacks);

To perform fuzzy matching, create a Matcher instance using a needle (the search string) and a Config. You can then match against a list of strings using match_list or use match_list_parallel to distribute the workload across multiple threads.

Note: Frizbee will panic if the needle length exceeds config.scoring.max_needle_len(). The default limit is 10,922 characters.

use frizbee::{Config, Matcher, Pattern};

let needle = "fBr";
let haystacks = ["fooBar", "foo_bar", "barfoo", "prelude", "println!"];

let mut matcher = Matcher::new(needle, &Config::default());
let matches = matcher.match_list(&haystacks);
// or in parallel (8 threads)
let matches = matcher.match_list_parallel(&haystacks, 8);