1 use criterion
::{black_box, criterion_group, criterion_main, Criterion}
;
2 use itertools
::Itertools
;
3 use itertools
::free
::cloned
;
4 use itertools
::iproduct
;
8 use std
::ops
::{Add, Range}
;
12 use crate::extra
::ZipSlices
;
14 fn slice_iter(c
: &mut Criterion
) {
15 let xs
: Vec
<_
> = repeat(1i32).take(20).collect();
17 c
.bench_function("slice iter", move |b
| {
18 b
.iter(|| for elt
in xs
.iter() {
24 fn slice_iter_rev(c
: &mut Criterion
) {
25 let xs
: Vec
<_
> = repeat(1i32).take(20).collect();
27 c
.bench_function("slice iter rev", move |b
| {
28 b
.iter(|| for elt
in xs
.iter().rev() {
34 fn zip_default_zip(c
: &mut Criterion
) {
35 let xs
= vec
![0; 1024];
36 let ys
= vec
![0; 768];
37 let xs
= black_box(xs
);
38 let ys
= black_box(ys
);
40 c
.bench_function("zip default zip", move |b
| {
42 for (&x
, &y
) in xs
.iter().zip(&ys
) {
50 fn zipdot_i32_default_zip(c
: &mut Criterion
) {
51 let xs
= vec
![2; 1024];
52 let ys
= vec
![2; 768];
53 let xs
= black_box(xs
);
54 let ys
= black_box(ys
);
56 c
.bench_function("zipdot i32 default zip", move |b
| {
59 for (&x
, &y
) in xs
.iter().zip(&ys
) {
67 fn zipdot_f32_default_zip(c
: &mut Criterion
) {
68 let xs
= vec
![2f32; 1024];
69 let ys
= vec
![2f32; 768];
70 let xs
= black_box(xs
);
71 let ys
= black_box(ys
);
73 c
.bench_function("zipdot f32 default zip", move |b
| {
76 for (&x
, &y
) in xs
.iter().zip(&ys
) {
84 fn zip_default_zip3(c
: &mut Criterion
) {
85 let xs
= vec
![0; 1024];
86 let ys
= vec
![0; 768];
87 let zs
= vec
![0; 766];
88 let xs
= black_box(xs
);
89 let ys
= black_box(ys
);
90 let zs
= black_box(zs
);
92 c
.bench_function("zip default zip3", move |b
| {
94 for ((&x
, &y
), &z
) in xs
.iter().zip(&ys
).zip(&zs
) {
103 fn zip_slices_ziptuple(c
: &mut Criterion
) {
104 let xs
= vec
![0; 1024];
105 let ys
= vec
![0; 768];
107 c
.bench_function("zip slices ziptuple", move |b
| {
109 let xs
= black_box(&xs
);
110 let ys
= black_box(&ys
);
111 for (&x
, &y
) in itertools
::multizip((xs
, ys
)) {
119 fn zipslices(c
: &mut Criterion
) {
120 let xs
= vec
![0; 1024];
121 let ys
= vec
![0; 768];
122 let xs
= black_box(xs
);
123 let ys
= black_box(ys
);
125 c
.bench_function("zipslices", move |b
| {
127 for (&x
, &y
) in ZipSlices
::new(&xs
, &ys
) {
135 fn zipslices_mut(c
: &mut Criterion
) {
136 let xs
= vec
![0; 1024];
137 let ys
= vec
![0; 768];
138 let xs
= black_box(xs
);
139 let mut ys
= black_box(ys
);
141 c
.bench_function("zipslices mut", move |b
| {
143 for (&x
, &mut y
) in ZipSlices
::from_slices(&xs
[..], &mut ys
[..]) {
151 fn zipdot_i32_zipslices(c
: &mut Criterion
) {
152 let xs
= vec
![2; 1024];
153 let ys
= vec
![2; 768];
154 let xs
= black_box(xs
);
155 let ys
= black_box(ys
);
157 c
.bench_function("zipdot i32 zipslices", move |b
| {
160 for (&x
, &y
) in ZipSlices
::new(&xs
, &ys
) {
168 fn zipdot_f32_zipslices(c
: &mut Criterion
) {
169 let xs
= vec
![2f32; 1024];
170 let ys
= vec
![2f32; 768];
171 let xs
= black_box(xs
);
172 let ys
= black_box(ys
);
174 c
.bench_function("zipdot f32 zipslices", move |b
| {
177 for (&x
, &y
) in ZipSlices
::new(&xs
, &ys
) {
185 fn zip_checked_counted_loop(c
: &mut Criterion
) {
186 let xs
= vec
![0; 1024];
187 let ys
= vec
![0; 768];
188 let xs
= black_box(xs
);
189 let ys
= black_box(ys
);
191 c
.bench_function("zip checked counted loop", move |b
| {
193 // Must slice to equal lengths, and then bounds checks are eliminated!
194 let len
= cmp
::min(xs
.len(), ys
.len());
208 fn zipdot_i32_checked_counted_loop(c
: &mut Criterion
) {
209 let xs
= vec
![2; 1024];
210 let ys
= vec
![2; 768];
211 let xs
= black_box(xs
);
212 let ys
= black_box(ys
);
214 c
.bench_function("zipdot i32 checked counted loop", move |b
| {
216 // Must slice to equal lengths, and then bounds checks are eliminated!
217 let len
= cmp
::min(xs
.len(), ys
.len());
231 fn zipdot_f32_checked_counted_loop(c
: &mut Criterion
) {
232 let xs
= vec
![2f32; 1024];
233 let ys
= vec
![2f32; 768];
234 let xs
= black_box(xs
);
235 let ys
= black_box(ys
);
237 c
.bench_function("zipdot f32 checked counted loop", move |b
| {
239 // Must slice to equal lengths, and then bounds checks are eliminated!
240 let len
= cmp
::min(xs
.len(), ys
.len());
254 fn zipdot_f32_checked_counted_unrolled_loop(c
: &mut Criterion
) {
255 let xs
= vec
![2f32; 1024];
256 let ys
= vec
![2f32; 768];
257 let xs
= black_box(xs
);
258 let ys
= black_box(ys
);
260 c
.bench_function("zipdot f32 checked counted unrolled loop", move |b
| {
262 // Must slice to equal lengths, and then bounds checks are eliminated!
263 let len
= cmp
::min(xs
.len(), ys
.len());
264 let mut xs
= &xs
[..len
];
265 let mut ys
= &ys
[..len
];
268 let (mut p0
, mut p1
, mut p2
, mut p3
, mut p4
, mut p5
, mut p6
, mut p7
) =
269 (0., 0., 0., 0., 0., 0., 0., 0.);
271 // how to unroll and have bounds checks eliminated (by cristicbz)
272 // split sum into eight parts to enable vectorization (by bluss)
273 while xs
.len() >= 8 {
291 for i
in 0..xs
.len() {
299 fn zip_unchecked_counted_loop(c
: &mut Criterion
) {
300 let xs
= vec
![0; 1024];
301 let ys
= vec
![0; 768];
302 let xs
= black_box(xs
);
303 let ys
= black_box(ys
);
305 c
.bench_function("zip unchecked counted loop", move |b
| {
307 let len
= cmp
::min(xs
.len(), ys
.len());
310 let x
= *xs
.get_unchecked(i
);
311 let y
= *ys
.get_unchecked(i
);
320 fn zipdot_i32_unchecked_counted_loop(c
: &mut Criterion
) {
321 let xs
= vec
![2; 1024];
322 let ys
= vec
![2; 768];
323 let xs
= black_box(xs
);
324 let ys
= black_box(ys
);
326 c
.bench_function("zipdot i32 unchecked counted loop", move |b
| {
328 let len
= cmp
::min(xs
.len(), ys
.len());
332 let x
= *xs
.get_unchecked(i
);
333 let y
= *ys
.get_unchecked(i
);
342 fn zipdot_f32_unchecked_counted_loop(c
: &mut Criterion
) {
343 let xs
= vec
![2.; 1024];
344 let ys
= vec
![2.; 768];
345 let xs
= black_box(xs
);
346 let ys
= black_box(ys
);
348 c
.bench_function("zipdot f32 unchecked counted loop", move |b
| {
350 let len
= cmp
::min(xs
.len(), ys
.len());
354 let x
= *xs
.get_unchecked(i
);
355 let y
= *ys
.get_unchecked(i
);
364 fn zip_unchecked_counted_loop3(c
: &mut Criterion
) {
365 let xs
= vec
![0; 1024];
366 let ys
= vec
![0; 768];
367 let zs
= vec
![0; 766];
368 let xs
= black_box(xs
);
369 let ys
= black_box(ys
);
370 let zs
= black_box(zs
);
372 c
.bench_function("zip unchecked counted loop3", move |b
| {
374 let len
= cmp
::min(xs
.len(), cmp
::min(ys
.len(), zs
.len()));
377 let x
= *xs
.get_unchecked(i
);
378 let y
= *ys
.get_unchecked(i
);
379 let z
= *zs
.get_unchecked(i
);
389 fn group_by_lazy_1(c
: &mut Criterion
) {
390 let mut data
= vec
![0; 1024];
391 for (index
, elt
) in data
.iter_mut().enumerate() {
395 let data
= black_box(data
);
397 c
.bench_function("group by lazy 1", move |b
| {
399 for (_key
, group
) in &data
.iter().group_by(|elt
| **elt
) {
408 fn group_by_lazy_2(c
: &mut Criterion
) {
409 let mut data
= vec
![0; 1024];
410 for (index
, elt
) in data
.iter_mut().enumerate() {
414 let data
= black_box(data
);
416 c
.bench_function("group by lazy 2", move |b
| {
418 for (_key
, group
) in &data
.iter().group_by(|elt
| **elt
) {
427 fn slice_chunks(c
: &mut Criterion
) {
428 let data
= vec
![0; 1024];
430 let data
= black_box(data
);
431 let sz
= black_box(10);
433 c
.bench_function("slice chunks", move |b
| {
435 for group
in data
.chunks(sz
) {
444 fn chunks_lazy_1(c
: &mut Criterion
) {
445 let data
= vec
![0; 1024];
447 let data
= black_box(data
);
448 let sz
= black_box(10);
450 c
.bench_function("chunks lazy 1", move |b
| {
452 for group
in &data
.iter().chunks(sz
) {
461 fn equal(c
: &mut Criterion
) {
462 let data
= vec
![7; 1024];
464 let alpha
= black_box(&data
[1..]);
465 let beta
= black_box(&data
[..l
- 1]);
467 c
.bench_function("equal", move |b
| {
469 itertools
::equal(alpha
, beta
)
474 fn merge_default(c
: &mut Criterion
) {
475 let mut data1
= vec
![0; 1024];
476 let mut data2
= vec
![0; 800];
478 for (_
, elt
) in data1
.iter_mut().enumerate() {
484 for (i
, elt
) in data2
.iter_mut().enumerate() {
492 let data1
= black_box(data1
);
493 let data2
= black_box(data2
);
495 c
.bench_function("merge default", move |b
| {
497 data1
.iter().merge(&data2
).count()
502 fn merge_by_cmp(c
: &mut Criterion
) {
503 let mut data1
= vec
![0; 1024];
504 let mut data2
= vec
![0; 800];
506 for (_
, elt
) in data1
.iter_mut().enumerate() {
512 for (i
, elt
) in data2
.iter_mut().enumerate() {
520 let data1
= black_box(data1
);
521 let data2
= black_box(data2
);
523 c
.bench_function("merge by cmp", move |b
| {
525 data1
.iter().merge_by(&data2
, PartialOrd
::le
).count()
530 fn merge_by_lt(c
: &mut Criterion
) {
531 let mut data1
= vec
![0; 1024];
532 let mut data2
= vec
![0; 800];
534 for (_
, elt
) in data1
.iter_mut().enumerate() {
540 for (i
, elt
) in data2
.iter_mut().enumerate() {
548 let data1
= black_box(data1
);
549 let data2
= black_box(data2
);
551 c
.bench_function("merge by lt", move |b
| {
553 data1
.iter().merge_by(&data2
, |a
, b
| a
<= b
).count()
558 fn kmerge_default(c
: &mut Criterion
) {
559 let mut data1
= vec
![0; 1024];
560 let mut data2
= vec
![0; 800];
562 for (_
, elt
) in data1
.iter_mut().enumerate() {
568 for (i
, elt
) in data2
.iter_mut().enumerate() {
576 let data1
= black_box(data1
);
577 let data2
= black_box(data2
);
578 let its
= &[data1
.iter(), data2
.iter()];
580 c
.bench_function("kmerge default", move |b
| {
582 its
.iter().cloned().kmerge().count()
587 fn kmerge_tenway(c
: &mut Criterion
) {
588 let mut data
= vec
![0; 10240];
590 let mut state
= 1729u16;
591 fn rng(state
: &mut u16) -> u16 {
592 let new
= state
.wrapping_mul(31421) + 6927;
597 for elt
in &mut data
{
598 *elt
= rng(&mut state
);
601 let mut chunks
= Vec
::new();
602 let mut rest
= &mut data
[..];
603 while rest
.len() > 0 {
604 let chunk_len
= 1 + rng(&mut state
) % 512;
605 let chunk_len
= cmp
::min(rest
.len(), chunk_len
as usize);
606 let (fst
, tail
) = {rest}
.split_at_mut(chunk_len
);
608 chunks
.push(fst
.iter().cloned());
612 // println!("Chunk lengths: {}", chunks.iter().format_with(", ", |elt, f| f(&elt.len())));
614 c
.bench_function("kmerge tenway", move |b
| {
616 chunks
.iter().cloned().kmerge().count()
621 fn fast_integer_sum
<I
>(iter
: I
) -> I
::Item
622 where I
: IntoIterator
,
623 I
::Item
: Default
+ Add
<Output
=I
::Item
>
625 iter
.into_iter().fold(<_
>::default(), |x
, y
| x
+ y
)
628 fn step_vec_2(c
: &mut Criterion
) {
629 let v
= vec
![0; 1024];
631 c
.bench_function("step vec 2", move |b
| {
633 fast_integer_sum(cloned(v
.iter().step_by(2)))
638 fn step_vec_10(c
: &mut Criterion
) {
639 let v
= vec
![0; 1024];
641 c
.bench_function("step vec 10", move |b
| {
643 fast_integer_sum(cloned(v
.iter().step_by(10)))
648 fn step_range_2(c
: &mut Criterion
) {
649 let v
= black_box(0..1024);
651 c
.bench_function("step range 2", move |b
| {
653 fast_integer_sum(v
.clone().step_by(2))
658 fn step_range_10(c
: &mut Criterion
) {
659 let v
= black_box(0..1024);
661 c
.bench_function("step range 10", move |b
| {
663 fast_integer_sum(v
.clone().step_by(10))
668 fn cartesian_product_iterator(c
: &mut Criterion
) {
669 let xs
= vec
![0; 16];
671 c
.bench_function("cartesian product iterator", move |b
| {
674 for (&x
, &y
, &z
) in iproduct
!(&xs
, &xs
, &xs
) {
684 fn cartesian_product_fold(c
: &mut Criterion
) {
685 let xs
= vec
![0; 16];
687 c
.bench_function("cartesian product fold", move |b
| {
690 iproduct
!(&xs
, &xs
, &xs
).fold((), |(), (&x
, &y
, &z
)| {
700 fn multi_cartesian_product_iterator(c
: &mut Criterion
) {
701 let xs
= [vec
![0; 16], vec
![0; 16], vec
![0; 16]];
703 c
.bench_function("multi cartesian product iterator", move |b
| {
706 for x
in xs
.iter().multi_cartesian_product() {
716 fn multi_cartesian_product_fold(c
: &mut Criterion
) {
717 let xs
= [vec
![0; 16], vec
![0; 16], vec
![0; 16]];
719 c
.bench_function("multi cartesian product fold", move |b
| {
722 xs
.iter().multi_cartesian_product().fold((), |(), x
| {
732 fn cartesian_product_nested_for(c
: &mut Criterion
) {
733 let xs
= vec
![0; 16];
735 c
.bench_function("cartesian product nested for", move |b
| {
752 fn all_equal(c
: &mut Criterion
) {
753 let mut xs
= vec
![0; 5_000_000];
754 xs
.extend(vec
![1; 5_000_000]);
756 c
.bench_function("all equal", move |b
| {
757 b
.iter(|| xs
.iter().all_equal())
761 fn all_equal_for(c
: &mut Criterion
) {
762 let mut xs
= vec
![0; 5_000_000];
763 xs
.extend(vec
![1; 5_000_000]);
765 c
.bench_function("all equal for", move |b
| {
777 fn all_equal_default(c
: &mut Criterion
) {
778 let mut xs
= vec
![0; 5_000_000];
779 xs
.extend(vec
![1; 5_000_000]);
781 c
.bench_function("all equal default", move |b
| {
782 b
.iter(|| xs
.iter().dedup().nth(1).is_none())
786 const PERM_COUNT
: usize = 6;
788 fn permutations_iter(c
: &mut Criterion
) {
789 struct NewIterator(Range
<usize>);
791 impl Iterator
for NewIterator
{
794 fn next(&mut self) -> Option
<Self::Item
> {
799 c
.bench_function("permutations iter", move |b
| {
801 for _
in NewIterator(0..PERM_COUNT
).permutations(PERM_COUNT
) {
808 fn permutations_range(c
: &mut Criterion
) {
809 c
.bench_function("permutations range", move |b
| {
811 for _
in (0..PERM_COUNT
).permutations(PERM_COUNT
) {
818 fn permutations_slice(c
: &mut Criterion
) {
819 let v
= (0..PERM_COUNT
).collect_vec();
821 c
.bench_function("permutations slice", move |b
| {
823 for _
in v
.as_slice().iter().permutations(PERM_COUNT
) {
835 zipdot_i32_default_zip
,
836 zipdot_f32_default_zip
,
841 zipdot_i32_zipslices
,
842 zipdot_f32_zipslices
,
843 zip_checked_counted_loop
,
844 zipdot_i32_checked_counted_loop
,
845 zipdot_f32_checked_counted_loop
,
846 zipdot_f32_checked_counted_unrolled_loop
,
847 zip_unchecked_counted_loop
,
848 zipdot_i32_unchecked_counted_loop
,
849 zipdot_f32_unchecked_counted_loop
,
850 zip_unchecked_counted_loop3
,
865 cartesian_product_iterator
,
866 cartesian_product_fold
,
867 multi_cartesian_product_iterator
,
868 multi_cartesian_product_fold
,
869 cartesian_product_nested_for
,
877 criterion_main
!(benches
);