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