1 /*
2 These benchmarks were lifted almost verbtaim out of the sliceslice crate. The
3 reason why we have these benchmarks is because they were the primary thing that
4 motivated me to write this particular memmem implementation. In particular, my
5 existing substring search implementation in the bstr crate did quite poorly
6 on these particular benchmarks. Moreover, while the benchmark setup is a little
7 weird, these benchmarks do reflect cases that I think are somewhat common:
8
9 N.B. In the sliceslice crate, the benchmarks are called "short" and "long."
10 Here, we call them sliceslice-words/words and sliceslice-i386/words,
11 respectively. The name change was made to be consistent with the naming
12 convention used for other benchmarks.
13
14 * In the sliceslice-words/words case, the benchmark is primarily about
15 searching very short haystacks using common English words.
16 * In the sliceslice-words/i386 case, the benchmark is primarily about searching
17 a longer haystack with common English words.
18
19 The main thing that's "weird" about these benchmarks is that each iteration
20 involves a lot of work. All of the other benchmarks in this crate focus on one
21 specific needle with one specific haystack, and each iteration is a single
22 search or iteration. But in these benchmarks, each iteration involves searching
23 with many needles against potentially many haystacks. Nevertheless, these have
24 proven useful targets for optimization.
25 */
26 use criterion::{black_box, Criterion};
27 use memchr::memmem;
28
29 use crate::{data::*, define};
30
all(c: &mut Criterion)31 pub fn all(c: &mut Criterion) {
32 search_short_haystack(c);
33 search_long_haystack(c);
34 search_i386_haystack(c);
35 }
36
search_short_haystack(c: &mut Criterion)37 fn search_short_haystack(c: &mut Criterion) {
38 let mut words = SLICESLICE_WORDS.lines().collect::<Vec<_>>();
39 words.sort_unstable_by_key(|word| word.len());
40 let words: Vec<&str> = words.iter().map(|&s| s).collect();
41
42 let needles = words.clone();
43 define(
44 c,
45 "memmem/krate/prebuilt/sliceslice-words/words",
46 &[],
47 Box::new(move |b| {
48 let searchers = needles
49 .iter()
50 .map(|needle| memmem::Finder::new(needle.as_bytes()))
51 .collect::<Vec<_>>();
52 b.iter(|| {
53 for (i, searcher) in searchers.iter().enumerate() {
54 for haystack in &needles[i..] {
55 black_box(
56 searcher.find(haystack.as_bytes()).is_some(),
57 );
58 }
59 }
60 });
61 }),
62 );
63
64 let needles = words.clone();
65 define(
66 c,
67 "memmem/krate_nopre/prebuilt/sliceslice-words/words",
68 &[],
69 Box::new(move |b| {
70 let searchers = needles
71 .iter()
72 .map(|needle| {
73 memmem::FinderBuilder::new()
74 .prefilter(memmem::Prefilter::None)
75 .build_forward(needle)
76 })
77 .collect::<Vec<_>>();
78 b.iter(|| {
79 for (i, searcher) in searchers.iter().enumerate() {
80 for haystack in &needles[i..] {
81 black_box(
82 searcher.find(haystack.as_bytes()).is_some(),
83 );
84 }
85 }
86 });
87 }),
88 );
89
90 let needles = words.clone();
91 define(
92 c,
93 "memmem/stud/prebuilt/sliceslice-words/words",
94 &[],
95 Box::new(move |b| {
96 b.iter(|| {
97 for (i, needle) in needles.iter().enumerate() {
98 for haystack in &needles[i..] {
99 black_box(haystack.contains(needle));
100 }
101 }
102 });
103 }),
104 );
105
106 #[cfg(target_arch = "x86_64")]
107 {
108 use sliceslice::x86::DynamicAvx2Searcher;
109
110 let needles = words.clone();
111 define(
112 c,
113 "memmem/sliceslice/prebuilt/sliceslice-words/words",
114 &[],
115 Box::new(move |b| {
116 let searchers = needles
117 .iter()
118 .map(|&needle| unsafe {
119 DynamicAvx2Searcher::new(needle.as_bytes())
120 })
121 .collect::<Vec<_>>();
122
123 b.iter(|| {
124 for (i, searcher) in searchers.iter().enumerate() {
125 for haystack in &needles[i..] {
126 black_box(unsafe {
127 searcher.search_in(haystack.as_bytes())
128 });
129 }
130 }
131 });
132 }),
133 );
134 }
135 }
136
search_long_haystack(c: &mut Criterion)137 fn search_long_haystack(c: &mut Criterion) {
138 let words: Vec<&str> = SLICESLICE_WORDS.lines().collect();
139 let haystack = SLICESLICE_HAYSTACK;
140 let needles = words.clone();
141 define(
142 c,
143 "memmem/krate/prebuilt/sliceslice-haystack/words",
144 &[],
145 Box::new(move |b| {
146 let searchers = needles
147 .iter()
148 .map(|needle| memmem::Finder::new(needle.as_bytes()))
149 .collect::<Vec<_>>();
150 b.iter(|| {
151 for searcher in searchers.iter() {
152 black_box(searcher.find(haystack.as_bytes()).is_some());
153 }
154 });
155 }),
156 );
157
158 let needles = words.clone();
159 define(
160 c,
161 "memmem/krate_nopre/prebuilt/sliceslice-haystack/words",
162 &[],
163 Box::new(move |b| {
164 let searchers = needles
165 .iter()
166 .map(|needle| {
167 memmem::FinderBuilder::new()
168 .prefilter(memmem::Prefilter::None)
169 .build_forward(needle)
170 })
171 .collect::<Vec<_>>();
172 b.iter(|| {
173 for searcher in searchers.iter() {
174 black_box(searcher.find(haystack.as_bytes()).is_some());
175 }
176 });
177 }),
178 );
179
180 let needles = words.clone();
181 define(
182 c,
183 "memmem/stud/prebuilt/sliceslice-haystack/words",
184 &[],
185 Box::new(move |b| {
186 b.iter(|| {
187 for needle in needles.iter() {
188 black_box(haystack.contains(needle));
189 }
190 });
191 }),
192 );
193
194 #[cfg(target_arch = "x86_64")]
195 {
196 use sliceslice::x86::DynamicAvx2Searcher;
197
198 let needles = words.clone();
199 define(
200 c,
201 "memmem/sliceslice/prebuilt/sliceslice-haystack/words",
202 &[],
203 Box::new(move |b| {
204 let searchers = needles
205 .iter()
206 .map(|needle| unsafe {
207 DynamicAvx2Searcher::new(needle.as_bytes())
208 })
209 .collect::<Vec<_>>();
210
211 b.iter(|| {
212 for searcher in &searchers {
213 black_box(unsafe {
214 searcher.search_in(haystack.as_bytes())
215 });
216 }
217 });
218 }),
219 );
220 }
221 }
222
search_i386_haystack(c: &mut Criterion)223 fn search_i386_haystack(c: &mut Criterion) {
224 let words: Vec<&str> = SLICESLICE_WORDS.lines().collect();
225 let haystack = SLICESLICE_I386;
226 let needles = words.clone();
227 define(
228 c,
229 "memmem/krate/prebuilt/sliceslice-i386/words",
230 &[],
231 Box::new(move |b| {
232 let searchers = needles
233 .iter()
234 .map(|needle| memmem::Finder::new(needle.as_bytes()))
235 .collect::<Vec<_>>();
236 b.iter(|| {
237 for searcher in searchers.iter() {
238 black_box(searcher.find(haystack.as_bytes()).is_some());
239 }
240 });
241 }),
242 );
243
244 let needles = words.clone();
245 define(
246 c,
247 "memmem/krate_nopre/prebuilt/sliceslice-i386/words",
248 &[],
249 Box::new(move |b| {
250 let searchers = needles
251 .iter()
252 .map(|needle| {
253 memmem::FinderBuilder::new()
254 .prefilter(memmem::Prefilter::None)
255 .build_forward(needle)
256 })
257 .collect::<Vec<_>>();
258 b.iter(|| {
259 for searcher in searchers.iter() {
260 black_box(searcher.find(haystack.as_bytes()).is_some());
261 }
262 });
263 }),
264 );
265
266 let needles = words.clone();
267 define(
268 c,
269 "memmem/stud/prebuilt/sliceslice-i386/words",
270 &[],
271 Box::new(move |b| {
272 b.iter(|| {
273 for needle in needles.iter() {
274 black_box(haystack.contains(needle));
275 }
276 });
277 }),
278 );
279
280 #[cfg(target_arch = "x86_64")]
281 {
282 use sliceslice::x86::DynamicAvx2Searcher;
283
284 let needles = words.clone();
285 define(
286 c,
287 "memmem/sliceslice/prebuilt/sliceslice-i386/words",
288 &[],
289 Box::new(move |b| {
290 let searchers = needles
291 .iter()
292 .map(|needle| unsafe {
293 DynamicAvx2Searcher::new(needle.as_bytes())
294 })
295 .collect::<Vec<_>>();
296
297 b.iter(|| {
298 for searcher in &searchers {
299 black_box(unsafe {
300 searcher.search_in(haystack.as_bytes())
301 });
302 }
303 });
304 }),
305 );
306 }
307 }
308