1 // Copyright 2018 Developers of the Rand project.
2 //
3 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
4 // https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
5 // <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
6 // option. This file may not be copied, modified, or distributed
7 // except according to those terms.
8
9 #![feature(test)]
10 #![allow(non_snake_case)]
11
12 extern crate test;
13
14 use test::Bencher;
15
16 use rand::prelude::*;
17 use rand::seq::*;
18 use std::mem::size_of;
19
20 // We force use of 32-bit RNG since seq code is optimised for use with 32-bit
21 // generators on all platforms.
22 use rand_pcg::Pcg32 as SmallRng;
23
24 const RAND_BENCH_N: u64 = 1000;
25
26 #[bench]
seq_shuffle_100(b: &mut Bencher)27 fn seq_shuffle_100(b: &mut Bencher) {
28 let mut rng = SmallRng::from_rng(thread_rng()).unwrap();
29 let x: &mut [usize] = &mut [1; 100];
30 b.iter(|| {
31 x.shuffle(&mut rng);
32 x[0]
33 })
34 }
35
36 #[bench]
seq_slice_choose_1_of_1000(b: &mut Bencher)37 fn seq_slice_choose_1_of_1000(b: &mut Bencher) {
38 let mut rng = SmallRng::from_rng(thread_rng()).unwrap();
39 let x: &mut [usize] = &mut [1; 1000];
40 for i in 0..1000 {
41 x[i] = i;
42 }
43 b.iter(|| {
44 let mut s = 0;
45 for _ in 0..RAND_BENCH_N {
46 s += x.choose(&mut rng).unwrap();
47 }
48 s
49 });
50 b.bytes = size_of::<usize>() as u64 * crate::RAND_BENCH_N;
51 }
52
53 macro_rules! seq_slice_choose_multiple {
54 ($name:ident, $amount:expr, $length:expr) => {
55 #[bench]
56 fn $name(b: &mut Bencher) {
57 let mut rng = SmallRng::from_rng(thread_rng()).unwrap();
58 let x: &[i32] = &[$amount; $length];
59 let mut result = [0i32; $amount];
60 b.iter(|| {
61 // Collect full result to prevent unwanted shortcuts getting
62 // first element (in case sample_indices returns an iterator).
63 for (slot, sample) in result.iter_mut().zip(x.choose_multiple(&mut rng, $amount)) {
64 *slot = *sample;
65 }
66 result[$amount - 1]
67 })
68 }
69 };
70 }
71
72 seq_slice_choose_multiple!(seq_slice_choose_multiple_1_of_1000, 1, 1000);
73 seq_slice_choose_multiple!(seq_slice_choose_multiple_950_of_1000, 950, 1000);
74 seq_slice_choose_multiple!(seq_slice_choose_multiple_10_of_100, 10, 100);
75 seq_slice_choose_multiple!(seq_slice_choose_multiple_90_of_100, 90, 100);
76
77 #[bench]
seq_iter_choose_from_1000(b: &mut Bencher)78 fn seq_iter_choose_from_1000(b: &mut Bencher) {
79 let mut rng = SmallRng::from_rng(thread_rng()).unwrap();
80 let x: &mut [usize] = &mut [1; 1000];
81 for i in 0..1000 {
82 x[i] = i;
83 }
84 b.iter(|| {
85 let mut s = 0;
86 for _ in 0..RAND_BENCH_N {
87 s += x.iter().choose(&mut rng).unwrap();
88 }
89 s
90 });
91 b.bytes = size_of::<usize>() as u64 * crate::RAND_BENCH_N;
92 }
93
94 #[derive(Clone)]
95 struct UnhintedIterator<I: Iterator + Clone> {
96 iter: I,
97 }
98 impl<I: Iterator + Clone> Iterator for UnhintedIterator<I> {
99 type Item = I::Item;
100
next(&mut self) -> Option<Self::Item>101 fn next(&mut self) -> Option<Self::Item> {
102 self.iter.next()
103 }
104 }
105
106 #[derive(Clone)]
107 struct WindowHintedIterator<I: ExactSizeIterator + Iterator + Clone> {
108 iter: I,
109 window_size: usize,
110 }
111 impl<I: ExactSizeIterator + Iterator + Clone> Iterator for WindowHintedIterator<I> {
112 type Item = I::Item;
113
next(&mut self) -> Option<Self::Item>114 fn next(&mut self) -> Option<Self::Item> {
115 self.iter.next()
116 }
117
size_hint(&self) -> (usize, Option<usize>)118 fn size_hint(&self) -> (usize, Option<usize>) {
119 (std::cmp::min(self.iter.len(), self.window_size), None)
120 }
121 }
122
123 #[bench]
seq_iter_unhinted_choose_from_1000(b: &mut Bencher)124 fn seq_iter_unhinted_choose_from_1000(b: &mut Bencher) {
125 let mut rng = SmallRng::from_rng(thread_rng()).unwrap();
126 let x: &[usize] = &[1; 1000];
127 b.iter(|| {
128 UnhintedIterator { iter: x.iter() }
129 .choose(&mut rng)
130 .unwrap()
131 })
132 }
133
134 #[bench]
seq_iter_window_hinted_choose_from_1000(b: &mut Bencher)135 fn seq_iter_window_hinted_choose_from_1000(b: &mut Bencher) {
136 let mut rng = SmallRng::from_rng(thread_rng()).unwrap();
137 let x: &[usize] = &[1; 1000];
138 b.iter(|| {
139 WindowHintedIterator {
140 iter: x.iter(),
141 window_size: 7,
142 }
143 .choose(&mut rng)
144 })
145 }
146
147 #[bench]
seq_iter_choose_multiple_10_of_100(b: &mut Bencher)148 fn seq_iter_choose_multiple_10_of_100(b: &mut Bencher) {
149 let mut rng = SmallRng::from_rng(thread_rng()).unwrap();
150 let x: &[usize] = &[1; 100];
151 b.iter(|| x.iter().cloned().choose_multiple(&mut rng, 10))
152 }
153
154 #[bench]
seq_iter_choose_multiple_fill_10_of_100(b: &mut Bencher)155 fn seq_iter_choose_multiple_fill_10_of_100(b: &mut Bencher) {
156 let mut rng = SmallRng::from_rng(thread_rng()).unwrap();
157 let x: &[usize] = &[1; 100];
158 let mut buf = [0; 10];
159 b.iter(|| x.iter().cloned().choose_multiple_fill(&mut rng, &mut buf))
160 }
161
162 macro_rules! sample_indices {
163 ($name:ident, $fn:ident, $amount:expr, $length:expr) => {
164 #[bench]
165 fn $name(b: &mut Bencher) {
166 let mut rng = SmallRng::from_rng(thread_rng()).unwrap();
167 b.iter(|| index::$fn(&mut rng, $length, $amount))
168 }
169 };
170 }
171
172 sample_indices!(misc_sample_indices_1_of_1k, sample, 1, 1000);
173 sample_indices!(misc_sample_indices_10_of_1k, sample, 10, 1000);
174 sample_indices!(misc_sample_indices_100_of_1k, sample, 100, 1000);
175 sample_indices!(misc_sample_indices_100_of_1M, sample, 100, 1000_000);
176 sample_indices!(misc_sample_indices_100_of_1G, sample, 100, 1000_000_000);
177 sample_indices!(misc_sample_indices_200_of_1G, sample, 200, 1000_000_000);
178 sample_indices!(misc_sample_indices_400_of_1G, sample, 400, 1000_000_000);
179 sample_indices!(misc_sample_indices_600_of_1G, sample, 600, 1000_000_000);
180