譯者 | 陳峻
51CTO讀者成長計劃社群招募，咨詢小助手（微信號：TTalkxiaozhuli）
不知您是否了解單指令流多數據流，也就是我們常聽說的SIMD（Single Instruction Multiple Data）？它是采用單個控制器來控制多個處理器，同時對一組數據中的每一個分別執行相同的操作，從而實現空間上的并行性的一種技術。就SIMD的工作原理而言，我們可以將其理解為三個層次：
- 編譯器具有一定智能，可以自動矢量化（auto-vectorize）所有的代碼。
- 編譯器自動向量化的能力欠佳，容易受不相關代碼變更的影響，因此開發人員需要手動編寫明確的SIMD指令。
- 需要重復為每個不同的CPU架構手工編寫SIMD。此時，作為工具的編譯器，可以通過更好的指令和約束，以適合向量化的形式，編寫出可靠的向量化代碼。
在日常工作中，我們的開發場景通常處于第二級和第三級，需要用編譯器來優化模型。下面，我將和您討論靜態語言（如Rust或C++）編譯器優化的一般框架，以及如何將該框架應用于自動矢量化。
1、從編譯器的視角看問題
首先，讓我們來了解編譯器是如何查看代碼的。鑒于有著許多結構上相似之處，我們可以參照WebAssembly規范（https://webassembly.Github.io/spec/core/）來了解編譯器在優化方面的核心規范。如下方簡單代碼段所示，一個優化單元往往就是一個函數：
fn sum(xs: &[i32]) -> i32 {
let mut total = 0;
for i in 0..xs.len() {
total = total.wrApping_add(xs[i]);
}
total
}
在一些偽IR（指令寄存器）中，上述代碼表現為：
fn sum return i32 {
param xs_ptr: ptr
param xs_len: size
local total: i32
local i: size = 0
local x: i32
local total: i32 = 0
loop:
branch_if i >= xs_len :ret
load x base=xs_ptr offset=i
add total x
add i 1
goto :loop
ret:
return total
}
此處出現了兩個重要的特征實體：
- 作為粗略字節數組的程序內存，編譯器往往無法很好地推斷出內存中的內容。而且由于它們是由所有函數共享的，因此不同的函數可能會以不同的方式去解釋內存中的內容。
- 作為整數形式的局部變量，它們遵循編譯器可推理的數學屬性。
例如，如果編譯器看到了如下循環：
param n: u32
local i: u32 = 0
local total: u32
local tmp
loop:
branch_if i >= n :ret
set tmp i
mul tmp 4
add t tmp
goto :loop
ret:
return total
它可以推斷在每一次循環中，tmp能夠保持i * 4，進而會將其優化為：
param n: u32
local i: u32 = 0
local total: u32
local tmp = 0
loop:
branch_if i >= n :ret
add t tmp
add tmp 4 # replace multiplication with addition
goto :loop
ret:
return total
不過，如果我們進行相同的計算，但所有數字都位于內存中，那么編譯器將很難推斷出轉換的正確性。如果針對n的存儲和total實際是重疊的，而tmp與某些不在當前函數中的數據重疊了，該怎么辦呢？
其實，load和store指令可以作為數學局部變量和內存字節的橋梁。也就是說，load指令在內存中獲取一系列字節，將字節解釋為整數，并將該整數存儲到局部變量中。而store指令的執行操作正好相反。通過將某些內容從內存加載到本地，編譯器可以獲得對其進行精確推理的能力。因此，編譯器無需跟蹤內存的基本內容，只需檢查在特定時間點，從內存進行的加載是否正確即可。可見，編譯器一次只能真正推理一個函數，而且只能推理該函數中的局部變量。
2、將代碼向編譯器推近些
通過為編譯器提供更多的上下文，我們可以實現兩項核心的優化任務：
第一項核心優化是內聯（inlining）。它使用被調用者去代替特定的調用。據此，調用者和被調用者的局部變量都在同一個框架中，編譯器可以一起優化它們。
讓我們看一段Rust代碼：
fn sum(xs: &[i32]) -> i32 {
let mut total = 0;
for i in 0..xs.len() {
total = total.wrapping_add(xs[i]);
}
total
}
其中的表達式xs[i]實際上是一個函數調用。索引函數在訪問數組元素之前，會進行邊界檢查。將其內聯到sum中后，編譯器可以看到其代碼并消除之。畢竟，在內聯之后，函數傾向于處理一般情況，并在特定的調用站點（call-site），使用足夠的約束，來消除各種邊緣情況。
第二項核心優化是聚合的標量替換（scalar replacement of aggregates，SROA）。我們使用load避免對內存進行推理，而是對本地進行推理。
例如，有如下這樣一個函數：
fn permute(xs: &mut Vec<i32>) {
...
}
編譯器會收到一個指向某段內存的指針。由于該內存包含了一個復雜的結構（即：ptr、len、capacity triple），因此它很難推理出該結構的演變。對此，編譯器可以從內存中加載該結構，并使用一堆標量局部變量，來進行替換聚合：
fn permute(xs: &mut Vec<i32>) {
local ptr: ptr
local len: usize
local cap: usize
load ptr xs.ptr
load len xs.len
load cap xs.cap
...
store xs.ptr ptr
store xs.len len
store xs.cap cap
}
如此，編譯器再次獲得了推理能力。雖然與內聯類似，但是SROA主要用于內存，而不是代碼。
3、不可能與可能
使用編譯器模型的主要優勢在于：
- 在每個函數的基礎上進行優化
- 可以進行內聯函數的調用
- 擅長發現局部變量之間的關系，并據此重新排列代碼
- 能夠對內存進行有限的推理（即，決定何時適合load或store）。
當然，我們需要描述哪些代碼可以被可靠地優化，哪些代碼無法被優化，從而解釋零成本抽象（zero cost abstractions）。針對啟用內聯的情況，編譯器需要知道有哪個函數被實際調用了。如果屬于直接調用，編譯器則會嘗試著與之內聯；如果是間接調用（即：通過函數指針或通過虛函數表進行調用），那么在一般情況下，編譯器將無法與之內聯。對于間接調用而言，編譯器有時也可以推斷指針的值，并對調用進行去虛擬化（de-virtualize）。不過，這往往依賴于在其他地方已實現了成功的優化。
這也就是為什么在Rust中，每個函數都有一個唯一的、大小為零（zero-sized）的類型，而且并沒有運行時（runtime）的表示。它靜態的方式保證了編譯器始終可以內聯到代碼上，以使得抽象的成本為零，畢竟任何優化編譯器都會將其“融化”為零。
當然，更高級別的語言則可能會選擇始終使用函數指針去表示函數。實際上，在許多情況下，它們生成的代碼就等效為可優化的。不過，在源代碼中是不會有任何跡象來表明這是一個可優化的情況（實際指針在編譯時是可知的），還是真正的動態調用狀況。因此，使用Rust就保證了可優化和潛在可優化之間的區別，能夠反映在源語言之中，請參見如下代碼段：
// Compiler is guaranteed to be able to inline call to `f`.
fn call1<F: Fn()>(f: F) {
f()
}
// Compiler _might_ be able to inline call to `f`.
fn call2(f: fn()) {
f()
}
由上述代碼可知，其第一條規則便是使大多數調用可以被靜態解析，以允許內聯。而函數指針和動態調度則會防止內聯。此外，內存中的間接尋址也會給編譯器帶來如下麻煩：
struct Foo {
bar: Bar,
baz: Baz,
}
顯然，上述Foo結構對編譯器是完全透明的。不過，讓我們稍作如下修改：
struct Foo {
bar: Box<Bar>,
baz: Baz,
}
上述結果就不那么明確了。也就是說，被Foo占用的內存一般不會轉移到被Bar占用的內存處。同樣，在許多情況下，鑒于唯一性，編譯器可以通過box進行“不保證”的推理。
如下代碼段展示了map是如何被簽名和定義的。
#[inline]
fn map<B, F>(self, f: F) -> Map<Self, F>
where
Self: Sized,
F: FnMut(Self::Item) -> B,
{
Map::new(self, f)
}
關于內存的另一個重點是，一般而言，編譯器不能改變整體布局。SROA可以將一些數據結構加載到一堆局部變量中，然后可以用“一對指針”代替“一個指針和一個索引”的表示。不過，SROA最終將不得不具體化“一個指針和一個索引”，并將該表示存儲回內存之中。這是因為內存布局是在所有函數之間共享的，因此函數不能單方面地指定更優化的表示。
總之，只要能夠“看到”代碼，編譯器就能夠更擅長推理代碼。因此，請確保大多數調用在編譯時可以實現內聯。
四、SIMD
讓我們將前面討論的、為編譯器提供可優化代碼的通用框架，應用到自動矢量化上。下面是我們優化計算兩個字節片之間最長公共前綴的函數。
use std::iter::zip;
// 650 milliseconds
fn common_prefix(xs: &[u8], ys: &[u8]) -> usize {
let mut result = 0;
for (x, y) in zip(xs, ys) {
if x != y { break; }
result += 1
}
result
}
如果您已經有了自動矢量化的模型，或者已查看了匯編的輸出，那么就會發現一次僅處理一個字節的函數，效率非常慢。我們該如何解決這個問題呢？
SIMD既然可以同時處理多個值，那么我們就希望編譯器能夠同時比較一堆字節。例如，我們通過如下代碼段，先一次性處理16個字節，然后分別處理剩余部分，以便使得結構更加顯式化：
// 450 milliseconds
fn common_prefix(xs: &[u8], ys: &[u8]) -> usize {
let chunk_size = 16;
let mut result = 0;
'outer: for (xs_chunk, ys_chunk) in
zip(xs.chunks_exact(chunk_size), ys.chunks_exact(chunk_size))
{
for (x, y) in zip(xs_chunk, ys_chunk) {
if x != y { break 'outer; }
result += 1
}
}
for (x, y) in zip(&xs[result..], &ys[result..]) {
if x != y { break; }
result += 1
}
result
}
其實，上述代碼在速度上的提升是遠遠不夠的。具體來說，SIMD需要以相同的方式，并行處理塊中的所有值。在上述代碼中，我們用到了一個break。這意味著第n對字節的處理，取決于第n-1對。我們可以通過禁用短路（short-circuiting），來檢查整個字節塊是否匹配。當然，我們并不關心具體哪個特定字節出現了不匹配：
// 80 milliseconds
fn common_prefix3(xs: &[u8], ys: &[u8]) -> usize {
let chunk_size = 16;
let mut result = 0;
for (xs_chunk, ys_chunk) in
zip(xs.chunks_exact(chunk_size), ys.chunks_exact(chunk_size))
{
let mut chunk_equal: bool = true;
for (x, y) in zip(xs_chunk, ys_chunk) {
// NB: &, unlike &&, doesn't short-circuit.
chunk_equal = chunk_equal & (x == y);
}
if !chunk_equal { break; }
result += chunk_size;
}
for (x, y) in zip(&xs[result..], &ys[result..]) {
if x != y { break; }
result += 1
}
result
}
至此，矢量化已成功開始，而且幾乎減少了一個數量級的運行時間。我們現在可以使用迭代器來進行壓縮了。
// 80 milliseconds
fn common_prefix5(xs: &[u8], ys: &[u8]) -> usize {
let chunk_size = 16;
let off =
zip(xs.chunks_exact(chunk_size), ys.chunks_exact(chunk_size))
.take_while(|(xs_chunk, ys_chunk)| xs_chunk == ys_chunk)
.count() * chunk_size;
off + zip(&xs[off..], &ys[off..])
.take_while(|(x, y)| x == y)
.count()
}
顯然，此時的代碼已與我們開始時有了顯著不同。可見，我們不應盲目依賴編譯器的優化，而需要知道在何種情況下進行特定優化，以觸發它們編寫代碼的方式。例如，對于SIMD而言，我們需要根據處理元素塊來表達算法。而且在每個塊中，我們應確保沒有分支，讓所有元素都能以相同的方式處理。
原文鏈接：https://matklad.github.io/2023/04/09/can-you-trust-a-compiler-to-optimize-your-code.html
譯者介紹
陳峻 （Julian Chen），51CTO社區編輯，具有十多年的IT項目實施經驗，善于對內外部資源與風險實施管控，專注傳播網絡與信息安全知識與經驗。
