Line data Source code
1 : // The libMesh Finite Element Library.
2 : // Copyright (C) 2002-2026 Benjamin S. Kirk, John W. Peterson, Roy H. Stogner
3 :
4 : // This library is free software; you can redistribute it and/or
5 : // modify it under the terms of the GNU Lesser General Public
6 : // License as published by the Free Software Foundation; either
7 : // version 2.1 of the License, or (at your option) any later version.
8 :
9 : // This library is distributed in the hope that it will be useful,
10 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 : // Lesser General Public License for more details.
13 :
14 : // You should have received a copy of the GNU Lesser General Public
15 : // License along with this library; if not, write to the Free Software
16 : // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 :
18 :
19 :
20 : #ifndef LIBMESH_STORED_RANGE_H
21 : #define LIBMESH_STORED_RANGE_H
22 :
23 : // Local includes
24 : #include "libmesh/threads.h"
25 :
26 : // C++ includes
27 : #include <type_traits> // std::remove*
28 : #include <vector>
29 : #include <memory> // std::unique_ptr
30 : #include <functional> // std::function
31 :
32 : namespace libMesh
33 : {
34 :
35 : /**
36 : * The \p StoredRange class defines a contiguous, divisible set of objects.
37 : * This class is used primarily as the argument to function objects. The
38 : * range can then be subdivided into a number of "tasks" which can be executed
39 : * in parallel. This concept is central to the Threading Building Blocks
40 : * template library which can optionally be used by \p libMesh to implement
41 : * shared-memory parallelism.
42 : *
43 : * The implementation takes a user-provided object range and packs it into
44 : * a contiguous vector which can then be subdivided efficiently. A first-cut
45 : * implementation using raw element iterators incurred simply too much overhead
46 : * by using the predicated iterators, specifically operations such as advancing
47 : * such iterators has a cost proportional to the amount the iterator is advanced.
48 : * Hence in this implementation the user-provided range is packed into a vector.
49 : *
50 : * \author Benjamin S. Kirk
51 : * \date 2008
52 : * \brief Utility class for defining generic ranges for threading.
53 : */
54 : template <typename iterator_type, typename object_type>
55 : class StoredRange
56 : {
57 : public:
58 : /**
59 : * Allows an \p StoredRange to behave like an STL container.
60 : */
61 : typedef typename std::vector<object_type> vec_type;
62 : typedef const object_type * const_iterator;
63 : typedef typename std::unique_ptr<vec_type, std::function<void (vec_type *)>> ptr_type;
64 :
65 : /**
66 : * Allows conversion from non-const to const pointer objects
67 : */
68 : typedef std::remove_const_t<std::remove_pointer_t<object_type>> * nonconst_object_type;
69 :
70 : /**
71 : * Constructor. Optionally takes the \p grainsize parameter, which is the
72 : * smallest chunk the range may be broken into for parallel
73 : * execution.
74 : */
75 : StoredRange (const unsigned int new_grainsize = libMesh::default_grainsize()) :
76 : _end(),
77 : _begin(),
78 : _last(),
79 : _first(),
80 : _grainsize(new_grainsize),
81 : _objs(ptr_type(new vec_type(), [](vec_type * p){delete p;}))
82 : {}
83 :
84 : /**
85 : * Constructor. Takes the beginning and end of the range.
86 : * Optionally takes the \p grainsize parameter, which is the
87 : * smallest chunk the range may be broken into for parallel
88 : * execution.
89 : */
90 6324298 : StoredRange (const iterator_type & first,
91 : const iterator_type & last,
92 : const unsigned int new_grainsize = libMesh::default_grainsize()) :
93 5907468 : _end(),
94 5907468 : _begin(),
95 5907468 : _last(),
96 5907468 : _first(),
97 5907468 : _grainsize(new_grainsize),
98 18811434 : _objs(ptr_type(new vec_type(), [](vec_type * p){delete p;}))
99 : {
100 6324298 : this->reset(first, last);
101 6324298 : }
102 :
103 : /**
104 : * Constructor. Takes a std::vector of objects.
105 : * Optionally takes the \p grainsize parameter, which is the
106 : * smallest chunk the range may be broken into for parallel
107 : * execution.
108 : *
109 : * \note The std::vector passed in here MUST live for the
110 : * lifetime of this StoredRange! We are not responsible for
111 : * deleting this pointer.
112 : */
113 1495759 : StoredRange (vec_type * objs,
114 : const unsigned int new_grainsize = libMesh::default_grainsize()) :
115 1495759 : _end(end_of(*objs)),
116 1450887 : _begin(objs->data()),
117 1450887 : _last(objs->size()),
118 1450887 : _first(0),
119 1450887 : _grainsize(new_grainsize),
120 1675301 : _objs(ptr_type(objs, [](vec_type *){/*don't delete*/}))
121 : {
122 1495759 : }
123 :
124 : /**
125 : * Constructor. Takes pointers to objects, which are expected to
126 : * themselves be pointers but with const removed. This lets us
127 : * create a const range view of a saved non-const range.
128 : *
129 : * Optionally takes the \p grainsize parameter, which is the
130 : * smallest chunk the range may be broken into for parallel
131 : * execution.
132 : *
133 : * \note The pointer range passed in here MUST be dereferenceable
134 : * for the lifetime of this StoredRange!
135 : */
136 1100397 : StoredRange (const nonconst_object_type * begin,
137 : const nonconst_object_type * end,
138 : const unsigned int new_grainsize = libMesh::default_grainsize()) :
139 1075354 : _end(end),
140 1075354 : _begin(begin),
141 1125440 : _last(std::distance(begin, end)),
142 1075354 : _first(0),
143 1075354 : _grainsize(new_grainsize),
144 25043 : _objs(nullptr)
145 : {
146 25043 : }
147 :
148 : /**
149 : * Copy constructor. The \p StoredRange can be copied into
150 : * subranges for parallel execution. In this way the
151 : * initial \p StoredRange can be thought of as the root of
152 : * a binary tree. The root element is the only element
153 : * which interacts with the user. It takes a specified
154 : * range of objects and packs it into a contiguous vector
155 : * which can be split efficiently. However, there is no need
156 : * for the child ranges to contain this vector, so long as
157 : * the parent outlives the children. So we implement
158 : * the copy constructor to specifically omit the \p _objs
159 : * vector.
160 : */
161 201 : StoredRange (const StoredRange<iterator_type,object_type> & er):
162 207 : _end(er._end),
163 207 : _begin(er._begin),
164 207 : _last(er._last),
165 207 : _first(er._first),
166 207 : _grainsize(er._grainsize),
167 6 : _objs(nullptr)
168 : {
169 : // specifically, do *not* copy the vector
170 0 : }
171 :
172 : /**
173 : * NOTE: When using pthreads this constructor is MANDATORY!!!
174 : *
175 : * Copy constructor. The \p StoredRange can be copied into
176 : * subranges for parallel execution. In this way the
177 : * initial \p StoredRange can be thought of as the root of
178 : * a binary tree. The root element is the only element
179 : * which interacts with the user. It takes a specified
180 : * range of objects and packs it into a contiguous vector
181 : * which can be split efficiently. However, there is no need
182 : * for the child ranges to contain this vector, so long as
183 : * the parent outlives the children. So we implement
184 : * the copy constructor to specifically omit the \p _objs
185 : * vector. This version allows you to set the beginning and
186 : * ending of this new range to be different from that of the
187 : * one we're copying.
188 : */
189 17270 : StoredRange (const StoredRange<iterator_type,object_type> & er,
190 : const const_iterator & begin_range,
191 : const const_iterator & end_range):
192 8482 : _end(end_range),
193 8482 : _begin(begin_range),
194 0 : _last(0), // Initialize these in a moment
195 0 : _first(0),
196 17270 : _grainsize(er._grainsize),
197 8788 : _objs(nullptr)
198 : {
199 : // specifically, do *not* copy the vector
200 :
201 17270 : _first = std::distance(er._begin, _begin);
202 17270 : _last = _first + std::distance(_begin, _end);
203 17270 : }
204 :
205 : /**
206 : * Splits the range \p r. The first half
207 : * of the range is left in place, the second
208 : * half of the range is placed in *this.
209 : */
210 : StoredRange (StoredRange<iterator_type,object_type> & r, Threads::split ) :
211 : _end(r._end),
212 : _begin(r._begin),
213 : _last(r._last),
214 : _first(r._first),
215 : _grainsize(r._grainsize),
216 : _objs(nullptr)
217 : {
218 : const_iterator
219 : beginning = r._begin,
220 : ending = r._end,
221 : middle = beginning + std::distance(beginning, ending)/2u;
222 :
223 : r._end = _begin = middle;
224 :
225 : std::size_t
226 : first = r._first,
227 : last = r._last,
228 : half = first + (last-first)/2u;
229 :
230 : r._last = _first = half;
231 : }
232 :
233 : /**
234 : * Destructor. Releases the object array if we created it.
235 : */
236 8832703 : ~StoredRange () = default;
237 :
238 : /**
239 : * Resets the \p StoredRange to contain [first,last).
240 : *
241 : * \returns A reference to itself for convenience, so functions
242 : * expecting a \p StoredRange<> can be passed e.g. foo.reset(begin,end).
243 : */
244 : StoredRange<iterator_type, object_type> &
245 6324298 : reset (const iterator_type & first,
246 : const iterator_type & last)
247 : {
248 : // _objs must be initialized in order to call reset()
249 289145 : libmesh_assert(_objs);
250 :
251 289145 : _objs->clear();
252 :
253 600492726 : for (iterator_type it=first; it!=last; ++it)
254 318475209 : _objs->push_back(*it);
255 :
256 6324298 : _begin = _objs->data();
257 6324298 : _end = end_of(*_objs);
258 :
259 6324298 : _first = 0;
260 6324298 : _last = _objs->size();
261 :
262 6324298 : return *this;
263 : }
264 :
265 : /**
266 : * Resets the range to the last specified range. This method only exists
267 : * for efficiency -- it is more efficient to set the range to its previous
268 : * value without rebuilding the underlying vector.
269 : *
270 : * \returns A reference to itself for convenience, so functions
271 : * expecting a StoredRange<> can be passed e.g. foo.reset().
272 : */
273 370137 : StoredRange<iterator_type, object_type> & reset ()
274 : {
275 : // _objs must be initialized in order to call reset()
276 10916 : libmesh_assert(_objs);
277 :
278 383114 : _begin = _objs->data();
279 383114 : _end = end_of(*_objs);
280 :
281 23893 : _first = 0;
282 34809 : _last = _objs->size();
283 :
284 370137 : return *this;
285 : }
286 :
287 : /**
288 : * Beginning of the range.
289 : */
290 15689163 : const_iterator begin () const { return _begin; }
291 :
292 : /**
293 : * End of the range.
294 : */
295 71838082 : const_iterator end () const { return _end; }
296 :
297 : /**
298 : * Index in the stored vector of the first object.
299 : */
300 38944 : std::size_t first_idx () const { return _first; }
301 :
302 : /**
303 : * Index in the stored vector of the last object.
304 : */
305 : std::size_t last_idx () const { return _last; }
306 :
307 : /**
308 : * The grain size for the range. The range will be subdivided into
309 : * subranges not to exceed the grain size.
310 : */
311 15438773 : std::size_t grainsize () const {return _grainsize;}
312 :
313 : /**
314 : * Set the grain size.
315 : */
316 : void grainsize (const unsigned int & gs) {_grainsize = gs;}
317 :
318 : /**
319 : * \returns The size of the range.
320 : */
321 14744276 : std::size_t size () const { return std::distance(_begin, _end); }
322 :
323 : /**
324 : * \returns Whether two ranges are equal.
325 : */
326 142362 : bool operator== (const StoredRange<iterator_type, object_type> & other) const
327 : {
328 18860133 : for (auto it = this->begin(), it2 = other.begin();
329 18860133 : it != this->end() || it2 != other.end(); ++it, ++it2)
330 : {
331 18717771 : if (it == this->end() || it2 == other.end())
332 0 : return false;
333 :
334 18717771 : if (*it != *it2)
335 0 : return false;
336 : }
337 :
338 142362 : return true;
339 : }
340 :
341 : //------------------------------------------------------------------------
342 : // Methods that implement Range concept
343 : //------------------------------------------------------------------------
344 :
345 : /**
346 : * \returns \p true if the range is empty.
347 : */
348 2792 : bool empty() const { return (_begin == _end); }
349 :
350 : /**
351 : * \returns \p true if the range can be subdivided.
352 : */
353 : bool is_divisible() const { return this->grainsize() < static_cast<unsigned int>(std::distance(_begin, _end)); }
354 :
355 : private:
356 :
357 : /**
358 : * Helper for pre-C++26 compiles, where the compiler may have
359 : * empty_vector.data() return nullptr and technically pointer
360 : * arithmetic on nullptr may be Undefined Behavior.
361 : */
362 315323 : static const_iterator end_of(vec_type & objs) {
363 8218451 : return objs.size() ? (objs.data()+objs.size()) : objs.data();
364 : }
365 :
366 : const_iterator _end;
367 : const_iterator _begin;
368 : std::size_t _last;
369 : std::size_t _first;
370 : std::size_t _grainsize;
371 :
372 : ptr_type _objs;
373 : };
374 :
375 : } // namespace libMesh
376 :
377 : #endif // LIBMESH_STORED_RANGE_H
|