迴圈展開(loop unrolling)
每繞迴圈一圈都有一點小稅:遞增計數器、測試條件、跳回頂端。如果本體裡真正的工作很小,這個稅可能佔掉相當大一部分時間。迴圈展開藉由「每圈做好幾次迭代份的工作」來減少這個稅——把本體複製兩、四或八份,計數器每次就跨那麼多,使整體的條件測試與跳躍變少。
具體而言,一個跑 n 次、每圈一個操作的迴圈,可以改寫成跑 n/4 次、每圈四個操作。一個加總陣列的迴圈 for (i = 0; i < n; i++) s += a[i]; 在精神上變成一個做 s += a[i] + a[i+1] + a[i+2] + a[i+3]、並把 i 推進 4 的迴圈,外加一個小小的收尾迴圈,處理當 n 不是 4 的倍數時最後 0 到 3 個元素(餘數或尾段,epilogue)。除了削減迴圈開銷,展開也把好幾個獨立操作並排暴露出來,讓處理器的亂序與超純量機制一次有更多東西可咀嚼,也讓本體更容易向量化。
它重要在於:它是高效能內層迴圈的構件,也常是良好自動向量化的前提。但它受成本模型支配,且有真實的缺點:展開讓程式碼變大,可能溢出指令快取、反而拖慢速度,而且它只在迴圈開銷佔工作有意義的比例時才有幫助。一個值得誠實面對的提醒:展開不是免費的速度。編譯器在 -O2 與 -O3 選擇性地展開,正確的倍數取決於晶片,而對一個本體已經很重的迴圈過度展開毫無所獲、卻讓二進位檔膨脹——手動展開前先量測。
for (i = 0; i < n; i++) s += a[i]; // 展開 4 倍(加上 n 不被 4 整除時的餘數迴圈): for (i = 0; i + 3 < n; i += 4) s += a[i] + a[i+1] + a[i+2] + a[i+3]; for (; i < n; i++) s += a[i]; // 尾段處理剩下的
每圈四個元素把迴圈開銷削減四倍;小小的尾段在 n 非 4 的倍數時收尾。
展開以程式碼大小換取更少的迴圈測試,所以不是無條件更快:較大的本體可能溢出指令快取,而過度展開一個重迴圈只會膨脹二進位檔——讓編譯器決定,手動展開前先量測。