從簡單的 C 語言函式來看現代 Compiler 使用 SIMD 的威力

兩個禮拜前在 Hacker News Daily 上看到這篇很精彩的問題與分析,裡面展現出了現代 compiler 最佳化的能力,大量使用了 SIMD 來衝效能:「Why does this code execute more slowly after strength-reducing multiplications? (stackoverflow.com)」,原文在 Stack Overflow 上:「Why does this code execute more slowly after strength-reducing multiplications to loop-carried additions?」。

這篇會很長,除了本來 Stack Overflow 上的討論以外,我另外自己測 GCC 9.4.0 不加上 -O、加上 -O-O3,發現這次 Stack Overflow 給的範例剛剛好把這幾個常見的最佳化等級都練出不同結果,算是蠻厲害的題目。

作者一開始是寫了一個很簡單的版本 A,會透過 loop (對 i 進行) 計算 A*i^2 + B*i + C 的值,把結果放到 array 裡面:

double data[LEN];

void compute()
{
    const double A = 1.1, B = 2.2, C = 3.3;

    int i;
    for(i=0; i<LEN; i++) {
        data[i] = A*i*i + B*i + C;
    }
}

透過一些紙本公式計算可以知道,每次遞增的值雖然不是固定值,但也是有規律的:

所以可以改寫成一堆加號的版本 B:

void compute()
{
    const double A = 1.1, B = 2.2, C = 3.3;
    const double A2 = A+A;
    double Z = A+B;
    double Y = C;

    int i;
    for(i=0; i<LEN; i++) {
        data[i] = Y;
        Y += Z;
        Z += A2;
    }
}

理想上版本 A 在 loop 內用到三個乘法與兩個加法,而版本 B 只用到了三個加法,預期版本 B 應該會快不少,但實際上跑出來的結果剛好反過來:版本 B 慢了許多。

作者實際用 objdump 拉出來看,粗粗看下來也會發現版本 A 的指令多很多:

而版本 B 的指令簡單很多:

在討論下面已經有人給出解釋,主要的原因包括了兩個。

首先是現代 CPU 靠著暴力電路解決,乘法速度跟加法其實不像以前差那麼多,可以從 Instruction tables 這邊看到 MUL 類的指令速度雖然不能跟加法相比,但其實不算慢了,反倒是 DIV 整數除法類的指令比較痛。

另外一個原因,如果仔細看作者貼的 screenshot 分析會發現,在版本 A 裡面,一個 loop 其實做了四次 i 的運算 (add rax, 0x20),而版本 B 只做了一個 i 的運算 (add rax, 0x8),這邊 compiler 幫你 unroll 最佳化改用 SIMD 處理掉了。

在 Stack Overflow 的回答裡面,有人給了一段不錯的 code 示意,提到版本 A 其實先被展成像是這樣的程式碼:

int i;
for (i = 0; i < LEN; i += 4) {
    data[i+0] = A*(i+0)*(i+0) + B*(i+0) + C;
    data[i+1] = A*(i+1)*(i+1) + B*(i+1) + C;
    data[i+2] = A*(i+2)*(i+2) + B*(i+2) + C;
    data[i+3] = A*(i+3)*(i+3) + B*(i+3) + C;
}

然後被 SIMD 包起來處理掉了。

我把作者的 code (他有貼在 GitHub Gist 上) 拿下來編,用不同的 -O-O3 測試,然後去讀 assmebly 的部份也可以看到很多有趣的東西...

首先是在 -O3 的情況下 (也就是作者使用的參數),可以看到類似的結果:(我桌機的 CPU 是定速,沒有跑動態調整)

$ repeat 10 ./a
[-] Took: 248830 ns.
[-] Took: 249150 ns.
[-] Took: 248760 ns.
[-] Took: 248730 ns.
[-] Took: 248770 ns.
[-] Took: 248861 ns.
[-] Took: 248760 ns.
[-] Took: 253050 ns.
[-] Took: 248640 ns.
[-] Took: 249211 ns.
$ repeat 10 ./b
[-] Took: 686660 ns.
[-] Took: 696090 ns.
[-] Took: 696310 ns.
[-] Took: 694431 ns.
[-] Took: 691971 ns.
[-] Took: 697690 ns.
[-] Took: 693241 ns.
[-] Took: 692900 ns.
[-] Took: 654751 ns.
[-] Took: 679101 ns.

從版本 A 的 objdump -d -S -M intel a 可以看到作者 screenshot 內也有看的 unroll 與 SSE2 指令集:

13a0:       66 0f 6f c2             movdqa xmm0,xmm2
13a4:       48 83 c0 20             add    rax,0x20
13a8:       66 0f fe d6             paddd  xmm2,xmm6
13ac:       f3 0f e6 f8             cvtdq2pd xmm7,xmm0
13b0:       66 0f 28 cf             movapd xmm1,xmm7
13b4:       66 0f 70 c0 ee          pshufd xmm0,xmm0,0xee
13b9:       66 0f 59 cd             mulpd  xmm1,xmm5
13bd:       f3 0f e6 c0             cvtdq2pd xmm0,xmm0
13c1:       66 0f 59 cf             mulpd  xmm1,xmm7
13c5:       66 0f 59 fc             mulpd  xmm7,xmm4
13c9:       66 0f 58 cf             addpd  xmm1,xmm7
13cd:       66 0f 58 cb             addpd  xmm1,xmm3
13d1:       0f 29 48 e0             movaps XMMWORD PTR [rax-0x20],xmm1
13d5:       66 0f 28 c8             movapd xmm1,xmm0
13d9:       66 0f 59 cd             mulpd  xmm1,xmm5
13dd:       66 0f 59 c8             mulpd  xmm1,xmm0
13e1:       66 0f 59 c4             mulpd  xmm0,xmm4
13e5:       66 0f 58 c1             addpd  xmm0,xmm1
13e9:       66 0f 58 c3             addpd  xmm0,xmm3
13ed:       0f 29 40 f0             movaps XMMWORD PTR [rax-0x10],xmm0
13f1:       48 39 c2                cmp    rdx,rax
13f4:       75 aa                   jne    13a0 <compute+0x40>

而版本 B 的 objdump -d -S -M intel b 也符合作者提到的現象:

1340:       f2 0f 11 08             movsd  QWORD PTR [rax],xmm1
1344:       48 83 c0 08             add    rax,0x8
1348:       f2 0f 58 c8             addsd  xmm1,xmm0
134c:       f2 0f 58 c2             addsd  xmm0,xmm2
1350:       48 39 d0                cmp    rax,rdx
1353:       75 eb                   jne    1340 <compute+0x30>

但把 gcc 改成 -O 後,可以看到版本 A 的速度慢很多,但還是稍微比版本 B 快一些:

$ repeat 10 ./a
[-] Took: 571140 ns.
[-] Took: 570280 ns.
[-] Took: 571271 ns.
[-] Took: 573971 ns.
[-] Took: 571981 ns.
[-] Took: 569650 ns.
[-] Took: 566361 ns.
[-] Took: 571600 ns.
[-] Took: 571330 ns.
[-] Took: 571030 ns.
$ repeat 10 ./b
[-] Took: 697521 ns.
[-] Took: 696961 ns.
[-] Took: 696201 ns.
[-] Took: 694921 ns.
[-] Took: 696930 ns.
[-] Took: 695001 ns.
[-] Took: 701661 ns.
[-] Took: 698100 ns.
[-] Took: 702430 ns.
[-] Took: 702641 ns.

從 objdump 可以看到版本 A 的變化,退化成一次只處理一個,但把所有的數字都用 xmmN 存放計算:

11b1:       66 0f ef c9             pxor   xmm1,xmm1
11b5:       f2 0f 2a c8             cvtsi2sd xmm1,eax
11b9:       66 0f 28 c1             movapd xmm0,xmm1
11bd:       f2 0f 59 c4             mulsd  xmm0,xmm4
11c1:       f2 0f 59 c1             mulsd  xmm0,xmm1
11c5:       f2 0f 59 cb             mulsd  xmm1,xmm3
11c9:       f2 0f 58 c1             addsd  xmm0,xmm1
11cd:       f2 0f 58 c2             addsd  xmm0,xmm2
11d1:       f2 0f 11 04 c2          movsd  QWORD PTR [rdx+rax*8],xmm0
11d6:       48 83 c0 01             add    rax,0x1
11da:       48 3d 40 42 0f 00       cmp    rax,0xf4240
11e0:       75 cf                   jne    11b1 <compute+0x28>

而版本 B 在 -O 的情況下基本上是一樣的東西 (所以速度上差不多):

11b3:       f2 0f 11 08             movsd  QWORD PTR [rax],xmm1
11b7:       f2 0f 58 c8             addsd  xmm1,xmm0
11bb:       f2 0f 58 c2             addsd  xmm0,xmm2
11bf:       48 83 c0 08             add    rax,0x8
11c3:       48 39 d0                cmp    rax,rdx
11c6:       75 eb                   jne    11b3 <compute+0x2a>

再來是拔掉 -O,都不加就會超慢:

$ repeat 10 ./a
[-] Took: 1097091 ns.
[-] Took: 1092941 ns.
[-] Took: 1092501 ns.
[-] Took: 1091991 ns.
[-] Took: 1092441 ns.
[-] Took: 1093970 ns.
[-] Took: 1091341 ns.
[-] Took: 1093931 ns.
[-] Took: 1094111 ns.
[-] Took: 1092231 ns.
$ repeat 10 ./b
[-] Took: 2703282 ns.
[-] Took: 2705933 ns.
[-] Took: 2703582 ns.
[-] Took: 2702622 ns.
[-] Took: 2703043 ns.
[-] Took: 2702262 ns.
[-] Took: 2703352 ns.
[-] Took: 2703532 ns.
[-] Took: 2703112 ns.
[-] Took: 2702533 ns.

看 objdump 就可以發現幾乎都是對記憶體操作,沒有放到 register 裡面,這是版本 A:

11c1:       f2 0f 2a 45 e4          cvtsi2sd xmm0,DWORD PTR [rbp-0x1c]
11c6:       66 0f 28 c8             movapd xmm1,xmm0
11ca:       f2 0f 59 4d e8          mulsd  xmm1,QWORD PTR [rbp-0x18]
11cf:       f2 0f 2a 45 e4          cvtsi2sd xmm0,DWORD PTR [rbp-0x1c]
11d4:       f2 0f 59 c8             mulsd  xmm1,xmm0
11d8:       f2 0f 2a 45 e4          cvtsi2sd xmm0,DWORD PTR [rbp-0x1c]
11dd:       f2 0f 59 45 f0          mulsd  xmm0,QWORD PTR [rbp-0x10]
11e2:       f2 0f 58 c1             addsd  xmm0,xmm1
11e6:       f2 0f 58 45 f8          addsd  xmm0,QWORD PTR [rbp-0x8]
11eb:       8b 45 e4                mov    eax,DWORD PTR [rbp-0x1c]
11ee:       48 98                   cdqe   
11f0:       48 8d 14 c5 00 00 00    lea    rdx,[rax*8+0x0]
11f7:       00 
11f8:       48 8d 05 41 2e 00 00    lea    rax,[rip+0x2e41]
11ff:       f2 0f 11 04 02          movsd  QWORD PTR [rdx+rax*1],xmm0
1204:       83 45 e4 01             add    DWORD PTR [rbp-0x1c],0x1
1208:       81 7d e4 3f 42 0f 00    cmp    DWORD PTR [rbp-0x1c],0xf423f
120f:       7e b0                   jle    11c1 <compute+0x38>

這是版本 B:

11e8:       8b 45 cc                mov    eax,DWORD PTR [rbp-0x34]
11eb:       48 98                   cdqe   
11ed:       48 8d 14 c5 00 00 00    lea    rdx,[rax*8+0x0]
11f4:       00 
11f5:       48 8d 05 44 2e 00 00    lea    rax,[rip+0x2e44]
11fc:       f2 0f 10 45 d8          movsd  xmm0,QWORD PTR [rbp-0x28]
1201:       f2 0f 11 04 02          movsd  QWORD PTR [rdx+rax*1],xmm0
1206:       f2 0f 10 45 d8          movsd  xmm0,QWORD PTR [rbp-0x28]
120b:       f2 0f 58 45 d0          addsd  xmm0,QWORD PTR [rbp-0x30]
1210:       f2 0f 11 45 d8          movsd  QWORD PTR [rbp-0x28],xmm0
1215:       f2 0f 10 45 d0          movsd  xmm0,QWORD PTR [rbp-0x30]
121a:       f2 0f 58 45 f8          addsd  xmm0,QWORD PTR [rbp-0x8]
121f:       f2 0f 11 45 d0          movsd  QWORD PTR [rbp-0x30],xmm0
1224:       83 45 cc 01             add    DWORD PTR [rbp-0x34],0x1
1228:       81 7d cc 3f 42 0f 00    cmp    DWORD PTR [rbp-0x34],0xf423f
122f:       7e b7                   jle    11e8 <compute+0x5f>

寫到這邊差不多了,作者拿的這個範例算是很有趣的例子,尤其是現代 compiler 幫我們做了超多事情後,很多自己以為的 optimization 其實未必比較好,還是要有個 profiling review 才準...

Python 3.11 (目前還是 beta) 的效能大幅進步

Hacker News 上看到「Python 3.11 Performance Benchmarks Are Looking Fantastic」這篇,提到目前還在 beta 的 Python 3.11 效能已經比 Python 3.10 有大幅進步了:

Python 3.11 is 10~60% faster than Python 3.10 according to the official figures and a 1.22x speed-up with their standard benchmark suite.

HN 上對應的討論在「Python 3.11 Performance Benchmarks Are Looking Fantastic (phoronix.com)」。

從比較簡單的 PyBench 到 Python 官方的 pyperformance 都有大幅進步。

像是 PyBench:

然後 pyperformance 的部份挑個我自己用到比較多的,Django 相關的東西:

整體分數跑幾何平均的話會是:

When taking the geometric mean of all the Python benchmarks I carried out for this article on the AMD Ryzen 9 5950X, Python 3.11 Beta was about 41% faster overall than the current Python 3.10.4 stable release or 45% over the aging Python 3.8 series.

在官方文件上「Faster CPython」這邊有提到做了哪些事情,可以看到大家分頭去改善超多東西,累積起來就很驚人...

公平會對創業家兄弟與松果公司的 SEO 誘導轉向開罰

好像很少提到國內的新聞,但這則應該是這兩天蠻熱門的一個新聞,創業家兄弟與松果公司 (也是創業家兄弟公司) 被公平會開罰:「操作SEO搜尋關鍵字誤導消費者 創業家兄弟、松果公司挨罰」,相關的備份先留起來:Internet Archivearchive.today

公平會官方的新聞稿則可以在「利用程式設計引誘消費者「逛錯街」,公平會開罰」這邊看到,對應的網頁備份:Internet Archivearchive.today

用的是公平交易法第 25 條:

公平會於4月12日第1594次委員會議通過,創業家兄弟股份有限公司及松果購物股份有限公司利用「搜尋引擎優化 (Search Engine Optimization,簡稱SEO)」技術,並在搜尋引擎的顯示結果上不當顯示特定品牌名稱,使消費者誤認該賣場有販售特定品牌產品,藉以增進自身網站到訪率,違反公平交易法第25條規定,處創業家兄弟公司200萬元、松果公司80萬元罰鍰。

這條的條文可以從「公平交易法§25-全國法規資料庫」這邊看到:

除本法另有規定者外,事業亦不得為其他足以影響交易秩序之欺罔或顯失公平之行為。

主要的原因是點進去後卻沒有該項商品:

公平會發現,消費者在Google搜尋引擎打上特定品牌名稱,例如「悅夢床墊」時,搜尋結果會出現「悅夢床墊的熱銷搜尋結果│生活市集」、「人氣熱銷悅夢床墊口碑推薦品牌整理─松果購物」等搜尋結果,消費者被前述搜尋結果吸引點選進入「生活市集」、「松果購物」網站後,卻發現該賣場並無「悅夢床墊」之產品,此係生活市集及松果購物之經營者創業家兄弟公司及松果公司分別利用SEO技術所產生的現象。

而且會透過使用者在往站上搜尋的關鍵字產生對應的頁面:

公平會進一步調查後發現,創業家兄弟公司及松果公司對其所經營之「生活市集」及「松果購物」網頁進行設計,只要網路使用者在該2網站搜尋過「悅夢床墊」,縱然該2網站賣場並沒有賣「悅夢床墊」,其網站程式也會主動生成行銷文案網頁,以供搜尋引擎攫取。若有消費者之後在Google搜尋引擎查詢「悅夢床墊」時,搜尋結果便會帶出「悅夢床墊的熱銷搜尋結果│生活市集」、「人氣熱銷悅夢床墊口碑推薦品牌整理─松果購物」等搜尋結果項目,經消費者點選後即會導向「生活市集」、「松果購物」之網站。

然後判罰的部份:

公平會過往即曾就事業使用競爭對手事業名稱作為關鍵字廣告,並在關鍵字廣告併列競爭對手事業名稱之行為,認定違反公平交易法第25條規定。本案雖非創業家兄弟公司及松果公司直接使用「悅夢床墊」等他人商品品牌作為關鍵字廣告,但最終呈現之結果,本質上都是「誘導/轉向」(bait-and-switch)的欺罔行為,除了打斷消費者正常的商品搜尋與購買過程,也對其他販售該等品牌商品之經營者形成不公平競爭的效果。若任由發生而不予規範,未來將可能導致其他競爭者之競相仿效,消費者將更難以分辨搜尋結果呈現資訊之真偽,進而威脅電商市場之競爭秩序及消費者利益。故公平會認為違反公平交易法第25條「足以影響交易秩序之欺罔及顯失公平行為」,並分別處創業家兄弟公司200萬元、松果公司80萬元罰鍰。

所以這算是對 Dark pattern SEO 的部份開罰...

KataGo 最近的進展

KataGo 是目前 open source 裡最強的計算引擎了,不過先前的缺點就是得透過 OpenCL 或是 CUDA 才能跑,所以基本上得有張夠力的顯示卡才行。

如果要想要在 CPU 上跑 (不透過硬體顯示卡),一種方式是透過 OpenCL 的方式模擬,在 Linux 下可以透過 pocl 達成,效能就普普通通,但算是會動的東西,不過 Windows 下好像不太好弄... 這也是先前蠻多人還是繼續使用 Leela Zero 的原因。

最近 KataGo 在 1.5 版實做了純 CPU 版本的程式碼,是透過 Eigen 這套 library 達成的,不過大家測過以後發現慢到爆炸 XDDD

因為作者沒有提供 CPU 版本的 binary,我自己在 Linux 下抓程式碼 compile 後測試發現只會用一個 CPU (沒有 multi threading),對比於在 1080Ti 上跑 OpenCL 版本大約 150 visits/sec (40b),但 CPU 版本是 0.0x visits/sec 啊 XDDD

作者自己在 GitHub 上討論時也有提到這個版本只有確認正確性,完全沒有考慮效能...

不過就有其他人跳出來改善了,在「Optimization of Eigen backend #288」這邊可以看到 kaorahi 拋出了不少修改,可以看到從一開始的 eigen_naive_loop (對比 1.5 版有 13x 的成長) 一路到 borrow_tensorflow (1400x) 的版本,使得在 CPU 上面跑 15b 也有 10 visits/sec 了:

"borrow_tensorflow" version: x1400 speed up from 1.5.0 (70% of libtensorflow backend). Now 15b net is usable for me. I get 19 visits/s in benchmark and 10 visits/s in GUI with 15b net.

這樣看起來已經快了不少,這樣子 Leela Zero 應該會逐漸淡出了,CPU-only 算是最後一塊 Leela Zero 還可以爭的地盤...

Runtime 期間的最佳化工具:Dynimize

忘記在哪邊看到「Reduce MySQL CPU Usage Through Dynamic Binary Optimization」這篇文章了,裡面其實是在描述自家產品 Dynimize 的威猛。

翻了一些資料可以發現這個產品出來一陣子了,在 2018 的時候曾經在 Percona Live 上發表過:「Accelerating MySQL with JIT Compilers」,可以看出來有點像是 PGO (Profile-guided optimization) 的行為,只是他可以直接對 binary 處理。

定價的部份會是這類產品的重點,如果價錢比加硬體貴的話就沒那麼好用了... 在 Dynimize Pricing 這邊可以看到是 per CPU 的價錢,$0.00139/hr、$1/month 或是一次性的 $24,以效能提昇的程度來看,如果在 database 這邊是 CPU bound,是個頗值得投資的項目。

Microbrowser 的影響力

在「Microbrowsers are Everywhere」這篇文章裡提到在討論 Microbrowser 的影響力。這邊講的 Microbrowser 是指在各種平台上面貼連結時產生的預覽資訊,像是 IM 裡面連結的預覽資訊 (左邊的圖):

這些預覽通常都不會執行 JavaScript,所以不會觸動頁面裡追蹤的服務,而一般的業主就會低估這個管道。但透過這個方式觸及到使用者的量以及影響力,作者覺得有可能比 Googlebot 還大:

3. Microbrowser are probably more important than google bot

算是另外一個領域的 optimization,畢竟不同的平台預覽的效果都不同...

AWS Cloud 的用法

Hacker News Daily 上看到這則,分享了 AWS (他的前東家,超過八年) 的使用經驗:

除了可以在 Twitter 上看以外,也可以用 Thread reader 直接讀整條 thread,應該也還算清楚:「This is how I use the good parts of @awscloud, while filtering out all the distracting hype.」。

這邊的經驗談主要是在 web 與 app 相關的服務這塊:

有講到 AWS 的業務其實圍繞在 scalability 上發展,但這對 startup 可能反而是扣分,因為暴力法解反而可以大幅簡化架構換得 agile (而讓 startup 存活下來)。

另外從團隊的開發成本來看,這些 scale 的技術增加了開發成本,產生了很多開發上的限制,這些觀點也有點帶到「Premature optimization is the root of all evil」在講的事情:

最後的結論可以看到一些列表:

除了 DynamoDB 的意見不同外 (這邊提到的 DDB),其他的我都可以接受...

Googlebot 會用新版的 Chrome 跑 JavaScript 了

Googlebot 先前一直都是用 Chrome 41 版的引擎在跑,如果要考慮 SEO (for JavaScript),就得確認網站在 Chrome 41 上面可以執行 (於是 ES6 就...)。

今天從 John ResigTwitter 上看到 Googlebot 更新了引擎:「The new evergreen Googlebot」。

這樣針對 JS 的 SEO 省了不少事情...

V8 version 6.5 (Chrome 65) 的改變

V8 version 6.5 將會有不少改變:「V8 release v6.5」。

其中因為 Spectre 的關係,新的 V8 設計了 Untrusted code mode,拿來跑不信任的程式,裡面會設計反制措施。而且這在新版的 Chrome 將會預設開啟:

In response to the latest speculative side-channel attack called Spectre, V8 introduced an untrusted code mode. If you embed V8, consider leveraging this mode in case your application processes user-generated, not-trustworthy code. Please note that the mode is enabled by default, including in Chrome.

另外是針對 WebAssembly 提供邊下載邊 compile 的能力,這讓速度大幅提昇。在原文是拿一個比較大包的 WebAssembly 來測試:

For the graph below we measure the time it takes to download and compile a WebAssembly module with 67 MB and about 190,000 functions. We do the measurements with 25 Mbit/sec, 50 Mbit/sec, and 100 Mbit/sec download speed.

可以看到網路不夠快的使用者就會直接被 compile 速度跟上,讓瀏覽器在下載時就做一些事情。

另外在某些情況下對 Array 的操作會有大幅改善:

這些新功能與改善都會在 Chrome 65 推出。依照「Chrome Platform Status」這邊的資料,stable 版預定在三月初,beta 版應該是要出了... (雖然上面寫著 2/1,但目前好像還沒更新)

Amazon Aurora (MySQL) 推出的 Asynchronous Key Prefetch

Amazon Aurora (MySQL) 推出新的效能改善,可以改善 JOIN 時的效能:「Amazon Aurora (MySQL) Speeds Join Queries by More than 10x with Asynchronous Key Prefetch」。

看起來像是某個情況的 optimization,將可能的 random access 換成 sequential access 而得到大量的效能:

This feature applies to queries that require use of the Batched Key Access (BKA) join algorithm and Multi-Range Read (MRR) optimization, and improves performance when the underlying data set is not in the main memory buffer pool or query cache.

其實記憶體還是最好用的加速器,能加大硬拼就先硬拼... XD