平行演算法的使用 (Using Parallel Algorithms)

#cpp-concurrency #concept #parallel-algorithms #execution-policy

Overview Table

概念	重點
可平行化的演算法	`<algorithm>` 與 `<numeric>` 中大多數演算法皆有執行策略重載(`for_each`、`sort`、`transform`、`reduce`、`transform_reduce`…)
`std::accumulate` vs `std::reduce`	`accumulate` 無平行版(嚴格循序);`reduce` 是其廣義版,運算需結合律+交換律,否則結果不確定
簽名差異	每個普通重載對應一個多了 `ExecutionPolicy&&` 首參數的重載
迭代器要求提升	普通版收輸入/輸出迭代器之處,策略版一律要求前向迭代器 (forward iterator)
策略選擇	預設用 `par`;只有元素存取完全不需同步時才可升級 `par_unseq`
計數訪問量範例	`transform_reduce(par, ...)`:transform = 逐行解析(獨立),reduce = 合併結果(需 4 個 `operator()` 重載)

10.3 帶執行策略的演算法簽名

標準庫中被執行策略重載的演算法都在 <algorithm> 與 <numeric> 標頭檔中,包括:all_of、any_of、none_of、for_each、find 系列、count 系列、copy、transform、fill、generate、remove、unique、reverse、rotate、partition 系列、sort 系列、merge、集合運算、min/max_element、reduce、transform_reduce、inclusive_scan/exclusive_scan 系列、adjacent_difference 等。

std::accumulate 不在清單中:它嚴格定義為循序累加;其廣義版 std::reduce 才可平行化。
標準警告:若 reduce 的約簡運算不同時滿足結合律與交換律,因運算順序未指定,結果可能不確定。

每個「普通」重載都對應一個首參數為執行策略的重載,其餘參數順序不變。以 std::sort 為例:

template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

template<class ExecutionPolicy, class RandomAccessIterator>
void sort(ExecutionPolicy&& exec,
          RandomAccessIterator first, RandomAccessIterator last);

迭代器類別要求提升

策略重載與普通重載有一個影響部分演算法的重要差異:普通版允許輸入迭代器或輸出迭代器之處,策略版要求前向迭代器。以 std::copy 為例:

// 普通版:InputIterator / OutputIterator
template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
                    OutputIterator result);
// 策略版:兩端都要求 ForwardIterator
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 copy(ExecutionPolicy&& policy,
                      ForwardIterator1 first, ForwardIterator1 last,
                      ForwardIterator2 result);

C++ 標準庫的五類迭代器:

迭代器類別	方向/路徑	複製語義	典型用途
輸入迭代器	單向、單路徑	遞增後其他副本失效	讀取主控台/網路輸入、生成序列
輸出迭代器	單向、單路徑	寫入後其他副本失效	寫檔、向容器追加
前向迭代器	單向、多路徑	可保存先前元素的副本並繼續使用;回傳元素的實際參照	單向鏈結串列走訪
雙向迭代器	雙向、多路徑	同前向,另可後退	`std::list`、`std::map`
隨機存取迭代器	雙向 + 任意跨距、`[]` 索引	同雙向	`std::vector`、陣列

為什麼平行化要求前向迭代器

前向迭代器可自由複製且等價使用,遞增某個副本不會使其他副本失效——每個執行緒可以拿自己的迭代器副本獨立走訪各自的分段。模板參數名稱(InputIterator → ForwardIterator)在標準中代表語義約束:若策略重載允許輸入迭代器,對來源序列唯一迭代器的存取將強制序列化,扼殺平行的可能性。

10.3.1 平行演算法範例與策略選擇

最簡單的場景是平行迴圈:對容器每個元素做獨立處理(「令人尷尬的平行」,可獲得最大平行性)。OpenMP 寫法 vs 標準庫寫法:

#pragma omp parallel for
for (unsigned i = 0; i < v.size(); ++i) { do_stuff(v[i]); }

std::for_eachpar, v.begin(), v.end(), do_stuff;

標準庫會在內部建立執行緒、劃分資料,對每個元素 x 呼叫 do_stuff(x);元素如何在執行緒間劃分是實作細節。

執行策略的選擇

std::execution::par 是最常用的策略:只要程式碼適合平行化就應能與 par 一起工作。只有元素間有特定順序需求、或對共享資料有未同步存取時才會出問題。
par_unseq 用「對程式碼更嚴格的要求」換取庫更大的最佳化空間(重排、交錯任務、向量化)。最關鍵的要求:存取元素或執行操作時不得使用任何同步——不能用互斥鎖 (mutex)、原子變數或其他任何同步機制;要靠演算法本身的劃分保證不會多執行緒碰同一元素,並在演算法呼叫之外做外部同步。
沒有任何標準策略保證達到某種平行程度——par_unseq 也可能毫無加速。

代碼 10.1:元素內部有互斥鎖 → 可用 par,不可用 par_unseq

class X {
  mutable std::mutex m;
  int data;
public:
  int get_value() const { std::lock_guard guard(m); return data; }
  void increment()      { std::lock_guard guard(m); ++data; }
};
void increment_allvector<X>& v {
  std::for_eachpar, v.begin(), v.end(,
                [](X& x){ x.increment(); });
}

代碼 10.2:同步上移為整個容器一把鎖 → 元素存取無同步,可用 par_unseq

class Y { int data = 0; public: void increment(){ ++data; } };
class ProtectedY {           // 自身即 Lockable:lock()/unlock()
  std::mutex m; std::vector<Y> v;
public:
  void lock(){ m.lock(); } void unlock(){ m.unlock(); }
  std::vector<Y>& get_vec(){ return v; }
};
void increment_all(ProtectedY& data) {
  std::lock_guard guard(data);          // 外部先鎖整個容器
  auto& v = data.get_vec();
  std::for_eachpar_unseq, v.begin(), v.end(,
                [](Y& y){ y.increment(); });
}

粒度交換

代碼 10.1 在 par_unseq 下使用內部互斥鎖同步會導致未定義行為。代碼 10.2 把鎖的粒度從「每元素」改為「整個容器」,元素存取因此無同步、par_unseq 安全;代價是演算法執行期間,其他執行緒的併發存取必須等整個操作完成。

10.3.2 計數網站訪問量(`transform_reduce` 逐步解說)

情境:繁忙網站的日誌有數百萬條,想統計每頁被訪問幾次。分析分兩部分:(1) 逐行處理提取資訊——每行完全獨立;(2) 把結果聚合起來——只要總計正確即可逐個彙總。這正是 transform_reduce 的理想場景。

extern log_info parse_log_linestring const& line;        // ①
using visit_map_type = std::unordered_map<std::string, unsigned long long>;

visit_map_type count_visits_per_pagestring> const& log_lines {
  struct combine_visits { /* 4 個 operator() 重載,見下表 */ };
  return std::transform_reduce(                                 // ②
    std::execution::par, log_lines.begin(), log_lines.end(),
    visit_map_type(),          // 初始值:空 map
    combine_visits(),          // 約簡(binary op)
    parse_log_line);           // 轉換(unary op)
}

逐步解說:

步驟	元件	作用
①	`parse_log_line`	轉換:`std::string` 日誌行 → `log_info`(頁面、時間、瀏覽器…);各行獨立,無共享狀態
②	`transform_reduce(par, …)`	傳入 `par`:標準庫用硬體平行執行「先轉換、再約簡」
③	`operator()(map, map)`	合併兩個部分結果:把較小的 map 換到 rhsswap再逐項累加——把小 map 併入大 map 較有效率
④⑤	`operator()(log, map)` / `operator()(map, log)`	一筆記錄併入 map(兩種參數順序都要提供):`++map[log.page]`
⑥	`operator()(log, log)`	兩筆記錄直接生成一個新 map,各 `++` 一次

複雜度來源在約簡操作:因運算順序未指定,約簡運算子可能拿到「map+map、log+map、map+log、log+log」四種組合,所以 combine_visits 需要 4 個函式呼叫運算子重載——這也是不用 Lambda 而用函式物件的原因(Lambda 無法重載)。
效益:把「實作平行性的苦工」(第8、9章手工劃分、執行緒管理)委託給標準庫實作者,開發者專注於想要的結果。

reduce 類演算法的正確性前提

約簡運算必須具結合律與交換律(這裡的「合併訪問計數」滿足:加法可任意分組、交換)。若不滿足,std::reduce/transform_reduce 因運算順序未指定,結果不確定。

Exam/Test Patterns

情境/關鍵字	答案
想平行化 `std::accumulate`	用 `std::reduce`;前提:運算滿足結合律+交換律,否則結果不確定
普通重載收 `InputIterator`/`OutputIterator`,策略版?	一律提升為 `ForwardIterator`
為何前向迭代器對平行化重要	可自由複製、遞增不使其他副本失效,各執行緒能獨立走訪自己的分段
元素方法內含 `std::mutex` 保護	只能 `par`;`par_unseq` → UB
元素無同步、外層整個容器一把鎖	可用 `par_unseq`;代價:外部併發存取需等整個演算法完成
「逐行解析 + 彙總計數」日誌分析	`std::transform_reducepar, first, last, init, reduce_op, transform_op`
`transform_reduce` 的約簡函式物件為何要 4 個重載	順序未指定,可能組合 map+map / log+map / map+log / log+log;Lambda 無法重載故用函式物件
合併兩個 map 前先 `std::swap` 小的	把小 map 併入大 map,減少插入次數(效率)
`#pragma omp parallel for` 的標準庫等價	`std::for_eachpar, v.begin(), v.end(), f`
元素在執行緒間如何劃分	實作細節,由標準庫決定