]>
Commit | Line | Data |
---|---|---|
2c00a5a8 XL |
1 | //! Parallel iterator types for [ranges][std::range], |
2 | //! the type for values created by `a..b` expressions | |
3 | //! | |
4 | //! You will rarely need to interact with this module directly unless you have | |
5 | //! need to name one of the iterator types. | |
532ac7d7 | 6 | //! |
2c00a5a8 XL |
7 | //! ``` |
8 | //! use rayon::prelude::*; | |
532ac7d7 | 9 | //! |
2c00a5a8 XL |
10 | //! let r = (0..100u64).into_par_iter() |
11 | //! .sum(); | |
532ac7d7 | 12 | //! |
2c00a5a8 XL |
13 | //! // compare result with sequential calculation |
14 | //! assert_eq!((0..100).sum::<u64>(), r); | |
15 | //! ``` | |
16 | //! | |
17 | //! [std::range]: https://doc.rust-lang.org/core/ops/struct.Range.html | |
18 | ||
6a06907d XL |
19 | use crate::iter::plumbing::*; |
20 | use crate::iter::*; | |
2c00a5a8 | 21 | use std::ops::Range; |
532ac7d7 | 22 | use std::usize; |
2c00a5a8 XL |
23 | |
24 | /// Parallel iterator over a range, implemented for all integer types. | |
25 | /// | |
26 | /// **Note:** The `zip` operation requires `IndexedParallelIterator` | |
532ac7d7 | 27 | /// which is not implemented for `u64`, `i64`, `u128`, or `i128`. |
2c00a5a8 XL |
28 | /// |
29 | /// ``` | |
30 | /// use rayon::prelude::*; | |
31 | /// | |
32 | /// let p = (0..25usize).into_par_iter() | |
33 | /// .zip(0..25usize) | |
34 | /// .filter(|&(x, y)| x % 5 == 0 || y % 5 == 0) | |
35 | /// .map(|(x, y)| x * y) | |
36 | /// .sum::<usize>(); | |
37 | /// | |
38 | /// let s = (0..25usize).zip(0..25) | |
39 | /// .filter(|&(x, y)| x % 5 == 0 || y % 5 == 0) | |
40 | /// .map(|(x, y)| x * y) | |
41 | /// .sum(); | |
42 | /// | |
43 | /// assert_eq!(p, s); | |
44 | /// ``` | |
45 | #[derive(Debug, Clone)] | |
46 | pub struct Iter<T> { | |
47 | range: Range<T>, | |
48 | } | |
49 | ||
50 | impl<T> IntoParallelIterator for Range<T> | |
532ac7d7 XL |
51 | where |
52 | Iter<T>: ParallelIterator, | |
2c00a5a8 XL |
53 | { |
54 | type Item = <Iter<T> as ParallelIterator>::Item; | |
55 | type Iter = Iter<T>; | |
56 | ||
57 | fn into_par_iter(self) -> Self::Iter { | |
58 | Iter { range: self } | |
59 | } | |
60 | } | |
61 | ||
62 | struct IterProducer<T> { | |
63 | range: Range<T>, | |
64 | } | |
65 | ||
66 | impl<T> IntoIterator for IterProducer<T> | |
532ac7d7 XL |
67 | where |
68 | Range<T>: Iterator, | |
2c00a5a8 XL |
69 | { |
70 | type Item = <Range<T> as Iterator>::Item; | |
71 | type IntoIter = Range<T>; | |
72 | ||
73 | fn into_iter(self) -> Self::IntoIter { | |
74 | self.range | |
75 | } | |
76 | } | |
77 | ||
78 | macro_rules! indexed_range_impl { | |
79 | ( $t:ty ) => { | |
80 | impl ParallelIterator for Iter<$t> { | |
81 | type Item = $t; | |
82 | ||
83 | fn drive_unindexed<C>(self, consumer: C) -> C::Result | |
532ac7d7 XL |
84 | where |
85 | C: UnindexedConsumer<Self::Item>, | |
2c00a5a8 XL |
86 | { |
87 | bridge(self, consumer) | |
88 | } | |
89 | ||
90 | fn opt_len(&self) -> Option<usize> { | |
91 | Some(self.len()) | |
92 | } | |
93 | } | |
94 | ||
95 | impl IndexedParallelIterator for Iter<$t> { | |
96 | fn drive<C>(self, consumer: C) -> C::Result | |
532ac7d7 XL |
97 | where |
98 | C: Consumer<Self::Item>, | |
2c00a5a8 XL |
99 | { |
100 | bridge(self, consumer) | |
101 | } | |
102 | ||
103 | fn len(&self) -> usize { | |
104 | self.range.len() | |
105 | } | |
106 | ||
107 | fn with_producer<CB>(self, callback: CB) -> CB::Output | |
532ac7d7 XL |
108 | where |
109 | CB: ProducerCallback<Self::Item>, | |
2c00a5a8 XL |
110 | { |
111 | callback.callback(IterProducer { range: self.range }) | |
112 | } | |
113 | } | |
114 | ||
115 | impl Producer for IterProducer<$t> { | |
2c00a5a8 XL |
116 | type Item = <Range<$t> as Iterator>::Item; |
117 | type IntoIter = Range<$t>; | |
118 | fn into_iter(self) -> Self::IntoIter { | |
119 | self.range | |
120 | } | |
121 | ||
122 | fn split_at(self, index: usize) -> (Self, Self) { | |
123 | assert!(index <= self.range.len()); | |
124 | // For signed $t, the length and requested index could be greater than $t::MAX, and | |
125 | // then `index as $t` could wrap to negative, so wrapping_add is necessary. | |
126 | let mid = self.range.start.wrapping_add(index as $t); | |
532ac7d7 XL |
127 | let left = self.range.start..mid; |
128 | let right = mid..self.range.end; | |
2c00a5a8 XL |
129 | (IterProducer { range: left }, IterProducer { range: right }) |
130 | } | |
131 | } | |
532ac7d7 XL |
132 | }; |
133 | } | |
134 | ||
135 | trait UnindexedRangeLen<L> { | |
136 | fn len(&self) -> L; | |
2c00a5a8 XL |
137 | } |
138 | ||
139 | macro_rules! unindexed_range_impl { | |
532ac7d7 XL |
140 | ( $t:ty, $len_t:ty ) => { |
141 | impl UnindexedRangeLen<$len_t> for Range<$t> { | |
142 | fn len(&self) -> $len_t { | |
143 | let &Range { start, end } = self; | |
2c00a5a8 | 144 | if end > start { |
532ac7d7 | 145 | end.wrapping_sub(start) as $len_t |
2c00a5a8 XL |
146 | } else { |
147 | 0 | |
148 | } | |
149 | } | |
150 | } | |
151 | ||
152 | impl ParallelIterator for Iter<$t> { | |
153 | type Item = $t; | |
154 | ||
155 | fn drive_unindexed<C>(self, consumer: C) -> C::Result | |
532ac7d7 XL |
156 | where |
157 | C: UnindexedConsumer<Self::Item>, | |
2c00a5a8 | 158 | { |
e74abb32 XL |
159 | #[inline] |
160 | fn offset(start: $t) -> impl Fn(usize) -> $t { | |
161 | move |i| start.wrapping_add(i as $t) | |
162 | } | |
163 | ||
532ac7d7 XL |
164 | if let Some(len) = self.opt_len() { |
165 | // Drive this in indexed mode for better `collect`. | |
166 | (0..len) | |
167 | .into_par_iter() | |
e74abb32 | 168 | .map(offset(self.range.start)) |
532ac7d7 XL |
169 | .drive(consumer) |
170 | } else { | |
171 | bridge_unindexed(IterProducer { range: self.range }, consumer) | |
172 | } | |
173 | } | |
174 | ||
175 | fn opt_len(&self) -> Option<usize> { | |
176 | let len = self.range.len(); | |
177 | if len <= usize::MAX as $len_t { | |
178 | Some(len as usize) | |
179 | } else { | |
180 | None | |
181 | } | |
2c00a5a8 XL |
182 | } |
183 | } | |
184 | ||
185 | impl UnindexedProducer for IterProducer<$t> { | |
186 | type Item = $t; | |
187 | ||
188 | fn split(mut self) -> (Self, Option<Self>) { | |
532ac7d7 | 189 | let index = self.range.len() / 2; |
2c00a5a8 XL |
190 | if index > 0 { |
191 | let mid = self.range.start.wrapping_add(index as $t); | |
532ac7d7 | 192 | let right = mid..self.range.end; |
2c00a5a8 XL |
193 | self.range.end = mid; |
194 | (self, Some(IterProducer { range: right })) | |
195 | } else { | |
196 | (self, None) | |
197 | } | |
198 | } | |
199 | ||
200 | fn fold_with<F>(self, folder: F) -> F | |
532ac7d7 XL |
201 | where |
202 | F: Folder<Self::Item>, | |
2c00a5a8 XL |
203 | { |
204 | folder.consume_iter(self) | |
205 | } | |
206 | } | |
532ac7d7 | 207 | }; |
2c00a5a8 XL |
208 | } |
209 | ||
210 | // all Range<T> with ExactSizeIterator | |
532ac7d7 XL |
211 | indexed_range_impl! {u8} |
212 | indexed_range_impl! {u16} | |
213 | indexed_range_impl! {u32} | |
214 | indexed_range_impl! {usize} | |
215 | indexed_range_impl! {i8} | |
216 | indexed_range_impl! {i16} | |
217 | indexed_range_impl! {i32} | |
218 | indexed_range_impl! {isize} | |
2c00a5a8 XL |
219 | |
220 | // other Range<T> with just Iterator | |
532ac7d7 XL |
221 | unindexed_range_impl! {u64, u64} |
222 | unindexed_range_impl! {i64, u64} | |
532ac7d7 | 223 | unindexed_range_impl! {u128, u128} |
532ac7d7 | 224 | unindexed_range_impl! {i128, u128} |
2c00a5a8 XL |
225 | |
226 | #[test] | |
532ac7d7 | 227 | fn check_range_split_at_overflow() { |
2c00a5a8 XL |
228 | // Note, this split index overflows i8! |
229 | let producer = IterProducer { range: -100i8..100 }; | |
230 | let (left, right) = producer.split_at(150); | |
e74abb32 XL |
231 | let r1: i32 = left.range.map(i32::from).sum(); |
232 | let r2: i32 = right.range.map(i32::from).sum(); | |
2c00a5a8 XL |
233 | assert_eq!(r1 + r2, -100); |
234 | } | |
532ac7d7 | 235 | |
532ac7d7 XL |
236 | #[test] |
237 | fn test_i128_len_doesnt_overflow() { | |
238 | use std::{i128, u128}; | |
239 | ||
240 | // Using parse because some versions of rust don't allow long literals | |
241 | let octillion: i128 = "1000000000000000000000000000".parse().unwrap(); | |
242 | let producer = IterProducer { | |
243 | range: 0..octillion, | |
244 | }; | |
245 | ||
246 | assert_eq!(octillion as u128, producer.range.len()); | |
247 | assert_eq!(octillion as u128, (0..octillion).len()); | |
248 | assert_eq!(2 * octillion as u128, (-octillion..octillion).len()); | |
249 | ||
250 | assert_eq!(u128::MAX, (i128::MIN..i128::MAX).len()); | |
251 | } | |
252 | ||
253 | #[test] | |
254 | fn test_u64_opt_len() { | |
255 | use std::{u64, usize}; | |
256 | assert_eq!(Some(100), (0..100u64).into_par_iter().opt_len()); | |
257 | assert_eq!( | |
258 | Some(usize::MAX), | |
259 | (0..usize::MAX as u64).into_par_iter().opt_len() | |
260 | ); | |
261 | if (usize::MAX as u64) < u64::MAX { | |
262 | assert_eq!( | |
263 | None, | |
264 | (0..(usize::MAX as u64).wrapping_add(1)) | |
265 | .into_par_iter() | |
266 | .opt_len() | |
267 | ); | |
268 | assert_eq!(None, (0..u64::MAX).into_par_iter().opt_len()); | |
269 | } | |
270 | } | |
271 | ||
532ac7d7 XL |
272 | #[test] |
273 | fn test_u128_opt_len() { | |
274 | use std::{u128, usize}; | |
275 | assert_eq!(Some(100), (0..100u128).into_par_iter().opt_len()); | |
276 | assert_eq!( | |
277 | Some(usize::MAX), | |
278 | (0..usize::MAX as u128).into_par_iter().opt_len() | |
279 | ); | |
280 | assert_eq!(None, (0..1 + usize::MAX as u128).into_par_iter().opt_len()); | |
281 | assert_eq!(None, (0..u128::MAX).into_par_iter().opt_len()); | |
282 | } | |
283 | ||
284 | // `usize as i64` can overflow, so make sure to wrap it appropriately | |
285 | // when using the `opt_len` "indexed" mode. | |
286 | #[test] | |
287 | #[cfg(target_pointer_width = "64")] | |
288 | fn test_usize_i64_overflow() { | |
6a06907d | 289 | use crate::ThreadPoolBuilder; |
532ac7d7 | 290 | use std::i64; |
532ac7d7 XL |
291 | |
292 | let iter = (-2..i64::MAX).into_par_iter(); | |
293 | assert_eq!(iter.opt_len(), Some(i64::MAX as usize + 2)); | |
294 | ||
295 | // always run with multiple threads to split into, or this will take forever... | |
296 | let pool = ThreadPoolBuilder::new().num_threads(8).build().unwrap(); | |
297 | pool.install(|| assert_eq!(iter.find_last(|_| true), Some(i64::MAX - 1))); | |
298 | } |