]>
Commit | Line | Data |
---|---|---|
f20569fa XL |
1 | #![feature(test)] |
2 | ||
3 | extern crate test; | |
4 | #[macro_use] extern crate itertools; | |
5 | ||
6 | use test::{black_box}; | |
7 | use itertools::Itertools; | |
8 | ||
9 | use itertools::free::cloned; | |
10 | use itertools::Permutations; | |
11 | ||
12 | use std::iter::repeat; | |
13 | use std::cmp; | |
14 | use std::ops::{Add, Range}; | |
15 | ||
16 | mod extra; | |
17 | ||
18 | use extra::ZipSlices; | |
19 | ||
20 | #[bench] | |
21 | fn slice_iter(b: &mut test::Bencher) | |
22 | { | |
23 | let xs: Vec<_> = repeat(1i32).take(20).collect(); | |
24 | b.iter(|| for elt in xs.iter() { | |
25 | test::black_box(elt); | |
26 | }) | |
27 | } | |
28 | ||
29 | #[bench] | |
30 | fn slice_iter_rev(b: &mut test::Bencher) | |
31 | { | |
32 | let xs: Vec<_> = repeat(1i32).take(20).collect(); | |
33 | b.iter(|| for elt in xs.iter().rev() { | |
34 | test::black_box(elt); | |
35 | }) | |
36 | } | |
37 | ||
38 | #[bench] | |
39 | fn zip_default_zip(b: &mut test::Bencher) | |
40 | { | |
41 | let xs = vec![0; 1024]; | |
42 | let ys = vec![0; 768]; | |
43 | let xs = black_box(xs); | |
44 | let ys = black_box(ys); | |
45 | ||
46 | b.iter(|| { | |
47 | for (&x, &y) in xs.iter().zip(&ys) { | |
48 | test::black_box(x); | |
49 | test::black_box(y); | |
50 | } | |
51 | }) | |
52 | } | |
53 | ||
54 | #[bench] | |
55 | fn zipdot_i32_default_zip(b: &mut test::Bencher) | |
56 | { | |
57 | let xs = vec![2; 1024]; | |
58 | let ys = vec![2; 768]; | |
59 | let xs = black_box(xs); | |
60 | let ys = black_box(ys); | |
61 | ||
62 | b.iter(|| { | |
63 | let mut s = 0; | |
64 | for (&x, &y) in xs.iter().zip(&ys) { | |
65 | s += x * y; | |
66 | } | |
67 | s | |
68 | }) | |
69 | } | |
70 | ||
71 | #[bench] | |
72 | fn zipdot_f32_default_zip(b: &mut test::Bencher) | |
73 | { | |
74 | let xs = vec![2f32; 1024]; | |
75 | let ys = vec![2f32; 768]; | |
76 | let xs = black_box(xs); | |
77 | let ys = black_box(ys); | |
78 | ||
79 | b.iter(|| { | |
80 | let mut s = 0.; | |
81 | for (&x, &y) in xs.iter().zip(&ys) { | |
82 | s += x * y; | |
83 | } | |
84 | s | |
85 | }) | |
86 | } | |
87 | ||
88 | #[bench] | |
89 | fn zip_default_zip3(b: &mut test::Bencher) | |
90 | { | |
91 | let xs = vec![0; 1024]; | |
92 | let ys = vec![0; 768]; | |
93 | let zs = vec![0; 766]; | |
94 | let xs = black_box(xs); | |
95 | let ys = black_box(ys); | |
96 | let zs = black_box(zs); | |
97 | ||
98 | b.iter(|| { | |
99 | for ((&x, &y), &z) in xs.iter().zip(&ys).zip(&zs) { | |
100 | test::black_box(x); | |
101 | test::black_box(y); | |
102 | test::black_box(z); | |
103 | } | |
104 | }) | |
105 | } | |
106 | ||
107 | #[bench] | |
108 | fn zip_slices_ziptuple(b: &mut test::Bencher) | |
109 | { | |
110 | let xs = vec![0; 1024]; | |
111 | let ys = vec![0; 768]; | |
112 | ||
113 | b.iter(|| { | |
114 | let xs = black_box(&xs); | |
115 | let ys = black_box(&ys); | |
116 | for (&x, &y) in itertools::multizip((xs, ys)) { | |
117 | test::black_box(x); | |
118 | test::black_box(y); | |
119 | } | |
120 | }) | |
121 | } | |
122 | ||
123 | #[bench] | |
124 | fn zipslices(b: &mut test::Bencher) | |
125 | { | |
126 | let xs = vec![0; 1024]; | |
127 | let ys = vec![0; 768]; | |
128 | let xs = black_box(xs); | |
129 | let ys = black_box(ys); | |
130 | ||
131 | b.iter(|| { | |
132 | for (&x, &y) in ZipSlices::new(&xs, &ys) { | |
133 | test::black_box(x); | |
134 | test::black_box(y); | |
135 | } | |
136 | }) | |
137 | } | |
138 | ||
139 | #[bench] | |
140 | fn zipslices_mut(b: &mut test::Bencher) | |
141 | { | |
142 | let xs = vec![0; 1024]; | |
143 | let ys = vec![0; 768]; | |
144 | let xs = black_box(xs); | |
145 | let mut ys = black_box(ys); | |
146 | ||
147 | b.iter(|| { | |
148 | for (&x, &mut y) in ZipSlices::from_slices(&xs[..], &mut ys[..]) { | |
149 | test::black_box(x); | |
150 | test::black_box(y); | |
151 | } | |
152 | }) | |
153 | } | |
154 | ||
155 | #[bench] | |
156 | fn zipdot_i32_zipslices(b: &mut test::Bencher) | |
157 | { | |
158 | let xs = vec![2; 1024]; | |
159 | let ys = vec![2; 768]; | |
160 | let xs = black_box(xs); | |
161 | let ys = black_box(ys); | |
162 | ||
163 | b.iter(|| { | |
164 | let mut s = 0i32; | |
165 | for (&x, &y) in ZipSlices::new(&xs, &ys) { | |
166 | s += x * y; | |
167 | } | |
168 | s | |
169 | }) | |
170 | } | |
171 | ||
172 | #[bench] | |
173 | fn zipdot_f32_zipslices(b: &mut test::Bencher) | |
174 | { | |
175 | let xs = vec![2f32; 1024]; | |
176 | let ys = vec![2f32; 768]; | |
177 | let xs = black_box(xs); | |
178 | let ys = black_box(ys); | |
179 | ||
180 | b.iter(|| { | |
181 | let mut s = 0.; | |
182 | for (&x, &y) in ZipSlices::new(&xs, &ys) { | |
183 | s += x * y; | |
184 | } | |
185 | s | |
186 | }) | |
187 | } | |
188 | ||
189 | ||
190 | #[bench] | |
191 | fn zip_checked_counted_loop(b: &mut test::Bencher) | |
192 | { | |
193 | let xs = vec![0; 1024]; | |
194 | let ys = vec![0; 768]; | |
195 | let xs = black_box(xs); | |
196 | let ys = black_box(ys); | |
197 | ||
198 | b.iter(|| { | |
199 | // Must slice to equal lengths, and then bounds checks are eliminated! | |
200 | let len = cmp::min(xs.len(), ys.len()); | |
201 | let xs = &xs[..len]; | |
202 | let ys = &ys[..len]; | |
203 | ||
204 | for i in 0..len { | |
205 | let x = xs[i]; | |
206 | let y = ys[i]; | |
207 | test::black_box(x); | |
208 | test::black_box(y); | |
209 | } | |
210 | }) | |
211 | } | |
212 | ||
213 | #[bench] | |
214 | fn zipdot_i32_checked_counted_loop(b: &mut test::Bencher) | |
215 | { | |
216 | let xs = vec![2; 1024]; | |
217 | let ys = vec![2; 768]; | |
218 | let xs = black_box(xs); | |
219 | let ys = black_box(ys); | |
220 | ||
221 | b.iter(|| { | |
222 | // Must slice to equal lengths, and then bounds checks are eliminated! | |
223 | let len = cmp::min(xs.len(), ys.len()); | |
224 | let xs = &xs[..len]; | |
225 | let ys = &ys[..len]; | |
226 | ||
227 | let mut s = 0i32; | |
228 | ||
229 | for i in 0..len { | |
230 | s += xs[i] * ys[i]; | |
231 | } | |
232 | s | |
233 | }) | |
234 | } | |
235 | ||
236 | #[bench] | |
237 | fn zipdot_f32_checked_counted_loop(b: &mut test::Bencher) | |
238 | { | |
239 | let xs = vec![2f32; 1024]; | |
240 | let ys = vec![2f32; 768]; | |
241 | let xs = black_box(xs); | |
242 | let ys = black_box(ys); | |
243 | ||
244 | b.iter(|| { | |
245 | // Must slice to equal lengths, and then bounds checks are eliminated! | |
246 | let len = cmp::min(xs.len(), ys.len()); | |
247 | let xs = &xs[..len]; | |
248 | let ys = &ys[..len]; | |
249 | ||
250 | let mut s = 0.; | |
251 | ||
252 | for i in 0..len { | |
253 | s += xs[i] * ys[i]; | |
254 | } | |
255 | s | |
256 | }) | |
257 | } | |
258 | ||
259 | #[bench] | |
260 | fn zipdot_f32_checked_counted_unrolled_loop(b: &mut test::Bencher) | |
261 | { | |
262 | let xs = vec![2f32; 1024]; | |
263 | let ys = vec![2f32; 768]; | |
264 | let xs = black_box(xs); | |
265 | let ys = black_box(ys); | |
266 | ||
267 | b.iter(|| { | |
268 | // Must slice to equal lengths, and then bounds checks are eliminated! | |
269 | let len = cmp::min(xs.len(), ys.len()); | |
270 | let mut xs = &xs[..len]; | |
271 | let mut ys = &ys[..len]; | |
272 | ||
273 | let mut s = 0.; | |
274 | let (mut p0, mut p1, mut p2, mut p3, mut p4, mut p5, mut p6, mut p7) = | |
275 | (0., 0., 0., 0., 0., 0., 0., 0.); | |
276 | ||
277 | // how to unroll and have bounds checks eliminated (by cristicbz) | |
278 | // split sum into eight parts to enable vectorization (by bluss) | |
279 | while xs.len() >= 8 { | |
280 | p0 += xs[0] * ys[0]; | |
281 | p1 += xs[1] * ys[1]; | |
282 | p2 += xs[2] * ys[2]; | |
283 | p3 += xs[3] * ys[3]; | |
284 | p4 += xs[4] * ys[4]; | |
285 | p5 += xs[5] * ys[5]; | |
286 | p6 += xs[6] * ys[6]; | |
287 | p7 += xs[7] * ys[7]; | |
288 | ||
289 | xs = &xs[8..]; | |
290 | ys = &ys[8..]; | |
291 | } | |
292 | s += p0 + p4; | |
293 | s += p1 + p5; | |
294 | s += p2 + p6; | |
295 | s += p3 + p7; | |
296 | ||
297 | for i in 0..xs.len() { | |
298 | s += xs[i] * ys[i]; | |
299 | } | |
300 | s | |
301 | }) | |
302 | } | |
303 | ||
304 | #[bench] | |
305 | fn zip_unchecked_counted_loop(b: &mut test::Bencher) | |
306 | { | |
307 | let xs = vec![0; 1024]; | |
308 | let ys = vec![0; 768]; | |
309 | let xs = black_box(xs); | |
310 | let ys = black_box(ys); | |
311 | ||
312 | b.iter(|| { | |
313 | let len = cmp::min(xs.len(), ys.len()); | |
314 | for i in 0..len { | |
315 | unsafe { | |
316 | let x = *xs.get_unchecked(i); | |
317 | let y = *ys.get_unchecked(i); | |
318 | test::black_box(x); | |
319 | test::black_box(y); | |
320 | } | |
321 | } | |
322 | }) | |
323 | } | |
324 | ||
325 | #[bench] | |
326 | fn zipdot_i32_unchecked_counted_loop(b: &mut test::Bencher) | |
327 | { | |
328 | let xs = vec![2; 1024]; | |
329 | let ys = vec![2; 768]; | |
330 | let xs = black_box(xs); | |
331 | let ys = black_box(ys); | |
332 | ||
333 | b.iter(|| { | |
334 | let len = cmp::min(xs.len(), ys.len()); | |
335 | let mut s = 0i32; | |
336 | for i in 0..len { | |
337 | unsafe { | |
338 | let x = *xs.get_unchecked(i); | |
339 | let y = *ys.get_unchecked(i); | |
340 | s += x * y; | |
341 | } | |
342 | } | |
343 | s | |
344 | }) | |
345 | } | |
346 | ||
347 | #[bench] | |
348 | fn zipdot_f32_unchecked_counted_loop(b: &mut test::Bencher) | |
349 | { | |
350 | let xs = vec![2.; 1024]; | |
351 | let ys = vec![2.; 768]; | |
352 | let xs = black_box(xs); | |
353 | let ys = black_box(ys); | |
354 | ||
355 | b.iter(|| { | |
356 | let len = cmp::min(xs.len(), ys.len()); | |
357 | let mut s = 0f32; | |
358 | for i in 0..len { | |
359 | unsafe { | |
360 | let x = *xs.get_unchecked(i); | |
361 | let y = *ys.get_unchecked(i); | |
362 | s += x * y; | |
363 | } | |
364 | } | |
365 | s | |
366 | }) | |
367 | } | |
368 | ||
369 | #[bench] | |
370 | fn zip_unchecked_counted_loop3(b: &mut test::Bencher) | |
371 | { | |
372 | let xs = vec![0; 1024]; | |
373 | let ys = vec![0; 768]; | |
374 | let zs = vec![0; 766]; | |
375 | let xs = black_box(xs); | |
376 | let ys = black_box(ys); | |
377 | let zs = black_box(zs); | |
378 | ||
379 | b.iter(|| { | |
380 | let len = cmp::min(xs.len(), cmp::min(ys.len(), zs.len())); | |
381 | for i in 0..len { | |
382 | unsafe { | |
383 | let x = *xs.get_unchecked(i); | |
384 | let y = *ys.get_unchecked(i); | |
385 | let z = *zs.get_unchecked(i); | |
386 | test::black_box(x); | |
387 | test::black_box(y); | |
388 | test::black_box(z); | |
389 | } | |
390 | } | |
391 | }) | |
392 | } | |
393 | ||
394 | #[bench] | |
395 | fn group_by_lazy_1(b: &mut test::Bencher) { | |
396 | let mut data = vec![0; 1024]; | |
397 | for (index, elt) in data.iter_mut().enumerate() { | |
398 | *elt = index / 10; | |
399 | } | |
400 | ||
401 | let data = test::black_box(data); | |
402 | ||
403 | b.iter(|| { | |
404 | for (_key, group) in &data.iter().group_by(|elt| **elt) { | |
405 | for elt in group { | |
406 | test::black_box(elt); | |
407 | } | |
408 | } | |
409 | }) | |
410 | } | |
411 | ||
412 | #[bench] | |
413 | fn group_by_lazy_2(b: &mut test::Bencher) { | |
414 | let mut data = vec![0; 1024]; | |
415 | for (index, elt) in data.iter_mut().enumerate() { | |
416 | *elt = index / 2; | |
417 | } | |
418 | ||
419 | let data = test::black_box(data); | |
420 | ||
421 | b.iter(|| { | |
422 | for (_key, group) in &data.iter().group_by(|elt| **elt) { | |
423 | for elt in group { | |
424 | test::black_box(elt); | |
425 | } | |
426 | } | |
427 | }) | |
428 | } | |
429 | ||
430 | #[bench] | |
431 | fn slice_chunks(b: &mut test::Bencher) { | |
432 | let data = vec![0; 1024]; | |
433 | ||
434 | let data = test::black_box(data); | |
435 | let sz = test::black_box(10); | |
436 | ||
437 | b.iter(|| { | |
438 | for group in data.chunks(sz) { | |
439 | for elt in group { | |
440 | test::black_box(elt); | |
441 | } | |
442 | } | |
443 | }) | |
444 | } | |
445 | ||
446 | #[bench] | |
447 | fn chunks_lazy_1(b: &mut test::Bencher) { | |
448 | let data = vec![0; 1024]; | |
449 | ||
450 | let data = test::black_box(data); | |
451 | let sz = test::black_box(10); | |
452 | ||
453 | b.iter(|| { | |
454 | for group in &data.iter().chunks(sz) { | |
455 | for elt in group { | |
456 | test::black_box(elt); | |
457 | } | |
458 | } | |
459 | }) | |
460 | } | |
461 | ||
462 | #[bench] | |
463 | fn equal(b: &mut test::Bencher) { | |
464 | let data = vec![7; 1024]; | |
465 | let l = data.len(); | |
466 | let alpha = test::black_box(&data[1..]); | |
467 | let beta = test::black_box(&data[..l - 1]); | |
468 | b.iter(|| { | |
469 | itertools::equal(alpha, beta) | |
470 | }) | |
471 | } | |
472 | ||
473 | #[bench] | |
474 | fn merge_default(b: &mut test::Bencher) { | |
475 | let mut data1 = vec![0; 1024]; | |
476 | let mut data2 = vec![0; 800]; | |
477 | let mut x = 0; | |
478 | for (_, elt) in data1.iter_mut().enumerate() { | |
479 | *elt = x; | |
480 | x += 1; | |
481 | } | |
482 | ||
483 | let mut y = 0; | |
484 | for (i, elt) in data2.iter_mut().enumerate() { | |
485 | *elt += y; | |
486 | if i % 3 == 0 { | |
487 | y += 3; | |
488 | } else { | |
489 | y += 0; | |
490 | } | |
491 | } | |
492 | let data1 = test::black_box(data1); | |
493 | let data2 = test::black_box(data2); | |
494 | b.iter(|| { | |
495 | data1.iter().merge(&data2).count() | |
496 | }) | |
497 | } | |
498 | ||
499 | #[bench] | |
500 | fn merge_by_cmp(b: &mut test::Bencher) { | |
501 | let mut data1 = vec![0; 1024]; | |
502 | let mut data2 = vec![0; 800]; | |
503 | let mut x = 0; | |
504 | for (_, elt) in data1.iter_mut().enumerate() { | |
505 | *elt = x; | |
506 | x += 1; | |
507 | } | |
508 | ||
509 | let mut y = 0; | |
510 | for (i, elt) in data2.iter_mut().enumerate() { | |
511 | *elt += y; | |
512 | if i % 3 == 0 { | |
513 | y += 3; | |
514 | } else { | |
515 | y += 0; | |
516 | } | |
517 | } | |
518 | let data1 = test::black_box(data1); | |
519 | let data2 = test::black_box(data2); | |
520 | b.iter(|| { | |
521 | data1.iter().merge_by(&data2, PartialOrd::le).count() | |
522 | }) | |
523 | } | |
524 | ||
525 | #[bench] | |
526 | fn merge_by_lt(b: &mut test::Bencher) { | |
527 | let mut data1 = vec![0; 1024]; | |
528 | let mut data2 = vec![0; 800]; | |
529 | let mut x = 0; | |
530 | for (_, elt) in data1.iter_mut().enumerate() { | |
531 | *elt = x; | |
532 | x += 1; | |
533 | } | |
534 | ||
535 | let mut y = 0; | |
536 | for (i, elt) in data2.iter_mut().enumerate() { | |
537 | *elt += y; | |
538 | if i % 3 == 0 { | |
539 | y += 3; | |
540 | } else { | |
541 | y += 0; | |
542 | } | |
543 | } | |
544 | let data1 = test::black_box(data1); | |
545 | let data2 = test::black_box(data2); | |
546 | b.iter(|| { | |
547 | data1.iter().merge_by(&data2, |a, b| a <= b).count() | |
548 | }) | |
549 | } | |
550 | ||
551 | #[bench] | |
552 | fn kmerge_default(b: &mut test::Bencher) { | |
553 | let mut data1 = vec![0; 1024]; | |
554 | let mut data2 = vec![0; 800]; | |
555 | let mut x = 0; | |
556 | for (_, elt) in data1.iter_mut().enumerate() { | |
557 | *elt = x; | |
558 | x += 1; | |
559 | } | |
560 | ||
561 | let mut y = 0; | |
562 | for (i, elt) in data2.iter_mut().enumerate() { | |
563 | *elt += y; | |
564 | if i % 3 == 0 { | |
565 | y += 3; | |
566 | } else { | |
567 | y += 0; | |
568 | } | |
569 | } | |
570 | let data1 = test::black_box(data1); | |
571 | let data2 = test::black_box(data2); | |
572 | let its = &[data1.iter(), data2.iter()]; | |
573 | b.iter(|| { | |
574 | its.iter().cloned().kmerge().count() | |
575 | }) | |
576 | } | |
577 | ||
578 | #[bench] | |
579 | fn kmerge_tenway(b: &mut test::Bencher) { | |
580 | let mut data = vec![0; 10240]; | |
581 | ||
582 | let mut state = 1729u16; | |
583 | fn rng(state: &mut u16) -> u16 { | |
584 | let new = state.wrapping_mul(31421) + 6927; | |
585 | *state = new; | |
586 | new | |
587 | } | |
588 | ||
589 | for elt in &mut data { | |
590 | *elt = rng(&mut state); | |
591 | } | |
592 | ||
593 | let mut chunks = Vec::new(); | |
594 | let mut rest = &mut data[..]; | |
595 | while rest.len() > 0 { | |
596 | let chunk_len = 1 + rng(&mut state) % 512; | |
597 | let chunk_len = cmp::min(rest.len(), chunk_len as usize); | |
598 | let (fst, tail) = {rest}.split_at_mut(chunk_len); | |
599 | fst.sort(); | |
600 | chunks.push(fst.iter().cloned()); | |
601 | rest = tail; | |
602 | } | |
603 | ||
604 | // println!("Chunk lengths: {}", chunks.iter().format_with(", ", |elt, f| f(&elt.len()))); | |
605 | ||
606 | b.iter(|| { | |
607 | chunks.iter().cloned().kmerge().count() | |
608 | }) | |
609 | } | |
610 | ||
611 | ||
612 | fn fast_integer_sum<I>(iter: I) -> I::Item | |
613 | where I: IntoIterator, | |
614 | I::Item: Default + Add<Output=I::Item> | |
615 | { | |
616 | iter.into_iter().fold(<_>::default(), |x, y| x + y) | |
617 | } | |
618 | ||
619 | ||
620 | #[bench] | |
621 | fn step_vec_2(b: &mut test::Bencher) { | |
622 | let v = vec![0; 1024]; | |
623 | b.iter(|| { | |
624 | fast_integer_sum(cloned(v.iter().step(2))) | |
625 | }); | |
626 | } | |
627 | ||
628 | #[bench] | |
629 | fn step_vec_10(b: &mut test::Bencher) { | |
630 | let v = vec![0; 1024]; | |
631 | b.iter(|| { | |
632 | fast_integer_sum(cloned(v.iter().step(10))) | |
633 | }); | |
634 | } | |
635 | ||
636 | #[bench] | |
637 | fn step_range_2(b: &mut test::Bencher) { | |
638 | let v = black_box(0..1024); | |
639 | b.iter(|| { | |
640 | fast_integer_sum(v.clone().step(2)) | |
641 | }); | |
642 | } | |
643 | ||
644 | #[bench] | |
645 | fn step_range_10(b: &mut test::Bencher) { | |
646 | let v = black_box(0..1024); | |
647 | b.iter(|| { | |
648 | fast_integer_sum(v.clone().step(10)) | |
649 | }); | |
650 | } | |
651 | ||
652 | #[bench] | |
653 | fn cartesian_product_iterator(b: &mut test::Bencher) | |
654 | { | |
655 | let xs = vec![0; 16]; | |
656 | ||
657 | b.iter(|| { | |
658 | let mut sum = 0; | |
659 | for (&x, &y, &z) in iproduct!(&xs, &xs, &xs) { | |
660 | sum += x; | |
661 | sum += y; | |
662 | sum += z; | |
663 | } | |
664 | sum | |
665 | }) | |
666 | } | |
667 | ||
668 | #[bench] | |
669 | fn cartesian_product_fold(b: &mut test::Bencher) | |
670 | { | |
671 | let xs = vec![0; 16]; | |
672 | ||
673 | b.iter(|| { | |
674 | let mut sum = 0; | |
675 | iproduct!(&xs, &xs, &xs).fold((), |(), (&x, &y, &z)| { | |
676 | sum += x; | |
677 | sum += y; | |
678 | sum += z; | |
679 | }); | |
680 | sum | |
681 | }) | |
682 | } | |
683 | ||
684 | #[bench] | |
685 | fn multi_cartesian_product_iterator(b: &mut test::Bencher) | |
686 | { | |
687 | let xs = [vec![0; 16], vec![0; 16], vec![0; 16]]; | |
688 | ||
689 | b.iter(|| { | |
690 | let mut sum = 0; | |
691 | for x in xs.iter().multi_cartesian_product() { | |
692 | sum += x[0]; | |
693 | sum += x[1]; | |
694 | sum += x[2]; | |
695 | } | |
696 | sum | |
697 | }) | |
698 | } | |
699 | ||
700 | #[bench] | |
701 | fn multi_cartesian_product_fold(b: &mut test::Bencher) | |
702 | { | |
703 | let xs = [vec![0; 16], vec![0; 16], vec![0; 16]]; | |
704 | ||
705 | b.iter(|| { | |
706 | let mut sum = 0; | |
707 | xs.iter().multi_cartesian_product().fold((), |(), x| { | |
708 | sum += x[0]; | |
709 | sum += x[1]; | |
710 | sum += x[2]; | |
711 | }); | |
712 | sum | |
713 | }) | |
714 | } | |
715 | ||
716 | #[bench] | |
717 | fn cartesian_product_nested_for(b: &mut test::Bencher) | |
718 | { | |
719 | let xs = vec![0; 16]; | |
720 | ||
721 | b.iter(|| { | |
722 | let mut sum = 0; | |
723 | for &x in &xs { | |
724 | for &y in &xs { | |
725 | for &z in &xs { | |
726 | sum += x; | |
727 | sum += y; | |
728 | sum += z; | |
729 | } | |
730 | } | |
731 | } | |
732 | sum | |
733 | }) | |
734 | } | |
735 | ||
736 | #[bench] | |
737 | fn all_equal(b: &mut test::Bencher) { | |
738 | let mut xs = vec![0; 5_000_000]; | |
739 | xs.extend(vec![1; 5_000_000]); | |
740 | ||
741 | b.iter(|| xs.iter().all_equal()) | |
742 | } | |
743 | ||
744 | #[bench] | |
745 | fn all_equal_for(b: &mut test::Bencher) { | |
746 | let mut xs = vec![0; 5_000_000]; | |
747 | xs.extend(vec![1; 5_000_000]); | |
748 | ||
749 | b.iter(|| { | |
750 | for &x in &xs { | |
751 | if x != xs[0] { | |
752 | return false; | |
753 | } | |
754 | } | |
755 | true | |
756 | }) | |
757 | } | |
758 | ||
759 | #[bench] | |
760 | fn all_equal_default(b: &mut test::Bencher) { | |
761 | let mut xs = vec![0; 5_000_000]; | |
762 | xs.extend(vec![1; 5_000_000]); | |
763 | ||
764 | b.iter(|| xs.iter().dedup().nth(1).is_none()) | |
765 | } | |
766 | ||
767 | const PERM_COUNT: usize = 6; | |
768 | ||
769 | #[bench] | |
770 | fn permutations_iter(b: &mut test::Bencher) { | |
771 | struct NewIterator(Range<usize>); | |
772 | ||
773 | impl Iterator for NewIterator { | |
774 | type Item = usize; | |
775 | ||
776 | fn next(&mut self) -> Option<Self::Item> { | |
777 | self.0.next() | |
778 | } | |
779 | } | |
780 | ||
781 | b.iter(|| { | |
782 | for _ in NewIterator(0..PERM_COUNT).permutations(PERM_COUNT) { | |
783 | ||
784 | } | |
785 | }) | |
786 | } | |
787 | ||
788 | #[bench] | |
789 | fn permutations_range(b: &mut test::Bencher) { | |
790 | b.iter(|| { | |
791 | for _ in (0..PERM_COUNT).permutations(PERM_COUNT) { | |
792 | ||
793 | } | |
794 | }) | |
795 | } | |
796 | ||
797 | #[bench] | |
798 | fn permutations_slice(b: &mut test::Bencher) { | |
799 | let v = (0..PERM_COUNT).collect_vec(); | |
800 | ||
801 | b.iter(|| { | |
802 | for _ in v.as_slice().iter().permutations(PERM_COUNT) { | |
803 | ||
804 | } | |
805 | }) | |
806 | } |