每個程序員都應該了解的硬件知識
在追求高效代碼的路上，我們不可避免地會遇到代碼的性能瓶頸。為了了解、解釋一段代碼為什么低效，并嘗試改進低效的代碼，我們總是要了解硬件的工作原理。于是，我們可能會嘗試搜索有關某個架構的介紹、一些優化指南或者閱讀一些計算機科學的教科書（如：計算機組成原理）。但以上的內容可能都太過繁瑣、細節太多，在閱讀的過程中，我們可能會迷失在紛繁的細節中，沒法很好地將知識運用到實踐中。
本文旨在通過多個可運行的 benchmark 介紹常見的優化細節以及與之相關的硬件知識，為讀者建立一個簡單、有效的硬件心智模型。
一、Cache
首先要介紹的就是緩存 cache 。我們先來看一個引自 CSAPP 的經典例子：
pub fn row_major_traversal(arr: &mut Vec<Vec<usize>>) {
let n = arr.len();
for i in 0..n {
assert!(arr[i].len() == n);
for j in 0..n {
arr[i][j] += j;
}
}
}
pub fn column_major_traversal(arr: &mut Vec<Vec<usize>>) {
let n = arr.len();
for i in 0..n {
assert!(arr[i].len() == n);
for j in 0..n {
arr[j][i] += j;
}
}
}在上面兩個例子中，分別按行、按列迭代同樣大小的二維數組。
我們對這兩個函數進行 benchmark：
在上圖中，縱軸是平均耗時，橫軸是數組大小（如：2000.0 表示數組大小為：2000 x 2000）。我們看到按行迭代數組比按列迭代的效率高約 10 倍。
在現代的存儲架構中，cpu 和主存之間是 cache 。cpu 中的寄存器、高速緩存、內存三者的數據讀寫速度越來越慢。
而當 cpu 讀取一個數據的時候，會先嘗試從 cache 中讀取。如果發生 cache miss 的時候，才會將數據從主存中加載到 cache 中再讀取。而值得注意的是，cpu 每一次的讀取都是以 cache line 為單位的。也就是說，cpu 在讀取一個數據的時候，也會將該數據相鄰的、一個 cache line 內的數據也加載到 cache 中。而二維數組在內存中是按行排布的，換句話說，數組中相鄰的兩行是首尾相連排列的。所以在讀取 arr[i] 的時候，arr[i + 1] 、arr[i + 2] 等相鄰的數組元素也會被加載到 cache 中，而當下一次迭代中，需要讀取數組元素 arr[i + 1] 時，就能直接從 cache 中取出，速度非常快。而因為以列讀取數組時，arr[i][j] 和 arr[i + 1][j] 在內存中的位置就不再是緊密相連，而是相距一個數組行大小。這也導致了在讀取 arr[i][j] 時，arr[i + 1][j] 并沒有被加載到 cache 中。在下一次迭代時就會發生 cache miss 也就導致讀取速度大幅下降。
1.prefetcher
如果我們不再是按某種順序，而是隨機地遍歷數組，結果又會如何呢？
pub fn row_major_traversal(arr: &mut Vec<Vec<usize>>) {
let n = arr.len();
for i in 0..n {
assert!(arr[i].len() == n);
let ri: usize = rand::random();
std::intrinsics::black_box(ri);
for j in 0..n {
arr[i][j] += j;
}
}
}
pub fn column_major_traversal(arr: &mut Vec<Vec<usize>>) {
let n = arr.len();
for i in 0..n {
assert!(arr[i].len() == n);
let ri: usize = rand::random();
std::intrinsics::black_box(ri);
for j in 0..n {
arr[j][i] += j;
}
}
}
pub fn random_access(arr: &mut Vec<Vec<usize>>) {
let n = arr.len();
for i in 0..n {
assert!(arr[i].len() == n);
for j in 0..n {
let ri: usize = rand::random();
arr[j][ri % n] += j;
}
}
}理論上來說，隨機遍歷和按列遍歷都會導致頻繁地 cache miss ，所以兩者的效率應該是相近的。接下來，我們進行 benchmark：
可以看到，random_access 比 column_major 的效率還要低了 2 倍。原因是，在 cache 和 cpu 間還有 prefetcher
我們可以參考維基百科上的資料：
Cache prefetching can be accomplished either by hardware or by software.
- Hardware based prefetching is typically accomplished by having a dedicated hardware mechanism in the processor that watches the stream of instructions or data being requested by the executing program, recognizes the next few elements that the program might need based on this stream and prefetches into the processor's cache.
- Software based prefetching is typically accomplished by having the compiler analyze the code and insert additional "prefetch" instructions in the program during compilation itself.
而 random_access 會讓 prefetching 的機制失效，使得運行效率進一步下降。
2.cache associativity
如果我們按照不同的步長迭代一個數組會怎么樣呢？
pub fn iter_with_step(arr: &mut Vec<usize>, step: usize) {
let n = arr.len();
let mut i = 0;
for _ in 0..1000000 {
unsafe { arr.get_unchecked_mut(i).add_assign(1); }
i = (i + step) % n;
}
}steps 為：
let steps = [
1,
2,
4,
7, 8, 9,
15, 16, 17,
31, 32, 33,
61, 64, 67,
125, 128, 131,
253, 256, 259,
509, 512, 515,
1019, 1024, 1031
];我們進行測試：
可以看見當 step 為 2 的冪次時，都會有一個運行時間的突起，一個性能的毛刺。這是為什么呢？要回答這個問題，我們需要溫習一些計組知識。
cache 的大小是要遠小于主存的。這就意味著我們需要通過某種方式將主存的不同位置映射到緩存中。一般來說，共有 3 種不同的映射方式。
(1) 全相聯映射
全相聯映射允許主存中的行可以映射到緩存中的任意一行。這種映射方式靈活性很高，但會使得緩存的查找速度下降。
(2) 直接映射
直接映射則規定主存中的某一行只能映射到緩存中的特定行。這種映射方式查找速度高，但靈活性很低，會經常導致緩存沖突，從而導致頻繁 cache miss 。
(3) 組相聯映射
組相聯映射則嘗試吸收前兩者的優點，將緩存中的緩存行分組，主存中某一行只能映射到特定的一組，在組內則采取全相聯的映射方式。如果一組之內有 n 個緩存行，我們就稱這種映射方式為 n 路組相聯（n-way set associative）。
回到真實的 cpu 中，如：AMD Ryzen 7 4700u 。
我們可以看到，L1 cache 大小為 4 x 32 KB (128KB) ，采取 8 路組相聯，緩存行大小為 64 bytes 。也就是說，該緩存共有 4x32x1024 byte/64 byte = 2048 行，共分為 2048/8 = 256 組。也就是說，當迭代數組的步長為 時，數據更可能會被分到同一個組內，導致 cache miss 更加頻繁，從而導致效率下降。
（注：我的 cpu 是 intel i7-10750H ，算得的 L1 cache 的組數為 384 ，并不能很好地用理論解釋。）
3.false share
我們再來觀察一組 benchmark 。
use std::sync::atomic::{AtomicUsize, Ordering};
use std::thread;
fn increase(v: &AtomicUsize) {
for _ in 0..10000 {
v.fetch_add(1, Ordering::Relaxed);
}
}
pub fn share() {
let v = AtomicUsize::new(0);
thread::scope(|s| {
let ta = s.spawn(|| increase(&v));
let tb = s.spawn(|| increase(&v));
let tc = s.spawn(|| increase(&v));
let td = s.spawn(|| increase(&v));
ta.join().unwrap();
tb.join().unwrap();
tc.join().unwrap();
td.join().unwrap();
});
}
pub fn false_share() {
let a = AtomicUsize::new(0);
let b = AtomicUsize::new(0);
let c = AtomicUsize::new(0);
let d = AtomicUsize::new(0);
thread::scope(|s| {
let ta = s.spawn(|| increase(&a));
let tb = s.spawn(|| increase(&b));
let tc = s.spawn(|| increase(&c));
let td = s.spawn(|| increase(&d));
ta.join().unwrap();
tb.join().unwrap();
tc.join().unwrap();
td.join().unwrap();
});
}在 share 函數中，四個線程同時競爭原子變量 v 。而在 false_share 函數中，四個線程分別操作不同的原子變量，理論上線程之間不會產生數據競爭，所以 false_share 的執行效率應該比 share 要高。但 benchmark 的結果卻出乎意料：
可以看到 false_share 比 share 的執行效率還要低。
在前文中提到，cpu 在讀取數據時，是以一個 cache line 大小為單位將數據從主存中加載到 cache 中的。在前文中提到，筆者機器的 cache line 大小為：64 bytes 。而 false_share 函數中，四個原子變量在棧中的排布可能是：
a, b, c, d 四個原子變量在同一個 cache line 中，也就是說實際上四個線程實際上還是發生了競爭，產生了 false share 的現象。
那要如何解決這個問題呢？我們可以采用 #[repr(align(64))] （在不同的編程語言中又不同的寫法），告知編譯器將原子變量的內存地址以一個 cache line 大小對齊，從而避免四個原子變量位于同一個 cache line 中。
fn increase_2(v: &AlignAtomicUsize) {
for _ in 0..10000 {
v.v.fetch_add(1, Ordering::Relaxed);
}
}
#[repr(align(64))]
struct AlignAtomicUsize {
v: AtomicUsize,
}
impl AlignAtomicUsize {
pub fn new(val: usize) -> Self {
Self { v: AtomicUsize::new(val) }
}
}
pub fn non_share() {
let a = AlignAtomicUsize::new(0);
let b = AlignAtomicUsize::new(0);
let c = AlignAtomicUsize::new(0);
let d = AlignAtomicUsize::new(0);
thread::scope(|s| {
let ta = s.spawn(|| increase_2(&a));
let tb = s.spawn(|| increase_2(&b));
let tc = s.spawn(|| increase_2(&c));
let td = s.spawn(|| increase_2(&d));
ta.join().unwrap();
tb.join().unwrap();
tc.join().unwrap();
td.join().unwrap();
});
}我們再次進行 benchmark，這一次 benchmark 的結果就符合我們的預測了：
可以看見 non_share 相比前兩者，提升了近乎兩倍的效率。
二、pipeline
我們再看一個 benchmark：
pub trait Get {
fn get(&self) -> i32;
}
struct Foo { /* ... */ }
struct Bar { /* ... */ }
impl Get for Foo { /* ... */ }
impl Get for Bar { /* ... */ }
let mut arr: Vec<Box<dyn Get>> = vec![];
for _ in 0..10000 {
arr.push(Box::new(Foo::new()));
}
for _ in 0..10000 {
arr.push(Box::new(Bar::new()));
}
// 此時數組中元素的排列時有序的
arr.iter().filter(|v| v.get() > 0).count()
// 將數組打亂
arr.shuffle(&mut rand::thread_rng());
// 再次測試
arr.iter().filter(|v| v.get() > 0).count()測試結果為：
可以看見，sorted 和 unsorted 之間效率差約 2.67 倍。這是因為頻繁的分支預測失敗導致的。
在CPU 中，每一條指令的執行都會分為多個步驟，而現代計算機架構中存在一個結構 pipeline 可以同時執行處于不同執行階段的指令。
而 pipeline 要高效地工作，需要在執行指令 A 時就將接下來要執行的指令 B, C, D 等提前讀入。在一般的代碼中，pipeline 可以有效地工作，但遇到分支的時候，我們就遇到難題了：
如圖，pipeline 應該讀入 Code A 還是 Code B 呢？在執行分支語句前，誰也不知道，CPU 也是。如果我們還想要 pipeline 高效工作的話，我們就只剩下一條路：猜。只要猜得足夠準，我們的效率就能夠接近沒有分支的情況。“猜”這一步也有一個專業名詞——**流水線冒險**。而現代計算機在編譯器配合以及一些算法的幫助下，某些分支（如下圖所示）的預測成功率可以高達 99% 。
分支預測失敗的代價是要付出代價的。首先，我們要清除 pipeline 中的指令，因為它們不是接下來要執行的指令。其次，我們要將接下來要執行的指令一一加載進 pipeline 。最后，指令經過多個步驟被執行。
在測試代碼中，我們打亂數組后，就會導致分支預測頻繁失敗，最終導致了執行效率的下降。
三、數據依賴
我們再來看一段代碼：
pub fn dependent(a: &mut Vec<i32>, b: &mut Vec<i32>, c: &Vec<i32>) {
assert!(a.len() == 100000);
assert!(b.len() == 100000);
assert!(c.len() == 100000);
for i in 0..=99998 {
a[i] += b[i];
b[i + 1] += c[i];
}
a[9999] += b[9999];
}
pub fn independent(a: &mut Vec<i32>, b: &mut Vec<i32>, c: &Vec<i32>) {
assert!(a.len() == 100000);
assert!(b.len() == 100000);
assert!(c.len() == 100000);
a[0] += b[0];
for i in 0..=99998 {
b[i + 1] += c[i];
a[i + 1] += b[i + 1];
}
}在這段代碼中，我們通過兩種不同的方式迭代數組，并最終達成一致的效果。我們畫出，數據流圖如下圖：
在上圖中，我們用箭頭表示依賴關系（a[0] -> b[0] 表示 a[0] 的結果依賴于 b[0] ），用黑色箭頭表示在循環外進行的操作，用不同的顏色，表示不同迭代中的操作。我們可以看到，在 dependent 中，不同顏色的箭頭會出現在同一個數據流中，如：（a[1]->b[1]->c[0] 中就出現了紅色和藍色箭頭），這就意味著第 n + 1 次迭代會依賴于第 n 次迭代的結果，而 independent 中則沒有這種情況。
這會產生什么影響呢？我們來進行測試：
可以看到，出現了近 3 倍的效率差距。這有兩方面原因。
一是數據依賴會導致 pipeline 效率以及 cpu 指令級并行的效率變低。
二是這種迭代之間的依賴會阻止編譯器的向量化優化。我們觀察等價的 cpp 代碼（rust 1.71 的優化能力并不足以將 independet 向量化，我略感悲傷）。
#include <vector>
using i32 = int;
template<typename T>
using Vec = std::vector<T>;
void dependent(Vec<i32> &a, Vec<i32> &b, Vec<i32> &c) {
for (int i = 0; i < 9999; i++) {
a[i] += b[i];
b[i + 1] += c[i];
}
a[9999] += b[9999];
}
void independent(Vec<i32> &a, Vec<i32> &b, Vec<i32> &c) {
a[0] += b[0];
for (int i = 0; i < 9999; i++) {
b[i + 1] += c[i];
a[i + 1] += b[i + 1];
}
}查看匯編：
dependent(...):
mov rax, rdx
mov rdx, QWORD PTR [rsi]
mov rcx, QWORD PTR [rdi]
mov rdi, QWORD PTR [rax]
xor eax, eax
.L2:
mov esi, DWORD PTR [rdx+rax]
add DWORD PTR [rcx+rax], esi
mov esi, DWORD PTR [rdi+rax]
add DWORD PTR [rdx+4+rax], esi
add rax, 4
cmp rax, 39996
jne .L2
mov eax, DWORD PTR [rdx+39996]
add DWORD PTR [rcx+39996], eax
ret
independent(...):
mov rax, QWORD PTR [rdi]
mov rcx, rdx
mov rdx, QWORD PTR [rsi]
lea rdi, [rax+4]
mov esi, DWORD PTR [rdx]
add DWORD PTR [rax], esi
lea r8, [rdx+4]
mov rsi, QWORD PTR [rcx]
lea rcx, [rdx+20]
cmp rdi, rcx
lea rdi, [rax+20]
setnb cl
cmp r8, rdi
setnb dil
or ecx, edi
mov rdi, rdx
sub rdi, rsi
cmp rdi, 8
seta dil
test cl, dil
je .L9
mov rcx, rax
sub rcx, rsi
cmp rcx, 8
jbe .L9
mov ecx, 4
.L7:
movdqu xmm0, XMMWORD PTR [rsi-4+rcx]
movdqu xmm2, XMMWORD PTR [rdx+rcx]
paddd xmm0, xmm2
movups XMMWORD PTR [rdx+rcx], xmm0
movdqu xmm3, XMMWORD PTR [rax+rcx]
paddd xmm0, xmm3
movups XMMWORD PTR [rax+rcx], xmm0
add rcx, 16
cmp rcx, 39988
jne .L7
movq xmm0, QWORD PTR [rsi+39984]
movq xmm1, QWORD PTR [rdx+39988]
paddd xmm0, xmm1
movq QWORD PTR [rdx+39988], xmm0
movq xmm1, QWORD PTR [rax+39988]
paddd xmm1, xmm0
movq QWORD PTR [rax+39988], xmm1
mov ecx, DWORD PTR [rdx+39996]
add ecx, DWORD PTR [rsi+39992]
mov DWORD PTR [rdx+39996], ecx
add DWORD PTR [rax+39996], ecx
ret
.L9:
mov ecx, 4
.L6:
mov edi, DWORD PTR [rdx+rcx]
add edi, DWORD PTR [rsi-4+rcx]
mov DWORD PTR [rdx+rcx], edi
add DWORD PTR [rax+rcx], edi
add rcx, 4
cmp rcx, 40000
jne .L6
retAI助手可以看到，independent 函數被成功向量化。
