為多執行緒效能設計資料結構 (Designing Data Structures for Performance)

#cpp-concurrency #concept #concurrent-design #false-sharing #data-partitioning

Overview Table

主題	關鍵點
三大設計考量	爭用 (contention)、偽共享 (false sharing)、資料鄰近性 (data proximity)
矩陣乘法劃分	按列 / 按行 / 按塊;塊狀劃分讀取量最少、快取最友善
通用原則	同執行緒資料靠攏、減少每執行緒所需資料量、不同執行緒分開存放
偽共享測試法	在資料間填充大塊 padding,效能改善 ⇒ 偽共享確實存在

設計目標

第 6、7 章談的是「如何讓資料結構安全地被併發存取」;本節談的是「如何讓資料佈局跑得快」。改變劃分方式與資料佈局,常常不需修改演算法就能提升效能。三個關鍵因素:爭用、偽共享、資料鄰近性。

矩陣乘法的劃分範例

兩個上千行列的大矩陣相乘(結果矩陣元素 = 第一矩陣某行 × 第二矩陣某列的內積)。非稀疏矩陣以行連續 (row-major) 的大陣列儲存。假設行列數大於處理器數,劃分方式有三種:

按列劃分                按行劃分                按塊劃分
┌──┬──┬──┐          ┌────────────┐         ┌──────┬──────┐
│T1│T2│T3│          │     T1     │         │  T1  │  T2  │
│  │  │  │          ├────────────┤         ├──────┼──────┤
│  │  │  │          │     T2     │         │  T3  │  T4  │
│  │  │  │          ├────────────┤         │      │      │
└──┴──┴──┘          │     T3     │         └──────┴──────┘
每執行緒寫 N 列       每執行緒寫連續整行       每執行緒寫一個子矩陣

按列劃分:每執行緒需讀第一矩陣全部元素 + 第二矩陣對應列;寫入時各執行緒寫同一行的相鄰元素——若每執行緒的 N 個列元素恰好占滿整條 cache line,偽共享消失;否則行內交錯寫入易偽共享。
按行劃分:每執行緒需讀第二矩陣全部元素 + 第一矩陣對應行;寫入的是連續記憶體塊(row-major),偽共享只可能發生在相鄰塊的交界處——比按列劃分改善。
按塊劃分(先分列再分行):寫入仍有交界問題,但讀取量大幅減少——只需讀目標塊對應的行與列,不必讀整個來源矩陣。

讀取量試算(1,000×1,000 矩陣、100 個處理器)

每執行緒處理 10 整行(10,000 個元素):需讀第二矩陣全部 1,000,000 + 第一矩陣 10 行 10,000 ≈ 1,010,000 個元素。
每執行緒處理 100×100 的塊(同樣 10,000 個元素):只需第一矩陣 100 行(100,000)+ 第二矩陣 100 列(100,000)= 200,000 個元素,約為前者 1/5 → 快取缺失大幅減少。

塊的大小可在執行期依來源矩陣大小與處理器數調整;效能關鍵時務必在目標架構上實測。

通用原則,而非矩陣專屬

同樣的分析適用於任何「大塊資料在執行緒間劃分」的場景:仔細觀察資料存取模式,改變劃分方式常可在不動演算法的情況下提升效能。(真要做矩陣乘法,直接用成熟的專家庫更好。)

其他資料結構的存取模式

優化原則與陣列相同:

讓同一執行緒存取的資料在記憶體中緊密相鄰(資料鄰近性)。
減少每個執行緒所需的資料總量。
讓不同執行緒的資料相距夠遠,避免偽共享。

套用到非陣列結構比較麻煩:

二元樹:劃分是否有效取決於樹的平衡度與節點數;節點動態配置、散落各處 → 若節點只存指向實際值的指標,存取值就得再到主記憶體載入。若修改資料的執行緒能把「節點資料」與「樹結構」分開放,可避免兩者間的偽共享。
mutex 與被保護資料同放:優點——鎖 mutex 時資料多半已進快取,取得鎖的執行緒賺到。缺點——mutex 的鎖定是「讀-改-寫」原子操作,其他執行緒嘗試鎖 mutex 時會搶走該 cache line 的所有權;若 mutex 與資料同住一條 line,持鎖執行緒存取資料反而遭殃。

測試偽共享是否存在

在成員之間塞入超過一條 cache line 的填充,若效能因此提升,即證明偽共享存在:

struct protected_data {
  std::mutex m;
  // 不支援 std::hardware_destructive_interference_size 時,
  // 用遠大於一條 cache line 的 65536 位元組
  char padding[65536];
  my_data data_to_protect;   // 測 mutex 爭用與資料的偽共享
};

struct my_data {
  data_item1 d1;
  data_item2 d2;
  char padding[65536];
};
my_data some_array[256];     // 測陣列元素間的偽共享

診斷手法

padding 只是診斷工具:先加大 padding 驗證偽共享 → 確認後把 padding 縮到 std::hardware_destructive_interference_size,或重新安排資料佈局。

Exam/Test Patterns

情境/關鍵字	答案
「為效能設計資料結構要考慮哪三件事」	爭用、偽共享、資料鄰近性
「row-major 矩陣乘法,劃分方式怎麼選」	塊狀劃分:讀取量最少(200,000 vs 1,010,000)、快取缺失最少
「按行劃分為何優於按列劃分」	寫入為連續記憶體塊,偽共享僅在塊交界;按列則行內交錯寫入
「怎麼驗證效能瓶頸是偽共享」	資料間塞大塊 padding(如 65536 bytes),變快 ⇒ 偽共享存在
「mutex 該不該和資料放同一條 cache line」	有利有弊:持鎖者快取命中 vs 他人搶鎖時搶走整條 line;高爭用時應隔開
「樹狀結構的平行劃分」	取決於平衡度;節點散落 → 指標追蹤造成主記憶體載入;分離節點資料與樹結構