Debian Codegraph @

include/deal.II/base/thread_management.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2000 - 2025 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_thread_management_h
16 #define dealii_thread_management_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/exceptions.h>
22 #include <deal.II/base/multithread_info.h>
23 #include <deal.II/base/mutex.h>
24 #include <deal.II/base/std_cxx20/type_traits.h>
25 #include <deal.II/base/template_constraints.h>
26
27 #ifdef DEAL_II_WITH_TASKFLOW
28 # include <taskflow/taskflow.hpp>
29 #endif
30
31 #include <atomic>
32 #include <functional>
33 #include <future>
34 #include <list>
35 #include <memory>
36 #include <thread>
37 #include <tuple>
38 #include <utility>
39 #include <vector>
40
41 #ifdef DEAL_II_HAVE_CXX20
42 # include <concepts>
43 #endif
44
45
46 #ifdef DEAL_II_WITH_TBB
47 # include <tbb/task_group.h>
48 #endif
49
50 DEAL_II_NAMESPACE_OPEN
51
52 /**
53 * @addtogroup threads
54 * @{
55 */
56
57 /**
58 * A namespace for the implementation of thread management in deal.II. Most of
59 * the content of this namespace is discussed in detail in one of the reports
60 * linked to from the documentation page of deal.II.
61 *
62 * @ingroup threads
63 */
64 namespace Threads
65 {
66 /**
67 * Split the range <code>[begin,end)</code> into <code>n_intervals</code>
68 * subintervals of equal size. The last interval will be a little bit
69 * larger, if the number of elements in the whole range is not exactly
70 * divisible by <code>n_intervals</code>. The type of the iterators has to
71 * fulfill the requirements of a forward iterator, i.e.
72 * <code>operator++</code> must be available, and of course it must be
73 * assignable.
74 *
75 * A list of subintervals is returned as a vector of pairs of iterators,
76 * where each pair denotes the range <code>[begin[i],end[i])</code>.
77 *
78 * @ingroup threads
79 */
80 template <typename ForwardIterator>
81 std::vector<std::pair<ForwardIterator, ForwardIterator>>
82 split_range(const ForwardIterator &begin,
83 const ForwardIterator &end,
84 const unsigned int n_intervals);
85
86 /**
87 * Split the interval <code>[begin,end)</code> into subintervals of (almost)
88 * equal size. This function works mostly as the one before, with the
89 * difference that instead of iterators, now values are taken that define
90 * the whole interval.
91 *
92 * @ingroup threads
93 */
94 std::vector<std::pair<unsigned int, unsigned int>>
95 split_interval(const unsigned int begin,
96 const unsigned int end,
97 const unsigned int n_intervals);
98
99 /**
100 * @cond internal
101 */
102
103 /**
104 * A namespace in which helper functions and the like for the threading
105 * subsystem are implemented. The members of this namespace are not meant
106 * for public use.
107 */
108 namespace internal
109 {
110 /**
111 * @internal
112 *
113 * If in a sub-thread an exception is thrown, it is not propagated to the
114 * main thread. Therefore, the exception handler that is provided by the
115 * applications main function or some of its other parts will not be able
116 * to catch these exceptions. Therefore, we have to provide an exception
117 * handler in the top function of each sub-thread that at least catches
118 * the exception and prints some information, rather than letting the
119 * operating system to just kill the program without a message. In each of
120 * the functions we use as entry points to new threads, we therefore
121 * install a try-catch block, and if an exception of type
122 * <code>std::exception</code> is caught, it passes over control to this
123 * function, which will then provide some output.
124 */
125 [[noreturn]] void
126 handle_std_exception(const std::exception &exc);
127
128 /**
129 * @internal
130 *
131 * Same as above, but the type of the exception is not derived from
132 * <code>std::exception</code>, so there is little way to provide
133 * something more useful.
134 */
135 [[noreturn]] void
136 handle_unknown_exception();
137 } // namespace internal
138
139 /**
140 * @endcond
141 */
142
143 } // namespace Threads
144
145 /* ----------- implementation of functions in namespace Threads ---------- */
146 #ifndef DOXYGEN
147 namespace Threads
148 {
149 template <typename ForwardIterator>
150 std::vector<std::pair<ForwardIterator, ForwardIterator>>
151 split_range(const ForwardIterator &begin,
152 const ForwardIterator &end,
153 const unsigned int n_intervals)
154 {
155 using IteratorPair = std::pair<ForwardIterator, ForwardIterator>;
156
157 // in non-multithreaded mode, we often have the case that this
158 // function is called with n_intervals==1, so have a shortcut here
159 // to handle that case efficiently
160
161 if (n_intervals == 1)
162 return (std::vector<IteratorPair>(1, IteratorPair(begin, end)));
163
164 // if more than one interval requested, do the full work
165 const unsigned int n_elements = std::distance(begin, end);
166 const unsigned int n_elements_per_interval = n_elements / n_intervals;
167 const unsigned int residual = n_elements % n_intervals;
168
169 std::vector<IteratorPair> return_values(n_intervals);
170
171 return_values[0].first = begin;
172 for (unsigned int i = 0; i < n_intervals; ++i)
173 {
174 if (i != n_intervals - 1)
175 {
176 return_values[i].second = return_values[i].first;
177 // note: the cast is performed to avoid a warning of gcc
178 // that in the library `dist>=0' is checked (dist has a
179 // template type, which here is unsigned if no cast is
180 // performed)
181 std::advance(return_values[i].second,
182 static_cast<signed int>(n_elements_per_interval));
183 // distribute residual in division equally among the first
184 // few subintervals
185 if (i < residual)
186 ++return_values[i].second;
187
188 return_values[i + 1].first = return_values[i].second;
189 }
190 else
191 return_values[i].second = end;
192 }
193 return return_values;
194 }
195 } // namespace Threads
196
197 #endif // DOXYGEN
198
199 namespace Threads
200 {
201 namespace internal
202 {
203 /**
204 * @internal
205 *
206 * Given an arbitrary type RT, store an element of it and grant
207 * access to it through functions get() and set(). There are
208 * specializations for reference types (which need to be stored as
209 * pointers to the object being referenced), and for type void.
210 *
211 * This function is not dissimilar to the `std::promise`/`std::future`
212 * combination of classes. The difference is that a `std::promise`
213 * can only be read once via `std::future::get()` (presumably this
214 * design is due to the fact that `std::future::get()` can throw
215 * an exception previously stored in the `std::promise`). On
216 * the other hand, this class makes the result available for
217 * as many times as desired. It also doesn't store any exceptions
218 * (though they will be forwarded by the classes using the current
219 * class).
220 */
221 template <typename RT>
222 struct return_value
223 {
224 private:
225 RT value;
226 bool value_is_initialized;
227
228 public:
229 using reference_type = RT &;
230
231 inline return_value()
232 : value()
233 , value_is_initialized(false)
234 {}
235
236 inline reference_type
237 get()
238 {
239 Assert(
240 value_is_initialized,
241 ExcMessage(
242 "You cannot read the return value of a thread or task "
243 "if that value has not been set. This happens, for example, if "
244 "a task or thread threw an exception."));
245 return value;
246 }
247
248 inline void
249 set(RT &&v)
250 {
251 value = std::move(v);
252 }
253
254 /**
255 * Set the value from the given `std::future` object. If the future
256 * object holds an exception, the set will not happen and this function
257 * instead throws the exception stored in the future object.
258 */
259 inline void
260 set_from(std::future<RT> &v)
261 {
262 // Get the value from the std::future object. If the future holds
263 // an exception, then the assignment fails, we exit the function via the
264 // exception right away, and value_is_initialized is not set to true --
265 // that's something we can check later on.
266 value = std::move(v.get());
267 value_is_initialized = true;
268 }
269 };
270
271
272 /**
273 * @internal
274 *
275 * Given an arbitrary type RT, store an element of it and grant access to
276 * it through functions get() and set(). This is the specialization for
277 * reference types: since references cannot be set after construction time,
278 * we store a pointer instead, which holds the address of the object being
279 * referenced.
280 *
281 * This function is not dissimilar to the `std::promise`/`std::future`
282 * combination of classes. The difference is that a `std::promise`
283 * can only be read once via `std::future::get()` (presumably this
284 * design is due to the fact that `std::future::get()` can throw
285 * an exception previously stored in the `std::promise`). On
286 * the other hand, this class makes the result available for
287 * as many times as desired. It also doesn't store any exceptions
288 * (though they will be forwarded by the classes using the current
289 * class).
290 */
291 template <typename RT>
292 struct return_value<RT &>
293 {
294 private:
295 RT *value;
296 bool value_is_initialized;
297
298 public:
299 using reference_type = RT &;
300
301 inline return_value()
302 : value(nullptr)
303 , value_is_initialized(false)
304 {}
305
306 inline reference_type
307 get() const
308 {
309 Assert(
310 value_is_initialized,
311 ExcMessage(
312 "You cannot read the return value of a thread or task "
313 "if that value has not been set. This happens, for example, if "
314 "a task or thread threw an exception."));
315 return *value;
316 }
317
318 inline void
319 set(RT &v)
320 {
321 value = &v;
322 }
323
324 /**
325 * Set the value from the given `std::future` object. If the future
326 * object holds an exception, the set will not happen and this function
327 * instead throws the exception stored in the future object.
328 */
329 inline void
330 set_from(std::future<RT &> &v)
331 {
332 // Get the value from the std::future object. If the future holds
333 // an exception, then the assignment fails, we exit the function via the
334 // exception right away, and value_is_initialized is not set to true --
335 // that's something we can check later on.
336 value = &v.get();
337 value_is_initialized = true;
338 }
339 };
340
341
342 /**
343 * @internal
344 *
345 * Given an arbitrary type RT, store an element of it and grant access to
346 * it through functions get() and set(). This is the specialization for
347 * type void: there is obviously nothing to store, so no function set(),
348 * and a function get() that returns void.
349 *
350 * This function is not dissimilar to the `std::promise`/`std::future`
351 * combination of classes. The difference is that a `std::promise`
352 * can only be read once via `std::future::get()` (presumably this
353 * design is due to the fact that `std::future::get()` can throw
354 * an exception previously stored in the `std::promise`). On
355 * the other hand, this class makes the result available for
356 * as many times as desired. It also doesn't store any exceptions
357 * (though they will be forwarded by the classes using the current
358 * class).
359 */
360 template <>
361 struct return_value<void>
362 {
363 using reference_type = void;
364
365 static inline void
366 get()
367 {}
368
369
370 /**
371 * This function does nothing, because the `std::future` object
372 * does not actually hold a return value. However, if the future
373 * object holds an exception, the set will not happen and this function
374 * instead throws the exception stored in the future object.
375 */
376 inline void
377 set_from(std::future<void> &)
378 {}
379 };
380 } // namespace internal
381
382
383
384 namespace internal
385 {
386 /**
387 * A general template that returns std::ref(t) if t is of reference
388 * type, and t otherwise.
389 *
390 * The case that t is of reference type is handled in a partial
391 * specialization declared below.
392 */
393 template <typename T>
394 struct maybe_make_ref
395 {
396 static T
397 act(const T &t)
398 {
399 return t;
400 }
401 };
402
403
404
405 /**
406 * A general template that returns std::ref(t) if t is of reference
407 * type, and t otherwise.
408 *
409 * The case that t is of reference type is handled in this partial
410 * specialization.
411 */
412 template <typename T>
413 struct maybe_make_ref<T &>
414 {
415 static std::reference_wrapper<T>
416 act(T &t)
417 {
418 return std::ref(t);
419 }
420 };
421
422
423
424 /**
425 * Set the value of a std::promise object by evaluating the action.
426 *
427 * @dealiiConceptRequires{(std::invocable<Function> &&
428 * std::convertible_to<std::invoke_result_t<Function>, RT>)}
429 */
430 template <typename RT, typename Function>
431 DEAL_II_CXX20_REQUIRES(
432 (std::invocable<Function> &&
433 std::convertible_to<std::invoke_result_t<Function>, RT>))
434 void evaluate_and_set_promise(Function &function, std::promise<RT> &promise)
435 {
436 promise.set_value(function());
437 }
438
439
440 /**
441 * Set the value of a std::promise object by evaluating the
442 * action. This function is a specialization of the previous one
443 * for the case where the return type is `void`. Consequently, we
444 * can't set a value. But we do evaluate the function object and
445 * call `std::promise::set_value()` without argument.
446 *
447 * @dealiiConceptRequires{(std::invocable<Function>)}
448 */
449 template <typename Function>
450 DEAL_II_CXX20_REQUIRES((std::invocable<Function>))
451 void evaluate_and_set_promise(Function &function,
452 std::promise<void> &promise)
453 {
454 function();
455 promise.set_value();
456 }
457 } // namespace internal
458
459
460
461 /**
462 * This class describes a task object, i.e., what one obtains by calling
463 * Threads::new_task(). The idea is that Threads::new_task() allows one to run
464 * a function whenever the C++ run-time system finds it convenient --
465 * typically, when there is an idle processor available. This can be used to
466 * run things in the background when there is no immediate need for the
467 * result, or if there are other things that could well be done in parallel.
468 * Whenever the result of that background task is needed, one can call either
469 * Threads::Task::join() to just wait for the task to finish, or
470 * Threads::Task::return_value() to obtain the value that was returned by the
471 * function that was run on that background task. In both of these cases, one
472 * continues to reference the *operation* (namely, the Task object) that was
473 * in charge of computing the returned value. An alternative is to use the
474 * Threads::TaskResult class that references the *object* being computed
475 * rather than the task that computes it.
476 *
477 * This class is related to, but semantically not the same as, the
478 * [`std::future`](https://en.cppreference.com/w/cpp/thread/future) class that
479 * is returned by
480 * [`std::async`](https://en.cppreference.com/w/cpp/thread/async) (which is
481 * itself similar to what Threads::new_task() does). The principal conceptual
482 * difference is that `std::future` references the *returned object* (like
483 * Threads::TaskResult) whereas the current object references the task that
484 * computes that result.
485 *
486 * @ingroup threads
487 */
488 template <typename RT = void>
489 class Task
490 {
491 public:
492 /**
493 * Construct a task object, given a function object to execute on
494 * the task, and then schedule this function for
495 * execution. However, when MultithreadInfo::n_threads() returns
496 * 1, i.e., if the deal.II runtime system has been configured to
497 * only use one thread, then just execute the given function
498 * object.
499 *
500 * @post Using this constructor automatically makes the task object
501 * joinable().
502 */
503 Task(const std::function<RT()> &function_object)
504 {
505 if (MultithreadInfo::n_threads() > 1)
506 {
507 #ifdef DEAL_II_WITH_TASKFLOW
508
509 if (MultithreadInfo::get_taskflow_executor().this_worker_id() < 0)
510 {
511 task_data = std::make_shared<TaskData>(
512 MultithreadInfo::get_taskflow_executor().async(
513 function_object));
514 return;
515 }
516 #elif defined(DEAL_II_WITH_TBB)
517 // Create a promise object and from it extract a future that
518 // we can use to refer to the outcome of the task. For reasons
519 // explained below, we can't just create a std::promise object,
520 // but have to make do with a pointer to such an object.
521 std::unique_ptr<std::promise<RT>> promise =
522 std::make_unique<std::promise<RT>>();
523 task_data =
524 std::make_shared<TaskData>(std::move(promise->get_future()));
525
526 // Then start the task, using a task_group object (for just this one
527 // task) that is associated with the TaskData object. Note that we
528 // have to *copy* the function object being executed so that it is
529 // guaranteed to live on the called thread as well -- the copying is
530 // facilitated by capturing the 'function_object' variable by value.
531 //
532 // We also have to *move* the promise object into the new task's
533 // memory space because promises can not be copied and we can't refer
534 // to it by reference because it's a local variable of the current
535 // (surrounding) function that may go out of scope before the promise
536 // is ultimately set. This leads to a conundrum: if we had just
537 // declared 'promise' as an object of type std::promise, then we could
538 // capture it in the lambda function via
539 // [..., promise=std::move(promise)]() {...}
540 // and set the promise in the body of the lambda. But setting a
541 // promise is a non-const operation on the promise, and so we would
542 // actually have to declare the lambda function as 'mutable' because
543 // by default, lambda captures are 'const'. That is, we would have
544 // to write
545 // [..., promise=std::move(promise)]() mutable {...}
546 // But this leads to other problems: It turns out that the
547 // tbb::task_group::run() function cannot take mutable lambdas as
548 // argument :-(
549 //
550 // We work around this issue by not declaring the 'promise' variable
551 // as an object of type std::promise, but as a pointer to such an
552 // object. This pointer we can move, and the *pointer* itself can
553 // be 'const' (meaning we can leave the lambda as non-mutable)
554 // even though we modify the object *pointed to*. One would think
555 // that a std::unique_ptr would be the right choice for this, but
556 // that's not true: the resulting lambda function can then be
557 // non-mutable, but the lambda function object is not copyable
558 // and at least some TBB variants require that as well. So
559 // instead we move the std::unique_ptr used above into a
560 // std::shared_ptr to be stored within the lambda function object.
561 task_data->task_group->run(
562 [function_object,
563 promise =
564 std::shared_ptr<std::promise<RT>>(std::move(promise))]() {
565 try
566 {
567 internal::evaluate_and_set_promise(function_object, *promise);
568 }
569 catch (...)
570 {
571 try
572 {
573 // store anything thrown in the promise
574 promise->set_exception(std::current_exception());
575 }
576 catch (...)
577 {
578 // set_exception() may throw too. But ignore this on
579 // the task.
580 }
581 }
582 });
583 return;
584
585 #else
586 // If no threading library is supported, just fall back onto C++11
587 // facilities. The problem with this is that the standard does
588 // not actually say what std::async should do. The first
589 // argument to that function can be std::launch::async or
590 // std::launch::deferred, or both. The *intent* of the standard's
591 // authors was probably that if one sets it to
592 // std::launch::async | std::launch::deferred,
593 // that the task is run in a thread pool. But at least as of
594 // 2021, GCC doesn't do that: It just runs it on a new thread.
595 // If one chooses std::launch::deferred, it runs the task on
596 // the same thread but only when one calls join() on the task's
597 // std::future object. In the former case, this leads to
598 // oversubscription, in the latter case to undersubscription of
599 // resources. We choose oversubscription here.
600 //
601 // The issue illustrates why relying on external libraries
602 // with task schedulers is the way to go.
603 task_data = std::make_shared<TaskData>(
604 std::async(std::launch::async | std::launch::deferred,
605 function_object));
606 return;
607 #endif
608 }
609 {
610 // Only one thread allowed. So let the task run to completion
611 // and just emplace a 'ready' future.
612 //
613 // The design of std::promise/std::future is unclear, but it
614 // seems that the intent is to obtain the std::future before
615 // we set the std::promise. So create the TaskData object at
616 // the top and then run the task and set the returned
617 // value. Since everything here happens sequentially, it
618 // really doesn't matter in which order all of this is
619 // happening.
620 std::promise<RT> promise;
621 task_data = std::make_shared<TaskData>(promise.get_future());
622 try
623 {
624 internal::evaluate_and_set_promise(function_object, promise);
625 }
626 catch (...)
627 {
628 try
629 {
630 // store anything thrown in the promise
631 promise.set_exception(std::current_exception());
632 }
633 catch (...)
634 {
635 // set_exception() may throw too. But ignore this on
636 // the task.
637 }
638 }
639 }
640 }
641
642 /**
643 * Default constructor. You can't do much with a task object constructed
644 * this way, except for assigning it a task object that holds data created
645 * by the Threads::new_task() functions.
646 *
647 * @post Using this constructor leaves the object in an unjoinable state,
648 * i.e., joinable() will return false.
649 */
650 Task() = default;
651
652 /**
653 * Copy constructor. At the end of this operation, both the original and the
654 * new object refer to the same task, and both can ask for the returned
655 * object. That is, if you do
656 * @code
657 * Threads::Task<T> t1 = Threads::new_task(...);
658 * Threads::Task<T> t2 (t1);
659 * @endcode
660 * then calling `t2.return_value()` will return the same object (not just an
661 * object with the same value, but in fact the same address!) as
662 * calling `t1.return_value()`.
663 */
664 Task(const Task &other) = default;
665
666 /**
667 * Move constructor. At the end of this operation, the original object no
668 * longer refers to a task, and the new object refers to the same task
669 * as the original one originally did. That is, if you do
670 * @code
671 * Threads::Task<T> t1 = Threads::new_task(...);
672 * Threads::Task<T> t2 (std::move(t1));
673 * @endcode
674 * then calling `t2.return_value()` will return the object computed by
675 * the task, and `t1.return_value()` will result in an error because `t1`
676 * no longer refers to a task and consequently does not know anything
677 * about a return value.
678 */
679 Task(Task &&other) noexcept = default;
680
681 /**
682 * Copy operator. At the end of this operation, both the right hand and the
683 * left hand object refer to the same task, and both can ask for the
684 * returned object. That is, if you do
685 * @code
686 * Threads::Task<T> t1 = Threads::new_task(...);
687 * Threads::Task<T> t2;
688 * t2 = t1;
689 * @endcode
690 * then calling `t2.return_value()` will return the same object (not just an
691 * object with the same value, but in fact the same address!) as
692 * calling `t1.return_value()`.
693 */
694 Task &
695 operator=(const Task &other) = default;
696
697 /**
698 * Move operator. At the end of this operation, the right hand side object
699 * no longer refers to a task, and the left hand side object refers to the
700 * same task as the right hand side one originally did. That is, if you do
701 * @code
702 * Threads::Task<T> t1 = Threads::new_task(...);
703 * Threads::Task<T> t2;
704 * t2 = std::move(t1);
705 * @endcode
706 * then calling `t2.return_value()` will return the object computed by
707 * the task, and `t1.return_value()` will result in an error because `t1`
708 * no longer refers to a task and consequently does not know anything
709 * about a return value.
710 */
711 Task &
712 operator=(Task &&other) noexcept = default;
713
714 /**
715 * Join the task represented by this object, i.e. wait for it to finish.
716 *
717 * A task can be joined multiple times (while the first join() operation
718 * may block until the task has completed running, all successive attempts
719 * to join will return immediately).
720 *
721 * If the operation that was executed on the task with which this
722 * object was initialized throws an exception instead of returning
723 * regularly, then calling the current join() function will first
724 * wait for that task to finish, and then in turn throw the
725 * exception that the task operation had thrown originally. This
726 * allows for the propagation of exceptions from tasks executed on
727 * a separate thread to the calling thread.
728 *
729 * (This behavior differs from that of
730 * [`std::future`](https://en.cppreference.com/w/cpp/thread/future),
731 * where the `std::future::wait()` function only waits for
732 * completion of the operation, whereas the exception is
733 * propagated only once one calls `std::future::get()`. However,
734 * this is awkward when putting `void` functions onto separate
735 * tasks because these do not actually return anything;
736 * consequently, it is more natural to call `std::task::wait()`
737 * for such tasks than the `std::task::get()` function since the
738 * latter does not, actually, return anything that could be
739 * gotten.)
740 *
741 * @pre You can't call this function if you have used the default
742 * constructor of this class and have not assigned a task object to it. In
743 * other words, the function joinable() must return true.
744 */
745 void
746 join() const
747 {
748 // Make sure we actually have a task that we can wait for.
749 AssertThrow(joinable(), ExcNoTask());
750
751 task_data->wait();
752 }
753
754 /**
755 * Return whether the current object can be joined. You can join a task
756 * object once a task (typically created with Threads::new_task()) has
757 * actually been assigned to it. On the other hand, the function returns
758 * false if the object has been default constructed.
759 *
760 * A task can be joined multiple times (while the first join() operation
761 * may block until the task has completed running, all successive attempts
762 * to join will return immediately). Consequently, if this function
763 * returns true, it will continue to return true until the task object it
764 * reports on is assigned to from another object.
765 */
766 bool
767 joinable() const
768 {
769 return (task_data != nullptr);
770 }
771
772
773 /**
774 * Get the return value of the function of the task. Since it is
775 * only available once the thread finishes, this function
776 * internally also calls join(). You can call this function
777 * multiple times as long as the object refers to the same task,
778 * and expect to get the same return value every time. (With the
779 * exception of the case where the returned object has been moved;
780 * see below.)
781 *
782 * @note The function returns a <i>non-@p const reference</i> to
783 * the returned object, instead of the returned object. This
784 * allows writing code such as
785 * @code
786 * Threads::Task<int> t = Threads::new_task (...function returning an
787 * int...); t.return_value() = 42; // overwrite returned value int i =
788 * t.return_value(); // i is now 42
789 * @endcode
790 * You will rarely have a need to write such code. On the other hand,
791 * the function needs to return a writable (non-@p const) reference to
792 * support code such as this:
793 * @code
794 * std::unique_ptr<int> create_int (const std::string &s) { ... }
795 *
796 * void f()
797 * {
798 * Threads::Task<std::unique_ptr<int>>
799 * t = Threads::new_task (&create_int, "42");
800 *
801 * std::unique_ptr<int> i = std::move(t.return_value());
802 * ...
803 * }
804 * @endcode
805 * Here, it is necessary to `std::move` the returned object (namely,
806 * the <code>std::unique_ptr</code> object) because
807 * <code>std::unique_ptr</code> objects can not be copied. In other words,
808 * to get the pointer out of the object returned from the task, it needs
809 * to be moved, and in order to be moved, the current function needs to
810 * return a writable (non-@p const) reference.
811 *
812 * This function internally calls the join() member function. As a
813 * consequence, and as explained there, if the packaged task
814 * throws an exception that is then re-thrown by the join()
815 * function and consequently also the current function if you have
816 * not previously called join().
817 *
818 * @pre You can't call this function if you have used the default
819 * constructor of this class and have not assigned a task object to it. In
820 * other words, the function joinable() must return true.
821 */
822 typename internal::return_value<RT>::reference_type
823 return_value()
824 {
825 // Make sure we actually have a task that we can wait for.
826 AssertThrow(joinable(), ExcNoTask());
827
828 // Then return the promised object. If necessary, wait for the promise to
829 // be set.
830 return task_data->get();
831 }
832
833
834 /**
835 * @addtogroup Exceptions
836 * @{
837 */
838
839 /**
840 * Exception
841 */
842 DeclExceptionMsg(ExcNoTask,
843 "The current object is not associated with a task that "
844 "can be joined. It may have been detached, or you "
845 "may have already joined it in the past.");
846 /** @} */
847 private:
848 /**
849 * A data structure that holds a std::future into which the task deposits
850 * its return value. Since one can only call std::future::get() once,
851 * we do so in the get() member function and then move the returned object
852 * into the `returned_object` member variable from where we can read it
853 * multiple times and from where it can also be moved away if it is not
854 * copyable.
855 */
856 class TaskData
857 {
858 public:
859 /**
860 * Constructor. Initializes an std::future object and assumes
861 * that the task so set has not finished yet.
862 */
863 TaskData(std::future<RT> &&future) noexcept
864 : future(std::move(future))
865 , task_has_finished(false)
866 #ifdef DEAL_II_WITH_TBB
867 , task_group(std::make_unique<tbb::task_group>())
868 #endif
869 {}
870
871 /**
872 * There can only be one TaskData object referencing
873 * a task. Make sure that these objects are not copied.
874 */
875 TaskData(const TaskData &) = delete;
876
877 /**
878 * There can only be one TaskData object referencing
879 * a task. Make sure that these objects are not moved.
880 */
881 TaskData(TaskData &&) = delete;
882
883 /**
884 * There can only be one TaskData object referencing
885 * a task. Make sure that these objects are not copied.
886 */
887 TaskData &
888 operator=(const TaskData &) = delete;
889
890 /**
891 * There can only be one TaskData object referencing
892 * a task. Make sure that these objects are not moved.
893 */
894 TaskData &
895 operator=(TaskData &&) = delete;
896
897 /**
898 * Destructor. Wait for the results to be ready. This ensures that the
899 * last Task object holding a shared pointer to the current TaskData
900 * object blocks until the task has actually finished -- in essence,
901 * this makes sure that one cannot just abandon a task completely
902 * by letting all Task objects that point to it go out of scope.
903 */
904 ~TaskData() noexcept
905 {
906 // Explicitly wait for the results to be ready. This class stores
907 // a std::future object, and we could just let the compiler generate
908 // the destructor which would then call the destructor of std::future
909 // which *may* block until the future is ready. As explained in
910 // https://en.cppreference.com/w/cpp/thread/future/~future
911 // this is only a *may*, not a *must*. (The standard does not
912 // appear to say anything about it at all.) As a consequence,
913 // let's be explicit about waiting.
914 //
915 // One of the corner cases we have to worry about is that if a task
916 // ends by throwing an exception, then wait() will re-throw that
917 // exception on the thread that calls it, the first time around
918 // someone calls wait() (or the return_value() function of the
919 // surrounding class). So if we get to this constructor and an exception
920 // is thrown by wait(), then that means that the last Task object
921 // referring to a task is going out of scope with nobody having
922 // ever checked the return value of the task itself. In that case,
923 // one could argue that they would also not have cared about whether
924 // an exception is thrown, and that we should simply ignore the
925 // exception. This is what we do here. It is also the simplest solution,
926 // because we don't know what one should do with the exception to begin
927 // with: destructors aren't allowed to throw exceptions, so we can't
928 // just rethrow it here if one had been triggered.
929 try
930 {
931 wait();
932 }
933 catch (...)
934 {}
935 }
936
937 /**
938 * Wait for the std::future object to be ready, i.e., for the
939 * time when the std::promise receives its value. If this has
940 * already happened, this function can follow a fast path.
941 */
942 void
943 wait()
944 {
945 // If we have previously already moved the result, then we don't
946 // need a lock and can just return.
947 if (task_has_finished)
948 return;
949
950 // Else, we need to go under a lock and try again. A different thread
951 // may have waited and finished the task since then, so we have to try
952 // a second time. (This is Schmidt's double-checking pattern.)
953 std::lock_guard<std::mutex> lock(mutex);
954 if (task_has_finished)
955 return;
956 else
957 {
958 #ifdef DEAL_II_WITH_TASKFLOW
959 // We want to call executor.corun_until() to keep scheduling tasks
960 // until the task we are waiting for has actually finished. The
961 // problem is that TaskFlow documents that you can only call
962 // corun_until() on a worker of the executor. In other words, we
963 // can call it from *inside* other tasks, but not from the main
964 // thread (or other threads that might have been created outside
965 // of TaskFlow).
966 //
967 // Fortunately, we can check whether we are on a worker thread:
968 if (MultithreadInfo::get_taskflow_executor().this_worker_id() >= 0)
969 MultithreadInfo::get_taskflow_executor().corun_until([this]() {
970 return (future.wait_for(std::chrono::seconds(0)) ==
971 std::future_status::ready);
972 });
973 else
974 // We are on a thread not managed by TaskFlow. In that case, we
975 // can simply stop the current thread to wait for the task to
976 // finish (i.e., for the std::future object to become ready). We
977 // can do this because we need not fear that this leads to a
978 // deadlock: The current threads is waiting for completion of a
979 // task that is running on a completely different set of
980 // threads, and so not making any progress here can not deprive
981 // these other threads of the ability to schedule their tasks.
982 //
983 // Indeed, this is even true if the current thread is a worker
984 // of one executor and we are waiting for a task running on a
985 // different executor: The current task being stopped may block
986 // the current executor from scheduling more tasks, but it is
987 // unrelated to the tasks of the scheduler for which we are
988 // waiting for something, and so that other executor will
989 // eventually get around to scheduling the task we are waiting
990 // for, at which point the current task will also complete.
991 future.wait();
992
993 #elif defined(DEAL_II_WITH_TBB)
994 // If we build on the TBB, then we can't just wait for the
995 // std::future object to get ready. Apparently the TBB happily
996 // enqueues a task into an arena and then just sits on it without
997 // ever executing it unless someone expresses an interest in the
998 // task. The way to avoid this is to add the task to a
999 // tbb::task_group, and then here wait for the single task
1000 // associated with that task group.
1001 //
1002 // This also makes sense from another perspective. Imagine that
1003 // we allow at most N threads, and that we create N+1 tasks in such
1004 // a way that the first N all wait for the (N+1)st task to finish.
1005 // (See the multithreading/task_17 test for an example.) If they
1006 // all just sit in their std::future::wait() function, nothing
1007 // is ever going to happen because the scheduler sees that N tasks
1008 // are currently running and is never informed that all they're
1009 // doing is wait for another task to finish. What *needs* to
1010 // happen is that the wait() or join() function goes back into
1011 // the scheduler to make sure the scheduler knows that these
1012 // tasks are not actually using CPU time on the thread they're
1013 // working on, and that it is time to run other tasks on the
1014 // same thread -- this is the way we can eventually get that
1015 // (N+1)st task executed, which then unblocks the other N threads.
1016 // (Note that this also implies that multiple tasks can be
1017 // executing on the same thread at the same time -- not
1018 // concurrently, of course, but with one executing and the others
1019 // currently waiting for other tasks to finish.)
1020 //
1021 // If we get here, we know for a fact that atomically
1022 // (because under a lock), no other thread has so far
1023 // determined that we are finished and removed the
1024 // 'task_group' object. So we know that the pointer is
1025 // still valid. But we also know that, because below we
1026 // set the task_has_finished flag to 'true', that no other
1027 // thread will ever get back to this point and query the
1028 // 'task_group' object, so we can delete it.
1029 task_group->wait();
1030 task_group.reset();
1031 #endif
1032
1033 // Wait for the task to finish and then move its
1034 // result. (We could have made the set_from() function
1035 // that we call here wait for the future to be ready --
1036 // which happens implicitly when it calls future.get() --
1037 // but that would have required putting an explicit
1038 // future.wait() into the implementation of
1039 // internal::return_value<void>::set_from(), which is a
1040 // bit awkward: that class doesn't actually need to set
1041 // anything, and so it looks odd to have the explicit call
1042 // to future.wait() in the set_from() function. Avoid the
1043 // issue by just explicitly calling future.wait() here.)
1044 future.wait();
1045
1046 // Acquire the returned object. If the task ended in an
1047 // exception, `set_from` will call `std::future::get`, which
1048 // will throw an exception. This leaves `returned_object` in
1049 // an undefined state, but moreover we would bypass setting
1050 // `task_has_finished=true` below. So catch the exception
1051 // for just long enough that we can set that flag, and then
1052 // re-throw it:
1053 try
1054 {
1055 returned_object.set_from(future);
1056 }
1057 catch (...)
1058 {
1059 task_has_finished = true;
1060 throw;
1061 }
1062
1063 // If we got here, the task has ended without an exception and
1064 // we can safely set the flag and return.
1065 task_has_finished = true;
1066 }
1067 }
1068
1069
1070
1071 typename internal::return_value<RT>::reference_type
1072 get()
1073 {
1074 wait();
1075 return returned_object.get();
1076 }
1077
1078 private:
1079 /**
1080 * A mutex used to synchronize access to the data structures of this
1081 * class.
1082 */
1083 std::mutex mutex;
1084
1085 /**
1086 * The promise associated with the task that is represented by the current
1087 * class.
1088 */
1089 std::future<RT> future;
1090
1091 /**
1092 * A boolean indicating whether the task in question has finished.
1093 *
1094 * @note We are using a `std::atomic_bool` here because we have
1095 * to make sure that concurrent reads and stores between threads are
1096 * properly synchronized, and that sequential reads on a given thread
1097 * are not reordered or optimized away. A std::atomic [1] achieves
1098 * this because (if not otherwise annotated) reads and stores to the
1099 * boolean are subject to the std::memory_order_seq_cst memory
1100 * ordering [2]. This ensures that Schmidt's double checking does
1101 * indeed work. For additional information (and a potentially more
1102 * efficient implementation) see [3].
1103 *
1104 * [1] https://en.cppreference.com/w/cpp/atomic/atomic
1105 * [2] https://en.cppreference.com/w/cpp/atomic/memory_order
1106 * [3]
1107 * https://preshing.com/20130930/double-checked-locking-is-fixed-in-cpp11/
1108 */
1109 std::atomic<bool> task_has_finished;
1110
1111 /**
1112 * The place where the returned value is moved to once the std::future
1113 * has delivered.
1114 */
1115 internal::return_value<RT> returned_object;
1116
1117 #ifdef DEAL_II_WITH_TBB
1118 /**
1119 * A task group object we can wait for. This object is created in
1120 * the constructor, and is removed as soon as we have determined
1121 * that the task has finished, so as to free any resources the TBB
1122 * may still be holding in order to allow programs to still check
1123 * on the status of a task in this group.
1124 */
1125 std::unique_ptr<tbb::task_group> task_group;
1126
1127 friend class Task<RT>;
1128 #endif
1129 };
1130
1131 /**
1132 * A pointer to a descriptor of the object that described the task
1133 * and its return value.
1134 */
1135 std::shared_ptr<TaskData> task_data;
1136 };
1137
1138
1139
1140 /**
1141 * Overload of the new_task function for objects that can be converted to
1142 * std::function<RT ()>, i.e. anything that can be called like a
1143 * function object without arguments and returning an object of type RT (or
1144 * void).
1145 *
1146 * @note When MultithreadInfo::n_threads() returns 1, i.e., if the
1147 * deal.II runtime system has been configured to only use one
1148 * thread, then this function just executes the given function
1149 * object immediately and stores the return value in the Task
1150 * object returned by this function.
1151 *
1152 * @note Threads::new_task() is, in essence, equivalent to calling
1153 * `std::async(std::launch::async, ...)` in that it runs the given task
1154 * in the background. See https://en.cppreference.com/w/cpp/thread/async
1155 * for more information.
1156 *
1157 * @ingroup threads
1158 */
1159 template <typename RT>
1160 inline Task<RT>
1161 new_task(const std::function<RT()> &function)
1162 {
1163 return Task<RT>(function);
1164 }
1165
1166
1167
1168 /**
1169 * Overload of the new_task function for objects that can be called like a
1170 * function object without arguments. In particular, this function allows
1171 * calling Threads::new_task() with either objects that result from using
1172 * std::bind, or using lambda functions. For example, this function is called
1173 * when writing code such as
1174 * @code
1175 * Threads::Task<int>
1176 * task = Threads::new_task ( [] () {
1177 * do_this();
1178 * then_do_that();
1179 * return 42;
1180 * });
1181 * @endcode
1182 * Here, we schedule the call to the sequence of functions
1183 * <code>do_this()</code> and <code>then_do_that()</code> on
1184 * a separate task, by making the lambda function declared here the
1185 * function to execute on the task. The lambda function then returns
1186 * 42 (which is a bit pointless here, but it could of course be some
1187 * computed number), and this is going to be the returned value you
1188 * can later retrieve via <code>task.return_value()</code> once the
1189 * task (i.e., the body of the lambda function) has completed.
1190 *
1191 * @note When MultithreadInfo::n_threads() returns 1, i.e., if the
1192 * deal.II runtime system has been configured to only use one
1193 * thread, then this function just executes the given function
1194 * object immediately and stores the return value in the Task
1195 * object returned by this function.
1196 *
1197 * @note Every lambda function (or whatever else it is you pass to
1198 * the new_task() function here, for example the result of a
1199 * std::bind() expression) has a return type and consequently
1200 * returns an object of this type. This type can be inferred
1201 * using the C++11 <code>decltype</code> statement used in the
1202 * declaration of this function, and it is then used as the template
1203 * argument of the Threads::Task object returned by the current function.
1204 * In the example above, because the lambda function returns 42
1205 * (which in C++ has data type <code>int</code>), the inferred
1206 * type is <code>int</code> and the task object will have type
1207 * <code>Task@<int@></code>. In other words, it is not <i>necessary</i>
1208 * to explicitly specify in user code what that return type
1209 * of the lambda or std::bind expression will be, though it is
1210 * possible to explicitly do so by (entirely equivalently) writing
1211 * @code
1212 * Threads::Task<int>
1213 * task = Threads::new_task ( [] () -> int {
1214 * do_this();
1215 * then_do_that();
1216 * return 42;
1217 * });
1218 * @endcode
1219 *
1220 * @note In practice, the lambda functions you will pass to
1221 * new_task() will of course typically be more complicated.
1222 * In particular, they will likely <i>capture</i> variables
1223 * from the surrounding context and use them within the lambda.
1224 * See
1225 * https://en.wikipedia.org/wiki/Anonymous_function#C.2B.2B_.28since_C.2B.2B11.29
1226 * for more on how lambda functions work.
1227 *
1228 * @note If you pass a lambda function as an argument to the
1229 * current function that captures a variable <i>by reference</i>,
1230 * or if you use a std::bind that binds a function argument to
1231 * a reference variable using std::ref() or std::cref(), then
1232 * obviously you can only do this if the variables you reference
1233 * or capture have a lifetime that extends at least until the time
1234 * where the task finishes.
1235 *
1236 * @note Threads::new_task() is, in essence, equivalent to calling
1237 * `std::async(std::launch::async, ...)` in that it runs the given task
1238 * in the background. See https://en.cppreference.com/w/cpp/thread/async
1239 * for more information.
1240 *
1241 * @ingroup CPP11
1242 *
1243 * @dealiiConceptRequires{(std::invocable<FunctionObjectType>)}
1244 */
1245 template <typename FunctionObjectType>
1246 DEAL_II_CXX20_REQUIRES((std::invocable<FunctionObjectType>))
1247 inline auto new_task(FunctionObjectType function_object)
1248 -> Task<decltype(function_object())>
1249 {
1250 using return_type = decltype(function_object());
1251 dealii::MultithreadInfo::initialize_multithreading();
1252 return new_task(std::function<return_type()>(function_object));
1253 }
1254
1255
1256
1257 /**
1258 * Overload of the new_task function for non-member or static member
1259 * functions. See the other functions of same name for more information.
1260 *
1261 * @ingroup threads
1262 */
1263 template <typename RT, typename... Args>
1264 inline Task<RT>
1265 new_task(RT (*fun_ptr)(Args...), std_cxx20::type_identity_t<Args>... args)
1266 {
1267 auto dummy = std::make_tuple(internal::maybe_make_ref<Args>::act(args)...);
1268 return new_task(
1269 [dummy, fun_ptr]() -> RT { return std::apply(fun_ptr, dummy); });
1270 }
1271
1272
1273
1274 /**
1275 * Overload of the new_task function for other kinds of function objects
1276 * passed as first argument. This overload applies to cases where the first
1277 * argument is a lambda function that takes arguments (whose values are then
1278 * provided via subsequent arguments), or other objects that have function
1279 * call operators.
1280 *
1281 * This overload is useful when creating multiple tasks using the same lambda
1282 * function, but for different arguments. Say in code such as this:
1283 * @code
1284 * std::vector<Triangulation<dim>> triangulations;
1285 * [... initialize triangulations ...]
1286 *
1287 * auto something_expensive = [](const Triangulation<dim> &t) {...};
1288 *
1289 * // Apply something_expensive() to all elements of the collection of
1290 * // triangulations:
1291 * Threads::TaskGroup<> task_group;
1292 * for (const Triangulation<dim> &t : triangulations)
1293 * task_group += Threads::new_task (something_expensive, t);
1294 * task_group.join_all();
1295 * @endcode
1296 *
1297 * See the other functions of same name for more information.
1298 *
1299 * @note This overload is disabled if the first argument is a
1300 * pointer or reference to a function, as there is another overload
1301 * for that case. (Strictly speaking, this overload is disabled if the
1302 * first argument is a reference to a function or any kind of pointer.
1303 * But since only pointers to functions are invocable like functions,
1304 * and since another part of the declaration checks that the first
1305 * argument is invocable, testing that the first argument is not a
1306 * pointer is sufficient. We use this scheme because there is no type
1307 * trait to check whether something is a pointer-to-function: there
1308 * is only `std::is_pointer` and `std::is_function`, the latter of
1309 * which checks whether a type is a reference-to-function; but there is
1310 * no type trait for pointer-to-function.)
1311 *
1312 * @ingroup threads
1313 */
1314 template <
1315 typename FunctionObject,
1316 typename... Args,
1317 typename = std::enable_if_t<std::is_invocable_v<FunctionObject, Args...>>,
1318 typename = std::enable_if_t<std::is_function_v<FunctionObject> == false>,
1319 typename =
1320 std::enable_if_t<std::is_member_pointer_v<FunctionObject> == false>,
1321 typename = std::enable_if_t<std::is_pointer_v<FunctionObject> == false>>
1322 inline Task<std::invoke_result_t<FunctionObject, Args...>>
1323 new_task(const FunctionObject &fun, Args &&...args)
1324 {
1325 using RT = std::invoke_result_t<FunctionObject, Args...>;
1326 auto dummy = std::make_tuple(std::forward<Args>(args)...);
1327 return new_task([dummy, fun]() -> RT { return std::apply(fun, dummy); });
1328 }
1329
1330
1331
1332 /**
1333 * Overload of the non-const new_task function. See the other functions of
1334 * same name for more information.
1335 *
1336 * @ingroup threads
1337 */
1338 template <typename RT, typename C, typename... Args>
1339 inline Task<RT>
1340 new_task(RT (C::*fun_ptr)(Args...),
1341 std_cxx20::type_identity_t<C> &c,
1342 std_cxx20::type_identity_t<Args>... args)
1343 {
1344 // NOLINTNEXTLINE(modernize-avoid-bind) silence clang-tidy
1345 return new_task(std::function<RT()>(std::bind(
1346 fun_ptr, std::ref(c), internal::maybe_make_ref<Args>::act(args)...)));
1347 }
1348
1349 /**
1350 * Overload of the new_task function. See the other functions of same name for
1351 * more information.
1352 *
1353 * @ingroup threads
1354 */
1355 template <typename RT, typename C, typename... Args>
1356 inline Task<RT>
1357 new_task(RT (C::*fun_ptr)(Args...) const,
1358 std_cxx20::type_identity_t<const C> &c,
1359 std_cxx20::type_identity_t<Args>... args)
1360 {
1361 // NOLINTNEXTLINE(modernize-avoid-bind) silence clang-tidy
1362 return new_task(std::function<RT()>(std::bind(
1363 fun_ptr, std::cref(c), internal::maybe_make_ref<Args>::act(args)...)));
1364 }
1365
1366
1367 // ------------------------ TaskGroup -------------------------------------
1368
1369 /**
1370 * A container for task objects. Allows to add new task objects and wait for
1371 * them all together. The task objects need to have the same return value
1372 * for the called function.
1373 *
1374 * Note that the call to join_all() must be executed on the same thread as
1375 * the calls that add subtasks. Otherwise, there might be a deadlock. In
1376 * other words, a Task object should never passed on to another task for
1377 * calling the join() method.
1378 */
1379 template <typename RT = void>
1380 class TaskGroup
1381 {
1382 public:
1383 /**
1384 * Add another task object to the collection.
1385 */
1386 TaskGroup &
1387 operator+=(const Task<RT> &t)
1388 {
1389 tasks.push_back(t);
1390 return *this;
1391 }
1392
1393
1394 /**
1395 * Return how many tasks have been put into this group. This
1396 * function does not distinguish how many of these tasks have
1397 * already run and have finished, are still waiting to be
1398 * scheduled to a CPU resource, or are currently running. Tasks
1399 * that have been joined already are also still counted.
1400 */
1401 std::size_t
1402 size() const
1403 {
1404 return tasks.size();
1405 }
1406
1407 /**
1408 * Return a vector of objects that contain the return values of
1409 * the tasks contained in this group. This function can obviously
1410 * only return once all tasks are completed.
1411 *
1412 * The returned vector contains the returned values of tasks in
1413 * the same order in which these tasks were added to the task
1414 * group.
1415 *
1416 * @note This function only makes sense if `RT` is an actual data
1417 * type, rather than `void`. If the TaskGroup stores tasks that have
1418 * no return value, then you should simply call `join_all()`, which
1419 * also waits for all tasks to finish.
1420 */
1421 std::vector<RT>
1422 return_values()
1423 {
1424 std::vector<RT> results;
1425 results.reserve(size());
1426 for (auto &t : tasks)
1427 results.emplace_back(std::move(t.return_value()));
1428 return results;
1429 }
1430
1431
1432 /**
1433 * Wait for all tasks in the collection to finish. It is not a problem if
1434 * some of them have already been waited for, i.e. you may call this
1435 * function more than once, and you can also add new task objects between
1436 * subsequent calls to this function if you want.
1437 */
1438 void
1439 join_all() const
1440 {
1441 for (const auto &t : tasks)
1442 t.join();
1443 }
1444
1445 private:
1446 /**
1447 * List of task objects.
1448 */
1449 std::list<Task<RT>> tasks;
1450 };
1451
1452 } // namespace Threads
1453
1454 /**
1455 * @}
1456 */
1457
1458
1459 DEAL_II_NAMESPACE_CLOSE
1460 #endif