calloc() 與 malloc() 的差異

前陣子在 Hacker News Daily 上看到的,原文是 2016 的文章:「Why does calloc exist?」,裡面講的東西包括了 implementation dependent 的項目,所以要注意一下他的結論未必適用於所有的平台與情境。

malloc()calloc() 的用法是這樣,其中 calloc() 會申請 countsize 的空間:

void* buffer1 = malloc(size);
void* buffer2 = calloc(count, size);

第一個差異是,count * size 可能會 overflow (而 integer overflow 在 C 裡面是 undefined behavior),這點除非你在乘法時有檢查,不然大多數的行為都還是會生一個值出來。

calloc() 則是會幫你檢查,如果會發生 overflow 的時候就不會真的去要一塊記憶體用。

第二個差異是 calloc() 保證會將內容都設定為 0,這點在 POSIX 的標準裡面是這樣寫的:

The calloc() function shall allocate unused space for an array of nelem elements each of whose size in bytes is elsize. The space shall be initialized to all bits 0.

但作者就發現 malloc() + memset() + free() 還是比 calloc() + free() 慢很多:

~$ gcc calloc-1GiB-demo.c -o calloc-1GiB-demo
~$ ./calloc-1GiB-demo
calloc+free 1 GiB: 3.44 ms
malloc+memset+free 1 GiB: 365.00 ms

研究發現是 calloc() 用了 copy-on-write 的技巧,先把所有的 page 都指到同一塊完全被塞 0 的記憶體,只有在真的寫到該段記憶體時,系統才會要一塊空間來用:

Instead, it fakes it, using virtual memory: it takes a single 4 KiB page of memory that is already full of zeros (which it keeps around for just this purpose), and maps 1 GiB / 4 KiB = 262144 copy-on-write copies of it into our process's address space. So the first time we actually write to each of those 262144 pages, then at that point the kernel has to go and find a real page of RAM, write zeros to it, and then quickly swap it in place of the "virtual" page that was there before. But this happens lazily, on a page-by-page basis.

但畢竟這是 implementation dependent,看看有個印象就好。

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。

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

歐盟 2024 年年底強制使用 USB-C 充電頭 (終於,iPhone...)

Hacker News Daily 上看到「EU Passes Law to Switch iPhone to USB-C by End of 2024」,裡面指到了歐盟的新聞稿:「Long-awaited common charger for mobile devices will be a reality in 2024」。

2024 年年底 (所以是 2025 年) 將強制手機與平板都使用 USB-C 充電頭,2026 年則是延伸涵蓋到筆電:

By the end of 2024, all mobile phones, tablets and cameras sold in the EU will have to be equipped with a USB Type-C charging port. From spring 2026, the obligation will extend to laptops.

終於定案公告了,之前傳言好久了...

月份傳回值 0 表示一月的考古

Hacker News 上看到「History of Zero-Based Months? (jefftk.com)」這篇,在考古為什麼常常看到 function 在傳回「月份」時是以 0 表示一月。從這篇提到的「Why is day of the month 1-indexed but the month is 0-indexed in C? (twitter.com/hillelogram)」則是 2020 年的討論。

在討論裡面有提到 hillelogram 的 tweet,裡面有個看起來算合理的考古過程...

試著用 Thread Reader 產生單頁 (讀起來會比較好讀),但不知道為什麼一直失敗,結果往 Internet Archive 翻資料,倒是有 2020 年當初生成出來的版本

另外還是列出原來第一則 tweet:

作者在研究這個題目的時候,馬上可以想到的是 C 語言裡面的月份就是 0-indexed,而其他程式語言都很有可能會是因為 C 語言的關係一路把這個特性繼承下去:

直接跳到最後面作者的猜測,他覺得可能是為了讓後續使用起來更方便的關係。

其他的欄位大多都是透過類似 sprintf("%d") 的方式直接輸出數字,所以用 1-indexed 讓人直接讀,而月份則會透過 array 來轉字串,所以用 0-indexes 讓程式轉:

So that's my best guess: the programmers were working with constrained resources and could optimize `asctime` tricky pointer arithmetic on the month and day-of-week, so made them 0-indexed. Day-of-month is just for displaying to the user, so is 1-indexed.

沒辦法確定,但就是一種猜測,看起來還蠻... 合理... 的?

Decompile to C 的工具

昨天在 Hacker News 上看到「Decompiler Explorer (dogbolt.org)」這篇,裡面列出了很多 Decompile to C 的工具 (就不用直接硬看 assembly),包括了 open source 與商用軟體:

網站本身則是提供界面可以交叉比較,不過各家的結果看起來還是有侷限...

從簡單的 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 才準...

Golang 的排序演算法將換成 pdqsort,LLVM libc++ 換成 BlockQuicksort

Hacker News 首頁上看到的消息,Golang 將會把 sort.Sort() 換成 pdqsort (Pattern-defeating Quicksort):「Go will use pdqsort in next release (github.com/golang)」,對應的 commit 則是在「sort: use pdqsort」這邊可以看到。

然後另外是「Changing std:sort at Google’s scale and beyond (danlark.org)」這邊提到了,LLVMlibc++std::sortQuicksort 換成 BlockQuicksort。另外在文章裡面有提到一段 Knuth 老大在 TAOCP 裡講 sorting algorithm 沒有霸主的情況:

It would be nice if only one or two of the sorting methods would dominate all of the others, regardless of application or the computer being used. But in fact, each method has its own peculiar virtues. […] Thus we find that nearly all of the algorithms deserve to be remembered, since there are some applications in which they turn out to be best.

先回到 pdqsort 的部份,pdqsort 作者的 GitHub 上 (orlp/pdqsort) 可以看到他對 pdqsort 的說明:

Pattern-defeating quicksort (pdqsort) is a novel sorting algorithm that combines the fast average case of randomized quicksort with the fast worst case of heapsort, while achieving linear time on inputs with certain patterns.

看名字也可以知道 pdqsort 是從 Quicksort 改良的版本,而依照 Golang 的 commit 上的測試,與 Quicksort 相比,少數情況下會慢一點點,大多數的情況下會快一些,而在特殊情境下會讓 worst case 下降。

Golang 選擇把 unstable 的 Quicksort 換成 pdqsort,LLVM 則是選擇把 Quicksort 換成 BlockQuicksort,這邊看起來有些分歧...

反倒是各個程式語言對於 stable 的 Mergesort 陸陸續續都換成了 Timsort,看起來比較像是有個共識...

從三角函數 cosine 的實做問題學一些週邊知識...

前幾天在 Hacker News 上看到「Implementing Cosine in C from Scratch (2020) (austinhenley.com)」這篇 2020 的文章,原文是「Implementing cosine in C from scratch」,裡面內在講自己刻三角函數的 cosine 所遇到的一些嘗試。

cosine 是很基本的函數,所以可以使用的地方很多。另外一方面,也因為他不是那麼直覺就可以實做出來,在現代的實做裡面其實藏了超多細節...

不過真的有趣的是在翻 Hacker News 上的討論時陸陸續續翻其他的資料看到的知識。

第一個看到的是 Intel 對於 FPU-based 指令集內的 FSIN 因為 π 的精度不夠而導致誤差超大 (尤其是在 0 點附近的時候):「Intel Underestimates Error Bounds by 1.3 quintillion」,然後 AMD 是「相容」到底,所以一樣慘:「Accuracy of FSIN and other x87 trigonometric instructions on AMD processors」。

這個就是有印象,但是太久沒有提到就會忘記...

第二個是 musl libc 裡的 cosine 實做 (看註解應該是從 FreeBSD 的 libc 移植過來的?):「__cos.c\math\src」與「cos.c\math\src」(話說 cgit 在 html 內 title 的內容對路徑的表達方式頗有趣,居然是反過來放...)。

拆開的部份是先將範圍限制在 [-\pi/4, \pi/4] 後 (這個部份看起來是透過 __rem_pio2.c 處理),再丟進公式實際運算。

另外帶出來第三個知識,查資料的時候翻到 binary64 (這也是 C 語言裡面的 double) 與 binary128 的差異:

而大家很常拿來惡搞的 double double 則是利用兩個 double 存放,形式是 v = head + tail,利用不同的 exponent 表示來不同部份的值,以提高經度:

A common software technique to implement nearly quadruple precision using pairs of double-precision values is sometimes called double-double arithmetic.

不過這樣的精確度只能到 106 bits,雖然跟 binary128 能達到的 113 bits 相比低了一些,但在大多數的情況下也還算夠用:

Using pairs of IEEE double-precision values with 53-bit significands, double-double arithmetic provides operations on numbers with significands of at least[4] 2 × 53 = 106 bits (...), only slightly less precise than the 113-bit significand of IEEE binary128 quadruple precision.

C 語言的兩個笑話 (以及他的惡搞原理)

Twitter 上看到兩則 C 語言的笑話:

第一個的 "-0.5"char[],補了 + 1 會往後一格,所以會變成移到 "0.5" 的部份。

所以如果改成 -0.6,你會發現輸出變成 0.6

第二個的 50 ** "2" 則是利用了 2 的 ascii code 是 0x32,換成十進制剛好是 50,然後中間的 ** 其實是一個乘號與一個 pointer 的用法,實際上剛好會是 50*50=2500 的運算。

如果你改成 "3" 的話會輸出 2550

作者在 Twitter 的後續有提到,這些都是特別挑過的數字所造成的「巧合」,你換掉這些數字的話通常會爛掉
(除非你也很精心挑過),不要誤解亂用 XDDD

拿 pytest 測 C 的程式

Hacker News 上看到「Running C unit tests with Pytest (p403n1x87.github.io)」這串討論,就如同標題所寫的,拿 pytestC 的程式:「Running C unit tests with pytest」。

拿既有還蠻成熟的 testing framework 來用,而且看他的範例裡,C 的部份只要 symbol 有 expose (non-static) 就可以測,看起來不需要用到 Python 特殊的資料結構...

之後如果有機會也可以用看看...