舊的成本模型，以及它為何失效
你至今爬過的每一級，都用浮點運算次數來衡量演算法——它執行的浮點加法與乘法的數目。高斯消去法是 O(n^3)，快速傅立葉轉換是 O(N log N)，蒙地卡羅誤差按 O(1/sqrt(N)) 下降。那種直覺——數算術，越少浮點運算就越快——一路忠實地服務我們，至今仍是面對任何方法該問的第一個問題。這篇指南談的是那個直覺不再是全部真相的時刻，原因出在真實硬體的構造方式。
這裡有個令人不安的事實，直白說出來。在現代處理器上，一次浮點乘法大約花一奈秒的工作量——就叫它一個時間單位。要去取一個「不」在附近的數字，一路從主記憶體（RAM）搬過來，大約要一百個這樣的單位。算術單元嚼數字的速度，遠遠快過記憶體系統送上數字的速度。於是一個對每個載入的數字只做幾次浮點運算的計算，大半輩子都在「等」——乘法器閒坐著，資料慢吞吞地爬進來。標題就是全部的教訓：浮點運算很便宜，記憶體卻很慢。
層級結構：從又快又小到又慢又大的金字塔
硬體設計者沒辦法讓所有記憶體既快又大——快的記憶體既昂貴，又在物理上必須緊貼算術單元。於是他們蓋了一座記憶體層級：一疊記憶體，每一層都比上一層更大也更慢。最頂端坐著暫存器（幾十個數字，瞬間可得）。在它們底下是小小的 L1 快取，接著是較大的 L2，再來是更大的 L3 快取——每一層都比前一層慢上幾倍、大上數倍。最底層是主記憶體：以 GB 計，但離得有百來個單位遠。（磁碟與網路坐得更下面，慢得更多。）整座金字塔的存在，是為了偽造一件不可能的事：一份「感覺」既快又巨大的記憶體。
level size ~cost to reach one number ----------- -------------- -------------------------- registers ~dozens 1 (instant, in the ALU) L1 cache ~32 KB ~4 L2 cache ~256 KB-1 MB ~12 L3 cache ~8-64 MB ~40 main memory ~GBs ~100-300 disk / net ~TBs+ ~100,000+ (don't go here in a loop) numbers are rough orders of magnitude, not exact, and vary by machine
這套機械是自動運作的。當你要一個數字，硬體先檢查最快的那一層；如果它在那裡（一次「快取命中」），你幾乎不付代價；如果不在（一次快取失誤），硬體就得沿金字塔往下走去把它取來，「那」就是上百單位的罰款。關鍵在於，當它終於去主記憶體時，並不是只搬回你那一個數字——它把一整段連續的區塊（叫做一條快取線，通常是 64 位元組，約八個雙精度數）一起拉上來，賭你接下來會想要這些鄰居。這個賭注划不划算，全看你怎麼寫你的迴圈。記住，一次快取失誤的代價，可能超過對一百個數字做的算術——所以主宰帳單的是失誤，不是浮點運算。
算術強度：每位元組的浮點運算，決定一切的那個數
如果記憶體流量是我們付的錢，我們就需要一種方式來衡量一個計算對那份流量有多「節省」。那個衡量就是算術強度：一個核心執行的浮點運算次數，除以它在記憶體之間搬動的位元組數。高強度意味著你對每個取來的數字做了大量有用的算術——資料對得起這趟旅程。低強度意味著你碰一下每個數字、幾乎什麼都不做就把它丟掉——你付了記憶體的全額運費，卻幾乎完全沒用上算術單元。
用兩個作用在長度 n 向量上的核心把它具象化。第一個，向量加總 z_i = x_i + y_i：你載入兩個數字、做一次加法、存回一個數字——三次記憶體運算換一次浮點運算。它的強度約為每 24 位元組 1 次浮點運算，低得無可救藥；這個核心幾乎所有時間都耗在等記憶體。現在對照矩陣乘矩陣 C = A B，對 n 乘 n 的矩陣：它搬動約 n^2 個數字，卻執行約 n^3 次乘加，所以它的強度按 n 增長——每個數字一旦取來，就被重複使用 n 次。正是這唯一的差別，使得這兩個核心，一個能跑得接近晶片的尖峰速度，另一個永遠不能，無論程式設計師多聰明。
屋頂線：你是記憶體受限還是計算受限？
算術強度給了我們一張能把任何核心分類的圖像：屋頂線模型。想像一張圖，橫軸是算術強度（每位元組的浮點運算），縱軸是可達速度（每秒的浮點運算）。機器加上兩道天花板。一道是位於晶片尖峰算術速率的水平直線——你永遠算不過它。另一道是從左邊升起的斜線，由記憶體頻寬決定：在低強度時，你的速度被位元組能多快抵達所封頂，而那個上限隨強度成比例升高。兩者合起來看起來像一片屋頂：左邊一道上升的斜坡，彎進右邊一道平坦的天花板。
現在按你的核心的強度把它擺到圖上。如果它落在斜的那段——彎折點的左邊——它就是記憶體受限：它的速度由頻寬支配，而加更多算術單元毫無用處，因為資料沒辦法來得更快。如果它落在平的那段下面——彎折點的右邊——它就是計算受限：記憶體系統跟得上，你是真正被原始算術吞吐量所限。向量加總坐在很左邊（記憶體受限）；一個寫得好的矩陣乘法坐在右邊（計算受限）。屋頂線在你優化任何一行之前就告訴你，你手上實際上是哪一種問題——從而哪些修正才可能有用。
這把優化誠實地重新框定了。對一個記憶體受限的核心，買更快的算術單元是白花錢；唯一真正的勝利來自「搬更少的資料」——這意味著重新安排計算，讓每個取來的數字在還留在快取裡時就被重複使用，提高資料局部性與強度。當家的把戲是分塊（鋪磚）：把問題切成能塞進快取的小塊，趁一塊還燙手時把它身上所有的工作做完，再換下一塊。這就是你如何讓一個核心沿著屋頂線往右滑、朝計算天花板靠近，也正是下一篇指南的核心。
為什麼這改變你的思考方式——以及一個誠實的提醒
退一步，感受這個轉變。兩個浮點運算次數「相同」的演算法，真實執行時間可以差上 10 倍或更多，純粹因為其中一個以友善、連續的順序碰記憶體，而另一個跳來跳去。你會在下一篇指南遇到的經典例子：用課本的方式乘兩個矩陣，相對於用分塊的方式，做的是「完全一樣」的算術，然而分塊版本在同一台機器上可以快好幾倍。浮點運算根本沒變；變的只是記憶體流量。一旦你把這件事內化，你就不再只問「做了幾次運算？」，而開始問「我的資料是怎麼移動的？」
而這裡有一個貫穿整個領域的實用結論：這在很大程度上正是為什麼你該伸手去拿調校過的函式庫BLAS 與 LAPACK，而不是自己手寫迴圈。寫那些常式的專家花了數年為每種快取大小做分塊、鋪磚、調校記憶體流量——這份工作你幾乎肯定不該自己重做。「浮點運算很便宜，記憶體卻很慢」正是那些函式庫被打造來利用的原則，站在它們之上，是你免費取得又快又正確的程式的方法。