用 C++ 測試記憶體延遲

本文內容採用創用 CC 姓名標示-非商業性-相同方式分享 3.0 台灣 授權條款授權.

---

許多的 benchmark 工具 (e.g., geekbench v4, aida64) 都具有測量記憶體延遲的功能，有些甚至還能測試快取的延遲。 於是我就很好奇，到底這些工具是怎麼定義記憶體延遲的呢？ 進一步說，有可能用簡單的 C++ 程式就重現出這些工具的測量結果嗎？

估計記憶體延遲之組合語言指令

經過了一番資料搜尋跟測試之後，我得出了結論——僅需 100 行左右的程式碼，便有辦法重現出 aida64 的記憶體延遲數據。 而這個方法，也早在下面這篇 1996 年的論文就被提出：

Jan. 96 Usenix, Larry McVoy and Carl Staelin, Larry McVoy, lmbench: Portable tools for performance analysis.

這篇論文中提到，因為 CPU superscalar 之特性，CPU 同一個時間內允許發送多個記憶體要求。 換句話說，讓指令間有相依性方能得到正確的記憶體延遲數據，而最簡單的方法就是重複下面這個指令：

1mov  r4, (r4)

把 register 4 所指到的位置讀出來，把他當作 pointer 塞回 register 4。這個用法初見有點奇怪，但事實上 C++ 中的 linked list traversal 經過編譯之後就是這個組合語言指令。

1Node *p;
2const int kCOUNT = 1000000;
3for (int i = 0; i < kCOUNT; ++i) {
4	p = p->next;
5}

接著，手動 unroll 可以減少 loop 對於執行時間的影響：

1Node *p;
2const int kCOUNT = 1000000;
3for (int i = 0; i < kCOUNT; ++i) {
4	p = p->next; p = p->next; p = p->next; p = p->next;
5	p = p->next; p = p->next; p = p->next; p = p->next;
6}

於是我們只要計算「執行時間」除以「執行 next 的總次數」就可以了，上面這個例子是 8000000 次。

創造環狀 linked list

剩下的步驟就是創造一個可以無限 traverse 的 link list，方便計算時間。自然而然我們會想到把 list 的 nodes 串成一圈（注意本文中提到的 list 都是單向的），這也是 1996 年論文的作法：

如果我們把 node 的總數控制好，就能讓所有的 node 都落在特定的記憶體層級 (e.g., DRAM or cache)，例如圖中 1 MB 的設定大約是 2020 年 x86 CPU 的 L3 cache 的大小，一個 pointer 8 bytes 的話，總共是 k_NUM_NODE=131072 個 nodes。對應到以下程式碼：

1struct Node {
2	Node *next;
3};
4for (int i = 0; i < kNUM_NODE-1; ++i) {
5	nodes[i].next = nodes+i+1;
6}
7nodes[kNUM_NODE-1].next = nodes;

在我的 Ryzen 3700X + DDR4 3200 環境下執行，跑出了 1.08 ns 的 DRAM 延遲，這跟 2020 x86 常見的 50~150 ns 的數據相去甚遠，應該是搞錯了什麼，下面我們來解決這個問題。

創造環狀 linked list version 2——考慮 cache

一個明顯的問題是因為現在的 CPU 的 cache line 很大，通常是 64 bytes，因此上面這種連續的存取方式會有 7/8 的 cache hit，根本量不准。

解決方法就是要讓 pointer 落在不同的 cache line 裡面：

只要用 union 把 Node 變成 64 bytes 就好：

1struct Node { union {
2	Node *next;
3	char padding[kCACHE_LINE];
4};};

同樣，在我的 Ryzen 3700X + DDR4 3200 環境下執行，跑出了 3.6 ns 的 DRAM 延遲，雖然慢了三倍，但是還是跟合理數字差了一個數量級，這應該還是搞錯了什麼 ，於是下面只好多寫一個章節。

創造環狀 linked list version 3——考慮 prefetch

經過仔細思考後，2020 的 CPU 相較 1996 年的 CPU 強了非常多，例如 prefetch，這是一個 CPU 會猜你要的資料，先把資料抓進來的功能 。 雖然也造成了像是 spectre/meltdown 這種完全沒人想到的漏洞。

對於 CPU 來說，這種線性存取的記憶體存取實在是太好猜了，所以我們量出來的 DRAM 速度才會比實際上快 10 倍以上。解決的方式當然就是把 node 的連接方式隨機化，稍後的結果也可以看到這的確解決了問題。

因此，我們必須建立一個隨機連結的環狀 linked list（下稱隨機環），而隨機就會讓然想到 leetcode 偶而會出現的水塘抽樣法，因此下面使用水塘抽樣來建立隨機環。當然，水塘抽樣並不是唯一的方法，只是我覺得這樣作比較看起來厲害而已。

水塘抽樣最經典的實用例子如下：

在未知確實行數的文字檔中抽取任意一行，換句話說，不可以先把整個檔案掃描以判定總行數再作抽樣。必須保每一行抽取的機率相等，即是說如果最後發現文字檔共有 N 行，則每一行被抽取的機率均為 1/N。

而解法如下：

抽取第一行為最終結果 (answer) →
抽取第二行，用 1/2 的機率替換掉 answer →
抽取第三行，用 1/3 的機率替換掉 answer → ……

套用類似精神，我們假設現在前面已經建立一個大小為 4 的隨機環，並且想把第五個 node 隨機插入，構成大小為 5 的隨機環：

接著我們隨機找出一位苦主（綠色的 cur）以及他的後面那個（藍色的 nxt），我們的第五個 node 就要插入兩者中間：

完成！

其對應之程式碼如下：

 1std::default_random_engine rng;
 2std::uniform_int_distribution<long> uid;
 3nodes[0].next = nodes;
 4for (int i = 1; i < kNUM_NODE; ++i) {
 5	Node *cur = nodes + uid(rng) % i;
 6	Node *nxt = cur->next;
 7	Node *tail = nodes + i;
 8	cur->next = tail;
 9	tail->next = nxt;
10}

順帶一提，上面這段程式碼第三行的初始狀態是這樣：

結果驗證

下方我找了多台電腦系統的組合，可以看到跟 aida64 測量結果一致。

Overall

我們的結果

AIDA64

個別作圖

AMD 2400G+DDR4 2400

AMD 3700X+DDR4 3200

AMD 4700U+LPDDR4x 4266

Intel 8700+DDR4 2666

Intel 9300H+DDR4 2400