Debian Codegraph @

.cargo/vendor/rayon/src/iter/par_bridge.rs

raw
1 #[cfg(not(feature = "web_spin_lock"))]
2 use std::sync::Mutex;
3
4 #[cfg(feature = "web_spin_lock")]
5 use wasm_sync::Mutex;
6
7 use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
8
9 use crate::iter::plumbing::{bridge_unindexed, Folder, UnindexedConsumer, UnindexedProducer};
10 use crate::iter::ParallelIterator;
11 use crate::{current_num_threads, current_thread_index};
12
13 /// Conversion trait to convert an `Iterator` to a `ParallelIterator`.
14 ///
15 /// This creates a "bridge" from a sequential iterator to a parallel one, by distributing its items
16 /// across the Rayon thread pool. This has the advantage of being able to parallelize just about
17 /// anything, but the resulting `ParallelIterator` can be less efficient than if you started with
18 /// `par_iter` instead. However, it can still be useful for iterators that are difficult to
19 /// parallelize by other means, like channels or file or network I/O.
20 ///
21 /// Iterator items are pulled by `next()` one at a time, synchronized from each thread that is
22 /// ready for work, so this may become a bottleneck if the serial iterator can't keep up with the
23 /// parallel demand. The items are not buffered by `IterBridge`, so it's fine to use this with
24 /// large or even unbounded iterators.
25 ///
26 /// The resulting iterator is not guaranteed to keep the order of the original iterator.
27 ///
28 /// # Examples
29 ///
30 /// To use this trait, take an existing `Iterator` and call `par_bridge` on it. After that, you can
31 /// use any of the `ParallelIterator` methods:
32 ///
33 /// ```
34 /// use rayon::iter::ParallelBridge;
35 /// use rayon::prelude::ParallelIterator;
36 /// use std::sync::mpsc::channel;
37 ///
38 /// let rx = {
39 /// let (tx, rx) = channel();
40 ///
41 /// tx.send("one!");
42 /// tx.send("two!");
43 /// tx.send("three!");
44 ///
45 /// rx
46 /// };
47 ///
48 /// let mut output: Vec<&'static str> = rx.into_iter().par_bridge().collect();
49 /// output.sort_unstable();
50 ///
51 /// assert_eq!(&*output, &["one!", "three!", "two!"]);
52 /// ```
53 pub trait ParallelBridge: Sized {
54 /// Creates a bridge from this type to a `ParallelIterator`.
55 fn par_bridge(self) -> IterBridge<Self>;
56 }
57
58 impl<T: Iterator + Send> ParallelBridge for T
59 where
60 T::Item: Send,
61 {
62 fn par_bridge(self) -> IterBridge<Self> {
63 IterBridge { iter: self }
64 }
65 }
66
67 /// `IterBridge` is a parallel iterator that wraps a sequential iterator.
68 ///
69 /// This type is created when using the `par_bridge` method on `ParallelBridge`. See the
70 /// [`ParallelBridge`] documentation for details.
71 ///
72 /// [`ParallelBridge`]: trait.ParallelBridge.html
73 #[derive(Debug, Clone)]
74 pub struct IterBridge<Iter> {
75 iter: Iter,
76 }
77
78 impl<Iter: Iterator + Send> ParallelIterator for IterBridge<Iter>
79 where
80 Iter::Item: Send,
81 {
82 type Item = Iter::Item;
83
84 fn drive_unindexed<C>(self, consumer: C) -> C::Result
85 where
86 C: UnindexedConsumer<Self::Item>,
87 {
88 let num_threads = current_num_threads();
89 let threads_started: Vec<_> = (0..num_threads).map(|_| AtomicBool::new(false)).collect();
90
91 bridge_unindexed(
92 &IterParallelProducer {
93 split_count: AtomicUsize::new(num_threads),
94 iter: Mutex::new(self.iter.fuse()),
95 threads_started: &threads_started,
96 },
97 consumer,
98 )
99 }
100 }
101
102 struct IterParallelProducer<'a, Iter> {
103 split_count: AtomicUsize,
104 iter: Mutex<std::iter::Fuse<Iter>>,
105 threads_started: &'a [AtomicBool],
106 }
107
108 impl<Iter: Iterator + Send> UnindexedProducer for &IterParallelProducer<'_, Iter> {
109 type Item = Iter::Item;
110
111 fn split(self) -> (Self, Option<Self>) {
112 // Check if the iterator is exhausted
113 let update = self
114 .split_count
115 .fetch_update(Ordering::Relaxed, Ordering::Relaxed, |c| c.checked_sub(1));
116 (self, update.is_ok().then_some(self))
117 }
118
119 fn fold_with<F>(self, mut folder: F) -> F
120 where
121 F: Folder<Self::Item>,
122 {
123 // Guard against work-stealing-induced recursion, in case `Iter::next()`
124 // calls rayon internally, so we don't deadlock our mutex. We might also
125 // be recursing via `folder` methods, which doesn't present a mutex hazard,
126 // but it's lower overhead for us to just check this once, rather than
127 // updating additional shared state on every mutex lock/unlock.
128 // (If this isn't a rayon thread, then there's no work-stealing anyway...)
129 if let Some(i) = current_thread_index() {
130 // Note: If the number of threads in the pool ever grows dynamically, then
131 // we'll end up sharing flags and may falsely detect recursion -- that's
132 // still fine for overall correctness, just not optimal for parallelism.
133 let thread_started = &self.threads_started[i % self.threads_started.len()];
134 if thread_started.swap(true, Ordering::Relaxed) {
135 // We can't make progress with a nested mutex, so just return and let
136 // the outermost loop continue with the rest of the iterator items.
137 return folder;
138 }
139 }
140
141 loop {
142 if let Ok(mut iter) = self.iter.lock() {
143 if let Some(it) = iter.next() {
144 drop(iter);
145 folder = folder.consume(it);
146 if folder.full() {
147 return folder;
148 }
149 } else {
150 return folder;
151 }
152 } else {
153 // any panics from other threads will have been caught by the pool,
154 // and will be re-thrown when joined - just exit
155 return folder;
156 }
157 }
158 }
159 }