Execution Policy of STL Algorithms in Modern C++

C++ algorithms are a set of pre-defined functions that can perform various operations on containers, such as arrays, vectors, and lists. These algorithms have a defined execution policy that determines how they execute and how they interact with the underlying hardware.

The C++ 17 standard introduces three new execution policies and one policy was introduced in C++20. These execution policies in C++ allow algorithms to be executed in different ways depending on the requirements of the task and the hardware available. They are as follows:

std::execution::sequenced_policy
std::execution::parallel_policy
std::execution::parallel_unsequenced_policy
std::execution::unsequenced_policy

1. std::execution::sequenced_policy

This policy specifies that the algorithm should execute sequentially, i.e., without parallelization. When no execution policy is specified, the algorithms will be executed sequentially.

Syntax of sequenced_policy

stlFunction (std::execution::seq, ...other_arguments...);

We just have to pass the execution policy object names as std::execution::seq as an argument to the supported STL function. The functions are already overloaded to accept it.

Example of sequenced_policy

C++

#include <algorithm>

#include <iostream>

#include <vector>

#include <execution>

int main()

std::vector<int> v = 5, 2, 3, 1, 4 ;

std::sort(std::execution::seq, v.begin(), v.end());

for (auto i : v)

std::cout << i << " ";

return 0;

Output

5 4 3 2 1

In this example, we create a vector of integers and then sort its elements using the std::sort algorithm with the std::execution::seq policy. The result is a sorted vector with elements 1, 2, 3, 4, 5 .

Advantages of sequenced_policy

Simple and predictable.
Avoid data races.
Good for small tasks as parallel overhead does not exist.

Disadvantages of sequenced_policy

Not efficient for large tasks.

2. std::execution::parallel_policy

This policy specifies that the algorithm should execute in parallel, i.e., using multiple threads. The standard does not specify the number of threads that should be used, but it should be more than one.

Syntax of parallel_policy

stlFunction (std::execution::par, ...other_arguments...);

The execution policy object std::execution::par is passed as the argument to the STL algorithm function.

Example of parallel_policy

C++

#include <algorithm>

#include <execution>

#include <iostream>

#include <vector>

int main()

std::vector<int> v1 = 1, 2, 3, 4, 5 ;

std::vector<int> v2(5);

std::transform(std::execution::par, v1.begin(),

v1.end(), v2.begin(),

[](int x) return x * x; );

for (int i : v2)

std::cout << i << " ";

return 0;

Output

1 4 9 16 25

In this example, we create two vectors of integers v1 and v2, and then use the std::transform algorithm with the std::execution::par policy to square the elements of v1 and store the result in v2. The result is a vector v2 with elements 1, 4, 9, 16, 25 .

Advantages of parallel_policy

Faster execution for larger tasks.
Optimal usage of multi-core systems.

Disadvantages of parallel_policy

May introduce overhead.
May not always be faster than sequential execution due to this overhead.
Can introduce race conditions.

3. std::execution::parallel_unsequenced_policy

This policy specifies that the algorithm should execute in parallel and may produce non-deterministic results, i.e., the order in which the elements are processed is not guaranteed. These execution policies are implemented using a combination of hardware and software mechanisms, such as threads and SIMD instructions, to optimize the performance of the algorithms.

Syntax of parallel_unsequenced_policy

stlFunction (std::execution::par_unseq, ...other_arguments...);

This execution policy may include both parallelization and vectorization in contrast to paralled_policy which might only include parallel execution.

Example of parallel_unsequenced_policy

C++

#include <algorithm>

#include <iostream>

#include <vector>

#include <execution>

int main()

std::vector<int> v = 1, 2, 3, 4, 5 ;

std::for_each(std::execution::par_unseq, v.begin(),

v.end(),

[](int x) std::cout << x << " "; );

return 0;

Output

1 2 3 4 5

In this example, we create a vector of integers and then use the std::for_each algorithm with the std::execution::par_unseq policy to print its elements in parallel and unordered. The result can be any permutation of the input vector, depending on the order in which the elements are processed.

Advantages of parallel_unsequenced_policy

Faster execution for repetitive operations.
Can be used on hardware with vector instructions.

Disadvantages of parallel_unsequenced_policy

Not suitable for all tasks.
May not be supported on all hardware.

4. std::execution::unsequenced_policy

This policy specifies that the execution of the algorithm may be vectorized, i.e, executed on a single thread using instructions that operate on multiple data items.

Syntax of unsequenced_policy

stlFunction (std::execution::unseq, ...other_arguments...);

Example of unsequenced_policy

C++

#include <algorithm>

#include <iostream>

#include <vector>

#include <execution>

int main()

std::vector<int> v = 1, 2, 3, 4, 5 ;

std::for_each(std::execution::unseq, v.begin(),

v.end(),

[](int x) std::cout << x << " "; );

return 0;

Output

1 2 3 4 5

Advantages of unsequenced_policy

Fast Execution on a single thread
Avoids Race Conditions

Disadvantages of unsequenced_policy

Some Hardware may not support vectorization.
Non-Deterministic execution sequence.

Performance Comparison between Execution Policies

We can compare the performance difference between the execution policies using a simple C++ program as shown below:

C++

#include <chrono>

#include <execution>

#include <iostream>

#include <vector>

void execTime(auto policy_type, std::vector<int>& num,

std::string pType_name)

auto start_time

= std::chrono::high_resolution_clock::now();

long long sum = 0;

std::for_each(policy_type, num.begin(), num.end(),

[&](int n) sum += n; );

auto end_time

= std::chrono::high_resolution_clock::now();

auto taken_time = std::chrono::duration_cast<

std::chrono::milliseconds>(

end_time - start_time)

.count();

std::cout << pType_name

<< " execution time: " << taken_time

<< "msn";

int main()

int size = 9999999;

std::vector<int> num(size);

for (int i = 0; i < size; i++)

num[i] = i;

execTime(std::execution::seq, num, "Sequenced");

execTime(std::execution::unseq, num, "Unsequenced");

execTime(std::execution::par, num, "Parallel");

execTime(std::execution::par_unseq, num,

"Parallel Unsequenced");

return 0;

Output

Sequenced execution time: 917ms
Unsequenced execution time: 406ms
Parallel execution time: 897ms
Parallel Unsequenced execution time: 420ms

As we can see, of all the execution policies, the unsequenced_policy is the fastest because of vectorization. Then comes parallel_unsequenced_policy followed by the parallel_policy. At last, we sequenced the execution method as expected.

Note: The above code can only be executed using C++20 Standard or above compiler.

Conclusion

It’s worth noting that not all algorithms support all execution policies, and some algorithms may have different performance characteristics depending on the execution policy used. It’s important to choose the execution policy that best fits the requirements of the task and the hardware available and to test different policies to determine the optimal one for a given task.

FAQs on Execution Policies for STL Algorithms

1. In which version was the execution policies first added in C++ ISO Standard?

STL Algorithms execution policies were first introduced in C++17 Standard and then C++20 also added one more type later on.

2. List the STL Algorithms that support execution policies.

Here is the full list of C++ algorithms that support execution policies:

std:: adjacent_difference	std:: adjacent_find	std::all_of	std::any_of
std:: copy	std:: copy_if	std:: copy_n	std:: count
std:: count_if	std:: equal	std:: fill	std:: fill_n
std:: find	std:: find_end	std:: find_first_of	std :: find if
std:: find_if_not	std:: generate	std:: generate_n	std:: includes
std:: inner_product	std:: inplace_merge	std:: is_heap	std:: is_heap_until
std:: is_partitioned	std: is_sorted	std:: is_sorted_until	std: lexicographical_compare
std :: max element	std:: merge	std:: min_element	std :: minmax_element
std:: mismatch	std move	std:: none_of	std:: nth_element
std:: partial_sort	std partial_sort_copy	std: partition	std:: partition_copy
std: remove	std:: remove_copy	std: remove_copy_if	std:: remove_if
std:: replace	std:: replace_copy	std: replace_copy_if	std:: replace_if
std: reverse	std:: reverse_copy	std:: rotate	std:: rotate_copy
std:: search	std:: search_n	std:: set_difference	std:: set_intersection
std:: set_symmetric_difference	std:: set_union	std:: sort	std: stable_partition
std:: stable_sort	std:: swap_ranges	std:: transform	std:: uninitialized_copy
std: uninitialized_copy_n	std:: uninitialized_fill	std:: uninitialized_fill_n	std:: unique
std:: unique_copy

Keep in mind that the availability of these policies may vary depending on the implementation and the version of the C++ standard used.

#Algorithm, #Algorithms, #Amp, #Arrays, #C, #C17, #C20, #Code, #Container, #Containers, #Data, #DifferenceBetween, #Full, #Hardware, #How, #ISO, #It, #List, #Lists, #Max, #Merge, #Method, #Mind, #One, #Partition, #Performance, #Permutation, #Policy, #Read, #Responsive, #Reverse, #Search, #Sequential, #Software, #Square, #STL, #String, #Syntax, #Table, #Time, #Transform

Published on The Digital Insider at https://bit.ly/40H5wdI.

Julio Marchi © Speaks Out Network

Search This Blog