最佳化編譯器與其限制 (Optimizing Compilers & Blockers)

Overview Table

小節	主題	核心概念	書頁
5.1	最佳化編譯器的能力與限制	safe optimization、兩大 optimization blockers:memory aliasing 與函式 side effect	p.534-538
5.2	表達程式效能	CPE (cycles per element):以時脈週期為單位量測迴圈效能	p.538-540
5.3	程式範例	vector 抽象資料型別 + `combine1` 作為一路最佳化的基準	p.540-544
5.4	消除迴圈低效率	code motion:把 `vec_length`/`strlen` 移出迴圈;隱藏的漸近低效率	p.544-548
5.5	減少程序呼叫	`combine3` 直接存取陣列,去除迴圈內函式呼叫(意外地沒有立即加速)	p.548-549
5.6	消除不必要的記憶體參考	`combine4` 用區域變數 `acc` 累積,記憶體操作從 2 讀 1 寫降為 1 讀	p.550-553

版本	方法	int +	int *	FP +	FP *
combine1	抽象、未最佳化	22.68	20.02	19.98	20.18
combine1	`-O1`	10.12	10.12	10.17	11.14
combine2	移出 `vec_length`	7.02	9.03	9.02	11.03
combine3	直接存取資料	7.17	9.02	9.02	11.03
combine4	累積於暫存變數	1.27	3.01	3.01	5.01

全章策略 (p.534)

只做「剛好足夠」的原始碼改寫,讓編譯器接手產生高效率程式碼——比直接寫組合語言保留了可讀性、模組性、可攜性。反覆「修改 → 量測 → 讀組譯輸出」是高效能程式的實際寫法;辨識 critical path(迴圈重複執行時形成的資料相依鏈)可推得執行時間下界。

5.1 最佳化編譯器的能力與限制 (p.534-538)

現代編譯器能簡化運算式、共用重複計算、減少計算次數。gcc 以 -Og 做基本最佳化,-O1/-O2/-O3 逐級加強;層級越高效能越好,但程式體積膨脹且更難用除錯工具除錯。書中刻意以 -O1 為主(業界慣例為 -O2),以突顯 C 寫法本身對產出碼效率的影響——寫得好的程式配 -O1 可大勝 naive 版本配最高最佳化等級。

Safe optimization:編譯器只能做「在 C 標準保證的範圍內,對所有可能情況行為完全相同」的轉換;寧可保守也不冒險。
gcc 的最佳化能力被評為「adequate, but not exceptional」——不做激進轉換,因此程式設計者要多花力氣寫出好最佳化的程式。

Blocker 1:Memory Aliasing(記憶體別名)

void twiddle1(long *xp, long *yp) { *xp += *yp; *xp += *yp; }  /* 6 次記憶體參考 */
void twiddle2(long *xp, long *yp) { *xp += 2* *yp; }           /* 3 次記憶體參考 */

當 xp == yp(aliasing)時兩者行為不同:twiddle1 使 *xp 變 4 倍(連續兩次翻倍),twiddle2 只變 3 倍(*xp += 2*(*xp))。編譯器不知道呼叫端會怎麼傳參數,必須假設兩指標可能相等,故不能把 twiddle1 最佳化成 twiddle2 的形式。

xp ──┐                xp ──┬──> [ 同一位址 ]
     ├─> [不同位址]        │
yp ──┘   (無 alias)   yp ──┘   (aliased:最佳化不安全)

另一例:*q = y; *p = x; t1 = *q; 中 t1 的值取決於 p、q 是否 alias(無 alias 得 3000,有 alias 得 1000)——編譯器無法判定時,兩種情況都得假設可能,可用的最佳化因而受限 (p.535-536)。

Blocker 2:函式呼叫的 Side Effects

long f();
long func1() { return f() + f() + f() + f(); }  /* 呼叫 4 次 */
long func2() { return 4*f(); }                   /* 呼叫 1 次 */

若 f() 有 side effect(如 return counter++; 修改全域狀態),func1 回傳 0+1+2+3 = 6 而 func2 回傳 4*0 = 0。多數編譯器不去分析函式是否無 side effect,一律假設最壞情況、保留所有函式呼叫。

Inline substitution(行內展開,p.537 Aside)

把函式呼叫替換成函式本體(gcc 於 -O1 以上或 -finline 嘗試),既省呼叫開銷又開啟後續最佳化空間,例如展開後的 func1 可整併成 t = 4*counter + 6; counter += 4;。限制與代價:

gcc 只對同一個檔案內定義的函式做 inlining(跨檔的函式庫呼叫不適用)。
被 inline 掉的呼叫無法用 gdb 設中斷點追蹤,也無法被 profiler 正確計入(§3.10.2 的除錯工具、§5.14.1 的 profiling)。

5.2 表達程式效能:CPE (p.538-540)

處理器活動由時脈 (clock) 控制,頻率以 GHz(每秒 $10^{9}$ 週期)表示;週期時間 = 時脈頻率的倒數,如 4 GHz 時脈的週期為 $1 / (4 \times 10^{9})$ 秒 = 0.25 ns = 250 ps。以「時脈週期數」而非 ns/ps 表達量測,才反映執行了多少指令而非時脈多快。

對迭代處理 n 個元素的程序,執行時間可近似為:

T = Overhead + CPE \times n

CPE (cycles per element):線性項係數,即「每元素有效週期數」。以 prefix sum 為例(以 least squares fit 求得):psum1 為 $368 + 9.0 n$ 、psum2(2 路 loop unrolling,每迭代算 2 個元素)為 $368 + 6.0 n$ → CPE 分別為 9.0 與 6.0。
用「每元素」而非「每迭代」:因 05-Program-Optimization/03-Loop-Unrolling-and-Parallelism 之類技術會改變迭代次數,但我們最終在乎的是處理固定長度向量的總時間。
n 夠大(如 > 200)時線性項主導,常數 overhead(計時碼、進入程序、迴圈設定與收尾)可忽略。
Prefix sum 定義 (式 5.1): $p_{0} = a_{0}, p_{i} = p_{i - 1} + a_{i} (1 \leq i < n)$
Least squares fit (p.540 Aside):找 $y = m x + b$ 使誤差 $E (m, b) = \sum_{i = 1, n} (m x_{i} + b - y_{i})^{2}$ 最小(對 m、b 偏微分並設為 0 求解)。

交叉點計算模式(Practice 5.2 型)

給多個 $T_{i} = c_{i} + {CPE}_{i} \cdot n$ ,問哪個 n 區間誰最快 → 解不等式找整數交叉點。例: $60 + 35 n$ 、 $136 + 4 n$ 、 $157 + 1.25 n$ 三版本,小 n 時常數項低者勝,大 n 時 CPE 低者勝(記得 n 是整數)。

5.3 程式範例:vector ADT 與 combine1 (p.540-544)

貫穿全章的例子:vector 抽象資料型別由 header + data array 兩塊記憶體構成:

vec_ptr ──> ┌─────────┐
            │ len     │             data array
            │ data ───┼──> ┌────┬────┬────┬─ ─ ─┬───────┐
            └─────────┘    │ 0  │ 1  │ 2  │ ... │ len-1 │
              header       └────┴────┴────┴─ ─ ─┴───────┘
                             (len 個 data_t 元素)

typedef struct { long len; data_t *data; } vec_rec, *vec_ptr;

data_t 以 typedef 切換為 int/long/float/double 分別編譯量測;實驗顯示 32/64 位元整數效能相同(除法運算除外)、單/雙精度浮點效能相同,故表格只分 int / FP 兩欄。
get_vec_element(v, i, &val) 對每次存取做 bounds checking(越界回傳 0),類似 Java 的陣列表示法——降低出錯機會但拖慢執行。
combine1(Figure 5.5)把向量所有元素以某運算合併為單一值,用編譯期常數 IDENT/OP 切換:#define IDENT 0 + #define OP + 為總和;#define IDENT 1 + #define OP * 為乘積。
量測平台為 Intel Core i7 Haswell(reference machine);絕對數字不保證跨機器成立,但趨勢在多種 compiler/processor 組合上大致一致。
combine1 未最佳化 CPE 約 22.68;僅加 -O1 就快超過 2 倍(約 10.12)——養成開啟最佳化的習慣是零成本的第一步(-Og 結果相近)。
量測本身有雜訊:精確量週期數很難,讀數時心裡上下修個幾百分之一週期即可(書中不「美化」數字,如 22.68 實際更可能是 23.00)。
決定套用哪些轉換組合是寫快程式的「black art」:有些轉換單獨無效、卻是啟用後續最佳化的前提;最佳做法是實驗與分析並行——反覆嘗試、量測、讀組譯碼找瓶頸。

5.4 消除迴圈低效率:Code Motion (p.544-548)

combine1 把 vec_length(v) 放在 for 迴圈的測試條件中,而測試條件每次迭代都要重新求值(03-Machine-Level-Programs/03-Control-Flow §3.6.7 的迴圈翻譯),但向量長度在迴圈中不變。combine2 在迴圈前先算 long length = vec_length(v); → int + 的 CPE 從 10.12 降到 7.02。

Code motion(程式碼移動):辨識「執行多次(如迴圈內)但結果不變」的計算,移到較早、執行頻率較低的位置。
編譯器會嘗試 code motion,但對「改變函式呼叫位置或次數」的轉換非常保守——它無法可靠判定函式是否有 side effect,只能假設有(若 vec_length 有 side effect,combine1/combine2 行為就不同)。因此程式設計者必須自己動手幫編譯器搬移。

極端案例:lower1 的隱藏平方複雜度

/* 慢:strlen 在迴圈測試中,每次迭代重算 */
for (i = 0; i < strlen(s); i++)             /* lower1: O(n²) */
    if (s[i] >= 'A' && s[i] <= 'Z') s[i] -= ('A' - 'a');

/* 快:先存長度 */
long len = strlen(s);
for (i = 0; i < len; i++) ...               /* lower2: O(n) */

C 字串以 null 結尾,strlen 必須逐字元掃到 '\0',單次成本 $O (n)$ ;lower1 在 n 次迭代各呼叫一次 → 總時間 $\propto n^{2}$ 。
實測特徵:字串長度每加倍,lower1 時間變 4 倍(平方)、lower2 變 2 倍(線性)。長度 1,048,576 時 lower1 約 1,050 秒(逾 17 分鐘),lower2 僅 2.0 ms——快 50 萬倍以上,且字串越長差距越大。
編譯器無法自動搬出 strlen:迴圈本身在修改字串內容,要證明「沒有字元在零與非零之間變化」超出任何編譯器(即使搭配 inlining)的分析能力,只能靠人手動轉換。

隱藏的漸近低效率 (asymptotic inefficiency)

看似無害的小程式(大小寫轉換)在小測資下沒問題,部署後遇上百萬字元輸入就成了主要瓶頸——程式通常只用小資料集測試,平方複雜度不會現形。避免寫出這種程式碼是合格程式設計者的職責 (p.547-548)。

呼叫次數分析模式(Practice 5.3 型)

for 迴圈中:init 執行 1 次;test 每次迭代前都執行(含最後失敗那次);update 與 body 每迭代 1 次。如 for (i = min(x,y); i < max(x,y); incr(&i,1)) 中 max 在測試裡會被重複呼叫;先把 min/max 存入區域變數(片段 C)即是手動 code motion。

5.5 減少程序呼叫 (p.548-549)

combine2 每迭代仍呼叫 get_vec_element,其中的 bounds checking 每次都比對索引 i 與邊界——但簡單分析即知此迴圈所有存取必然合法,檢查是明顯的低效率來源。combine3 新增 get_vec_start(v) 回傳 data array 起始位址,迴圈內改為直接 data[i] 存取,內層迴圈零函式呼叫。

結果出乎意料:CPE 幾乎沒變(int + 甚至從 7.02 微幅變差為 7.17)——內層迴圈中其他操作(每迭代對 *dest 的記憶體讀寫)才是瓶頸,get_vec_element 的成本被掩蓋(§5.11.2 會解釋為何重複 bounds checking 沒有額外代價)。
教訓:單一轉換不一定立即見效,但它是通往大幅改善的必要步驟之一。
模組性代價:純粹主義者批評此舉破壞抽象(使用者不該知道 vector 內部是陣列而非 linked list);務實派視之為達成高效能的必要步驟。

5.6 消除不必要的記憶體參考 (p.550-553)

檢視 combine3 內層迴圈的 x86-64 組譯碼(data_t = double、OP = *):

combine3 內層迴圈 (-O1):每迭代 2 讀 1 寫
.L17:
  vmovsd (%rbx), %xmm0        ← 從 dest 讀回累積值(浪費!)
  vmulsd (%rdx), %xmm0, %xmm0 ← 乘上 data[i](1 次讀)
  vmovsd %xmm0, (%rbx)        ← 寫回 dest
  addq   $8, %rdx             ← 指標 data+i 前進 8 bytes
  cmpq   %rax, %rdx           ← 與 data+length 比較
  jne    .L17

combine4 內層迴圈:累積值留在 %xmm0,每迭代僅 1 讀
.L25:
  vmulsd (%rdx), %xmm0, %xmm0
  addq   $8, %rdx
  cmpq   %rax, %rdx
  jne    .L25

combine3 每迭代把累積值寫入 *dest、下一迭代又讀回——讀到的本來就是剛寫的值,純屬浪費。combine4 引入區域變數 data_t acc = IDENT;(accumulator)在迴圈中累積,迴圈結束後才寫一次 *dest;編譯器便能把 acc 放進暫存器 %xmm0。效能提升 2.2×–5.7×,int + 降到 1.27 CPE。

為何編譯器不能自動做這件事?又是 aliasing

若 dest 指向向量內部,兩版本行為不同。例:int 乘法、IDENT = 1、v = [2, 3, 5],呼叫 combineX(v, get_vec_start(v) + 2)(dest alias 到最後一個元素):

函式	初始	迴圈前	i=0	i=1	i=2	最終
combine3	[2,3,5]	[2,3,1]	[2,3,2]	[2,3,6]	[2,3,36]	[2,3,36]
combine4	[2,3,5]	[2,3,5]	[2,3,5]	[2,3,5]	[2,3,5]	[2,3,30]

combine3: 每迭代寫回 *dest ──> 改到 v[2] ──> 之後的迭代讀到被污染的值
          1 → 2·1=2 → 3·2=6 → 6·6=36
combine4: acc 在暫存器累積 1·2·3·5 = 30 ──> 迴圈結束才寫入 v[2]

combine4 的行為或許更貼近函式的「意圖」,但編譯器不能猜測程式設計者的意圖與使用情境;給它 combine3,保守做法就是保留每次讀寫記憶體,即使較慢。

-O2 的例外 (Practice 5.4, p.552)

gcc -O2 編譯 combine3 時 CPE 大幅改善至接近 combine4(int + 為 1.60,其餘相同):它把累積值留在 %xmm0,但每迭代仍執行 vmovsd %xmm0, (%rbx) 寫回 dest、只是消除了讀回。此轉換仍是 safe 的——暫存器中的值恆等於剛寫入 *dest 的值(迭代間沒有其他寫入者),故即使 aliasing 存在,行為與 -O1 版完全一致。可見「消除讀取」可被安全自動化,「消除寫入」則會在 aliasing 情況下改變行為,編譯器不能做。

通往 5.7 的橋樑

至此的最佳化(降低程序呼叫開銷、排除 optimization blockers)不依賴目標機器的任何特性,CPE 已從剛開最佳化時的 9–11 降到 1.25–5。要再往下壓,必須理解處理器微架構 (microarchitecture) 與指令級平行 → 05-Program-Optimization/02-Modern-Processor-Operation。

Exam/Test Patterns

情境 / 關鍵字	答案
`twiddle1` vs `twiddle2`,`xp == yp`	memory aliasing:twiddle1 使值 ×4,twiddle2 使值 ×3 → 編譯器不能互轉
三步加減 swap 且 `xp == yp`(Practice 5.1 型)	第一步後 `xp = 2x`;第二步 `yp = xp - yp = 0`;第三步仍為 0(原值被清成 0)
為何編譯器不把 `f()+f()+f()+f()` 改成 `4*f()`	`f` 可能有 side effect(如 `counter++`):前者得 6、後者得 0
「4 GHz 處理器的週期時間?」	週期 = 1/頻率 = 0.25 ns = 250 ps
執行時間 $c + k \cdot n$ ,問 k 的意義	k 即 CPE;比較多版本快慢 → 解不等式找 n 的整數交叉區間
迴圈測試條件中呼叫 `strlen`/`vec_length`	手動 code motion 移到迴圈前;`strlen` 版總時間 $O (n^{2})$
「長度加倍、時間變 4 倍」	平方時間特徵;加倍→時間 ×2 才是線性
`for (i = min(..); i < max(..); incr(..))` 各函式呼叫次數	init 1 次;test 條件每迭代重算;body/update 每迭代 1 次(Practice 5.3)
combine3 → combine4 沒被編譯器自動化的原因	`dest` 可能 alias 向量元素;`[2,3,5]` 乘積例:36 vs 30
combine2 → combine3(去除迴圈內呼叫/bounds check)為何沒加速	瓶頸在每迭代對 `*dest` 的記憶體讀寫,不在函式呼叫
`-O2` 下 combine3 內層迴圈只剩 store、無 load	消除讀取是 safe(暫存器值恆等於記憶體值);消除寫入才會在 aliasing 下變行為
inlining 的兩個副作用	gdb 無法對被展開的呼叫設中斷點;profiler 無法正確歸因(§5.14.1)
高最佳化等級 (`-O2`/`-O3`) 的代價	程式體積膨脹、標準除錯工具難以除錯;好的 C 寫法 + `-O1` 可勝 naive + 最高等級
bounds checking 每次存取都做	降低程式錯誤機會、但可能拖慢執行(類似 Java 陣列)