hibitset/iter/parallel.rs
1use rayon::iter::plumbing::{bridge_unindexed, Folder, UnindexedConsumer, UnindexedProducer};
2use rayon::iter::ParallelIterator;
3
4use iter::{BitIter, BitSetLike, Index, BITS, LAYERS};
5use util::average_ones;
6
7/// A `ParallelIterator` over a [`BitSetLike`] structure.
8///
9/// [`BitSetLike`]: ../../trait.BitSetLike.html
10#[derive(Debug)]
11pub struct BitParIter<T>(T, u8);
12
13impl<T> BitParIter<T> {
14 /// Creates a new `BitParIter`. You usually don't call this function
15 /// but just [`.par_iter()`] on a bit set.
16 ///
17 /// Default layer split amount is 3.
18 ///
19 /// [`.par_iter()`]: ../../trait.BitSetLike.html#method.par_iter
20 pub fn new(set: T) -> Self {
21 BitParIter(set, 3)
22 }
23
24 /// Sets how many layers are split when forking.
25 ///
26 /// # Examples
27 ///
28 /// ```
29 /// # extern crate rayon;
30 /// # extern crate hibitset;
31 /// # use hibitset::{BitSet, BitSetLike};
32 /// # use rayon::iter::ParallelIterator;
33 /// # fn main() {
34 /// let mut bitset = BitSet::new();
35 /// bitset.par_iter()
36 /// .layers_split(2)
37 /// .count();
38 /// # }
39 /// ```
40 ///
41 /// The value should be in range [1, 3]
42 ///
43 /// | splits | largest smallest unit of work |
44 /// |--------|-------------------------------|
45 /// | 1 | usize_bits<sup>3</sup> |
46 /// | 2 | usize_bits<sup>2</sup> |
47 /// | 3 | usize_bits |
48 ///
49 pub fn layers_split(mut self, layers: u8) -> Self {
50 assert!(layers >= 1);
51 assert!(layers <= 3);
52 self.1 = layers;
53 self
54 }
55}
56
57impl<T> ParallelIterator for BitParIter<T>
58where
59 T: BitSetLike + Send + Sync,
60{
61 type Item = Index;
62
63 fn drive_unindexed<C>(self, consumer: C) -> C::Result
64 where
65 C: UnindexedConsumer<Self::Item>,
66 {
67 bridge_unindexed(BitProducer((&self.0).iter(), self.1), consumer)
68 }
69}
70
71/// Allows splitting and internally iterating through `BitSet`.
72///
73/// Usually used internally by `BitParIter`.
74#[derive(Debug)]
75pub struct BitProducer<'a, T: 'a + Send + Sync>(pub BitIter<&'a T>, pub u8);
76
77impl<'a, T: 'a + Send + Sync> UnindexedProducer for BitProducer<'a, T>
78where
79 T: BitSetLike,
80{
81 type Item = Index;
82
83 /// How the splitting is done:
84 ///
85 /// 1) First the highest layer that has at least one set bit
86 /// is searched.
87 ///
88 /// 2) If the layer that was found, has only one bit that's set,
89 /// it's cleared. After that the correct prefix for the cleared
90 /// bit is figured out and the descending is continued.
91 ///
92 /// 3) If the layer that was found, has more than one bit that's set,
93 /// a mask is created that splits it's set bits as close to half
94 /// as possible.
95 /// After creating the mask the layer is masked by either the mask
96 /// or it's complement constructing two distinct producers which
97 /// are then returned.
98 ///
99 /// 4) If there isn't any layers that have more than one set bit,
100 /// splitting doesn't happen.
101 ///
102 /// The actual iteration is performed by the sequential iterator
103 /// `BitIter` which internals are modified by this splitting
104 /// algorithm.
105 ///
106 /// This splitting strategy should split work evenly if the set bits
107 /// are distributed close to uniformly random.
108 /// As the strategy only looks one layer at the time, if there are subtrees
109 /// that have lots of work and sibling subtrees that have little of work,
110 /// then it will produce non-optimal splittings.
111 fn split(mut self) -> (Self, Option<Self>) {
112 let splits = self.1;
113 let other = {
114 let mut handle_level = |level: usize| {
115 if self.0.masks[level] == 0 {
116 // Skip the empty layers
117 None
118 } else {
119 // Top levels prefix is zero because there is nothing before it
120 let level_prefix = self.0.prefix.get(level).cloned().unwrap_or(0);
121 let first_bit = self.0.masks[level].trailing_zeros();
122 average_ones(self.0.masks[level])
123 .and_then(|average_bit| {
124 let mask = (1 << average_bit) - 1;
125 let mut other = BitProducer(
126 BitIter::new(self.0.set, [0; LAYERS], [0; LAYERS - 1]),
127 splits,
128 );
129 // The `other` is the more significant half of the mask
130 other.0.masks[level] = self.0.masks[level] & !mask;
131 other.0.prefix[level - 1] = (level_prefix | average_bit as u32) << BITS;
132 // The upper portion of the prefix is maintained, because the `other`
133 // will iterate the same subtree as the `self` does
134 other.0.prefix[level..].copy_from_slice(&self.0.prefix[level..]);
135 // And the `self` is the less significant one
136 self.0.masks[level] &= mask;
137 self.0.prefix[level - 1] = (level_prefix | first_bit) << BITS;
138 Some(other)
139 })
140 .or_else(|| {
141 // Because there is only one bit left we descend to it
142 let idx = level_prefix as usize | first_bit as usize;
143 self.0.prefix[level - 1] = (idx as u32) << BITS;
144 // The level that is descended from doesn't have anything
145 // interesting so it can be skipped in the future.
146 self.0.masks[level] = 0;
147 self.0.masks[level - 1] = self.0.set.get_from_layer(level - 1, idx);
148 None
149 })
150 }
151 };
152 let top_layer = LAYERS - 1;
153 let mut h = handle_level(top_layer);
154 for i in 1..splits {
155 h = h.or_else(|| handle_level(top_layer - i as usize));
156 }
157 h
158 };
159 (self, other)
160 }
161
162 fn fold_with<F>(self, folder: F) -> F
163 where
164 F: Folder<Self::Item>,
165 {
166 folder.consume_iter(self.0)
167 }
168}
169
170#[cfg(test)]
171mod test_bit_producer {
172 use rayon::iter::plumbing::UnindexedProducer;
173
174 use super::BitProducer;
175 use iter::BitSetLike;
176 use util::BITS;
177
178 fn test_splitting(split_levels: u8) {
179 fn visit<T>(mut us: BitProducer<T>, d: usize, i: usize, mut trail: String, c: &mut usize)
180 where
181 T: Send + Sync + BitSetLike,
182 {
183 if d == 0 {
184 assert!(us.split().1.is_none(), "{}", trail);
185 *c += 1;
186 } else {
187 for j in 1..(i + 1) {
188 let (new_us, them) = us.split();
189 us = new_us;
190 let them = them.expect(&trail);
191 let mut trail = trail.clone();
192 trail.push_str(&i.to_string());
193 visit(them, d, i - j, trail, c);
194 }
195 trail.push_str("u");
196 visit(us, d - 1, BITS, trail, c);
197 }
198 }
199
200 let usize_bits = ::std::mem::size_of::<usize>() * 8;
201
202 let mut c = ::BitSet::new();
203 for i in 0..(usize_bits.pow(3) * 2) {
204 assert!(!c.add(i as u32));
205 }
206
207 let us = BitProducer((&c).iter(), split_levels);
208 let (us, them) = us.split();
209
210 let mut count = 0;
211 visit(
212 us,
213 split_levels as usize - 1,
214 BITS,
215 "u".to_owned(),
216 &mut count,
217 );
218 visit(
219 them.expect("Splitting top level"),
220 split_levels as usize - 1,
221 BITS,
222 "t".to_owned(),
223 &mut count,
224 );
225 assert_eq!(usize_bits.pow(split_levels as u32 - 1) * 2, count);
226 }
227
228 #[test]
229 fn max_3_splitting_of_two_top_bits() {
230 test_splitting(3);
231 }
232
233 #[test]
234 fn max_2_splitting_of_two_top_bits() {
235 test_splitting(2);
236 }
237
238 #[test]
239 fn max_1_splitting_of_two_top_bits() {
240 test_splitting(1);
241 }
242}