平行演算法練習題 (Practice - Parallel Algorithms)

平行版是既有演算法的重載:在參數列表最前面新增一個執行策略參數,其餘參數相同,例如 std::sortpar, v.begin(), v.end()。
par 只表示允許平行:實作若需要仍可以串行方式執行——沒有任何標準策略保證達到特定平行程度。

定義於 <execution>:

• std::execution::sequenced_policy → 物件 std::execution::seq
• std::execution::parallel_policy → 物件 std::execution::par
• std::execution::parallel_unsequenced_policy → 物件 std::execution::par_unseq

策略物件只能複製,不能自行建構(有特殊初始化要求);實作可以額外提供非標準策略,但開發者不能自訂。

只要帶有標準執行策略(包括 seq),異常逃逸出演算法就會呼叫 std::terminate 終止程式;帶標準策略時演算法唯一可能拋出的異常是 std::bad_alloc(庫內部資源不足)。
不帶策略的版本則會把異常正常傳播給呼叫者。

不得使用任何形式的同步:不能用互斥鎖 (mutex)、原子變數或其他同步機制,也不能呼叫任何內部需要同步的函式;只能操作元素本身,不得修改執行緒間或元素間共享的狀態。
原因:par_unseq 允許操作在同一執行緒內交錯、並在執行緒間遷移(可在 A 執行緒啟動、B 執行、C 完成)——在交錯執行下取鎖可能造成死結等問題,故任何同步都是未定義行為。外部同步須在演算法呼叫之外完成。

策略重載一律要求前向迭代器 (forward iterator)(如 ForwardIterator1/2)。
前向迭代器是多路徑迭代器:可自由複製、等價使用,且遞增不會使其他副本失效——每個執行緒能持有自己的迭代器副本獨立走訪分段。若允許輸入迭代器(副本會失效、單路徑),對來源的存取將被強制序列化,失去平行可能。

std::accumulate 標準定義為嚴格循序的累加,故不在平行化清單中;平行累加應使用其廣義版 std::reduce(或 transform_reduce)。
前提:約簡運算必須同時滿足結合律與交換律——因為運算順序未指定,不滿足時結果不確定。

多個執行緒同時執行 Lambda 會對 count 產生資料競爭 (data race) → 未定義行為。
即使庫實際沒用多執行緒仍是 UB:是否有 UB 是呼叫的靜態屬性,不依賴庫實作細節。
修正:把 count 改成 std::atomic<int> 或用互斥鎖(代價:對計數的存取序列化,可能失去平行效益);若本來就要「依序填 1..N」,應改用無策略的 std::for_each(seq 也不保證存取順序)或 std::iota。

只能選 par:par 允許在元素操作中使用同步(mutex/atomic);par_unseq 禁止任何同步,元素內部取鎖會導致未定義行為。
重構成 par_unseq(代碼 10.2 模式):移除元素內部互斥鎖,把鎖上移為整個容器一把(如 ProtectedY 提供 lock()/unlock()),在呼叫演算法之前以 std::lock_guard 鎖住整個容器,使元素存取本身完全無同步。

10.1(細粒度 + par):演算法執行期間其他執行緒仍可併發存取「未被處理中」的元素,併發性佳;但每次元素操作都有取鎖開銷,且同步的存在使庫無法交錯/向量化(只能用 par)。
10.2(粗粒度 + par_unseq):元素存取零同步,庫可最大化重排、交錯與向量化,單次演算法執行更快;但演算法執行期間外部併發存取必須等整個操作完成,鎖粒度變粗。
取捨:若演算法呼叫期間幾乎沒有外部併發存取(批次處理),10.2 較好;若容器需被多方持續併發使用,10.1 的細粒度較合適。

因為 par 下約簡順序未指定,約簡運算子可能收到四種參數組合:map+map、log_info+map、map+log_info、log_info+log_info,所以需要 4 個重載;Lambda 無法重載,故用函式物件(struct)實作。
swap 的目的:確保永遠把較小的 map 併入較大的 map——插入/累加次數取決於較小者的元素數,能減少雜湊表操作次數、提升合併效率。
整體設計成立的前提:逐行解析彼此獨立(transform 無共享狀態),且「合併計數」滿足結合律+交換律,聚合順序不影響最終結果。