Tag: programming

前陣子 Hacker News 很慢的一些背景知識

看到 Ask HN: Is Hacker News slow for anyone else? 這邊的討論，dang (Hacker News 的管理員) 在 35157344 這邊就有出來說明：

All: our poor server is smoking today* so I've had to reduce the page size of comments. There are 1500+ comments in this thread but if you want to read more than a few dozen you'll need to page through them by clicking the More link at the bottom. I apologize!

Also, if you're cool with read-only access, just log out (edit: or use an incognito tab) and all will be fast again.

* yes, HN still runs on one core, at least the part that serves logged-in requests, and yes this will all get better someday...it kills me that this isn't done yet but one day you will all see

另外比較特別的是，Hacker News 是用 Arc (Lisp) 寫的，不過看起來沒有考慮到 optimization，加上那天 Reddit 也掛了，的確帶動 Hacker News 這邊更新的頻率比較高...

Ruby 再引入另外一套 JIT 實做：RJIT

在 Hacker News Daily 上看到「RJIT #7448」這個，Ruby 上一套新的 JIT 實做。

這次的 RJIT 取代掉先前的 MJIT：

This PR replaces the current implementation of MJIT with a new JIT called "RJIT"

有些特點，其中一個是 RJIT 在 buildtime 與 runtime 都不需要 compiler，這是因為 RJIT 直接用 Ruby 實做：

RJIT uses a pure-Ruby assembler to generate native code

  • MJIT requires a C compiler at runtime. YJIT requires a Rust compiler at build time. RJIT doesn't require them.
  • This means that RJIT's warmup could be slower than YJIT, but it's still much faster than MJIT's.

另外值得注意的是，RJIT 的作者 k0kubun 跟 YJIT 的作者 Maxime Chevalier-Boisvert 都是 Shopify 的員工，可以看出 Shopify 對於 Ruby 效能的痛？決定直接自己養人改善效能。

回到 RJIT 這邊跑的測試，可以看到他是用 YJIT 的測試套件測，這也就不會太奇怪了。

跟這次取代掉的 MJIT 相比，RJIT 在 Headline 這包測試都 OK，在 Other 這包則是有來有回，而在 Micro 這包則是有不少項目輸掉 (相比於前兩者)：

這樣整體看起來算是有進步，下一版 Ruby 更新應該就會有了。

Ruby 3.2.0 把 YJIT 列為穩定功能了

去年有寫過 Ruby 的 YJIT 帶來的效能提昇：「YJIT 帶給 Ruby 大量的效能提昇」。

在這次的 Ruby 3.2.0 發布就把 YJIT 列為穩定功能了：「Ruby 3.2.0」。

  • YJIT is no longer experimental
    • Has been tested on production workloads for over a year and proven to be quite stable.

另外就是支援的平台，看起來是多了 arm64 這邊的支援，所以馬上列表就多了一堆新機器：

  • YJIT now supports both x86-64 and arm64/aarch64 CPUs on Linux, MacOS, BSD and other UNIX platforms.
    • This release brings support for Apple M1/M2, AWS Graviton, Raspberry Pi 4 and more.

另外是每個程式語言幾乎都會遇到的 regexp 類的問題，這次 Ruby 3.2.0 利用 Memoization 的方式降低某些 regexp 的消耗：

# This match takes 10 sec. in Ruby 3.1, and 0.003 sec. in Ruby 3.2
/^a*b?a*$/ =~ "a" * 50000 + "x"

而另外一組 regexp 也可以看出類似的效果：

用一些記憶體空間換取效能，降低被 DoS 的一些機會。另外一方面，引入了 regexp timeout 的 workaround，緩解真的被打的時候的資源消耗上限：

The optimization above cannot be applied to some kind of regular expressions, such as those including advanced features (e.g., back-references or look-around), or with a huge fixed number of repetitions. As a fallback measure, a timeout feature for Regexp matches is also introduced.

C 語言裡面的 ??! 符號

在 Hacker News Daily 上看到這個奇怪的知識：「What does the ??!??! operator do in C? (stackoverflow.com)」，原文在 Stack Overflow 上：「What does the ??!??! operator do in C?」。

這是 trigraph，在 C89 就有了，從 Rationale for International Standard—Programming Languages—C 這邊的 5.2.1.1 可以看到 trigraph 的歷史原因：

Trigraph sequences were introduced in C89 as alternate spellings of some characters to allow the implementation of C in character sets which do not provide a sufficient number of non-alphabetic graphics

而且是強制要求實做：

Implementations are required to support these alternate spellings, even if the character set in use is ASCII, in order to allow transportation of code from systems which must use the trigraphs. AMD1 also added digraphs (see §6.4.6 and §MSE.4).

其中遇到的問題就是當年得決定 C 可以用的 charset，得考慮到很多不同機器 charset 相容性的問題：

The C89 Committee faced a serious problem in trying to define a character set for C. Not all of the character sets in general use have the right number of characters, nor do they support the graphical symbols that C users expect to see. For instance, many character sets for languages other than English resemble ASCII except that codes used for graphic characters in ASCII are instead used for alphabetic characters or diacritical marks. C relies upon a richer set of graphic characters than most other programming languages, so the representation of programs in character sets other than ASCII is a greater problem than for most other programming languages.

然後就使用了 ISO/IEC 646 這個標準 (要記得 Unicode 1.0.0 是 1991 年才出現)：

The solution is an internationally agreed-upon repertoire in terms of which an international representation of C can be defined. ISO has defined such a standard, ISO/IEC 646, which describes an invariant subset of ASCII.

The characters in the ASCII repertoire used by C and absent from the ISO/IEC 646 invariant repertoire are:

[ ] { } \ | ~ ^

後面就是定義 ?? 當作 escape digraph。

算是一個歷史產物，現在不太需要用到了...

用 GPT-3 解讀程式碼

在 Hacker News 上看到的方法，Simon Willison 試著把程式碼餵進 GPT-3，然後問 GPT-3 程式碼的意思，看起來答的還不錯：「Using GPT-3 to explain how code works」，對應的討論 (包括 Simon Willison 的回應) 則可以在「Using GPT-3 to explain how code works (simonwillison.net)」這邊看到。

第一個範例裡面可以解讀 regular expression，雖然裡面對 (?xm) 的解讀是錯的，但我會說已經很強了...

第二個範例在解釋 Shadow DOM，看起來也解釋的很不錯...

第三個範例回來原來產生程式碼的例子，拿來生 SQL 指令。

後面的 bonus 題目居然是拿來解釋數學公式，他直接丟 TeX 文字進去要 GPT-3 解釋柯西不等式 (Cauchy–Schwarz inequality)。這樣我想到以前高微作業常常會有一堆證明題，好像可以丟進去要 GPT-3 給證明耶...

測試 Neovim + GitHub Copilot

如同之前在「GitHub Copilot 宣佈 GA」提到的，Copilot 有支援 Neovim，找了一下在 GitHub 上的 github/copilot.vim 這邊可以取得。

Copilot.vim is a Vim plugin for GitHub Copilot. For now, it requires Neovim 0.6 (for virtual lines support) and a Node.js installation.

主要有兩個 dependency 問題，第一個是 Neovim 版本要 0.6+，而在 Ubuntu 20.04 內的版本不夠新 (22.04 的看起來就夠)，可以裝 PPA 版本解決：「Neovim Stable」。

另外一個是 Node.js 版本需要到 16+ (20.04 與 22.04 內建的都不夠)，這個我是靠 nvm 解決。

先在 GitHub 網站上開通 Copilot，再照著說明，回到 Neovim 裡執行 :Copilot setup，跟著步驟跑授權流程就可以了。

接下來隨便開個 test.py 或是 test.php 檔開始寫，就會發現有 suggestion 跑出來了。

這邊拿 feedgen 測試會不會動，輸入 feed. 後就會出現灰色的 subtitle(title)：

這時候按 tab 就會展出來了。

AWS 也推出了 GitHub Copilot 的競爭對手 Amazon CodeWhisperer

AWS 推出了 Amazon CodeWhisperer，可以看做是 GitHub Copilot 的競爭產品：「Now in Preview – Amazon CodeWhisperer- ML-Powered Coding Companion」，在 Hacker News 上的討論還不多：「Copilot just got company: Amazon announced Codewhisperer (amazon.com)」。

目前還是 Preview 所以是免費的，但也還沒有提供價錢：

During the preview period, developers can use CodeWhisperer for free.

另外目前提供的程式語言只有 Python、Java 與 JavaScript：

The preview supports code written in Python, Java, and JavaScript, using VS Code, IntelliJ IDEA, PyCharm, WebStorm, and AWS Cloud9. Support for the AWS Lambda Console is in the works and should be ready very soon.

至於 training 的資料集，這邊有提到的是 open source 專案與 Amazon 自家的東西：

CodeWhisperer code generation is powered by ML models trained on various data sources, including Amazon and open-source code.

開發應該需要一段時間，不知道是剛好，還是被 GitHub Copilot 轉 GA 的事件強迫推出 Preview 版...

從簡單的 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」這邊有提到做了哪些事情，可以看到大家分頭去改善超多東西，累積起來就很驚人...