複旦大學961-計算機系統基礎-第二章-優化程式性能

961全部内容連結

文章目錄

• 優化程式性能
• 優化編譯器的能力
• 編譯器優化的局限性
• 表示程式性能
• 特定體系結構或應用特性的性能優化
• 限制因素
• 确認和消除性能瓶頸
• • 确定性能瓶頸
  • 消除性能瓶頸

優化程式性能

《CSAPP》P341

1. 選擇合适的算法和資料結構
2. 編寫出編譯器能夠有效優化以轉換成高效可執行代碼的源代碼
3. 消除不必要的功能，讓代碼盡可能有效地執行所期望的任務。如不必要的函數調用，條件測試和記憶體引用。

《CSAPP》P387 5.13 應用：性能提高技術

1. 進階設計：選擇合适的算法和資料結構
2. 基本編碼原則：避免限制優化的因素，這樣編譯器就能産生高效的代碼，例如：消除連續的函數調用，消除不必要的記憶體引用。
3. 低級優化：結構化代碼以利用硬體功能。如：①展開循環，降低開銷，并且使得進一步的優化成為可能； ②通過使用例如多個累積變量和重新結合等技術，找到方法提高指令級并行；③用功能性的風格重寫條件操作，使得編譯采用條件資料傳送。

優化編譯器的能力

《CSAPP》P342

優化編譯器的能力：現代編譯器運用複雜精細的算法來确定一個程式中計算的是什麼值，以及他們是被如何使用的。然後利用一些機會來簡化表達式，在幾個不同的地方使用同一個計算，以及降低一個給定的計算必須被執行的次數。大多編譯器，包括GCC，會向使用者提供一些優化級别參數，優化級别越高，程式性能越高，但也可能增加程式的規模，也可能使标準的調試工具很難對程式進行調試。

編譯器優化的局限性

《CSAPP》P342

編譯器優化的局限性：編譯器隻會對程式使用安全的優化。也就是說編譯器在簡化語句時，會考慮到所有情況，如果可能會出問題，就不會對其進行優化。這種情況下，就需要開發人員自行優化。 例如下面代碼：

void twiddle1(long *xp, long *yp) {
	*xp += *yp;
	*xp += *yp;
} // 該語句效率低，需要六次訪存（2次讀*xp，2次寫*xp，2次讀*yp）

void twiddle2(long *xp, long *yp) {
	*xp += 2* *yp;
} // 該語句效率高，僅需要3次訪存（讀*xp，讀*yp，寫*xp）
           

該例子中，若xp和yp指向的是不同的位址，則1,2的結果是一樣的，但如果他們指向的是同一位址，則他們的結果會不一緻（1的xp會變為原來的4倍，2的xp會變為原來的3倍）。編譯器考慮到可能會出現不一緻，是以編譯器并不會将twiddle1優化成twiddle2。

這種妨礙編譯器優化的因素稱為妨礙優化的因素（optimization blocker）。上述這種兩個指針可能指向同一個記憶體位置的情況稱為記憶體别名使用（memory aliasing） 。

表示程式性能

《CSAPP》P345

我們引入度量标準每元素的周期數（Cycles Per Element, CPE） 作為一種表示程式性能并指導我們改進代碼的方法。CPE這種度量标準幫助我們在更細節的級别上了解疊代程式的循環性能。這樣的度量标準對執行重複計算的程式來說是很适當的，例如圖像進行中的像素，或是計算矩陣乘積中的元素。

每元素的周期數：

1. 周期：指的是CPU的時鐘周期
2. 元素：指要處理的集合的一個元素

每元素的周期數就是指處理一個元素要消耗的CPU時鐘周期的數量

例如：

該圖中：psum1和psum2指的是兩個程式函數。slope是斜率（這個斜率就是CPE的值），橫坐标是集合元素的數量，縱坐标是時鐘周期數。

也就是說，當集合元素數為0時，它們消耗的時鐘周期數為400，當集合元素數為200時，psum1消耗的時鐘期周期數為2200。是以psum1的CPE的值為9，也就是 (2200-400)/200 = 9。 psum2的算法一樣。顯然，psum2函數的性能更好。

CPE的計算公式：

C P E = f ( n ) − f ( 0 ) n       其 中 f ( n ) 表 示 n 個 元 素 時 消 耗 的 時 鐘 周 期 數 CPE = \frac{f(n) - f(0)}{n} ~~~~~其中f(n)表示n個元素時消耗的時鐘周期數 CPE=nf(n)−f(0)​     其中f(n)表示n個元素時消耗的時鐘周期數

特定體系結構或應用特性的性能優化

《CSAPP》P350-P377

1. 消除循環的低效率：就是把循環裡面的代碼效率寫的高一點。因為非循環部分影響較小，可以忽略不計。但是循環裡面的代碼要執行多次，影響比較大
2. 減少過程調用：過程調用就是函數調用。過程調用會帶來開銷，而且會妨礙大多數形式的程式優化。
3. 消除不必要的記憶體引用：不要頻繁直接操作指針。可以申請一個局部變量，對局部變量進行操作。比如， for(;; ) *p+=1; 可以改成 a=*p; for(;; ) a+=1; *p=a;
4. 了解現代處理器：了解現代處理器可以幫助優化程式性能。現代處理器支援指令集并行，即看似代碼是一條一條執行的，但實際上在CPU中，可以多條指令一起執行。若一系列操作必須按照嚴格順序執行時，就會遇到延遲界限（latency bound） ，因為在下一條指令開始之前，這條指令必須結束。這個界限是程式性能的終極限制。
5. 循環展開：循環展開是一種程式變換，通過增加每次疊代計算的元素的數量，減少循環的疊代次數。它減少了不直接有助于程式結果的操作的數量，第二，它提供了一些方法，可以進一步變化代碼，減少整個計算中關鍵路徑上的操作數量。
6. 提高并行性：由4知，現代CPU是可以并行執行的。但不是所有代碼都會并行，改造代碼讓其可以并行執行就可以提高程式性能。 如 for(;;i++) a = arr[i]; 可以改造為 for(;;i+=2) {a = arr[i]; b= arr[i+1] }; a += b 前者for循環中隻有一行代碼，是以整個for循環都是串行執行的。而改造後的後者，循環次數降低了一倍，而且for循環中的兩行代碼可以并行執行，是以整體提高了性能。

限制因素

《CSAPP》P378

1. 寄存器溢出，當采用提高循環并行性的優化時，若我們的并行度p超過了可用的寄存器數量，那麼編譯器就會借助于（resort to）溢出（spilling） ，将某些臨時值存放到記憶體中，通常是在運作時堆棧上配置設定空間。這樣我們優化的優勢就很可能消失。
2. 分支預測和預測錯誤處罰：當分支預測邏輯不能正确預測一個分支是否要跳轉的時候，條件分支可能會招緻很大的預測錯誤處罰。若CPU支援投機執行（speculative execution），處理器會開始執行預測的分支目标處的指令。若預測正确，就“送出”投機執行的指令的結果，若預測錯誤，則丢棄。

确認和消除性能瓶頸

《CSAPP》P388

确定性能瓶頸

對于很大的程式，我們很難知道應該優化什麼地方。是以需要借助代碼剖析程式（code profiler） ，這是在程式執行時收集性能資料的分析工具。

程式剖析（profiling） 運作程式的一個版本，其中插入了工具代碼，以确定程式的各個部分需要多少時間。這樣就可以知道哪一塊消耗的時間最長，然後針對消耗最長的這塊代碼進行優化了。

Unix提供了一個剖析程式GPROF。它确定程式中每個函數花費了多少CPU時間。其次，它計算了每個函數被調用的次數，以執行調用的函數來分類。

Amdahl定律的思想：當我們對系統的某個部分加速時，其對系統整體性能的影響取決于該部分的重要性和加速程度。

消除性能瓶頸

使用剖析程式來指導優化，一步一步消除性能瓶頸。