| 1 |
//! Traits and functions used to implement parallel iteration. These are |
| 2 |
//! low-level details -- users of parallel iterators should not need to |
| 3 |
//! interact with them directly. See [the `plumbing` README][r] for a general overview. |
| 4 |
//! |
| 5 |
//! [r]: https://github.com/rayon-rs/rayon/blob/main/src/iter/plumbing/README.md |
| 6 |
|
| 7 |
use crate::join_context; |
| 8 |
|
| 9 |
use super::IndexedParallelIterator; |
| 10 |
|
| 11 |
use std::usize; |
| 12 |
|
| 13 |
/// The `ProducerCallback` trait is a kind of generic closure, |
| 14 |
/// [analogous to `FnOnce`][FnOnce]. See [the corresponding section in |
| 15 |
/// the plumbing README][r] for more details. |
| 16 |
/// |
| 17 |
/// [r]: https://github.com/rayon-rs/rayon/blob/main/src/iter/plumbing/README.md#producer-callback |
| 18 |
/// [FnOnce]: https://doc.rust-lang.org/std/ops/trait.FnOnce.html |
| 19 |
pub trait ProducerCallback<T> { |
| 20 |
/// The type of value returned by this callback. Analogous to |
| 21 |
/// [`Output` from the `FnOnce` trait][Output]. |
| 22 |
/// |
| 23 |
/// [Output]: https://doc.rust-lang.org/std/ops/trait.FnOnce.html#associatedtype.Output |
| 24 |
type Output; |
| 25 |
|
| 26 |
/// Invokes the callback with the given producer as argument. The |
| 27 |
/// key point of this trait is that this method is generic over |
| 28 |
/// `P`, and hence implementors must be defined for any producer. |
| 29 |
fn callback<P>(self, producer: P) -> Self::Output |
| 30 |
where |
| 31 |
P: Producer<Item = T>; |
| 32 |
} |
| 33 |
|
| 34 |
/// A `Producer` is effectively a "splittable `IntoIterator`". That |
| 35 |
/// is, a producer is a value which can be converted into an iterator |
| 36 |
/// at any time: at that point, it simply produces items on demand, |
| 37 |
/// like any iterator. But what makes a `Producer` special is that, |
| 38 |
/// *before* we convert to an iterator, we can also **split** it at a |
| 39 |
/// particular point using the `split_at` method. This will yield up |
| 40 |
/// two producers, one producing the items before that point, and one |
| 41 |
/// producing the items after that point (these two producers can then |
| 42 |
/// independently be split further, or be converted into iterators). |
| 43 |
/// In Rayon, this splitting is used to divide between threads. |
| 44 |
/// See [the `plumbing` README][r] for further details. |
| 45 |
/// |
| 46 |
/// Note that each producer will always produce a fixed number of |
| 47 |
/// items N. However, this number N is not queryable through the API; |
| 48 |
/// the consumer is expected to track it. |
| 49 |
/// |
| 50 |
/// NB. You might expect `Producer` to extend the `IntoIterator` |
| 51 |
/// trait. However, [rust-lang/rust#20671][20671] prevents us from |
| 52 |
/// declaring the DoubleEndedIterator and ExactSizeIterator |
| 53 |
/// constraints on a required IntoIterator trait, so we inline |
| 54 |
/// IntoIterator here until that issue is fixed. |
| 55 |
/// |
| 56 |
/// [r]: https://github.com/rayon-rs/rayon/blob/main/src/iter/plumbing/README.md |
| 57 |
/// [20671]: https://github.com/rust-lang/rust/issues/20671 |
| 58 |
pub trait Producer: Send + Sized { |
| 59 |
/// The type of item that will be produced by this producer once |
| 60 |
/// it is converted into an iterator. |
| 61 |
type Item; |
| 62 |
|
| 63 |
/// The type of iterator we will become. |
| 64 |
type IntoIter: Iterator<Item = Self::Item> + DoubleEndedIterator + ExactSizeIterator; |
| 65 |
|
| 66 |
/// Convert `self` into an iterator; at this point, no more parallel splits |
| 67 |
/// are possible. |
| 68 |
fn into_iter(self) -> Self::IntoIter; |
| 69 |
|
| 70 |
/// The minimum number of items that we will process |
| 71 |
/// sequentially. Defaults to 1, which means that we will split |
| 72 |
/// all the way down to a single item. This can be raised higher |
| 73 |
/// using the [`with_min_len`] method, which will force us to |
| 74 |
/// create sequential tasks at a larger granularity. Note that |
| 75 |
/// Rayon automatically normally attempts to adjust the size of |
| 76 |
/// parallel splits to reduce overhead, so this should not be |
| 77 |
/// needed. |
| 78 |
/// |
| 79 |
/// [`with_min_len`]: ../trait.IndexedParallelIterator.html#method.with_min_len |
| 80 |
fn min_len(&self) -> usize { |
| 81 |
1 |
| 82 |
} |
| 83 |
|
| 84 |
/// The maximum number of items that we will process |
| 85 |
/// sequentially. Defaults to MAX, which means that we can choose |
| 86 |
/// not to split at all. This can be lowered using the |
| 87 |
/// [`with_max_len`] method, which will force us to create more |
| 88 |
/// parallel tasks. Note that Rayon automatically normally |
| 89 |
/// attempts to adjust the size of parallel splits to reduce |
| 90 |
/// overhead, so this should not be needed. |
| 91 |
/// |
| 92 |
/// [`with_max_len`]: ../trait.IndexedParallelIterator.html#method.with_max_len |
| 93 |
fn max_len(&self) -> usize { |
| 94 |
usize::MAX |
| 95 |
} |
| 96 |
|
| 97 |
/// Split into two producers; one produces items `0..index`, the |
| 98 |
/// other `index..N`. Index must be less than or equal to `N`. |
| 99 |
fn split_at(self, index: usize) -> (Self, Self); |
| 100 |
|
| 101 |
/// Iterate the producer, feeding each element to `folder`, and |
| 102 |
/// stop when the folder is full (or all elements have been consumed). |
| 103 |
/// |
| 104 |
/// The provided implementation is sufficient for most iterables. |
| 105 |
fn fold_with<F>(self, folder: F) -> F |
| 106 |
where |
| 107 |
F: Folder<Self::Item>, |
| 108 |
{ |
| 109 |
folder.consume_iter(self.into_iter()) |
| 110 |
} |
| 111 |
} |
| 112 |
|
| 113 |
/// A consumer is effectively a [generalized "fold" operation][fold], |
| 114 |
/// and in fact each consumer will eventually be converted into a |
| 115 |
/// [`Folder`]. What makes a consumer special is that, like a |
| 116 |
/// [`Producer`], it can be **split** into multiple consumers using |
| 117 |
/// the `split_at` method. When a consumer is split, it produces two |
| 118 |
/// consumers, as well as a **reducer**. The two consumers can be fed |
| 119 |
/// items independently, and when they are done the reducer is used to |
| 120 |
/// combine their two results into one. See [the `plumbing` |
| 121 |
/// README][r] for further details. |
| 122 |
/// |
| 123 |
/// [r]: https://github.com/rayon-rs/rayon/blob/main/src/iter/plumbing/README.md |
| 124 |
/// [fold]: https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.fold |
| 125 |
/// [`Folder`]: trait.Folder.html |
| 126 |
/// [`Producer`]: trait.Producer.html |
| 127 |
pub trait Consumer<Item>: Send + Sized { |
| 128 |
/// The type of folder that this consumer can be converted into. |
| 129 |
type Folder: Folder<Item, Result = Self::Result>; |
| 130 |
|
| 131 |
/// The type of reducer that is produced if this consumer is split. |
| 132 |
type Reducer: Reducer<Self::Result>; |
| 133 |
|
| 134 |
/// The type of result that this consumer will ultimately produce. |
| 135 |
type Result: Send; |
| 136 |
|
| 137 |
/// Divide the consumer into two consumers, one processing items |
| 138 |
/// `0..index` and one processing items from `index..`. Also |
| 139 |
/// produces a reducer that can be used to reduce the results at |
| 140 |
/// the end. |
| 141 |
fn split_at(self, index: usize) -> (Self, Self, Self::Reducer); |
| 142 |
|
| 143 |
/// Convert the consumer into a folder that can consume items |
| 144 |
/// sequentially, eventually producing a final result. |
| 145 |
fn into_folder(self) -> Self::Folder; |
| 146 |
|
| 147 |
/// Hint whether this `Consumer` would like to stop processing |
| 148 |
/// further items, e.g. if a search has been completed. |
| 149 |
fn full(&self) -> bool; |
| 150 |
} |
| 151 |
|
| 152 |
/// The `Folder` trait encapsulates [the standard fold |
| 153 |
/// operation][fold]. It can be fed many items using the `consume` |
| 154 |
/// method. At the end, once all items have been consumed, it can then |
| 155 |
/// be converted (using `complete`) into a final value. |
| 156 |
/// |
| 157 |
/// [fold]: https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.fold |
| 158 |
pub trait Folder<Item>: Sized { |
| 159 |
/// The type of result that will ultimately be produced by the folder. |
| 160 |
type Result; |
| 161 |
|
| 162 |
/// Consume next item and return new sequential state. |
| 163 |
fn consume(self, item: Item) -> Self; |
| 164 |
|
| 165 |
/// Consume items from the iterator until full, and return new sequential state. |
| 166 |
/// |
| 167 |
/// This method is **optional**. The default simply iterates over |
| 168 |
/// `iter`, invoking `consume` and checking after each iteration |
| 169 |
/// whether `full` returns false. |
| 170 |
/// |
| 171 |
/// The main reason to override it is if you can provide a more |
| 172 |
/// specialized, efficient implementation. |
| 173 |
fn consume_iter<I>(mut self, iter: I) -> Self |
| 174 |
where |
| 175 |
I: IntoIterator<Item = Item>, |
| 176 |
{ |
| 177 |
for item in iter { |
| 178 |
self = self.consume(item); |
| 179 |
if self.full() { |
| 180 |
break; |
| 181 |
} |
| 182 |
} |
| 183 |
self |
| 184 |
} |
| 185 |
|
| 186 |
/// Finish consuming items, produce final result. |
| 187 |
fn complete(self) -> Self::Result; |
| 188 |
|
| 189 |
/// Hint whether this `Folder` would like to stop processing |
| 190 |
/// further items, e.g. if a search has been completed. |
| 191 |
fn full(&self) -> bool; |
| 192 |
} |
| 193 |
|
| 194 |
/// The reducer is the final step of a `Consumer` -- after a consumer |
| 195 |
/// has been split into two parts, and each of those parts has been |
| 196 |
/// fully processed, we are left with two results. The reducer is then |
| 197 |
/// used to combine those two results into one. See [the `plumbing` |
| 198 |
/// README][r] for further details. |
| 199 |
/// |
| 200 |
/// [r]: https://github.com/rayon-rs/rayon/blob/main/src/iter/plumbing/README.md |
| 201 |
pub trait Reducer<Result> { |
| 202 |
/// Reduce two final results into one; this is executed after a |
| 203 |
/// split. |
| 204 |
fn reduce(self, left: Result, right: Result) -> Result; |
| 205 |
} |
| 206 |
|
| 207 |
/// A stateless consumer can be freely copied. These consumers can be |
| 208 |
/// used like regular consumers, but they also support a |
| 209 |
/// `split_off_left` method that does not take an index to split, but |
| 210 |
/// simply splits at some arbitrary point (`for_each`, for example, |
| 211 |
/// produces an unindexed consumer). |
| 212 |
pub trait UnindexedConsumer<I>: Consumer<I> { |
| 213 |
/// Splits off a "left" consumer and returns it. The `self` |
| 214 |
/// consumer should then be used to consume the "right" portion of |
| 215 |
/// the data. (The ordering matters for methods like find_first -- |
| 216 |
/// values produced by the returned value are given precedence |
| 217 |
/// over values produced by `self`.) Once the left and right |
| 218 |
/// halves have been fully consumed, you should reduce the results |
| 219 |
/// with the result of `to_reducer`. |
| 220 |
fn split_off_left(&self) -> Self; |
| 221 |
|
| 222 |
/// Creates a reducer that can be used to combine the results from |
| 223 |
/// a split consumer. |
| 224 |
fn to_reducer(&self) -> Self::Reducer; |
| 225 |
} |
| 226 |
|
| 227 |
/// A variant on `Producer` which does not know its exact length or |
| 228 |
/// cannot represent it in a `usize`. These producers act like |
| 229 |
/// ordinary producers except that they cannot be told to split at a |
| 230 |
/// particular point. Instead, you just ask them to split 'somewhere'. |
| 231 |
/// |
| 232 |
/// (In principle, `Producer` could extend this trait; however, it |
| 233 |
/// does not because to do so would require producers to carry their |
| 234 |
/// own length with them.) |
| 235 |
pub trait UnindexedProducer: Send + Sized { |
| 236 |
/// The type of item returned by this producer. |
| 237 |
type Item; |
| 238 |
|
| 239 |
/// Split midway into a new producer if possible, otherwise return `None`. |
| 240 |
fn split(self) -> (Self, Option<Self>); |
| 241 |
|
| 242 |
/// Iterate the producer, feeding each element to `folder`, and |
| 243 |
/// stop when the folder is full (or all elements have been consumed). |
| 244 |
fn fold_with<F>(self, folder: F) -> F |
| 245 |
where |
| 246 |
F: Folder<Self::Item>; |
| 247 |
} |
| 248 |
|
| 249 |
/// A splitter controls the policy for splitting into smaller work items. |
| 250 |
/// |
| 251 |
/// Thief-splitting is an adaptive policy that starts by splitting into |
| 252 |
/// enough jobs for every worker thread, and then resets itself whenever a |
| 253 |
/// job is actually stolen into a different thread. |
| 254 |
#[derive(Clone, Copy)] |
| 255 |
struct Splitter { |
| 256 |
/// The `splits` tell us approximately how many remaining times we'd |
| 257 |
/// like to split this job. We always just divide it by two though, so |
| 258 |
/// the effective number of pieces will be `next_power_of_two()`. |
| 259 |
splits: usize, |
| 260 |
} |
| 261 |
|
| 262 |
impl Splitter { |
| 263 |
#[inline] |
| 264 |
fn new() -> Splitter { |
| 265 |
Splitter { |
| 266 |
splits: crate::current_num_threads(), |
| 267 |
} |
| 268 |
} |
| 269 |
|
| 270 |
#[inline] |
| 271 |
fn try_split(&mut self, stolen: bool) -> bool { |
| 272 |
let Splitter { splits } = *self; |
| 273 |
|
| 274 |
if stolen { |
| 275 |
// This job was stolen! Reset the number of desired splits to the |
| 276 |
// thread count, if that's more than we had remaining anyway. |
| 277 |
self.splits = Ord::max(crate::current_num_threads(), self.splits / 2); |
| 278 |
true |
| 279 |
} else if splits > 0 { |
| 280 |
// We have splits remaining, make it so. |
| 281 |
self.splits /= 2; |
| 282 |
true |
| 283 |
} else { |
| 284 |
// Not stolen, and no more splits -- we're done! |
| 285 |
false |
| 286 |
} |
| 287 |
} |
| 288 |
} |
| 289 |
|
| 290 |
/// The length splitter is built on thief-splitting, but additionally takes |
| 291 |
/// into account the remaining length of the iterator. |
| 292 |
#[derive(Clone, Copy)] |
| 293 |
struct LengthSplitter { |
| 294 |
inner: Splitter, |
| 295 |
|
| 296 |
/// The smallest we're willing to divide into. Usually this is just 1, |
| 297 |
/// but you can choose a larger working size with `with_min_len()`. |
| 298 |
min: usize, |
| 299 |
} |
| 300 |
|
| 301 |
impl LengthSplitter { |
| 302 |
/// Creates a new splitter based on lengths. |
| 303 |
/// |
| 304 |
/// The `min` is a hard lower bound. We'll never split below that, but |
| 305 |
/// of course an iterator might start out smaller already. |
| 306 |
/// |
| 307 |
/// The `max` is an upper bound on the working size, used to determine |
| 308 |
/// the minimum number of times we need to split to get under that limit. |
| 309 |
/// The adaptive algorithm may very well split even further, but never |
| 310 |
/// smaller than the `min`. |
| 311 |
#[inline] |
| 312 |
fn new(min: usize, max: usize, len: usize) -> LengthSplitter { |
| 313 |
let mut splitter = LengthSplitter { |
| 314 |
inner: Splitter::new(), |
| 315 |
min: Ord::max(min, 1), |
| 316 |
}; |
| 317 |
|
| 318 |
// Divide the given length by the max working length to get the minimum |
| 319 |
// number of splits we need to get under that max. This rounds down, |
| 320 |
// but the splitter actually gives `next_power_of_two()` pieces anyway. |
| 321 |
// e.g. len 12345 / max 100 = 123 min_splits -> 128 pieces. |
| 322 |
let min_splits = len / Ord::max(max, 1); |
| 323 |
|
| 324 |
// Only update the value if it's not splitting enough already. |
| 325 |
if min_splits > splitter.inner.splits { |
| 326 |
splitter.inner.splits = min_splits; |
| 327 |
} |
| 328 |
|
| 329 |
splitter |
| 330 |
} |
| 331 |
|
| 332 |
#[inline] |
| 333 |
fn try_split(&mut self, len: usize, stolen: bool) -> bool { |
| 334 |
// If splitting wouldn't make us too small, try the inner splitter. |
| 335 |
len / 2 >= self.min && self.inner.try_split(stolen) |
| 336 |
} |
| 337 |
} |
| 338 |
|
| 339 |
/// This helper function is used to "connect" a parallel iterator to a |
| 340 |
/// consumer. It will convert the `par_iter` into a producer P and |
| 341 |
/// then pull items from P and feed them to `consumer`, splitting and |
| 342 |
/// creating parallel threads as needed. |
| 343 |
/// |
| 344 |
/// This is useful when you are implementing your own parallel |
| 345 |
/// iterators: it is often used as the definition of the |
| 346 |
/// [`drive_unindexed`] or [`drive`] methods. |
| 347 |
/// |
| 348 |
/// [`drive_unindexed`]: ../trait.ParallelIterator.html#tymethod.drive_unindexed |
| 349 |
/// [`drive`]: ../trait.IndexedParallelIterator.html#tymethod.drive |
| 350 |
pub fn bridge<I, C>(par_iter: I, consumer: C) -> C::Result |
| 351 |
where |
| 352 |
I: IndexedParallelIterator, |
| 353 |
C: Consumer<I::Item>, |
| 354 |
{ |
| 355 |
let len = par_iter.len(); |
| 356 |
return par_iter.with_producer(Callback { len, consumer }); |
| 357 |
|
| 358 |
struct Callback<C> { |
| 359 |
len: usize, |
| 360 |
consumer: C, |
| 361 |
} |
| 362 |
|
| 363 |
impl<C, I> ProducerCallback<I> for Callback<C> |
| 364 |
where |
| 365 |
C: Consumer<I>, |
| 366 |
{ |
| 367 |
type Output = C::Result; |
| 368 |
fn callback<P>(self, producer: P) -> C::Result |
| 369 |
where |
| 370 |
P: Producer<Item = I>, |
| 371 |
{ |
| 372 |
bridge_producer_consumer(self.len, producer, self.consumer) |
| 373 |
} |
| 374 |
} |
| 375 |
} |
| 376 |
|
| 377 |
/// This helper function is used to "connect" a producer and a |
| 378 |
/// consumer. You may prefer to call [`bridge`], which wraps this |
| 379 |
/// function. This function will draw items from `producer` and feed |
| 380 |
/// them to `consumer`, splitting and creating parallel tasks when |
| 381 |
/// needed. |
| 382 |
/// |
| 383 |
/// This is useful when you are implementing your own parallel |
| 384 |
/// iterators: it is often used as the definition of the |
| 385 |
/// [`drive_unindexed`] or [`drive`] methods. |
| 386 |
/// |
| 387 |
/// [`bridge`]: fn.bridge.html |
| 388 |
/// [`drive_unindexed`]: ../trait.ParallelIterator.html#tymethod.drive_unindexed |
| 389 |
/// [`drive`]: ../trait.IndexedParallelIterator.html#tymethod.drive |
| 390 |
pub fn bridge_producer_consumer<P, C>(len: usize, producer: P, consumer: C) -> C::Result |
| 391 |
where |
| 392 |
P: Producer, |
| 393 |
C: Consumer<P::Item>, |
| 394 |
{ |
| 395 |
let splitter = LengthSplitter::new(producer.min_len(), producer.max_len(), len); |
| 396 |
return helper(len, false, splitter, producer, consumer); |
| 397 |
|
| 398 |
fn helper<P, C>( |
| 399 |
len: usize, |
| 400 |
migrated: bool, |
| 401 |
mut splitter: LengthSplitter, |
| 402 |
producer: P, |
| 403 |
consumer: C, |
| 404 |
) -> C::Result |
| 405 |
where |
| 406 |
P: Producer, |
| 407 |
C: Consumer<P::Item>, |
| 408 |
{ |
| 409 |
if consumer.full() { |
| 410 |
consumer.into_folder().complete() |
| 411 |
} else if splitter.try_split(len, migrated) { |
| 412 |
let mid = len / 2; |
| 413 |
let (left_producer, right_producer) = producer.split_at(mid); |
| 414 |
let (left_consumer, right_consumer, reducer) = consumer.split_at(mid); |
| 415 |
let (left_result, right_result) = join_context( |
| 416 |
|context| { |
| 417 |
helper( |
| 418 |
mid, |
| 419 |
context.migrated(), |
| 420 |
splitter, |
| 421 |
left_producer, |
| 422 |
left_consumer, |
| 423 |
) |
| 424 |
}, |
| 425 |
|context| { |
| 426 |
helper( |
| 427 |
len - mid, |
| 428 |
context.migrated(), |
| 429 |
splitter, |
| 430 |
right_producer, |
| 431 |
right_consumer, |
| 432 |
) |
| 433 |
}, |
| 434 |
); |
| 435 |
reducer.reduce(left_result, right_result) |
| 436 |
} else { |
| 437 |
producer.fold_with(consumer.into_folder()).complete() |
| 438 |
} |
| 439 |
} |
| 440 |
} |
| 441 |
|
| 442 |
/// A variant of [`bridge_producer_consumer`] where the producer is an unindexed producer. |
| 443 |
/// |
| 444 |
/// [`bridge_producer_consumer`]: fn.bridge_producer_consumer.html |
| 445 |
pub fn bridge_unindexed<P, C>(producer: P, consumer: C) -> C::Result |
| 446 |
where |
| 447 |
P: UnindexedProducer, |
| 448 |
C: UnindexedConsumer<P::Item>, |
| 449 |
{ |
| 450 |
let splitter = Splitter::new(); |
| 451 |
bridge_unindexed_producer_consumer(false, splitter, producer, consumer) |
| 452 |
} |
| 453 |
|
| 454 |
fn bridge_unindexed_producer_consumer<P, C>( |
| 455 |
migrated: bool, |
| 456 |
mut splitter: Splitter, |
| 457 |
producer: P, |
| 458 |
consumer: C, |
| 459 |
) -> C::Result |
| 460 |
where |
| 461 |
P: UnindexedProducer, |
| 462 |
C: UnindexedConsumer<P::Item>, |
| 463 |
{ |
| 464 |
if consumer.full() { |
| 465 |
consumer.into_folder().complete() |
| 466 |
} else if splitter.try_split(migrated) { |
| 467 |
match producer.split() { |
| 468 |
(left_producer, Some(right_producer)) => { |
| 469 |
let (reducer, left_consumer, right_consumer) = |
| 470 |
(consumer.to_reducer(), consumer.split_off_left(), consumer); |
| 471 |
let bridge = bridge_unindexed_producer_consumer; |
| 472 |
let (left_result, right_result) = join_context( |
| 473 |
|context| bridge(context.migrated(), splitter, left_producer, left_consumer), |
| 474 |
|context| bridge(context.migrated(), splitter, right_producer, right_consumer), |
| 475 |
); |
| 476 |
reducer.reduce(left_result, right_result) |
| 477 |
} |
| 478 |
(producer, None) => producer.fold_with(consumer.into_folder()).complete(), |
| 479 |
} |
| 480 |
} else { |
| 481 |
producer.fold_with(consumer.into_folder()).complete() |
| 482 |
} |
| 483 |
} |