影響併發效能的因素 (Factors Affecting Performance)

#cpp-concurrency #concept #concurrent-design #false-sharing #cache-ping-pong

Overview Table

因素	問題	對策
處理器數量	執行緒多於硬體支援 → 超額申請 (oversubscription)	`std::thread::hardware_concurrencyasync(`、執行緒池
資料爭用	多處理器搶同一資料 → 快取乒乓 (cache ping-pong)	減少多執行緒對同一記憶體位置的競爭
mutex 爭用	鎖資料在核心間搬移、OS 層序列化	降低鎖粒度與存取頻率;注意讀寫鎖也會改寫 mutex
偽共享 (false sharing)	不同執行緒的資料同住一條 cache line	填充間隔 ≥ `hardware_destructive_interference_size`
資料鬆散	資料散落多條 cache line → 快取缺失	讓同一執行緒的資料緊湊(constructive size 內)
任務切換	可跑執行緒過多 → 切換開銷 + 快取失效	限制工作執行緒數量

處理器數量與超額申請 (oversubscription)

能真正併發的執行緒數由硬體決定(16 個硬體執行緒的機器,無論是 1×16 核、4×雙核…都一樣只能同時跑 16 條)。可跑的執行緒(未阻塞)多於硬體支援數時,處理器把時間浪費在執行緒切換上,稱為超額申請 (oversubscription)。

std::thread::hardware_concurrency() 回報硬體可支援的併發執行緒數,可用來決定開幾條執行緒。
std::async() 由標準庫統籌所有呼叫,自動避免超額申請;謹慎設計的執行緒池亦可。
併發程式在不同平台(單核多芯/多核/多處理器)行為與效能特性可能完全不同,必須在近似目標的平台上測試。

hardware_concurrency() 的盲點

它不會考慮其他應用程式已占用的執行緒;若程式多處各自依它開執行緒、或系統同時跑多個 CPU 密集程式,仍會超額申請。它也可能回傳 0(資訊不可得),使用時要有預設值。

資料爭用與快取乒乓 (cache ping-pong)

多執行緒唯讀同一資料沒問題(各自快取一份);一旦有執行緒修改資料,變更就得傳播到其他核心的快取,非常耗時。

std::atomic<unsigned long> counter(0);
void processing_loop() {
  while (counter.fetch_add(1, std::memory_order_relaxed) < 100000000)
    do_something();
}

fetch_add 是「讀-改-寫」操作,每次都要取得最新值 → counter 的 cache line 在處理器之間反覆搬移。
處理器互相等待對方完成更新 → 高爭用 (high contention);很少互等則為低爭用 (low contention)。
資料在各處理器快取間來回傳遞,即快取乒乓 (cache ping-pong);等待快取轉移時處理器什麼都做不了。

 CPU A 快取 ──(修改 counter,取得所有權)──▶ CPU B 快取失效
 CPU B 快取 ◀──(修改 counter,取得所有權)── CPU A 快取失效
        └────── cache line 來回「乒乓」,兩邊輪流停等 ──────┘

mutex 爭用

迴圈中鎖 mutex 與上面的原子操作情況類似:mutex 本身的資料也要在核心間搬移;搬移時間直接成為下一個執行緒等鎖的時間。

差異:mutex 爭用通常由作業系統層級序列化執行緒——等鎖的執行緒會被排程走,讓別的執行緒跑;原子操作的爭用則讓處理器原地等快取。
讀寫鎖(單寫者多讀者,3.3.2)的反直覺陷阱:即使是讀者,取得共享鎖也要修改 mutex 內部計數 → cache line 照樣乒乓,可能抵銷讀寫鎖帶來的收益。

處理器快取以 cache line(通常 32 或 64 位元組)為單位搬移,不是單一位址。多個小資料項(如相鄰的 int)會落在同一條 cache line:

執行緒 A 更新元素 0、執行緒 B 更新元素 1——資料毫不相關,但同住一條 line,所有權仍在兩顆處理器間反覆轉移 → 快取乒乓照樣發生。這就是偽共享:共享的是 cache line,不是資料。
解法:調整資料佈局——同一執行緒用的資料放近(同一 line),不同執行緒的資料隔開(不同 line)。

C++17 工具(標頭 <new>)

std::hardware_destructive_interference_size:可能發生偽共享的最大連續位元組數——不同執行緒的資料間隔 ≥ 此值即可避免偽共享。
std::hardware_constructive_interference_size:保證落在同一條 cache line 的最大連續位元組數(需對齊)——單執行緒熱資料塞進此大小內可提升快取命中。

資料緊湊度 (data proximity)

偽共享是「不同執行緒的資料太近」;反過來,單執行緒的資料太散也傷效能:

資料散落多條 cache line → 要載入更多 line、記憶體存取延遲上升。
每條 line 混入無關資料 → 浪費寶貴快取空間、快取缺失 (cache miss) 增加。
執行緒數多於核心時問題放大:任務切換後若各執行緒資料橫跨多條 line,重建快取的成本更高。

超額申請與頻繁任務切換

執行緒多於處理器本身很正常(執行緒常在等 I/O、mutex、條件變數,等待中的執行緒不占 CPU)。真正的問題是準備就緒的執行緒遠多於處理器:

OS 忙於輪流切換任務以保證公平 → 切換開銷 + 快取壓力,效果等同前述快取問題。
成因:無限制地生執行緒(見遞迴劃分)、或按任務類型劃分導致執行緒數 > 處理器數且全為 CPU 密集。
對策:限制工作執行緒數量(如 8.1.2 的作法);若超額申請源自任務劃分本身,換劃分方式收益有限。

Exam/Test Patterns

情境/關鍵字	答案
「就緒執行緒 > 硬體執行緒數,效能反而下降」	超額申請:切換開銷;用 `hardware_concurrency()` 限量或改用 `std::async()`/執行緒池
「多執行緒反覆改同一個 `atomic` 計數器很慢」	快取乒乓:cache line 所有權在處理器間搬移;減少對同一記憶體位置的寫入競爭
「兩執行緒改的是不同變數還是很慢」	偽共享:變數同住一條 cache line;以 `hardware_destructive_interference_size` 填充隔開
「讀寫鎖沒有帶來預期效能」	讀者也要修改 mutex 內部狀態 → mutex 所在 line 乒乓
「單執行緒資料散落各處、cache miss 高」	資料緊湊度:熱資料塞進 `hardware_constructive_interference_size` 內
「destructive vs constructive interference size」	destructive = 隔開避免偽共享的最小間距;constructive = 靠攏提升命中的同 line 上限
「mutex 爭用與 atomic 爭用差在哪」	mutex 由 OS 排程序列化(執行緒讓出 CPU);atomic 讓處理器原地等快取轉移