| 1 |
# Parallel Iterators |
| 2 |
|
| 3 |
These are some notes on the design of the parallel iterator traits. |
| 4 |
This file does not describe how to **use** parallel iterators. |
| 5 |
|
| 6 |
## The challenge |
| 7 |
|
| 8 |
Parallel iterators are more complicated than sequential iterators. |
| 9 |
The reason is that they have to be able to split themselves up and |
| 10 |
operate in parallel across the two halves. |
| 11 |
|
| 12 |
The current design for parallel iterators has two distinct modes in |
| 13 |
which they can be used; as we will see, not all iterators support both |
| 14 |
modes (which is why there are two): |
| 15 |
|
| 16 |
- **Pull mode** (the `Producer` and `UnindexedProducer` traits): in this mode, |
| 17 |
the iterator is asked to produce the next item using a call to `next`. This |
| 18 |
is basically like a normal iterator, but with a twist: you can split the |
| 19 |
iterator in half to produce disjoint items in separate threads. |
| 20 |
- in the `Producer` trait, splitting is done with `split_at`, which accepts |
| 21 |
an index where the split should be performed. Only indexed iterators can |
| 22 |
work in this mode, as they know exactly how much data they will produce, |
| 23 |
and how to locate the requested index. |
| 24 |
- in the `UnindexedProducer` trait, splitting is done with `split`, which |
| 25 |
simply requests that the producer divide itself *approximately* in half. |
| 26 |
This is useful when the exact length and/or layout is unknown, as with |
| 27 |
`String` characters, or when the length might exceed `usize`, as with |
| 28 |
`Range<u64>` on 32-bit platforms. |
| 29 |
- In theory, any `Producer` could act unindexed, but we don't currently |
| 30 |
use that possibility. When you know the exact length, a `split` can |
| 31 |
simply be implemented as `split_at(length/2)`. |
| 32 |
- **Push mode** (the `Consumer` and `UnindexedConsumer` traits): in |
| 33 |
this mode, the iterator instead is *given* each item in turn, which |
| 34 |
is then processed. This is the opposite of a normal iterator. It's |
| 35 |
more like a `for_each` call: each time a new item is produced, the |
| 36 |
`consume` method is called with that item. (The traits themselves are |
| 37 |
a bit more complex, as they support state that can be threaded |
| 38 |
through and ultimately reduced.) Like producers, there are two |
| 39 |
variants of consumers which differ in how the split is performed: |
| 40 |
- in the `Consumer` trait, splitting is done with `split_at`, which |
| 41 |
accepts an index where the split should be performed. All |
| 42 |
iterators can work in this mode. The resulting halves thus have an |
| 43 |
idea about how much data they expect to consume. |
| 44 |
- in the `UnindexedConsumer` trait, splitting is done with |
| 45 |
`split_off_left`. There is no index: the resulting halves must be |
| 46 |
prepared to process any amount of data, and they don't know where that |
| 47 |
data falls in the overall stream. |
| 48 |
- Not all consumers can operate in this mode. It works for |
| 49 |
`for_each` and `reduce`, for example, but it does not work for |
| 50 |
`collect_into_vec`, since in that case the position of each item is |
| 51 |
important for knowing where it ends up in the target collection. |
| 52 |
|
| 53 |
## How iterator execution proceeds |
| 54 |
|
| 55 |
We'll walk through this example iterator chain to start. This chain |
| 56 |
demonstrates more-or-less the full complexity of what can happen. |
| 57 |
|
| 58 |
```rust |
| 59 |
vec1.par_iter() |
| 60 |
.zip(vec2.par_iter()) |
| 61 |
.flat_map(some_function) |
| 62 |
.for_each(some_other_function) |
| 63 |
``` |
| 64 |
|
| 65 |
To handle an iterator chain, we start by creating consumers. This |
| 66 |
works from the end. So in this case, the call to `for_each` is the |
| 67 |
final step, so it will create a `ForEachConsumer` that, given an item, |
| 68 |
just calls `some_other_function` with that item. (`ForEachConsumer` is |
| 69 |
a very simple consumer because it doesn't need to thread any state |
| 70 |
between items at all.) |
| 71 |
|
| 72 |
Now, the `for_each` call will pass this consumer to the base iterator, |
| 73 |
which is the `flat_map`. It will do this by calling the `drive_unindexed` |
| 74 |
method on the `ParallelIterator` trait. `drive_unindexed` basically |
| 75 |
says "produce items for this iterator and feed them to this consumer"; |
| 76 |
it only works for unindexed consumers. |
| 77 |
|
| 78 |
(As an aside, it is interesting that only some consumers can work in |
| 79 |
unindexed mode, but all producers can *drive* an unindexed consumer. |
| 80 |
In contrast, only some producers can drive an *indexed* consumer, but |
| 81 |
all consumers can be supplied indexes. Isn't variance neat.) |
| 82 |
|
| 83 |
As it happens, `FlatMap` only works with unindexed consumers anyway. |
| 84 |
This is because flat-map basically has no idea how many items it will |
| 85 |
produce. If you ask flat-map to produce the 22nd item, it can't do it, |
| 86 |
at least not without some intermediate state. It doesn't know whether |
| 87 |
processing the first item will create 1 item, 3 items, or 100; |
| 88 |
therefore, to produce an arbitrary item, it would basically just have |
| 89 |
to start at the beginning and execute sequentially, which is not what |
| 90 |
we want. But for unindexed consumers, this doesn't matter, since they |
| 91 |
don't need to know how much data they will get. |
| 92 |
|
| 93 |
Therefore, `FlatMap` can wrap the `ForEachConsumer` with a |
| 94 |
`FlatMapConsumer` that feeds to it. This `FlatMapConsumer` will be |
| 95 |
given one item. It will then invoke `some_function` to get a parallel |
| 96 |
iterator out. It will then ask this new parallel iterator to drive the |
| 97 |
`ForEachConsumer`. The `drive_unindexed` method on `flat_map` can then |
| 98 |
pass the `FlatMapConsumer` up the chain to the previous item, which is |
| 99 |
`zip`. At this point, something interesting happens. |
| 100 |
|
| 101 |
## Switching from push to pull mode |
| 102 |
|
| 103 |
If you think about `zip`, it can't really be implemented as a |
| 104 |
consumer, at least not without an intermediate thread and some |
| 105 |
channels or something (or maybe coroutines). The problem is that it |
| 106 |
has to walk two iterators *in lockstep*. Basically, it can't call two |
| 107 |
`drive` methods simultaneously, it can only call one at a time. So at |
| 108 |
this point, the `zip` iterator needs to switch from *push mode* into |
| 109 |
*pull mode*. |
| 110 |
|
| 111 |
You'll note that `Zip` is only usable if its inputs implement |
| 112 |
`IndexedParallelIterator`, meaning that they can produce data starting |
| 113 |
at random points in the stream. This need to switch to push mode is |
| 114 |
exactly why. If we want to split a zip iterator at position 22, we |
| 115 |
need to be able to start zipping items from index 22 right away, |
| 116 |
without having to start from index 0. |
| 117 |
|
| 118 |
Anyway, so at this point, the `drive_unindexed` method for `Zip` stops |
| 119 |
creating consumers. Instead, it creates a *producer*, a `ZipProducer`, |
| 120 |
to be exact, and calls the `bridge` function in the `internals` |
| 121 |
module. Creating a `ZipProducer` will in turn create producers for |
| 122 |
the two iterators being zipped. This is possible because they both |
| 123 |
implement `IndexedParallelIterator`. |
| 124 |
|
| 125 |
The `bridge` function will then connect the consumer, which is |
| 126 |
handling the `flat_map` and `for_each`, with the producer, which is |
| 127 |
handling the `zip` and its predecessors. It will split down until the |
| 128 |
chunks seem reasonably small, then pull items from the producer and |
| 129 |
feed them to the consumer. |
| 130 |
|
| 131 |
## The base case |
| 132 |
|
| 133 |
The other time that `bridge` gets used is when we bottom out in an |
| 134 |
indexed producer, such as a slice or range. There is also a |
| 135 |
`bridge_unindexed` equivalent for - you guessed it - unindexed producers, |
| 136 |
such as string characters. |
| 137 |
|
| 138 |
<a name="producer-callback"> |
| 139 |
|
| 140 |
## What on earth is `ProducerCallback`? |
| 141 |
|
| 142 |
We saw that when you call a parallel action method like |
| 143 |
`par_iter.reduce()`, that will create a "reducing" consumer and then |
| 144 |
invoke `par_iter.drive_unindexed()` (or `par_iter.drive()`) as |
| 145 |
appropriate. This may create yet more consumers as we proceed up the |
| 146 |
parallel iterator chain. But at some point we're going to get to the |
| 147 |
start of the chain, or to a parallel iterator (like `zip()`) that has |
| 148 |
to coordinate multiple inputs. At that point, we need to start |
| 149 |
converting parallel iterators into producers. |
| 150 |
|
| 151 |
The way we do this is by invoking the method `with_producer()`, defined on |
| 152 |
`IndexedParallelIterator`. This is a callback scheme. In an ideal world, |
| 153 |
it would work like this: |
| 154 |
|
| 155 |
```rust |
| 156 |
base_iter.with_producer(|base_producer| { |
| 157 |
// here, `base_producer` is the producer for `base_iter` |
| 158 |
}); |
| 159 |
``` |
| 160 |
|
| 161 |
In that case, we could implement a combinator like `map()` by getting |
| 162 |
the producer for the base iterator, wrapping it to make our own |
| 163 |
`MapProducer`, and then passing that to the callback. Something like |
| 164 |
this: |
| 165 |
|
| 166 |
```rust |
| 167 |
struct MapProducer<'f, P, F: 'f> { |
| 168 |
base: P, |
| 169 |
map_op: &'f F, |
| 170 |
} |
| 171 |
|
| 172 |
impl<I, F> IndexedParallelIterator for Map<I, F> |
| 173 |
where I: IndexedParallelIterator, |
| 174 |
F: MapOp<I::Item>, |
| 175 |
{ |
| 176 |
fn with_producer<CB>(self, callback: CB) -> CB::Output { |
| 177 |
let map_op = &self.map_op; |
| 178 |
self.base_iter.with_producer(|base_producer| { |
| 179 |
// Here `producer` is the producer for `self.base_iter`. |
| 180 |
// Wrap that to make a `MapProducer` |
| 181 |
let map_producer = MapProducer { |
| 182 |
base: base_producer, |
| 183 |
map_op: map_op |
| 184 |
}; |
| 185 |
|
| 186 |
// invoke the callback with the wrapped version |
| 187 |
callback(map_producer) |
| 188 |
}); |
| 189 |
} |
| 190 |
}); |
| 191 |
``` |
| 192 |
|
| 193 |
This example demonstrates some of the power of the callback scheme. |
| 194 |
It winds up being a very flexible setup. For one thing, it means we |
| 195 |
can take ownership of `par_iter`; we can then in turn give ownership |
| 196 |
away of its bits and pieces into the producer (this is very useful if |
| 197 |
the iterator owns an `&mut` slice, for example), or create shared |
| 198 |
references and put *those* in the producer. In the case of map, for |
| 199 |
example, the parallel iterator owns the `map_op`, and we borrow |
| 200 |
references to it which we then put into the `MapProducer` (this means |
| 201 |
the `MapProducer` can easily split itself and share those references). |
| 202 |
The `with_producer` method can also create resources that are needed |
| 203 |
during the parallel execution, since the producer does not have to be |
| 204 |
returned. |
| 205 |
|
| 206 |
Unfortunately there is a catch. We can't actually use closures the way |
| 207 |
I showed you. To see why, think about the type that `map_producer` |
| 208 |
would have to have. If we were going to write the `with_producer` |
| 209 |
method using a closure, it would have to look something like this: |
| 210 |
|
| 211 |
```rust |
| 212 |
pub trait IndexedParallelIterator: ParallelIterator { |
| 213 |
type Producer; |
| 214 |
fn with_producer<CB, R>(self, callback: CB) -> R |
| 215 |
where CB: FnOnce(Self::Producer) -> R; |
| 216 |
... |
| 217 |
} |
| 218 |
``` |
| 219 |
|
| 220 |
Note that we had to add this associated type `Producer` so that |
| 221 |
we could specify the argument of the callback to be `Self::Producer`. |
| 222 |
Now, imagine trying to write that `MapProducer` impl using this style: |
| 223 |
|
| 224 |
```rust |
| 225 |
impl<I, F> IndexedParallelIterator for Map<I, F> |
| 226 |
where I: IndexedParallelIterator, |
| 227 |
F: MapOp<I::Item>, |
| 228 |
{ |
| 229 |
type MapProducer = MapProducer<'f, P::Producer, F>; |
| 230 |
// ^^ wait, what is this `'f`? |
| 231 |
|
| 232 |
fn with_producer<CB, R>(self, callback: CB) -> R |
| 233 |
where CB: FnOnce(Self::Producer) -> R |
| 234 |
{ |
| 235 |
let map_op = &self.map_op; |
| 236 |
// ^^^^^^ `'f` is (conceptually) the lifetime of this reference, |
| 237 |
// so it will be different for each call to `with_producer`! |
| 238 |
} |
| 239 |
} |
| 240 |
``` |
| 241 |
|
| 242 |
This may look familiar to you: it's the same problem that we have |
| 243 |
trying to define an `Iterable` trait. Basically, the producer type |
| 244 |
needs to include a lifetime (here, `'f`) that refers to the body of |
| 245 |
`with_producer` and hence is not in scope at the impl level. |
| 246 |
|
| 247 |
If we had [associated type constructors][1598], we could solve this |
| 248 |
problem that way. But there is another solution. We can use a |
| 249 |
dedicated callback trait like `ProducerCallback`, instead of `FnOnce`: |
| 250 |
|
| 251 |
[1598]: https://github.com/rust-lang/rfcs/pull/1598 |
| 252 |
|
| 253 |
```rust |
| 254 |
pub trait ProducerCallback<T> { |
| 255 |
type Output; |
| 256 |
fn callback<P>(self, producer: P) -> Self::Output |
| 257 |
where P: Producer<Item=T>; |
| 258 |
} |
| 259 |
``` |
| 260 |
|
| 261 |
Using this trait, the signature of `with_producer()` looks like this: |
| 262 |
|
| 263 |
```rust |
| 264 |
fn with_producer<CB: ProducerCallback<Self::Item>>(self, callback: CB) -> CB::Output; |
| 265 |
``` |
| 266 |
|
| 267 |
Notice that this signature **never has to name the producer type** -- |
| 268 |
there is no associated type `Producer` anymore. This is because the |
| 269 |
`callback()` method is generically over **all** producers `P`. |
| 270 |
|
| 271 |
The problem is that now the `||` sugar doesn't work anymore. So we |
| 272 |
have to manually create the callback struct, which is a mite tedious. |
| 273 |
So our `MapProducer` code looks like this: |
| 274 |
|
| 275 |
```rust |
| 276 |
impl<I, F> IndexedParallelIterator for Map<I, F> |
| 277 |
where I: IndexedParallelIterator, |
| 278 |
F: MapOp<I::Item>, |
| 279 |
{ |
| 280 |
fn with_producer<CB>(self, callback: CB) -> CB::Output |
| 281 |
where CB: ProducerCallback<Self::Item> |
| 282 |
{ |
| 283 |
return self.base.with_producer(Callback { callback: callback, map_op: self.map_op }); |
| 284 |
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |
| 285 |
// Manual version of the closure sugar: create an instance |
| 286 |
// of a struct that implements `ProducerCallback`. |
| 287 |
|
| 288 |
// The struct declaration. Each field is something that need to capture from the |
| 289 |
// creating scope. |
| 290 |
struct Callback<CB, F> { |
| 291 |
callback: CB, |
| 292 |
map_op: F, |
| 293 |
} |
| 294 |
|
| 295 |
// Implement the `ProducerCallback` trait. This is pure boilerplate. |
| 296 |
impl<T, F, CB> ProducerCallback<T> for Callback<CB, F> |
| 297 |
where F: MapOp<T>, |
| 298 |
CB: ProducerCallback<F::Output> |
| 299 |
{ |
| 300 |
type Output = CB::Output; |
| 301 |
|
| 302 |
fn callback<P>(self, base: P) -> CB::Output |
| 303 |
where P: Producer<Item=T> |
| 304 |
{ |
| 305 |
// The body of the closure is here: |
| 306 |
let producer = MapProducer { base: base, |
| 307 |
map_op: &self.map_op }; |
| 308 |
self.callback.callback(producer) |
| 309 |
} |
| 310 |
} |
| 311 |
} |
| 312 |
} |
| 313 |
``` |
| 314 |
|
| 315 |
OK, a bit tedious, but it works! |