Debian Codegraph @

.cargo/vendor/rayon/FAQ.md

raw
1 # Rayon FAQ
2
3 This file is for general questions that don't fit into the README or
4 crate docs.
5
6 ## How many threads will Rayon spawn?
7
8 By default, Rayon uses the same number of threads as the number of
9 CPUs available. Note that on systems with hyperthreading enabled this
10 equals the number of logical cores and not the physical ones.
11
12 If you want to alter the number of threads spawned, you can set the
13 environmental variable `RAYON_NUM_THREADS` to the desired number of
14 threads or use the
15 [`ThreadPoolBuilder::build_global` function](https://docs.rs/rayon/*/rayon/struct.ThreadPoolBuilder.html#method.build_global)
16 method.
17
18 ## How does Rayon balance work between threads?
19
20 Behind the scenes, Rayon uses a technique called **work stealing** to
21 try and dynamically ascertain how much parallelism is available and
22 exploit it. The idea is very simple: we always have a pool of worker
23 threads available, waiting for some work to do. When you call `join`
24 the first time, we shift over into that pool of threads. But if you
25 call `join(a, b)` from a worker thread W, then W will place `b` into
26 its work queue, advertising that this is work that other worker
27 threads might help out with. W will then start executing `a`.
28
29 While W is busy with `a`, other threads might come along and take `b`
30 from its queue. That is called *stealing* `b`. Once `a` is done, W
31 checks whether `b` was stolen by another thread and, if not, executes
32 `b` itself. If W runs out of jobs in its own queue, it will look
33 through the other threads' queues and try to steal work from them.
34
35 This technique is not new. It was first introduced by the
36 [Cilk project][cilk], done at MIT in the late nineties. The name Rayon
37 is an homage to that work.
38
39 [cilk]: http://supertech.csail.mit.edu/cilk/
40
41 ## What should I do if I use `Rc`, `Cell`, `RefCell` or other non-Send-and-Sync types?
42
43 There are a number of non-threadsafe types in the Rust standard library,
44 and if your code is using them, you will not be able to combine it
45 with Rayon. Similarly, even if you don't have such types, but you try
46 to have multiple closures mutating the same state, you will get
47 compilation errors; for example, this function won't work, because
48 both closures access `slice`:
49
50 ```rust
51 /// Increment all values in slice.
52 fn increment_all(slice: &mut [i32]) {
53 rayon::join(|| process(slice), || process(slice));
54 }
55 ```
56
57 The correct way to resolve such errors will depend on the case. Some
58 cases are easy: for example, uses of [`Rc`] can typically be replaced
59 with [`Arc`], which is basically equivalent, but thread-safe.
60
61 Code that uses `Cell` or `RefCell`, however, can be somewhat more complicated.
62 If you can refactor your code to avoid those types, that is often the best way
63 forward, but otherwise, you can try to replace those types with their threadsafe
64 equivalents:
65
66 - `Cell` -- replacement: `AtomicUsize`, `AtomicBool`, etc
67 - `RefCell` -- replacement: `RwLock`, or perhaps `Mutex`
68
69 However, you have to be wary! The parallel versions of these types
70 have different atomicity guarantees. For example, with a `Cell`, you
71 can increment a counter like so:
72
73 ```rust
74 let value = counter.get();
75 counter.set(value + 1);
76 ```
77
78 But when you use the equivalent `AtomicUsize` methods, you are
79 actually introducing a potential race condition (not a data race,
80 technically, but it can be an awfully fine distinction):
81
82 ```rust
83 let value = tscounter.load(Ordering::SeqCst);
84 tscounter.store(value + 1, Ordering::SeqCst);
85 ```
86
87 You can already see that the `AtomicUsize` API is a bit more complex,
88 as it requires you to specify an
89 [ordering](https://doc.rust-lang.org/std/sync/atomic/enum.Ordering.html). (I
90 won't go into the details on ordering here, but suffice to say that if
91 you don't know what an ordering is, and probably even if you do, you
92 should use `Ordering::SeqCst`.) The danger in this parallel version of
93 the counter is that other threads might be running at the same time
94 and they could cause our counter to get out of sync. For example, if
95 we have two threads, then they might both execute the "load" before
96 either has a chance to execute the "store":
97
98 ```
99 Thread 1 Thread 2
100 let value = tscounter.load(Ordering::SeqCst);
101 // value = X let value = tscounter.load(Ordering::SeqCst);
102 // value = X
103 tscounter.store(value+1); tscounter.store(value+1);
104 // tscounter = X+1 // tscounter = X+1
105 ```
106
107 Now even though we've had two increments, we'll only increase the
108 counter by one! Even though we've got no data race, this is still
109 probably not the result we wanted. The problem here is that the `Cell`
110 API doesn't make clear the scope of a "transaction" -- that is, the
111 set of reads/writes that should occur atomically. In this case, we
112 probably wanted the get/set to occur together.
113
114 In fact, when using the `Atomic` types, you very rarely want a plain
115 `load` or plain `store`. You probably want the more complex
116 operations. A counter, for example, would use `fetch_add` to
117 atomically load and increment the value in one step. Compare-and-swap
118 is another popular building block.
119
120 A similar problem can arise when converting `RefCell` to `RwLock`, but
121 it is somewhat less likely, because the `RefCell` API does in fact
122 have a notion of a transaction: the scope of the handle returned by
123 `borrow` or `borrow_mut`. So if you convert each call to `borrow` to
124 `read` (and `borrow_mut` to `write`), things will mostly work fine in
125 a parallel setting, but there can still be changes in behavior.
126 Consider using a `handle: RefCell<Vec<i32>>` like:
127
128 ```rust
129 let len = handle.borrow().len();
130 for i in 0 .. len {
131 let data = handle.borrow()[i];
132 println!("{}", data);
133 }
134 ```
135
136 In sequential code, we know that this loop is safe. But if we convert
137 this to parallel code with an `RwLock`, we do not: this is because
138 another thread could come along and do
139 `handle.write().unwrap().pop()`, and thus change the length of the
140 vector. In fact, even in *sequential* code, using very small borrow
141 sections like this is an anti-pattern: you ought to be enclosing the
142 entire transaction together, like so:
143
144 ```rust
145 let vec = handle.borrow();
146 let len = vec.len();
147 for i in 0 .. len {
148 let data = vec[i];
149 println!("{}", data);
150 }
151 ```
152
153 Or, even better, using an iterator instead of indexing:
154
155 ```rust
156 let vec = handle.borrow();
157 for data in vec {
158 println!("{}", data);
159 }
160 ```
161
162 There are several reasons to prefer one borrow over many. The most
163 obvious is that it is more efficient, since each borrow has to perform
164 some safety checks. But it's also more reliable: suppose we modified
165 the loop above to not just print things out, but also call into a
166 helper function:
167
168 ```rust
169 let vec = handle.borrow();
170 for data in vec {
171 helper(...);
172 }
173 ```
174
175 And now suppose, independently, this helper fn evolved and had to pop
176 something off of the vector:
177
178 ```rust
179 fn helper(...) {
180 handle.borrow_mut().pop();
181 }
182 ```
183
184 Under the old model, where we did lots of small borrows, this would
185 yield precisely the same error that we saw in parallel land using an
186 `RwLock`: the length would be out of sync and our indexing would fail
187 (note that in neither case would there be an actual *data race* and
188 hence there would never be undefined behavior). But now that we use a
189 single borrow, we'll see a borrow error instead, which is much easier
190 to diagnose, since it occurs at the point of the `borrow_mut`, rather
191 than downstream. Similarly, if we move to an `RwLock`, we'll find that
192 the code either deadlocks (if the write is on the same thread as the
193 read) or, if the write is on another thread, works just fine. Both of
194 these are preferable to random failures in my experience.
195
196 ## But wait, isn't Rust supposed to free me from this kind of thinking?
197
198 You might think that Rust is supposed to mean that you don't have to
199 think about atomicity at all. In fact, if you avoid interior
200 mutability (`Cell` and `RefCell` in a sequential setting, or
201 `AtomicUsize`, `RwLock`, `Mutex`, et al. in parallel code), then this
202 is true: the type system will basically guarantee that you don't have
203 to think about atomicity at all. But often there are times when you
204 WANT threads to interleave in the ways I showed above.
205
206 Consider for example when you are conducting a search in parallel, say
207 to find the shortest route. To avoid fruitless search, you might want
208 to keep a cell with the shortest route you've found thus far. This
209 way, when you are searching down some path that's already longer than
210 this shortest route, you can just stop and avoid wasted effort. In
211 sequential land, you might model this "best result" as a shared value
212 like `Rc<Cell<usize>>` (here the `usize` represents the length of best
213 path found so far); in parallel land, you'd use a `Arc<AtomicUsize>`.
214 Now we can make our search function look like:
215
216 ```rust
217 fn search(path: &Path, cost_so_far: usize, best_cost: &Arc<AtomicUsize>) {
218 if cost_so_far >= best_cost.load(Ordering::SeqCst) {
219 return;
220 }
221 ...
222 best_cost.store(...);
223 }
224 ```
225
226 Now in this case, we really WANT to see results from other threads
227 interjected into our execution!