Tue, 31 Dec 2024 09:12:43 -0500
Try to have Field as member type in Mappings etc.
0 | 1 | |
2 | use std::collections::BinaryHeap; | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
3 | use std::cmp::{PartialOrd, Ord, Ordering, Ordering::*, max}; |
0 | 4 | use std::marker::PhantomData; |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
5 | use std::sync::{Arc, Mutex, MutexGuard, Condvar}; |
0 | 6 | use crate::types::*; |
5 | 7 | use crate::nanleast::NaNLeast; |
8 | use crate::sets::Cube; | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
9 | use crate::parallelism::{thread_pool_size, thread_pool}; |
0 | 10 | use super::support::*; |
11 | use super::bt::*; | |
12 | use super::aggregator::*; | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
13 | use crate::parallelism::TaskBudget; |
0 | 14 | |
15 | /// Trait for sorting [`Aggregator`]s for [`BT`] refinement. | |
16 | /// | |
5 | 17 | /// The sorting involves two sorting keys, the “upper” and the “lower” key. Any [`BT`] nodes |
0 | 18 | /// with upper key less the lower key of another are discarded from the refinement process. |
5 | 19 | /// Nodes with the highest upper sorting key are picked for refinement. |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
20 | pub trait AggregatorSorting : Sync + Send + 'static { |
0 | 21 | // Priority |
22 | type Agg : Aggregator; | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
23 | type Sort : Ord + Copy + std::fmt::Debug + Sync + Send; |
0 | 24 | |
25 | /// Returns lower sorting key | |
26 | fn sort_lower(aggregator : &Self::Agg) -> Self::Sort; | |
27 | ||
28 | /// Returns upper sorting key | |
29 | fn sort_upper(aggregator : &Self::Agg) -> Self::Sort; | |
30 | ||
5 | 31 | /// Returns a sorting key that is less than any other sorting key. |
0 | 32 | fn bottom() -> Self::Sort; |
33 | } | |
34 | ||
35 | /// An [`AggregatorSorting`] for [`Bounds`], using the upper/lower bound as the upper/lower key. | |
36 | /// | |
37 | /// See [`LowerBoundSorting`] for the opposite ordering. | |
38 | pub struct UpperBoundSorting<F : Float>(PhantomData<F>); | |
39 | ||
40 | /// An [`AggregatorSorting`] for [`Bounds`], using the upper/lower bound as the lower/upper key. | |
41 | /// | |
42 | /// See [`UpperBoundSorting`] for the opposite ordering. | |
43 | pub struct LowerBoundSorting<F : Float>(PhantomData<F>); | |
44 | ||
45 | impl<F : Float> AggregatorSorting for UpperBoundSorting<F> { | |
46 | type Agg = Bounds<F>; | |
47 | type Sort = NaNLeast<F>; | |
48 | ||
49 | #[inline] | |
50 | fn sort_lower(aggregator : &Bounds<F>) -> Self::Sort { NaNLeast(aggregator.lower()) } | |
51 | ||
52 | #[inline] | |
53 | fn sort_upper(aggregator : &Bounds<F>) -> Self::Sort { NaNLeast(aggregator.upper()) } | |
54 | ||
55 | #[inline] | |
56 | fn bottom() -> Self::Sort { NaNLeast(F::NEG_INFINITY) } | |
57 | } | |
58 | ||
59 | ||
60 | impl<F : Float> AggregatorSorting for LowerBoundSorting<F> { | |
61 | type Agg = Bounds<F>; | |
62 | type Sort = NaNLeast<F>; | |
63 | ||
64 | #[inline] | |
65 | fn sort_upper(aggregator : &Bounds<F>) -> Self::Sort { NaNLeast(-aggregator.lower()) } | |
66 | ||
67 | #[inline] | |
68 | fn sort_lower(aggregator : &Bounds<F>) -> Self::Sort { NaNLeast(-aggregator.upper()) } | |
69 | ||
70 | #[inline] | |
71 | fn bottom() -> Self::Sort { NaNLeast(F::NEG_INFINITY) } | |
72 | } | |
73 | ||
5 | 74 | /// Return type of [`Refiner::refine`]. |
75 | /// | |
76 | /// The parameter `R` is the result type of the refiner acting on an [`Aggregator`] of type `A`. | |
0 | 77 | pub enum RefinerResult<A : Aggregator, R> { |
5 | 78 | /// Indicates an insufficiently refined state: the [`BT`] needs to be further refined. |
0 | 79 | NeedRefinement, |
80 | /// Indicates a certain result `R`, stop refinement immediately. | |
81 | Certain(R), | |
82 | /// Indicates an uncertain result: continue refinement until candidates have been exhausted | |
83 | /// or a certain result found. | |
84 | Uncertain(A, R) | |
85 | } | |
86 | ||
87 | use RefinerResult::*; | |
88 | ||
5 | 89 | /// A `Refiner` is used to search a [`BT`], refining the subdivision when necessary. |
90 | /// | |
91 | /// The search is performed by [`BTSearch::search_and_refine`]. | |
92 | /// The `Refiner` is used to determine whether an [`Aggregator`] `A` stored in the [`BT`] is | |
93 | /// sufficiently refined within a [`Cube`], and in such a case, produce a desired result (e.g. | |
94 | /// a maximum value of a function). | |
81
d2acaaddd9af
Try to have Field as member type in Mappings etc.
Tuomo Valkonen <tuomov@iki.fi>
parents:
9
diff
changeset
|
95 | pub trait Refiner<A, G, const N : usize> : Sync + Send + 'static |
d2acaaddd9af
Try to have Field as member type in Mappings etc.
Tuomo Valkonen <tuomov@iki.fi>
parents:
9
diff
changeset
|
96 | where A : Aggregator, |
d2acaaddd9af
Try to have Field as member type in Mappings etc.
Tuomo Valkonen <tuomov@iki.fi>
parents:
9
diff
changeset
|
97 | G : SupportGenerator<N> { |
0 | 98 | |
5 | 99 | /// The result type of the refiner |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
100 | type Result : std::fmt::Debug + Sync + Send + 'static; |
5 | 101 | /// The sorting to be employed by [`BTSearch::search_and_refine`] on node aggregators |
102 | /// to detemrine node priority. | |
0 | 103 | type Sorting : AggregatorSorting<Agg = A>; |
104 | ||
5 | 105 | /// Determines whether `aggregator` is sufficiently refined within `domain`. |
106 | /// | |
107 | /// If the aggregator is sufficiently refined that the desired `Self::Result` can be produced, | |
108 | /// a [`RefinerResult`]`::Certain` or `Uncertain` should be returned, depending on | |
109 | /// the confidence of the solution. In the uncertain case an improved aggregator should also | |
110 | /// be included. If the result cannot be produced, `NeedRefinement` should be | |
111 | /// returned. | |
112 | /// | |
113 | /// For example, if the refiner is used to minimise a function presented by the `BT`, | |
114 | /// an `Uncertain` result can be used to return a local maximum of the function on `domain` | |
115 | /// The result can be claimed `Certain` if it is a global maximum. In that case the | |
116 | /// refinment will stop immediately. A `NeedRefinement` result indicates that the `aggregator` | |
117 | /// and/or `domain` are not sufficiently refined to compute a lcoal maximum of sufficient | |
118 | /// quality. | |
119 | /// | |
120 | /// The vector `data` stored all the data of the [`BT`] in the node corresponding to `domain`. | |
121 | /// The `generator` can be used to convert `data` into [`Support`]s. The parameter `step` | |
122 | /// counts the calls to `refine`, and can be used to stop the refinement when a maximum | |
123 | /// number of steps is reached. | |
0 | 124 | fn refine( |
125 | &self, | |
126 | aggregator : &A, | |
81
d2acaaddd9af
Try to have Field as member type in Mappings etc.
Tuomo Valkonen <tuomov@iki.fi>
parents:
9
diff
changeset
|
127 | domain : &Cube<G::Field, N>, |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
128 | data : &[G::Id], |
0 | 129 | generator : &G, |
130 | step : usize, | |
131 | ) -> RefinerResult<A, Self::Result>; | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
132 | |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
133 | /// Fuse two [`Self::Result`]s (needed in threaded refinement). |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
134 | fn fuse_results(r1 : &mut Self::Result, r2 : Self::Result); |
0 | 135 | } |
136 | ||
137 | /// Structure for tracking the refinement process in a [`BinaryHeap`]. | |
138 | struct RefinementInfo<'a, F, D, A, S, RResult, const N : usize, const P : usize> | |
139 | where F : Float, | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
140 | D : 'static, |
0 | 141 | A : Aggregator, |
142 | S : AggregatorSorting<Agg = A> { | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
143 | /// Domain of `node` |
0 | 144 | cube : Cube<F, N>, |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
145 | /// Node to be refined |
0 | 146 | node : &'a mut Node<F, D, A, N, P>, |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
147 | /// Result and improve aggregator for the [`Refiner`] |
0 | 148 | refiner_info : Option<(A, RResult)>, |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
149 | /// For [`AggregatorSorting`] being used for the type system |
0 | 150 | sorting : PhantomData<S>, |
151 | } | |
152 | ||
153 | impl<'a, F, D, A, S, RResult, const N : usize, const P : usize> | |
154 | RefinementInfo<'a, F, D, A, S, RResult, N, P> | |
155 | where F : Float, | |
156 | D : 'static, | |
157 | A : Aggregator, | |
158 | S : AggregatorSorting<Agg = A> { | |
159 | ||
160 | #[inline] | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
161 | fn with_aggregator<U>(&self, f : impl FnOnce(&A) -> U) -> U { |
0 | 162 | match self.refiner_info { |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
163 | Some((ref agg, _)) => f(agg), |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
164 | None => f(&self.node.aggregator), |
0 | 165 | } |
166 | } | |
167 | ||
168 | #[inline] | |
169 | fn sort_lower(&self) -> S::Sort { | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
170 | self.with_aggregator(S::sort_lower) |
0 | 171 | } |
172 | ||
173 | #[inline] | |
174 | fn sort_upper(&self) -> S::Sort { | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
175 | self.with_aggregator(S::sort_upper) |
0 | 176 | } |
177 | } | |
178 | ||
179 | impl<'a, F, D, A, S, RResult, const N : usize, const P : usize> PartialEq | |
180 | for RefinementInfo<'a, F, D, A, S, RResult, N, P> | |
181 | where F : Float, | |
182 | D : 'static, | |
183 | A : Aggregator, | |
184 | S : AggregatorSorting<Agg = A> { | |
185 | ||
186 | #[inline] | |
187 | fn eq(&self, other : &Self) -> bool { self.cmp(other) == Equal } | |
188 | } | |
189 | ||
190 | impl<'a, F, D, A, S, RResult, const N : usize, const P : usize> PartialOrd | |
191 | for RefinementInfo<'a, F, D, A, S, RResult, N, P> | |
192 | where F : Float, | |
193 | D : 'static, | |
194 | A : Aggregator, | |
195 | S : AggregatorSorting<Agg = A> { | |
196 | ||
197 | #[inline] | |
198 | fn partial_cmp(&self, other : &Self) -> Option<Ordering> { Some(self.cmp(other)) } | |
199 | } | |
200 | ||
201 | impl<'a, F, D, A, S, RResult, const N : usize, const P : usize> Eq | |
202 | for RefinementInfo<'a, F, D, A, S, RResult, N, P> | |
203 | where F : Float, | |
204 | D : 'static, | |
205 | A : Aggregator, | |
206 | S : AggregatorSorting<Agg = A> { | |
207 | } | |
208 | ||
209 | impl<'a, F, D, A, S, RResult, const N : usize, const P : usize> Ord | |
210 | for RefinementInfo<'a, F, D, A, S, RResult, N, P> | |
211 | where F : Float, | |
212 | D : 'static, | |
213 | A : Aggregator, | |
214 | S : AggregatorSorting<Agg = A> { | |
215 | ||
216 | #[inline] | |
217 | fn cmp(&self, other : &Self) -> Ordering { | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
218 | self.with_aggregator(|agg1| other.with_aggregator(|agg2| { |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
219 | match S::sort_upper(agg1).cmp(&S::sort_upper(agg2)) { |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
220 | Equal => S::sort_lower(agg1).cmp(&S::sort_lower(agg2)), |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
221 | order => order, |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
222 | } |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
223 | })) |
0 | 224 | } |
225 | } | |
226 | ||
5 | 227 | /// This is a container for a [`BinaryHeap`] of [`RefinementInfo`]s together with tracking of |
228 | /// the greatest lower bound of the [`Aggregator`]s of the [`Node`]s therein accroding to | |
229 | /// chosen [`AggregatorSorting`]. | |
230 | struct HeapContainer<'a, F, D, A, S, RResult, const N : usize, const P : usize> | |
0 | 231 | where F : Float, |
232 | D : 'static + Copy, | |
233 | Const<P> : BranchCount<N>, | |
234 | A : Aggregator, | |
235 | S : AggregatorSorting<Agg = A> { | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
236 | /// Priority queue of nodes to be refined |
0 | 237 | heap : BinaryHeap<RefinementInfo<'a, F, D, A, S, RResult, N, P>>, |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
238 | /// Maximum of node sorting lower bounds seen in the heap |
0 | 239 | glb : S::Sort, |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
240 | /// Number of insertions in the heap since previous prune |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
241 | insert_counter : usize, |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
242 | /// If a result has been found by some refinment threat, it is stored here |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
243 | result : Option<RResult>, |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
244 | /// Refinement step counter |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
245 | step : usize, |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
246 | /// Number of threads currently processing (not sleeping) |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
247 | n_processing : usize, |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
248 | /// Threshold for heap pruning |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
249 | heap_prune_threshold : usize, |
0 | 250 | } |
251 | ||
252 | impl<'a, F, D, A, S, RResult, const N : usize, const P : usize> | |
253 | HeapContainer<'a, F, D, A, S, RResult, N, P> | |
254 | where F : Float, | |
255 | D : 'static + Copy, | |
256 | Const<P> : BranchCount<N>, | |
257 | A : Aggregator, | |
258 | S : AggregatorSorting<Agg = A> { | |
259 | ||
5 | 260 | /// Push `ri` into the [`BinaryHeap`]. Do greatest lower bound maintenance. |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
261 | /// |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
262 | /// Returns a boolean indicating whether the push was actually performed due to glb |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
263 | /// filtering or not. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
264 | #[inline] |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
265 | fn push(&mut self, ri : RefinementInfo<'a, F, D, A, S, RResult, N, P>) -> bool { |
0 | 266 | if ri.sort_upper() >= self.glb { |
267 | let l = ri.sort_lower(); | |
268 | self.heap.push(ri); | |
269 | self.glb = self.glb.max(l); | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
270 | self.insert_counter += 1; |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
271 | true |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
272 | } else { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
273 | false |
0 | 274 | } |
275 | } | |
276 | } | |
277 | ||
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
278 | impl<F : Float, D, A, const N : usize, const P : usize> |
0 | 279 | Branches<F,D,A,N,P> |
280 | where Const<P> : BranchCount<N>, | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
281 | A : Aggregator, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
282 | D : 'static + Copy + Send + Sync { |
0 | 283 | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
284 | /// Stage all subnodes of `self` into the refinement queue `container`. |
0 | 285 | fn stage_refine<'a, S, RResult>( |
286 | &'a mut self, | |
287 | domain : Cube<F,N>, | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
288 | container : &mut HeapContainer<'a, F, D, A, S, RResult, N, P>, |
0 | 289 | ) where S : AggregatorSorting<Agg = A> { |
290 | // Insert all subnodes into the refinement heap. | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
291 | for (node, cube) in self.nodes_and_cubes_mut(&domain) { |
0 | 292 | container.push(RefinementInfo { |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
293 | cube, |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
294 | node, |
0 | 295 | refiner_info : None, |
296 | sorting : PhantomData, | |
297 | }); | |
298 | } | |
299 | } | |
300 | } | |
301 | ||
302 | ||
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
303 | impl<F : Float, D, A, const N : usize, const P : usize> |
0 | 304 | Node<F,D,A,N,P> |
305 | where Const<P> : BranchCount<N>, | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
306 | A : Aggregator, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
307 | D : 'static + Copy + Send + Sync { |
0 | 308 | |
309 | /// If `self` is a leaf node, uses the `refiner` to determine whether further subdivision | |
310 | /// is required to get a sufficiently refined solution for the problem the refiner is used | |
311 | /// to solve. If the refiner returns [`RefinerResult::Certain`] result, it is returned. | |
312 | /// If [`RefinerResult::Uncertain`] is returned, the leaf is inserted back into the refinement | |
313 | /// queue `container`. If `self` is a branch, its subnodes are staged into `container` using | |
314 | /// [`Branches::stage_refine`]. | |
5 | 315 | /// |
316 | /// `domain`, as usual, indicates the spatial area corresponding to `self`. | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
317 | fn search_and_refine<'a, 'b, 'c, R, G>( |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
318 | self : &'a mut Self, |
0 | 319 | domain : Cube<F,N>, |
320 | refiner : &R, | |
321 | generator : &G, | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
322 | container_arc : &'c Arc<Mutex<HeapContainer<'a, F, D, A, R::Sorting, R::Result, N, P>>>, |
0 | 323 | step : usize |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
324 | ) -> Result<R::Result, MutexGuard<'c, HeapContainer<'a, F, D, A, R::Sorting, R::Result, N, P>>> |
81
d2acaaddd9af
Try to have Field as member type in Mappings etc.
Tuomo Valkonen <tuomov@iki.fi>
parents:
9
diff
changeset
|
325 | where R : Refiner<A, G, N>, |
d2acaaddd9af
Try to have Field as member type in Mappings etc.
Tuomo Valkonen <tuomov@iki.fi>
parents:
9
diff
changeset
|
326 | G : SupportGenerator<N, Id=D, RealField = F>, |
d2acaaddd9af
Try to have Field as member type in Mappings etc.
Tuomo Valkonen <tuomov@iki.fi>
parents:
9
diff
changeset
|
327 | G::SupportType : LocalAnalysis<A, Cube<F, N>> { |
0 | 328 | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
329 | //drop(container); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
330 | |
0 | 331 | // Refine a leaf. |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
332 | let res = match self.data { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
333 | NodeOption::Leaf(ref mut v) => { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
334 | let res = refiner.refine(&self.aggregator, &domain, v, generator, step); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
335 | if let NeedRefinement = res { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
336 | // The refiner has deemed the leaf unsufficiently refined, so subdivide |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
337 | // it and add the new nodes into the refinement priority heap. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
338 | let mut it = v.iter(); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
339 | // Only create new branches if there's anything to add. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
340 | // We insert the last item first to mix the support_hint a bit. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
341 | if let Some(&d0) = it.next_back() { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
342 | // Construct new Branches |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
343 | let support = generator.support_for(d0); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
344 | let mut b = Branches::new_with(&domain, &support); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
345 | b.insert(&domain, d0, Const::<1>, &support, TaskBudget::none()); |
0 | 346 | for &d in it { |
347 | let support = generator.support_for(d); | |
348 | // TODO: can we be smarter than just refining one level? | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
349 | b.insert(&domain, d, Const::<1>, &support, TaskBudget::none()); |
0 | 350 | } |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
351 | // Update current node and stage refinement of new branches. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
352 | b.summarise_into(&mut self.aggregator); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
353 | // FIXME: parent aggregators are not updated and will be out-of-date, but |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
354 | // right now pointsource_algs is not really taking advantage of the |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
355 | // aggregators being updated. Moreover, insertion and aggregator refinement |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
356 | // code in `bt.rs` will overflow the stack in deeply nested trees. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
357 | // We nevertheless need to store `b` into `self` to be able to queue |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
358 | // the branches. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
359 | self.data = NodeOption::Branches(Arc::new(b)); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
360 | // This ugly match is needed to keep the compiler happy about lifetimes. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
361 | match self.data { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
362 | NodeOption::Branches(ref mut arc_b) => { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
363 | let mut container = container_arc.lock().unwrap(); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
364 | // Safe: we just created arg_b and have a mutable exclusive |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
365 | // reference to self containing it. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
366 | unsafe { Arc::get_mut_unchecked(arc_b) } |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
367 | .stage_refine(domain, &mut *container); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
368 | return Err(container) |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
369 | }, |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
370 | _ => unreachable!("This cannot happen"), |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
371 | } |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
372 | } |
0 | 373 | } |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
374 | res |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
375 | }, |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
376 | NodeOption::Branches(ref mut b) => { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
377 | // Insert branches into refinement priority queue. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
378 | let mut container = container_arc.lock().unwrap(); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
379 | Arc::make_mut(b).stage_refine(domain, &mut *container); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
380 | return Err(container) |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
381 | }, |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
382 | NodeOption::Uninitialised => { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
383 | refiner.refine(&self.aggregator, &domain, &[], generator, step) |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
384 | }, |
0 | 385 | }; |
386 | ||
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
387 | match res { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
388 | Uncertain(agg, val) => { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
389 | // The refiner gave an undertain result. Push a leaf back into the refinement queue |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
390 | // with the new refined aggregator and custom return value. It will be popped and |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
391 | // returned in the loop of [`BTSearch::search_and_refine`] when there are no |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
392 | // unrefined candidates that could potentially be better according to their basic |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
393 | // aggregator. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
394 | let mut container = container_arc.lock().unwrap(); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
395 | container.push(RefinementInfo { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
396 | cube : domain, |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
397 | node : self, |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
398 | refiner_info : Some((agg, val)), |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
399 | sorting : PhantomData, |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
400 | }); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
401 | Err(container) |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
402 | }, |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
403 | Certain(val) => { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
404 | // The refiner gave a certain result so return it to allow early termination |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
405 | Ok(val) |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
406 | }, |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
407 | NeedRefinement => { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
408 | // This should only happen when we run into NodeOption::Uninitialised above. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
409 | // There's really nothing to do. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
410 | panic!("Do not know whow to refine uninitialised nodes"); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
411 | } |
0 | 412 | } |
413 | } | |
414 | } | |
415 | ||
5 | 416 | /// Interface trait to a refining search on a [`BT`]. |
417 | /// | |
418 | /// This can be removed and the methods implemented directly on [`BT`] once Rust's const generics | |
419 | /// are flexible enough to allow fixing `P=pow(2, N)`. | |
0 | 420 | pub trait BTSearch<F, const N : usize> : BTImpl<F, N> |
421 | where F : Float { | |
422 | ||
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
423 | /// Perform a search on on `Self`, as determined by `refiner`. |
5 | 424 | /// |
425 | /// Nodes are inserted in a priority queue and processed in the order determined by the | |
426 | /// [`AggregatorSorting`] [`Refiner::Sorting`]. Leaf nodes are subdivided until the refiner | |
427 | /// decides that a sufficiently refined leaf node has been found, as determined by either the | |
428 | /// refiner returning a [`RefinerResult::Certain`] result, or a previous | |
429 | /// [`RefinerResult::Uncertain`] result is found again at the top of the priority queue. | |
430 | /// | |
431 | /// The `generator` converts [`BTImpl::Data`] stored in the bisection tree into a [`Support`]. | |
0 | 432 | fn search_and_refine<'b, R, G>( |
433 | &'b mut self, | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
434 | refiner : R, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
435 | generator : &Arc<G>, |
0 | 436 | ) -> Option<R::Result> |
81
d2acaaddd9af
Try to have Field as member type in Mappings etc.
Tuomo Valkonen <tuomov@iki.fi>
parents:
9
diff
changeset
|
437 | where R : Refiner<Self::Agg, G, N> + Sync + Send + 'static, |
d2acaaddd9af
Try to have Field as member type in Mappings etc.
Tuomo Valkonen <tuomov@iki.fi>
parents:
9
diff
changeset
|
438 | G : SupportGenerator<N, Id=Self::Data, RealField = F> + Sync + Send + 'static, |
d2acaaddd9af
Try to have Field as member type in Mappings etc.
Tuomo Valkonen <tuomov@iki.fi>
parents:
9
diff
changeset
|
439 | G::SupportType : LocalAnalysis<Self::Agg, Cube<F, N>>; |
0 | 440 | } |
441 | ||
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
442 | fn refinement_loop<F : Float, D, A, R, G, const N : usize, const P : usize> ( |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
443 | wakeup : Option<Arc<Condvar>>, |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
444 | refiner : &R, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
445 | generator_arc : &Arc<G>, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
446 | container_arc : &Arc<Mutex<HeapContainer<F, D, A, R::Sorting, R::Result, N, P>>>, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
447 | ) where A : Aggregator, |
81
d2acaaddd9af
Try to have Field as member type in Mappings etc.
Tuomo Valkonen <tuomov@iki.fi>
parents:
9
diff
changeset
|
448 | R : Refiner<A, G, N>, |
d2acaaddd9af
Try to have Field as member type in Mappings etc.
Tuomo Valkonen <tuomov@iki.fi>
parents:
9
diff
changeset
|
449 | G : SupportGenerator<N, Id=D, RealField = F>, |
d2acaaddd9af
Try to have Field as member type in Mappings etc.
Tuomo Valkonen <tuomov@iki.fi>
parents:
9
diff
changeset
|
450 | G::SupportType : LocalAnalysis<A, Cube<F, N>>, |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
451 | Const<P> : BranchCount<N>, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
452 | D : 'static + Copy + Sync + Send + std::fmt::Debug { |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
453 | |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
454 | let mut did_park = true; |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
455 | let mut container = container_arc.lock().unwrap(); |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
456 | |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
457 | 'main: loop { |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
458 | // Find a node to process |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
459 | let ri = 'get_next: loop { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
460 | if did_park { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
461 | container.n_processing += 1; |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
462 | did_park = false; |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
463 | } |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
464 | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
465 | // Some refinement task/thread has found a result, return |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
466 | if container.result.is_some() { |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
467 | container.n_processing -= 1; |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
468 | break 'main |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
469 | } |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
470 | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
471 | match container.heap.pop() { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
472 | // There's work to be done. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
473 | Some(ri) => break 'get_next ri, |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
474 | // No work to be done; park if some task/thread is still processing nodes, |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
475 | // fail if not. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
476 | None => { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
477 | debug_assert!(container.n_processing > 0); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
478 | container.n_processing -= 1; |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
479 | if container.n_processing == 0 { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
480 | break 'main; |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
481 | } else if let Some(ref c) = wakeup { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
482 | did_park = true; |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
483 | container = c.wait(container).unwrap(); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
484 | continue 'get_next; |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
485 | } else { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
486 | break 'main |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
487 | } |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
488 | } |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
489 | }; |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
490 | }; |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
491 | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
492 | let step = container.step; |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
493 | container.step += 1; |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
494 | |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
495 | if let Some((_, result)) = ri.refiner_info { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
496 | // Terminate based on a “best possible” result. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
497 | container.result = Some(result); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
498 | container.n_processing -= 1; |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
499 | break 'main |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
500 | } |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
501 | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
502 | // Do priority queue maintenance |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
503 | if container.insert_counter > container.heap_prune_threshold { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
504 | // Make sure glb is good. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
505 | match container.heap.iter().map(|ri| ri.sort_lower()).reduce(max) { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
506 | Some(glb) => { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
507 | container.glb = glb; |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
508 | // Prune |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
509 | container.heap.retain(|ri| ri.sort_upper() >= glb); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
510 | }, |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
511 | None => { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
512 | container.glb = R::Sorting::bottom() |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
513 | } |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
514 | } |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
515 | container.insert_counter = 0; |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
516 | } |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
517 | |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
518 | // Unlock the mutex… |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
519 | drop(container); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
520 | |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
521 | // … and process the node. We may get returned an already unlocked mutex. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
522 | match Node::search_and_refine(ri.node, ri.cube, refiner, &**generator_arc, |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
523 | &container_arc, step) { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
524 | Ok(r) => { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
525 | let mut container = container_arc.lock().unwrap(); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
526 | // Terminate based on a certain result from the refiner |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
527 | match container.result { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
528 | Some(ref mut r_prev) => R::fuse_results(r_prev, r), |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
529 | None => container.result = Some(r), |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
530 | } |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
531 | break 'main |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
532 | }, |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
533 | Err(cnt) => { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
534 | container = cnt; |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
535 | // Wake up another thread if one is sleeping; there should be now work in the |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
536 | // queue. |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
537 | if let Some(ref c) = wakeup { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
538 | c.notify_one(); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
539 | } |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
540 | } |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
541 | } |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
542 | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
543 | } |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
544 | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
545 | // Make sure no task is sleeping |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
546 | if let Some(ref c) = wakeup { |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
547 | c.notify_all(); |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
548 | } |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
549 | } |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
550 | |
0 | 551 | // Needed to get access to a Node without a trait interface. |
552 | macro_rules! impl_btsearch { | |
553 | ($($n:literal)*) => { $( | |
554 | impl<'a, M, F, D, A> | |
555 | BTSearch<F, $n> | |
556 | for BT<M,F,D,A,$n> | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
557 | where //Self : BTImpl<F,$n,Data=D,Agg=A, Depth=M>, // <== automatically deduced |
0 | 558 | M : Depth, |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
559 | F : Float + Send, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
560 | A : Aggregator, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
561 | D : 'static + Copy + Sync + Send + std::fmt::Debug { |
0 | 562 | fn search_and_refine<'b, R, G>( |
563 | &'b mut self, | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
564 | refiner : R, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
565 | generator : &Arc<G>, |
0 | 566 | ) -> Option<R::Result> |
81
d2acaaddd9af
Try to have Field as member type in Mappings etc.
Tuomo Valkonen <tuomov@iki.fi>
parents:
9
diff
changeset
|
567 | where R : Refiner<A, G, $n>, |
d2acaaddd9af
Try to have Field as member type in Mappings etc.
Tuomo Valkonen <tuomov@iki.fi>
parents:
9
diff
changeset
|
568 | G : SupportGenerator<$n, Id=D, RealField = F>, |
d2acaaddd9af
Try to have Field as member type in Mappings etc.
Tuomo Valkonen <tuomov@iki.fi>
parents:
9
diff
changeset
|
569 | G::SupportType : LocalAnalysis<A, Cube<F, $n>> { |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
570 | let mut init_container = HeapContainer { |
0 | 571 | heap : BinaryHeap::new(), |
572 | glb : R::Sorting::bottom(), | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
573 | insert_counter : 0, |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
574 | result : None, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
575 | step : 0, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
576 | n_processing : 0, |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
577 | // An arbitrary threshold for starting pruning of the heap |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
578 | heap_prune_threshold : 2u32.pow(16.max($n * self.depth.value())) as usize |
0 | 579 | }; |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
580 | init_container.push(RefinementInfo { |
0 | 581 | cube : self.domain, |
582 | node : &mut self.topnode, | |
583 | refiner_info : None, | |
584 | sorting : PhantomData, | |
585 | }); | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
586 | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
587 | let container_arc = Arc::new(Mutex::new(init_container)); |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
588 | if let Some(pool) = thread_pool() { |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
589 | let n = thread_pool_size(); |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
590 | pool.scope(|s| { |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
591 | let wakeup = Arc::new(Condvar::new()); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
592 | for _ in 0..n { |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
593 | let refiner_ref = &refiner; |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
594 | let container_t = Arc::clone(&container_arc); |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
595 | let wakeup_t = Arc::clone(&wakeup); |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
596 | s.spawn(move |_| { |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
597 | refinement_loop(Some(wakeup_t), refiner_ref, generator, |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
598 | &container_t); |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
599 | }); |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
600 | } |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
601 | refinement_loop(Some(wakeup), &refiner, generator, &container_arc); |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
602 | }); |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
603 | } else { |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
604 | refinement_loop(None, &refiner, generator, &container_arc); |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
605 | } |
0 | 606 | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
607 | match Arc::try_unwrap(container_arc) { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
608 | Ok(mtx) => mtx.into_inner().unwrap().result, |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
609 | Err(_) => panic!("Refinement threads not finished properly."), |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
610 | } |
0 | 611 | } |
612 | } | |
613 | )* } | |
614 | } | |
615 | ||
616 | impl_btsearch!(1 2 3 4); | |
617 |