Joel Galenson | 66036a8 | 2020-07-07 13:29:38 -0700 | [diff] [blame] | 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] |
| 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] |
| 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] |
| 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 | |
| 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 | |
| 114 | fn next(&mut self) -> Option<Self::Item> { |
| 115 | self.iter.next() |
| 116 | } |
| 117 | |
| 118 | fn size_hint(&self) -> (usize, Option<usize>) { |
| 119 | (std::cmp::min(self.iter.len(), self.window_size), None) |
| 120 | } |
| 121 | } |
| 122 | |
| 123 | #[bench] |
| 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] |
| 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] |
| 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] |
| 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); |