STL Algorithm Overloads

Overloads for selecting execution policies at runtime. More...

Collaboration diagram for STL Algorithm Overloads:

Functions
template<class InputIt , class OutputIt >
OutputIt	std::copy (const Utopia::ExecPolicy policy, InputIt first, InputIt last, OutputIt d_first)
	Copy the input range to a new range. More...
template<class InputIt , class UnaryFunction >
void	std::for_each (const Utopia::ExecPolicy policy, InputIt first, InputIt last, UnaryFunction f)
	Apply a function to a range. More...
template<class InputIt , class OutputIt , class UnaryOperation >
OutputIt	std::transform (const Utopia::ExecPolicy policy, InputIt first1, InputIt last1, OutputIt d_first, UnaryOperation unary_op)
	Apply a unary operator to a range and store the result in a new range. More...
template<class InputIt1 , class InputIt2 , class OutputIt , class BinaryOperation >
OutputIt	std::transform (const Utopia::ExecPolicy policy, InputIt1 first1, InputIt1 last1, InputIt2 first2, OutputIt d_first, BinaryOperation binary_op)
	Apply a binary operator to two ranges and store the result in a new range. More...

Detailed Description

Overloads for selecting execution policies at runtime.

These algorithms are overloads of the respective STL algorithms where the ExecutionPolicy template parameter has been replaced by the Utopia::ExecPolicy runtime parameter. Developers can use these overloads to have the Utopia Parallel Facilities decide the actual execution policy at runtime. This is done by inserting the algorithm into the Utopia::exec_parallel function.

Using these overloads, developers still have to take care of potential data races, as if they are always executed with the intended execution policy.

How to add more algorithms

To add another algorithm overload, have a look at the original algorithm signature. A list of STL algorithms can be found here. Copy the signature including the ExecutionPolicy. Remove the ExecutionPolicy template parameter and replace the ExecutionPolicy argument with Utopia::ExecPolicy. Inside the function, call Utopia::exec_parallel with the Utopia::ExecPolicy as first argument. The second argument is a generic lambda which captures nothing ([]) and takes a single generic argument which will be a tuple containing the algorithm's arguments (auto&& args_tpl). In the lambda body, create a localized version of your STL algorithm which simply takes a list of arguments and calls the STL algorithm. Depending on the algorithm return type, make sure to return the STL algorithm return value. Finally, add the other arguments of the algorithm overload to the call to Utopia::exec_parallel.

The result looks weird, but wrapping the arguments inside a tuple relieves us from writing different code for the case where std::execution is not defined.

Example:

#include <utopia/core/parallel.hh>
 
// Inject into STL namespace for true overload
namespace std {
 
// Same template signature as sequential `do_stuff`, plus exec policy
template<class InputIt, class OutputIt>
OutputIt
do_stuff(const Utopia::ExecPolicy policy,  // <-- Runtime policy
         InputIt first,
         InputIt last,
         OutputIt d_first)
{
 
    return Utopia::exec_parallel(
        policy,  // <-- Runtime policy passed to this function
        [](auto&& args_tpl) {  // <-- Arguments wrapped into a tuple
            // Create localized version of algorithm for use in std::apply
            auto do_stuff = [](auto&&... args) {
                return std::do_stuff(args...);
            };
 
            // Call the algorithm with the arguments packed into the tuple
            // NOTE: Thanks to the `args_tpl` tuple, this call handles
            //       cases with varying numbers of arguments and in
            //       particular, the case where `std::execution` is not
            //       defined!
            return std::apply(do_stuff, args_tpl);
        },
        // Now add the arguments that will be packed into the tuple
        first,
        last,
        d_first);
}
 
} // namespace std

Function Documentation

copy()

template<class InputIt , class OutputIt >

OutputIt std::copy	(	const Utopia::ExecPolicy	policy,
		InputIt	first,
		InputIt	last,
		OutputIt	d_first
	)

Copy the input range to a new range.

See https://en.cppreference.com/w/cpp/algorithm/copy

for_each()

template<class InputIt , class UnaryFunction >

void std::for_each	(	const Utopia::ExecPolicy	policy,
		InputIt	first,
		InputIt	last,
		UnaryFunction	f
	)

Apply a function to a range.

See https://en.cppreference.com/w/cpp/algorithm/for_each

transform() [1/2]

template<class InputIt , class OutputIt , class UnaryOperation >

OutputIt std::transform	(	const Utopia::ExecPolicy	policy,
		InputIt	first1,
		InputIt	last1,
		OutputIt	d_first,
		UnaryOperation	unary_op
	)

Apply a unary operator to a range and store the result in a new range.

See https://en.cppreference.com/w/cpp/algorithm/transform

transform() [2/2]

template<class InputIt1 , class InputIt2 , class OutputIt , class BinaryOperation >

OutputIt std::transform	(	const Utopia::ExecPolicy	policy,
		InputIt1	first1,
		InputIt1	last1,
		InputIt2	first2,
		OutputIt	d_first,
		BinaryOperation	binary_op
	)

Apply a binary operator to two ranges and store the result in a new range.

See https://en.cppreference.com/w/cpp/algorithm/transform