Line data Source code
1 : // The libMesh Finite Element Library.
2 : // Copyright (C) 2002-2025 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 <vector>
28 : #include <memory> // std::unique_ptr
29 : #include <functional> // std::function
30 :
31 : namespace libMesh
32 : {
33 :
34 : /**
35 : * The \p StoredRange class defines a contiguous, divisible set of objects.
36 : * This class is used primarily as the argument to function objects. The
37 : * range can then be subdivided into a number of "tasks" which can be executed
38 : * in parallel. This concept is central to the Threading Building Blocks
39 : * template library which can optionally be used by \p libMesh to implement
40 : * shared-memory parallelism.
41 : *
42 : * The implementation takes a user-provided object range and packs it into
43 : * a contiguous vector which can then be subdivided efficiently. A first-cut
44 : * implementation using raw element iterators incurred simply too much overhead
45 : * by using the predicated iterators, specifically operations such as advancing
46 : * such iterators has a cost proportional to the amount the iterator is advanced.
47 : * Hence in this implementation the user-provided range is packed into a vector.
48 : *
49 : * \author Benjamin S. Kirk
50 : * \date 2008
51 : * \brief Utility class for defining generic ranges for threading.
52 : */
53 : template <typename iterator_type, typename object_type>
54 : class StoredRange
55 : {
56 : public:
57 : /**
58 : * Allows an \p StoredRange to behave like an STL container.
59 : */
60 : typedef typename std::vector<object_type> vec_type;
61 : typedef typename vec_type::const_iterator const_iterator;
62 : typedef typename std::unique_ptr<vec_type, std::function<void (vec_type *)>> ptr_type;
63 :
64 : /**
65 : * Constructor. Optionally takes the \p grainsize parameter, which is the
66 : * smallest chunk the range may be broken into for parallel
67 : * execution.
68 : */
69 16389 : StoredRange (const unsigned int new_grainsize = 1000) :
70 : _end(),
71 : _begin(),
72 15465 : _last(),
73 15465 : _first(),
74 15465 : _grainsize(new_grainsize),
75 49167 : _objs(ptr_type(new vec_type(), [](vec_type * p){delete p;}))
76 16389 : {}
77 :
78 : /**
79 : * Constructor. Takes the beginning and end of the range.
80 : * Optionally takes the \p grainsize parameter, which is the
81 : * smallest chunk the range may be broken into for parallel
82 : * execution.
83 : */
84 2903540 : StoredRange (const iterator_type & first,
85 : const iterator_type & last,
86 : const unsigned int new_grainsize = 1000) :
87 : _end(),
88 : _begin(),
89 2803850 : _last(),
90 2803850 : _first(),
91 2803850 : _grainsize(new_grainsize),
92 8710620 : _objs(ptr_type(new vec_type(), [](vec_type * p){delete p;}))
93 : {
94 2903540 : this->reset(first, last);
95 2903540 : }
96 :
97 : /**
98 : * Constructor. Takes a std::vector of objects.
99 : * Optionally takes the \p grainsize parameter, which is the
100 : * smallest chunk the range may be broken into for parallel
101 : * execution.
102 : *
103 : * \note The std::vector passed in here MUST live for the
104 : * lifetime of this StoredRange! We are not responsible for
105 : * deleting this pointer.
106 : */
107 944048 : StoredRange (vec_type * objs,
108 : const unsigned int new_grainsize = 1000) :
109 : _end(objs->end()),
110 : _begin(objs->begin()),
111 915168 : _last(objs->size()),
112 915168 : _first(0),
113 915168 : _grainsize(new_grainsize),
114 1030688 : _objs(ptr_type(objs, [](vec_type *){/*don't delete*/}))
115 : {
116 944048 : }
117 :
118 : /**
119 : * Copy constructor. The \p StoredRange can be copied into
120 : * subranges for parallel execution. In this way the
121 : * initial \p StoredRange can be thought of as the root of
122 : * a binary tree. The root element is the only element
123 : * which interacts with the user. It takes a specified
124 : * range of objects and packs it into a contiguous vector
125 : * which can be split efficiently. However, there is no need
126 : * for the child ranges to contain this vector, so long as
127 : * the parent outlives the children. So we implement
128 : * the copy constructor to specifically omit the \p _objs
129 : * vector.
130 : */
131 : StoredRange (const StoredRange<iterator_type,object_type> & er):
132 : _end(er._end),
133 : _begin(er._begin),
134 : _last(er._last),
135 : _first(er._first),
136 : _grainsize(er._grainsize),
137 : _objs(nullptr)
138 : {
139 : // specifically, do *not* copy the vector
140 : }
141 :
142 : /**
143 : * NOTE: When using pthreads this constructor is MANDATORY!!!
144 : *
145 : * Copy constructor. The \p StoredRange can be copied into
146 : * subranges for parallel execution. In this way the
147 : * initial \p StoredRange can be thought of as the root of
148 : * a binary tree. The root element is the only element
149 : * which interacts with the user. It takes a specified
150 : * range of objects and packs it into a contiguous vector
151 : * which can be split efficiently. However, there is no need
152 : * for the child ranges to contain this vector, so long as
153 : * the parent outlives the children. So we implement
154 : * the copy constructor to specifically omit the \p _objs
155 : * vector. This version allows you to set the beginning and
156 : * ending of this new range to be different from that of the
157 : * one we're copying.
158 : */
159 251926 : StoredRange (const StoredRange<iterator_type,object_type> & er,
160 : const const_iterator & begin_range,
161 : const const_iterator & end_range):
162 118143 : _end(end_range),
163 118143 : _begin(begin_range),
164 : _last(0), // Initialize these in a moment
165 : _first(0),
166 251926 : _grainsize(er._grainsize),
167 133783 : _objs(nullptr)
168 : {
169 : // specifically, do *not* copy the vector
170 :
171 251926 : _first = std::distance(er._begin, _begin);
172 251926 : _last = _first + std::distance(_begin, _end);
173 251926 : }
174 :
175 : /**
176 : * Splits the range \p r. The first half
177 : * of the range is left in place, the second
178 : * half of the range is placed in *this.
179 : */
180 : StoredRange (StoredRange<iterator_type,object_type> & r, Threads::split ) :
181 : _end(r._end),
182 : _begin(r._begin),
183 : _last(r._last),
184 : _first(r._first),
185 : _grainsize(r._grainsize),
186 : _objs(nullptr)
187 : {
188 : const_iterator
189 : beginning = r._begin,
190 : ending = r._end,
191 : middle = beginning + std::distance(beginning, ending)/2u;
192 :
193 : r._end = _begin = middle;
194 :
195 : std::size_t
196 : first = r._first,
197 : last = r._last,
198 : half = first + (last-first)/2u;
199 :
200 : r._last = _first = half;
201 : }
202 :
203 : /**
204 : * Destructor. Releases the object array if we created it.
205 : */
206 4144783 : ~StoredRange () = default;
207 :
208 : /**
209 : * Resets the \p StoredRange to contain [first,last).
210 : *
211 : * \returns A reference to itself for convenience, so functions
212 : * expecting a \p StoredRange<> can be passed e.g. foo.reset(begin,end).
213 : */
214 : StoredRange<iterator_type, object_type> &
215 3164109 : reset (const iterator_type & first,
216 : const iterator_type & last)
217 : {
218 : // _objs must be initialized in order to call reset()
219 57429 : libmesh_assert(_objs);
220 :
221 57429 : _objs->clear();
222 :
223 171067459 : for (iterator_type it=first; it!=last; ++it)
224 91350508 : _objs->push_back(*it);
225 :
226 3164109 : _begin = _objs->begin();
227 3164109 : _end = _objs->end();
228 :
229 3164109 : _first = 0;
230 3164109 : _last = _objs->size();
231 :
232 3164109 : return *this;
233 : }
234 :
235 : /**
236 : * Resets the range to the last specified range. This method only exists
237 : * for efficiency -- it is more efficient to set the range to its previous
238 : * value without rebuilding the underlying vector.
239 : *
240 : * \returns A reference to itself for convenience, so functions
241 : * expecting a StoredRange<> can be passed e.g. foo.reset().
242 : */
243 7584 : StoredRange<iterator_type, object_type> & reset ()
244 : {
245 : // _objs must be initialized in order to call reset()
246 7584 : libmesh_assert(_objs);
247 :
248 263303 : _begin = _objs->begin();
249 263303 : _end = _objs->end();
250 :
251 263303 : _first = 0;
252 24813 : _last = _objs->size();
253 :
254 253658 : return *this;
255 : }
256 :
257 : /**
258 : * Beginning of the range.
259 : */
260 4323585 : const_iterator begin () const { return _begin; }
261 :
262 : /**
263 : * End of the range.
264 : */
265 4229579 : const_iterator end () const { return _end; }
266 :
267 : /**
268 : * Index in the stored vector of the first object.
269 : */
270 40060 : std::size_t first_idx () const { return _first; }
271 :
272 : /**
273 : * Index in the stored vector of the last object.
274 : */
275 : std::size_t last_idx () const { return _last; }
276 :
277 : /**
278 : * The grain size for the range. The range will be subdivided into
279 : * subranges not to exceed the grain size.
280 : */
281 : std::size_t grainsize () const {return _grainsize;}
282 :
283 : /**
284 : * Set the grain size.
285 : */
286 : void grainsize (const unsigned int & gs) {_grainsize = gs;}
287 :
288 : /**
289 : * \returns The size of the range.
290 : */
291 853192 : std::size_t size () const { return std::distance(_begin, _end); }
292 :
293 : //------------------------------------------------------------------------
294 : // Methods that implement Range concept
295 : //------------------------------------------------------------------------
296 :
297 : /**
298 : * \returns \p true if the range is empty.
299 : */
300 598 : bool empty() const { return (_begin == _end); }
301 :
302 : /**
303 : * \returns \p true if the range can be subdivided.
304 : */
305 : bool is_divisible() const { return this->grainsize() < static_cast<unsigned int>(std::distance(_begin, _end)); }
306 :
307 : private:
308 :
309 : const_iterator _end;
310 : const_iterator _begin;
311 : std::size_t _last;
312 : std::size_t _first;
313 : std::size_t _grainsize;
314 :
315 : ptr_type _objs;
316 : };
317 :
318 : } // namespace libMesh
319 :
320 : #endif // LIBMESH_STORED_RANGE_H
|
