1 use std::time::Duration;
2
3 use aho_corasick::{packed, AhoCorasick, AhoCorasickBuilder, MatchKind};
4 use criterion::{
5 criterion_group, criterion_main, Bencher, Criterion, Throughput,
6 };
7
8 mod build;
9 mod input;
10 mod random;
11 mod same;
12 mod sherlock;
13
all(c: &mut Criterion)14 fn all(c: &mut Criterion) {
15 build::all(c);
16 sherlock::all(c);
17 random::all(c);
18 same::all(c);
19 }
20
21 /// Define a benchmark that tests the standard non-overlapping Aho-Corasick
22 /// algorithm, using both its NFA and DFA variants.
define_aho_corasick<B: AsRef<[u8]>>( c: &mut Criterion, group_name: &str, bench_name: &str, corpus: &[u8], count: usize, patterns: Vec<B>, )23 fn define_aho_corasick<B: AsRef<[u8]>>(
24 c: &mut Criterion,
25 group_name: &str,
26 bench_name: &str,
27 corpus: &[u8],
28 count: usize,
29 patterns: Vec<B>,
30 ) {
31 let patterns: Vec<Vec<u8>> =
32 patterns.into_iter().map(|b| b.as_ref().to_vec()).collect();
33
34 let haystack = corpus.to_vec();
35 let name = format!("nfa/{}", bench_name);
36 // let aut = AhoCorasick::new(patterns.clone());
37 let aut = AhoCorasickBuilder::new()
38 .match_kind(MatchKind::LeftmostFirst)
39 .dfa(false)
40 .build(patterns.clone());
41 define(c, group_name, &name, corpus, move |b| {
42 b.iter(|| assert_eq!(count, aut.find_iter(&haystack).count()));
43 });
44
45 let haystack = corpus.to_vec();
46 let name = format!("dfa/{}", bench_name);
47 // let aut = AhoCorasickBuilder::new().dfa(true).build(patterns.clone());
48 let aut = AhoCorasickBuilder::new()
49 .match_kind(MatchKind::LeftmostFirst)
50 .dfa(true)
51 .build(patterns.clone());
52 define(c, group_name, &name, corpus, move |b| {
53 b.iter(|| assert_eq!(count, aut.find_iter(&haystack).count()));
54 });
55
56 let name = format!("packed/teddy/{}", bench_name);
57 let haystack = corpus.to_vec();
58 let mut builder = packed::Config::new().force_teddy(true).builder();
59 builder.extend(patterns.clone());
60 if let Some(searcher) = builder.build() {
61 define(c, group_name, &name, corpus, move |b| {
62 b.iter(|| {
63 assert_eq!(count, searcher.find_iter(&haystack).count())
64 });
65 });
66 }
67
68 let name = format!("packed/rabinkarp/{}", bench_name);
69 let haystack = corpus.to_vec();
70 let mut builder = packed::Config::new().force_rabin_karp(true).builder();
71 builder.extend(patterns.clone());
72 if let Some(searcher) = builder.build() {
73 define(c, group_name, &name, corpus, move |b| {
74 b.iter(|| {
75 assert_eq!(count, searcher.find_iter(&haystack).count())
76 });
77 });
78 }
79 }
80
81 /// Define a benchmark that tests the different combinations of Aho-Corasick
82 /// DFAs. e.g., With and without byte classes and premultiplied state ids.
define_aho_corasick_dfa<B, F>( c: &mut Criterion, group_name: &str, bench_name: &str, corpus: &[u8], kind: MatchKind, count: usize, patterns: Vec<B>, find_count: F, ) where B: AsRef<[u8]>, F: 'static + Clone + Fn(&AhoCorasick, &[u8]) -> usize,83 fn define_aho_corasick_dfa<B, F>(
84 c: &mut Criterion,
85 group_name: &str,
86 bench_name: &str,
87 corpus: &[u8],
88 kind: MatchKind,
89 count: usize,
90 patterns: Vec<B>,
91 find_count: F,
92 ) where
93 B: AsRef<[u8]>,
94 F: 'static + Clone + Fn(&AhoCorasick, &[u8]) -> usize,
95 {
96 let patterns: Vec<Vec<u8>> =
97 patterns.into_iter().map(|b| b.as_ref().to_vec()).collect();
98
99 let counter = find_count.clone();
100 let haystack = corpus.to_vec();
101 let name = format!("dfa/byteclass-premultiply/{}", bench_name);
102 let aut = AhoCorasickBuilder::new()
103 .match_kind(kind)
104 .dfa(true)
105 .byte_classes(true)
106 .premultiply(true)
107 .build(patterns.clone());
108 define(c, group_name, &name, corpus, move |b| {
109 b.iter(|| assert_eq!(count, counter(&aut, &haystack)))
110 });
111
112 let counter = find_count.clone();
113 let haystack = corpus.to_vec();
114 let name = format!("dfa/nobyteclass-premultiply/{}", bench_name);
115 let aut = AhoCorasickBuilder::new()
116 .match_kind(kind)
117 .dfa(true)
118 .byte_classes(false)
119 .premultiply(true)
120 .build(patterns.clone());
121 define(c, group_name, &name, corpus, move |b| {
122 b.iter(|| assert_eq!(count, counter(&aut, &haystack)))
123 });
124
125 let counter = find_count.clone();
126 let haystack = corpus.to_vec();
127 let name = format!("dfa/byteclass-nopremultiply/{}", bench_name);
128 let aut = AhoCorasickBuilder::new()
129 .match_kind(kind)
130 .dfa(true)
131 .byte_classes(true)
132 .premultiply(false)
133 .build(patterns.clone());
134 define(c, group_name, &name, corpus, move |b| {
135 b.iter(|| assert_eq!(count, counter(&aut, &haystack)))
136 });
137
138 let counter = find_count.clone();
139 let haystack = corpus.to_vec();
140 let name = format!("dfa/nobyteclass-nopremultiply/{}", bench_name);
141 let aut = AhoCorasickBuilder::new()
142 .match_kind(kind)
143 .dfa(true)
144 .byte_classes(false)
145 .premultiply(false)
146 .build(patterns.clone());
147 define(c, group_name, &name, corpus, move |b| {
148 b.iter(|| assert_eq!(count, counter(&aut, &haystack)))
149 });
150 }
151
152 /// A convenience wrapper for defining a benchmark tied to a particular corpus.
153 /// The corpus is used to provide throughput statistics. This also tweaks the
154 /// standard Criterion configuration so that benchmarks run a bit more quickly.
define( c: &mut Criterion, group_name: &str, bench_name: &str, corpus: &[u8], bench: impl FnMut(&mut Bencher<'_>) + 'static, )155 fn define(
156 c: &mut Criterion,
157 group_name: &str,
158 bench_name: &str,
159 corpus: &[u8],
160 bench: impl FnMut(&mut Bencher<'_>) + 'static,
161 ) {
162 c.benchmark_group(group_name)
163 .throughput(Throughput::Bytes(corpus.len() as u64))
164 .sample_size(10)
165 .warm_up_time(Duration::from_millis(500))
166 .measurement_time(Duration::from_secs(2))
167 .bench_function(bench_name, bench);
168 }
169
170 /// Like define, but specifically useful for defining benchmarks that measure a
171 /// slower routine (i.e., in the low milliseconds per iteration).
define_long( c: &mut Criterion, group_name: &str, bench_name: &str, corpus: &[u8], bench: impl FnMut(&mut Bencher<'_>) + 'static, )172 fn define_long(
173 c: &mut Criterion,
174 group_name: &str,
175 bench_name: &str,
176 corpus: &[u8],
177 bench: impl FnMut(&mut Bencher<'_>) + 'static,
178 ) {
179 c.benchmark_group(group_name)
180 .throughput(Throughput::Bytes(corpus.len() as u64))
181 .sample_size(20)
182 .warm_up_time(Duration::from_millis(500))
183 .measurement_time(Duration::from_secs(2))
184 .bench_function(bench_name, bench);
185 }
186
187 criterion_group!(g1, all);
188 criterion_main!(g1);
189