C++17 并行化STL算法

概念

為了從現代的多核體系中受益，C++17標準庫引入了并行 STL算法，允許使用多個線程并行處理元素。

C++17為許多算法擴展了一個新的參數來指明是否要并行運行算法。并且新增了一些專為并行編程補充的新算法。

環境準備

并行算法在 linux上使用 gcc 或者 clang進行編譯，需要

1. 安裝 tbb庫—— 線程構建模塊 (TBB) Thread Building Blocks
2. 鏈接時指定-ltbb選項

否則：

tbb庫	鏈接	結果
安裝	指定-ltbb選項	可正常使用并行算法
安裝	未指定	編譯錯誤
未安裝	指定	編譯錯誤
未安裝	未指定	正常編譯，但并行算法會串行化，變得和串行算法一樣

# 編譯選項
g++ ‐std=c++17 ‐ltbb main.cpp ‐o a.out

工具類

有時需要計時器來測量算法的速度。因此，引入一個簡單的輔助類。

初始化一個計時器，提供 printDiff()來打印出消耗的毫秒數 并 重新初始化計時器

#include <iostream>
#include <string>
#include <chrono>
/********************************************
* timer to print elapsed time
********************************************/
class Timer {
private:std::chrono::steady_clock::time_point last;
public:Timer() : last{std::chrono::steady_clock::now()} {}void printDiff(const std::string& msg = "Timer diff: ") {auto now{std::chrono::steady_clock::now()};std::chrono::duration<double, std::milli> diff{now ‐ last};std::cout << msg << diff.count() << "ms\n";last = std::chrono::steady_clock::now();}
};

并行算法 - 使用

怎么讓現有算法并行運行和使用新的并行算法

• 包含頭文件 <execution>

#include <execution> 

• C++17之后，一般來說可以向并行 STL算法傳遞不同的 執行策略 (execution policies) 作為第一個參數。

  • cpprefrence上看看STL算法支不支持，一般是：添加執行策略到第一個參數即可。例如，std::execution::par）

  • 使用參數 傳遞/修改 執行策略 的好處：可在運行時更改策略時（順序執行/并行執行），不需要再修改調用方式。

所有的并行算法要求迭代器至少是前向迭代器。

#include <execution> // for 執行策略
#include <algorithm>std::vector<std::string> coll {"a", "b", "c"};sort(coll.begin(), coll.end());
sort(std::execution::seq, coll.begin(), coll.end());
sort(std::execution::par, coll.begin(), coll.end());
sort(std::execution::par_unseq, coll.begin(), coll.end());// 并行計算平方根
for_each(std::execution::par,coll.begin(), coll.end(),[] (auto& val) {val.sqrt = std::sqrt(val.value);});

并行算法 - 執行策略

總覽

以下執行策略，分別是定義在 namespace std中的新類（sequenced_policy、parallel_policy、parallel_unsequenced_policy）的 constexpr對象。

執行策略	含義
std::execution::seq	順序執行
std::execution::par	并行化順序執行
std::execution::par_unseq	并行化亂序（矢量化）執行

標準庫提供了新的類型特征 std::is_execution_policy<>，在泛型編程中檢查模板參數是否是執行策略。

并行化亂序執行需要編譯器/硬件的特殊支持，從而檢測如何矢量化。

非并行化/并行化

1. 并行化——多個線程執行
2. 非并行化——單一線程

順序、亂序

1. 亂序：允許矢量化執行，不保證順序地對元素執行操作。

   即存在可能：

   • 某個線程在執行完某一個元素的處理之前可能會切換到其他的元素。

   • 某個線程先執行多個元素的第一步處理，再回過頭來對這些元素執行下一步處理。

2. 順序：不允許矢量化執行，順序地對元素執行操作

   當某個線程對新的元素進行操作之前，它會先處理完它之前處理過的其他元素。

選擇標準

benchmark測試結果，主要依賴于硬件、使用的 C++編譯器、使用的 C++庫（并行算法實際運行的方式是實現特定的）

沒有通用的方法來判斷什么場景什么時間值得使用并行算法。不能說多線程就一定比順序執行好：啟動和控制多線程也會消耗時間。

從理論上講，如下判斷依據可以作為參考：

• 簡單算法（每個元素計算耗時短），元素數量少。并行執行永遠會更慢建議順序執行 std::execution::seq 或 默認版本。

• 復雜算法（每個元素計算耗時長），元素數量多。適合使用并行算法

  • 處理過程需要獨立于其他元素的處理 —— 并行化順序執行 std::execution::par
  • 處理過程不需要獨立于其他元素的處理 —— 并行化亂序執行 std::execution::par_unseq

詳細介紹

順序執行 seq

std::execution::seq 指定順序執行

• 策略本身：

  • 單一線程執行
  • 單個線程對所有元素逐個執行操作。不允許矢量化執行，順序地對元素執行操作——當某個線程對新的元素進行操作之前，它會先處理完它之前處理過的其他元素。

• 與非并行化版本進行對比

  • 實際上，該策略非常類似不接受執行策略參數的非并行化版本
  • 但多一些約束條件：例如 for_each()不能返回值，所有的迭代器必須至少是前向迭代器

• 提供該策略的目的：

  • 可只修改一個參數來要求順序執行，而不是換用一個簽名不同的函數。

并行化順序執行 par

std::execution::par 指定并行化順序執行

• 策略本身：

  • 多個線程執行
  • 順序執行：允許矢量化

• 提供該策略的目的：

  • 比非并行化順序執行，可能要快一些

  • 避免在以下情況中出現死鎖或其它bug（與 par_unseq不同）

    執行了某個元素的第一步處理后必須在執行另一個元素的第一步處理之前執行這個元素接下來的處理步驟。

并行化亂序執行 par_unseq

std::execution::par_unseq 指定并行化亂序執行

• 策略本身：
  • 多個線程執行
  • 亂序執行：允許矢量化
• 提供該策略的目的：
  • 比非矢量化 順序執行，可能要快一些

并行化亂序執行需要編譯器/硬件的特殊支持來檢測哪些操作如何矢量化。

并行算法 - 異常處理

當指定了執行策略后：

• 處理元素的函數，因未捕獲的異常而退出時，會調用 std::terminate()

• 注意即使選擇了順序執行策略也會這樣。

注意：存在并行算法本身拋出異常的可能性！

例如，申請并行執行所需的臨時內存資源時失敗了，會拋出 std::bad_alloc 異常。從而直接 std::terminate()

所以，使用非并行化版本的算法有時是更好的選擇。

可以不使用并行算法

使用非并行算法可以提供以下好處：

• 可以使用輸入和輸出迭代器。
• 算法不會在遇到異常時 std::terminate()
• 算法可以避免因為意外使用元素導致的副作用。
• 算法可以提供額外的功能，例如 for_each()會返回傳入的可調用對象，我們可能會需要該對象最終的狀態

并行算法 - 限制

有限制的并行 STL算法

限制：返回類型 void、前向迭代器

for_each()

限制：前向迭代器

for_each_n() all_of(), and_of(), none_of() 
find(), find_if(), find_if_not() 
find_first_of() 
count(), count_if() 
mismatch() 
equal() 
is_partitioned() 
partial_sort_copy() 
includes() 
lexicographical_compare() 
fill_n() 
generate_n() 
reverse_copy() 
rotate_copy() 
copy(), copy_n(), copy_if() 
move() 
transform() 
replace_copy(), replace_copy_if() 
remove_copy(), remove_copy_if() 
unique_copy() 
partition_copy() 
merge() 
set_union(), set_intersection() 
set_differrnce(), set_symmetric_difference() 
inclusive_scan(), exclusive_scan() 
transform_inclusive_scan(), transform_exclusive_scan()

并行算法有哪些

原有算法

C++17之前，標準中不需要修改就可以并行運行的算法

find_end(), adjacent_find()
search(), search_n()（和“搜索器”一起使用時除外）
swap_ranges()
replace(), replace_if()
fill()
generate()
remove(), remove_if(), unique()
reverse(), rotate()
partition(), stable_partition()
sort(), stable_sort(), partial_sort()
is_sorted(), is_sorted_until()
nth_element()
inplace_merge()
is_heap(), is_heap_until()
min_element(), max_element(), min_max_element()

無并行版本的算法

• 為了并行地運行 accumulate()，使用reduce() 或者transform_reduce()。
• 為了并行地運行 partial_sum()，使用…scan()算法。
• 為了并行地運行 inner_product()，使用transform_reduce()。

accumulate()
partial_sum()
inner_product()
search()（和“搜索器”一起使用時）
copy_backward(), move_backward()
sample(), shuffle()
partition_point()
lower_bound(), upper_bound(), equal_range()
binary_search()
is_permutation()
next_permutation(), prev_permutation()
push_heap(), pop_heap(), make_heap(), sort_heap()

17引入新算法