1/*
2These benchmarks were lifted almost verbtaim out of the sliceslice crate. The
3reason why we have these benchmarks is because they were the primary thing that
4motivated me to write this particular memmem implementation. In particular, my
5existing substring search implementation in the bstr crate did quite poorly
6on these particular benchmarks. Moreover, while the benchmark setup is a little
7weird, these benchmarks do reflect cases that I think are somewhat common:
8
9N.B. In the sliceslice crate, the benchmarks are called "short" and "long."
10Here, we call them sliceslice-words/words and sliceslice-i386/words,
11respectively. The name change was made to be consistent with the naming
12convention 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
19The main thing that's "weird" about these benchmarks is that each iteration
20involves a lot of work. All of the other benchmarks in this crate focus on one
21specific needle with one specific haystack, and each iteration is a single
22search or iteration. But in these benchmarks, each iteration involves searching
23with many needles against potentially many haystacks. Nevertheless, these have
24proven useful targets for optimization.
25*/
26use criterion::{black_box, Criterion};
27use memchr::memmem;
28
29use crate::{data::*, define};
30
31pub fn all(c: &mut Criterion) {
32    search_short_haystack(c);
33    search_long_haystack(c);
34    search_i386_haystack(c);
35}
36
37fn 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
137fn 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
223fn 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