效能工程

機械同理心(mechanical sympathy)

一位懂得引擎、變速箱與輪胎實際表現的賽車手,開得更快也更少弄壞車——不是靠對抗機器,而是順著它。「機械同理心」這個詞從賽車借進軟體:在理解底層硬體真正如何運作的前提下寫程式,讓程式碼順著機器偏好的方式流動,而非逆著它的紋理。

實務上這意味著讓幾條關於現代硬體的硬事實來形塑你的程式碼。記憶體並不均勻:已在快速快取裡的資料,存取速度大約比待在主記憶體裡的快上百倍,而硬體是以整條快取線(通常 64 位元組)為單位抓取記憶體,並在你以可預測的步幅前進時先預取——所以按順序走過一個陣列,遠快於追逐散落的指標,即使兩者碰到的位元組數相同。分支會被預測,所以一個 CPU 能猜中的分支(幾乎總是被採取、或遵循簡單模式)近乎免費,而一個不可預測的分支則要付出把進行中的工作沖掉的代價。CPU 同時且亂序地做許多事,所以獨立的操作可重疊,而一條長相依鏈則被序列化。機械同理心就是安排你的資料與控制流,讓常見情況保持快取溫熱、保持分支可預測、保持有獨立工作可做——例如把你會一起掃描的紀錄連續存放,或把一個難以預測的分支換成無分支的運算。

它之所以重要,是因為在相同演算法下,記憶體友善與記憶體不友善程式碼之間的差距,動不動就是 5 到 50 倍——遠大於大多數微最佳化。不過誠實的說法是:機械同理心是「第二」根槓桿,不是第一根。一個漸進地做更少工作的更好演算法,通常勝過在舊演算法上任何程度的快取友善,而且你仍應該量測,而非假設哪個硬體效應主宰你的程式碼。並且細節(線大小、快取大小、預測有多積極)因 CPU 而異,所以原則持久而確切的數字不然——用你真實硬體上的 PMU 去確認。

把一個一億整數的陣列加總: 循序走訪 arr[0],arr[1],... -> 預取器串流快取線,快 隨機索引走訪 arr[perm[i]] -> 幾乎每一步一次快取未命中,約慢 10-30 倍 相同工作、相同結果;只有存取模式(因而區域性)不同。

演算法與輸出相同,卻差了一個數量級:循序模式讓預取器與快取與你同向工作。

機械同理心是好演算法的補充,絕非替代:在不利快取佈局上的 O(n log n) 方法,通常仍勝過快取完美的 O(n^2)。先修演算法,再去討好硬體——並且要量測,因為主宰的效應因程式碼而異。

又称
writing hardware-friendly codeworking with the grain of the machine硬體友善程式順著硬體的紋理