par_iter/iter/
splitter.rs

1use std::fmt::{self, Debug};
2
3use super::{plumbing::*, *};
4
5/// The `split` function takes arbitrary data and a closure that knows how to
6/// split it, and turns this into a `ParallelIterator`.
7///
8/// # Examples
9///
10/// As a simple example, Rayon can recursively split ranges of indices
11///
12/// ```
13/// use par_iter::iter;
14/// use par_iter::prelude::*;
15/// use std::ops::Range;
16///
17///
18/// // We define a range of indices as follows
19/// type Range1D = Range<usize>;
20///
21/// // Splitting it in two can be done like this
22/// fn split_range1(r: Range1D) -> (Range1D, Option<Range1D>) {
23///     // We are mathematically unable to split the range if there is only
24///     // one point inside of it, but we could stop splitting before that.
25///     if r.end - r.start <= 1 { return (r, None); }
26///
27///     // Here, our range is considered large enough to be splittable
28///     let midpoint = r.start + (r.end - r.start) / 2;
29///     (r.start..midpoint, Some(midpoint..r.end))
30/// }
31///
32/// // By using iter::split, Rayon will split the range until it has enough work
33/// // to feed the CPU cores, then give us the resulting sub-ranges
34/// iter::split(0..4096, split_range1).for_each(|sub_range| {
35///     // As our initial range had a power-of-two size, the final sub-ranges
36///     // should have power-of-two sizes too
37///     assert!((sub_range.end - sub_range.start).is_power_of_two());
38/// });
39/// ```
40///
41/// This recursive splitting can be extended to two or three dimensions,
42/// to reproduce a classic "block-wise" parallelization scheme of graphics and
43/// numerical simulations:
44///
45/// ```
46/// # use par_iter::iter;
47/// # use par_iter::prelude::*;
48/// # use std::ops::Range;
49/// # type Range1D = Range<usize>;
50/// # fn split_range1(r: Range1D) -> (Range1D, Option<Range1D>) {
51/// #     if r.end - r.start <= 1 { return (r, None); }
52/// #     let midpoint = r.start + (r.end - r.start) / 2;
53/// #     (r.start..midpoint, Some(midpoint..r.end))
54/// # }
55/// #
56/// // A two-dimensional range of indices can be built out of two 1D ones
57/// struct Range2D {
58///     // Range of horizontal indices
59///     pub rx: Range1D,
60///
61///     // Range of vertical indices
62///     pub ry: Range1D,
63/// }
64///
65/// // We want to recursively split them by the largest dimension until we have
66/// // enough sub-ranges to feed our mighty multi-core CPU. This function
67/// // carries out one such split.
68/// fn split_range2(r2: Range2D) -> (Range2D, Option<Range2D>) {
69///     // Decide on which axis (horizontal/vertical) the range should be split
70///     let width = r2.rx.end - r2.rx.start;
71///     let height = r2.ry.end - r2.ry.start;
72///     if width >= height {
73///         // This is a wide range, split it on the horizontal axis
74///         let (split_rx, ry) = (split_range1(r2.rx), r2.ry);
75///         let out1 = Range2D {
76///             rx: split_rx.0,
77///             ry: ry.clone(),
78///         };
79///         let out2 = split_rx.1.map(|rx| Range2D { rx, ry });
80///         (out1, out2)
81///     } else {
82///         // This is a tall range, split it on the vertical axis
83///         let (rx, split_ry) = (r2.rx, split_range1(r2.ry));
84///         let out1 = Range2D {
85///             rx: rx.clone(),
86///             ry: split_ry.0,
87///         };
88///         let out2 = split_ry.1.map(|ry| Range2D { rx, ry, });
89///         (out1, out2)
90///     }
91/// }
92///
93/// // Again, rayon can handle the recursive splitting for us
94/// let range = Range2D { rx: 0..800, ry: 0..600 };
95/// iter::split(range, split_range2).for_each(|sub_range| {
96///     // If the sub-ranges were indeed split by the largest dimension, then
97///     // if no dimension was twice larger than the other initially, this
98///     // property will remain true in the final sub-ranges.
99///     let width = sub_range.rx.end - sub_range.rx.start;
100///     let height = sub_range.ry.end - sub_range.ry.start;
101///     assert!((width / 2 <= height) && (height / 2 <= width));
102/// });
103/// ```
104pub fn split<D, S>(data: D, splitter: S) -> Split<D, S>
105where
106    D: Send,
107    S: Fn(D) -> (D, Option<D>) + Sync,
108{
109    Split { data, splitter }
110}
111
112/// `Split` is a parallel iterator using arbitrary data and a splitting
113/// function. This struct is created by the [`split()`] function.
114///
115/// [`split()`]: fn.split.html
116#[derive(Clone)]
117pub struct Split<D, S> {
118    data: D,
119    splitter: S,
120}
121
122impl<D: Debug, S> Debug for Split<D, S> {
123    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
124        f.debug_struct("Split").field("data", &self.data).finish()
125    }
126}
127
128impl<D, S> ParallelIterator for Split<D, S>
129where
130    D: Send,
131    S: Fn(D) -> (D, Option<D>) + Sync + Send,
132{
133    type Item = D;
134
135    fn drive_unindexed<C>(self, consumer: C) -> C::Result
136    where
137        C: UnindexedConsumer<Self::Item>,
138    {
139        let producer = SplitProducer {
140            data: self.data,
141            splitter: &self.splitter,
142        };
143        bridge_unindexed(producer, consumer)
144    }
145}
146
147struct SplitProducer<'a, D, S> {
148    data: D,
149    splitter: &'a S,
150}
151
152impl<'a, D, S> UnindexedProducer for SplitProducer<'a, D, S>
153where
154    D: Send,
155    S: Fn(D) -> (D, Option<D>) + Sync,
156{
157    type Item = D;
158
159    fn split(mut self) -> (Self, Option<Self>) {
160        let splitter = self.splitter;
161        let (left, right) = splitter(self.data);
162        self.data = left;
163        (self, right.map(|data| SplitProducer { data, splitter }))
164    }
165
166    fn fold_with<F>(self, folder: F) -> F
167    where
168        F: Folder<Self::Item>,
169    {
170        folder.consume(self.data)
171    }
172}
par_iter/iter/splitter.rs

par_iter/iter/
splitter.rs
