Tag: c

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)」這邊提到了，LLVM 將 libc++ 的 std::sort 從 Quicksort 換成 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)」這串討論，就如同標題所寫的，拿 pytest 測 C 的程式：「Running C unit tests with pytest」。

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

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

兩個 unsigned int 取平均值的方法

在 Hacker News Daily 上看到 Raymond Chen 在講怎麼對兩個 unsigned int 取平均值的方法：「On finding the average of two unsigned integers without overflow」，這篇裡面提到了不少有趣的歷史，另外 Hacker News 上的討論「Finding the average of two unsigned integers without overflow (microsoft.com)」也可以翻翻。

最直覺的解法會有 overflow 的問題：

unsigned average(unsigned a, unsigned b)
{
    return (a + b) / 2;
}

如果已知 a 與 b 的大小的話 (如同作者說的，蠻多時候都符合這個情況)，可以用這個方法避免 integer overflow：

unsigned average(unsigned low, unsigned high)
{
    return low + (high - low) / 2;
}

另外還有個方法是有專利的 (「Calculating the average of two integer numbers rounded towards zero in a single instruction cycle」)，雖然在 2016 年到期了，各除以二相加後，只有 a 與 b 都是奇數的情況下需要補 1：

unsigned average(unsigned a, unsigned b)
{
    return (a / 2) + (b / 2) + (a & b & 1);
}

接下來的這個方法用 AND 與 XOR 搞事，其中的原理可以解釋成，相同的 bit 不動表示值不需要動，不同的 bit 表示降一位 (除以 2)：

unsigned average(unsigned a, unsigned b)
{
    return (a & b) + (a ^ b) / 2;
}

最後是暴力解，用個比較大的 data type 搞定他：

unsigned average(unsigned a, unsigned b)
{
    // Suppose "unsigned" is a 32-bit type and
    // "unsigned long long" is a 64-bit type.
    return ((unsigned long long)a + b) / 2;
}

後面有很多 assembly 的妖魔鬼怪跑出來就不提了 XDDD

電子紙的螢幕 BOOX Mira Series

看到「BOOX Mira Series」這個，主要是因為現在公司的老闆是電子墨水的發明人之一 (也是 E Ink 的 cofounder)，所以看到一些電子墨水的新聞也會覺得有趣...

比較小的 BOOX Mira 是 13.3" 的 4:3 螢幕，但 resolution 也已經拉到 2200x1650 了，207 ppi，走 Mini HDMI 或是 Type C 輸入，賣 US$799，從圖片上看起來像是攜帶性的。

而比較大的 BOOX Mira Pro 則是 25.3" 的 16:9 螢幕 (3200x1800)，145 ppi，可以走 HDMI/Mini HDMI/DP 或是 Type C，價錢則是 US$1799，從圖片上看起來是放在桌面上的。

因為電子紙的特性，畫面的更新速度不像傳統螢幕那樣，要想一下使用的情境...

QOI 圖片無損壓縮演算法

在 Hacker News Daily 上看到「Lossless Image Compression in O(n) Time」這篇，作者丟出了一個圖片的無損壓縮演算法，壓縮與解壓縮的速度超快，但壓縮率又不輸 PNG 太多，在 Hacker News 上的討論也可以看一下：「QOI: Lossless Image Compression in O(n) Time (phoboslab.org)」。

裡面有提到在遊戲產業常用到的 stb_image.h：

Yes, stb_image saved us all from the pains of dealing with libpng and is therefore used in countless games and apps. A while ago I aimed to do the same for video with pl_mpeg, with some success.

作者的簡介也可以看到他的主業也在遊戲這塊：

My name is Dominic Szablewski. I build games, experiment with JavaScript and occasionally tinker with low-level C.

圖片的無損壓縮與解壓縮算是遊戲創作者蠻常用到的功能，所以他想要看看這塊有沒有機會有更好的工具，於是他就用了四個很簡單的演算法幹完了 QOI (然後發現效果很讚)：

  • A run of the previous pixel
  • An index into a previously seen pixel
  • The difference to the previous pixel
  • Full rgba values

其實從 Hacker News 的討論也可以看到這組演算法也常被拿出來在現代的壓縮演算法使用，所以雖然作者自稱不是 compression guy，但他用的演算法其實蠻專業的...

然後挑 single thread 主要是可以避免 threading 的複雜度以及 overhead，在「QOI Benchmark Results」這頁可以看到，無論是什麼類型的檔案，壓縮與解壓縮的速度都相當漂亮，而且壓縮率又沒有差 libpng 太多。

而且作者自己有提到，還沒用到 SIMD 指令集加速，這樣猜測應該還有不少空間...

StackOverflow 開賣 Ctrl、C、V 的鍵盤

StackOverflow 今年愚人節的鍵盤真的開賣了：「No joke—you can buy our copy/paste keyboard right now」。

愚人節的文章在「Introducing The Key」，這次開賣的網站是跟 Drop 合作：「Stack Overflow The Key Macropad | Mechanical Keyboards | Mini Mechanical Keyboards | Drop」，可以看到是機械鍵盤，但要 US$29 一隻...

鍵盤是凱華 BOX 黑軸：

They’re also outfitted with Kailh Box Black switches to deliver an ultra-smooth linear feel.

然後可程式化定義 XDDD

Fully programmable, these three keys can do much more than copy and paste. In fact, you can configure them to perform virtually any key command you want.

不過想要的人也得注意一下，目前看到的 ship date 是年底了：

Estimated ship date is Dec 13, 2021 PT.

然後目前已經賣出 2.6k 件了？XDDD

2.6k Sold

USB Type-C 要增加 240W 的規格...

在「USB Type-C Specification 2.1 allows up to 240W Extended Power Range (EPR)」這邊看到這個規格：

Extended Power Range cables have additional requirements to assure that these cables can deliver the full defined voltage and current range for USB PD EPR operation. EPR cables shall functionally support a reported 50 V and 5 A o peration. The minimum functional voltage that a cable shall support is 53.65 V. The electrical components potentially in the path of V BUS in an EPR cable, e.g. bypass capacitors, should be minimally rated for 63 V.

All EPR cables shall be Electronically Marked and include EPR-specific information in the eMarker as defined by the USB PD specification. As defined in the USB PD specification, EPR cables are marked as 50 V and 5 A capable. All EPR cables shall be visibly identified with EPR cable identification icons as defined by the USB-IF. This is required so that end users will be able to confirm visually that the cable supports up to as high of PDP = 240W as defined in the USB PD specification.

也是基於 E-Marker 晶片的關係，除了充電頭支援外，線本身也得支援。這解決了目前很多家桌機都自己搞 >100W 的 dock 來支援高瓦數的充電，推出一個標準來涵蓋收斂...

會不會搞到以後連桌機都可以用 USB-C 界面供電啊...

Google Groups 把 comp.lang.c 給禁了...

Hacker News Daily 上看到的，Google Groups 把 comp.lang.c 給禁了，連到 https://groups.google.com/g/comp.lang.c 可以看到無法使用的訊息：

警告：內容已遭禁止
comp.lang.c 已被認定為包含垃圾內容、惡意軟體或其他惡意內容。

如要進一步瞭解 Google 網路論壇的內容政策，請參閱這篇關於濫用本服務的說明中心文章，以及我們的《服務條款》。

這樣連歷史資料都看不到了...