譯者 | 陳峻

51CTO讀者成長計(jì)劃社群招募，咨詢小助手（微信號：TTalkxiaozhuli）

不知您是否了解單指令流多數(shù)據(jù)流，也就是我們常聽說的SIMD（Single Instruction Multiple Data）？它是采用單個(gè)控制器來控制多個(gè)處理器，同時(shí)對一組數(shù)據(jù)中的每一個(gè)分別執(zhí)行相同的操作，從而實(shí)現(xiàn)空間上的并行性的一種技術(shù)。就SIMD的工作原理而言，我們可以將其理解為三個(gè)層次：

• 編譯器具有一定智能，可以自動矢量化（auto-vectorize）所有的代碼。
• 編譯器自動向量化的能力欠佳，容易受不相關(guān)代碼變更的影響，因此開發(fā)人員需要手動編寫明確的SIMD指令。
• 需要重復(fù)為每個(gè)不同的CPU架構(gòu)手工編寫SIMD。此時(shí)，作為工具的編譯器，可以通過更好的指令和約束，以適合向量化的形式，編寫出可靠的向量化代碼。

在日常工作中，我們的開發(fā)場景通常處于第二級和第三級，需要用編譯器來優(yōu)化模型。下面，我將和您討論靜態(tài)語言（如Rust或C++）編譯器優(yōu)化的一般框架，以及如何將該框架應(yīng)用于自動矢量化。

1、從編譯器的視角看問題

首先，讓我們來了解編譯器是如何查看代碼的。鑒于有著許多結(jié)構(gòu)上相似之處，我們可以參照WebAssembly規(guī)范（https://webassembly.github.io/spec/core/）來了解編譯器在優(yōu)化方面的核心規(guī)范。如下方簡單代碼段所示，一個(gè)優(yōu)化單元往往就是一個(gè)函數(shù)：

fn sum(xs: &[i32]) -> i32 {
let mut total = 0;
for i in 0..xs.len() {
total = total.wrapping_add(xs[i]);
}
total
}
在一些偽IR（指令寄存器）中，上述代碼表現(xiàn)為：
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
}

此處出現(xiàn)了兩個(gè)重要的特征實(shí)體：

• 作為粗略字節(jié)數(shù)組的程序內(nèi)存，編譯器往往無法很好地推斷出內(nèi)存中的內(nèi)容。而且由于它們是由所有函數(shù)共享的，因此不同的函數(shù)可能會以不同的方式去解釋內(nèi)存中的內(nèi)容。
• 作為整數(shù)形式的局部變量，它們遵循編譯器可推理的數(shù)學(xué)屬性。

例如，如果編譯器看到了如下循環(huán)：

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

它可以推斷在每一次循環(huán)中，tmp能夠保持i * 4，進(jìn)而會將其優(yōu)化為：

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

不過，如果我們進(jìn)行相同的計(jì)算，但所有數(shù)字都位于內(nèi)存中，那么編譯器將很難推斷出轉(zhuǎn)換的正確性。如果針對n的存儲和total實(shí)際是重疊的，而tmp與某些不在當(dāng)前函數(shù)中的數(shù)據(jù)重疊了，該怎么辦呢？

其實(shí)，load和store指令可以作為數(shù)學(xué)局部變量和內(nèi)存字節(jié)的橋梁。也就是說，load指令在內(nèi)存中獲取一系列字節(jié)，將字節(jié)解釋為整數(shù)，并將該整數(shù)存儲到局部變量中。而store指令的執(zhí)行操作正好相反。通過將某些內(nèi)容從內(nèi)存加載到本地，編譯器可以獲得對其進(jìn)行精確推理的能力。因此，編譯器無需跟蹤內(nèi)存的基本內(nèi)容，只需檢查在特定時(shí)間點(diǎn)，從內(nèi)存進(jìn)行的加載是否正確即可。可見，編譯器一次只能真正推理一個(gè)函數(shù)，而且只能推理該函數(shù)中的局部變量。

2、將代碼向編譯器推近些

通過為編譯器提供更多的上下文，我們可以實(shí)現(xiàn)兩項(xiàng)核心的優(yōu)化任務(wù)：

第一項(xiàng)核心優(yōu)化是內(nèi)聯(lián)（inlining）。它使用被調(diào)用者去代替特定的調(diào)用。據(jù)此，調(diào)用者和被調(diào)用者的局部變量都在同一個(gè)框架中，編譯器可以一起優(yōu)化它們。

讓我們看一段Rust代碼：

fn sum(xs: &[i32]) -> i32 {

let mut total = 0;
for i in 0..xs.len() {
total = total.wrapping_add(xs[i]);
}
total
}

其中的表達(dá)式xs[i]實(shí)際上是一個(gè)函數(shù)調(diào)用。索引函數(shù)在訪問數(shù)組元素之前，會進(jìn)行邊界檢查。將其內(nèi)聯(lián)到sum中后，編譯器可以看到其代碼并消除之。畢竟，在內(nèi)聯(lián)之后，函數(shù)傾向于處理一般情況，并在特定的調(diào)用站點(diǎn)（call-site），使用足夠的約束，來消除各種邊緣情況。

第二項(xiàng)核心優(yōu)化是聚合的標(biāo)量替換（scalar replacement of aggregates，SROA）。我們使用load避免對內(nèi)存進(jìn)行推理，而是對本地進(jìn)行推理。

例如，有如下這樣一個(gè)函數(shù)：

fn permute(xs: &mut Vec<i32>) {
...
}

編譯器會收到一個(gè)指向某段內(nèi)存的指針。由于該內(nèi)存包含了一個(gè)復(fù)雜的結(jié)構(gòu)（即：ptr、len、capacity triple），因此它很難推理出該結(jié)構(gòu)的演變。對此，編譯器可以從內(nèi)存中加載該結(jié)構(gòu)，并使用一堆標(biāo)量局部變量，來進(jìn)行替換聚合：

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
}

如此，編譯器再次獲得了推理能力。雖然與內(nèi)聯(lián)類似，但是SROA主要用于內(nèi)存，而不是代碼。

3、不可能與可能

使用編譯器模型的主要優(yōu)勢在于：

• 在每個(gè)函數(shù)的基礎(chǔ)上進(jìn)行優(yōu)化
• 可以進(jìn)行內(nèi)聯(lián)函數(shù)的調(diào)用
• 擅長發(fā)現(xiàn)局部變量之間的關(guān)系，并據(jù)此重新排列代碼
• 能夠?qū)?nèi)存進(jìn)行有限的推理（即，決定何時(shí)適合load或store）。

當(dāng)然，我們需要描述哪些代碼可以被可靠地優(yōu)化，哪些代碼無法被優(yōu)化，從而解釋零成本抽象（zero cost abstractions）。針對啟用內(nèi)聯(lián)的情況，編譯器需要知道有哪個(gè)函數(shù)被實(shí)際調(diào)用了。如果屬于直接調(diào)用，編譯器則會嘗試著與之內(nèi)聯(lián)；如果是間接調(diào)用（即：通過函數(shù)指針或通過虛函數(shù)表進(jìn)行調(diào)用），那么在一般情況下，編譯器將無法與之內(nèi)聯(lián)。對于間接調(diào)用而言，編譯器有時(shí)也可以推斷指針的值，并對調(diào)用進(jìn)行去虛擬化（de-virtualize）。不過，這往往依賴于在其他地方已實(shí)現(xiàn)了成功的優(yōu)化。

這也就是為什么在Rust中，每個(gè)函數(shù)都有一個(gè)唯一的、大小為零（zero-sized）的類型，而且并沒有運(yùn)行時(shí)（runtime）的表示。它靜態(tài)的方式保證了編譯器始終可以內(nèi)聯(lián)到代碼上，以使得抽象的成本為零，畢竟任何優(yōu)化編譯器都會將其“融化”為零。

當(dāng)然，更高級別的語言則可能會選擇始終使用函數(shù)指針去表示函數(shù)。實(shí)際上，在許多情況下，它們生成的代碼就等效為可優(yōu)化的。不過，在源代碼中是不會有任何跡象來表明這是一個(gè)可優(yōu)化的情況（實(shí)際指針在編譯時(shí)是可知的），還是真正的動態(tài)調(diào)用狀況。因此，使用Rust就保證了可優(yōu)化和潛在可優(yōu)化之間的區(qū)別，能夠反映在源語言之中，請參見如下代碼段：

// 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()
}

由上述代碼可知，其第一條規(guī)則便是使大多數(shù)調(diào)用可以被靜態(tài)解析，以允許內(nèi)聯(lián)。而函數(shù)指針和動態(tài)調(diào)度則會防止內(nèi)聯(lián)。此外，內(nèi)存中的間接尋址也會給編譯器帶來如下麻煩：

struct Foo {
bar: Bar,
baz: Baz,
}

顯然，上述Foo結(jié)構(gòu)對編譯器是完全透明的。不過，讓我們稍作如下修改：

struct Foo {
bar: Box<Bar>,
baz: Baz,
}

上述結(jié)果就不那么明確了。也就是說，被Foo占用的內(nèi)存一般不會轉(zhuǎn)移到被Bar占用的內(nèi)存處。同樣，在許多情況下，鑒于唯一性，編譯器可以通過box進(jìn)行“不保證”的推理。

如下代碼段展示了map是如何被簽名和定義的。

#[inline]
fn map<B, F>(self, f: F) -> Map<Self, F>
where
Self: Sized,
F: FnMut(Self::Item) -> B,
{
Map::new(self, f)
}

關(guān)于內(nèi)存的另一個(gè)重點(diǎn)是，一般而言，編譯器不能改變整體布局。SROA可以將一些數(shù)據(jù)結(jié)構(gòu)加載到一堆局部變量中，然后可以用“一對指針”代替“一個(gè)指針和一個(gè)索引”的表示。不過，SROA最終將不得不具體化“一個(gè)指針和一個(gè)索引”，并將該表示存儲回內(nèi)存之中。這是因?yàn)閮?nèi)存布局是在所有函數(shù)之間共享的，因此函數(shù)不能單方面地指定更優(yōu)化的表示。

總之，只要能夠“看到”代碼，編譯器就能夠更擅長推理代碼。因此，請確保大多數(shù)調(diào)用在編譯時(shí)可以實(shí)現(xiàn)內(nèi)聯(lián)。

四、SIMD

讓我們將前面討論的、為編譯器提供可優(yōu)化代碼的通用框架，應(yīng)用到自動矢量化上。下面是我們優(yōu)化計(jì)算兩個(gè)字節(jié)片之間最長公共前綴的函數(shù)。

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
}

如果您已經(jīng)有了自動矢量化的模型，或者已查看了匯編的輸出，那么就會發(fā)現(xiàn)一次僅處理一個(gè)字節(jié)的函數(shù)，效率非常慢。我們該如何解決這個(gè)問題呢？

SIMD既然可以同時(shí)處理多個(gè)值，那么我們就希望編譯器能夠同時(shí)比較一堆字節(jié)。例如，我們通過如下代碼段，先一次性處理16個(gè)字節(jié)，然后分別處理剩余部分，以便使得結(jié)構(gòu)更加顯式化：

// 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
}

其實(shí)，上述代碼在速度上的提升是遠(yuǎn)遠(yuǎn)不夠的。具體來說，SIMD需要以相同的方式，并行處理塊中的所有值。在上述代碼中，我們用到了一個(gè)break。這意味著第n對字節(jié)的處理，取決于第n-1對。我們可以通過禁用短路（short-circuiting），來檢查整個(gè)字節(jié)塊是否匹配。當(dāng)然，我們并不關(guān)心具體哪個(gè)特定字節(jié)出現(xiàn)了不匹配：

// 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
}

至此，矢量化已成功開始，而且?guī)缀鯗p少了一個(gè)數(shù)量級的運(yùn)行時(shí)間。我們現(xiàn)在可以使用迭代器來進(jìn)行壓縮了。

// 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()
}

顯然，此時(shí)的代碼已與我們開始時(shí)有了顯著不同?？梢姡覀儾粦?yīng)盲目依賴編譯器的優(yōu)化，而需要知道在何種情況下進(jìn)行特定優(yōu)化，以觸發(fā)它們編寫代碼的方式。例如，對于SIMD而言，我們需要根據(jù)處理元素塊來表達(dá)算法。而且在每個(gè)塊中，我們應(yīng)確保沒有分支，讓所有元素都能以相同的方式處理。

原文鏈接：https://matklad.github.io/2023/04/09/can-you-trust-a-compiler-to-optimize-your-code.html

譯者介紹

陳峻 （Julian Chen），51CTO社區(qū)編輯，具有十多年的IT項(xiàng)目實(shí)施經(jīng)驗(yàn)，善于對內(nèi)外部資源與風(fēng)險(xiǎn)實(shí)施管控，專注傳播網(wǎng)絡(luò)與信息安全知識與經(jīng)驗(yàn)。