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,看起來比較像是有個共識...

LLVM 的更換授權進展

Hacker News Daily 上看到「LLVM relicensing update & call for help」這篇,在講 LLVM 計畫從 UIUC licenseMIT license 授權轉成 Apache License 2.0 的進展,在 Hacker News 上的討論「LLVM relicensing update and call for help (llvm.org)」也可以翻一下。


文章開頭還是先花了一些篇幅解釋,這個計畫主要是要處理專利的問題,原先的 developer policy 對於專利的句子太粗糙,會授權過多的權力給 LLVM。這對於一般個人可能影響不大,但對於手上有一卡車專利的公司來說就不太願意了。

另外一個問題是 LLVM 遇到的問題,因為 runtime library 的部份是用 UIUC license + MIT license 授權,但主體是用 UIUC license 授權,這使得主體的程式碼不能隨意搬到 runtime library 裡面:

The run time libraries were dual licensed under the UIUC and MIT license; the rest of the code only under the UIUC license. Therefore, we could not easily move code to run time libraries from other parts. The reason run time libraries were dual licensed was to enable linking to run time library binaries without requiring attribution to LLVM.

因為這些目標,所以新的授權會是 Apache License 2.0 為主,裡面有設計還算合理的專利授權條件,另外大家也算熟悉,再來是針對 object code 以及 GPLv2 設計了例外條款:

As an exception, if, as a result of your compiling your source code, portions of this Software are embedded into an Object form of such source code, you may redistribute such embedded portions in such Object form without complying with the conditions of Sections 4(a), 4(b) and 4(d) of the License.

In addition, if you combine or link compiled forms of this Software with software that is licensed under the GPLv2 ("Combined Software") and if a court of competent jurisdiction determines that the patent provision (Section 3), the indemnity provision (Section 9) or other Section of the License conflicts with the conditions of the GPLv2, you may retroactively and prospectively choose to deem waived or otherwise exclude such Section(s) of the License, but only in their entirety and only with respect to the Combined Software.

在「Long tail of individuals and corporations without a relicensing agreement yet」這邊有目前還沒有同意重新授權的人以及團隊的資料,看起來不會是每個人都願意重新授權,到時候可能還得再挑出來重寫,但有些可以獨立出來的可能可以維持,畢竟 UIUC licesne 與 MIT license 都是 permissive license,只要放到另外一個目錄下,大家知道不是 Apache License 2.0 就還好...

Windows 上的 Chrome 改用 Clang 編譯

這應該是上個禮拜蠻熱鬧的一件事情 (i.e. 很多人看熱鬧 XD),就是 Google ChromeVisual C++ 改成用 Clang 編譯:「Clang is now used to build Chrome for Windows」。


We conducted extensive A/B testing of performance. Performance telemetry numbers are about the same for MSVC-built and clang-built Chrome – some metrics get better, some get worse, but all of them are within 5% of each other.

後面有猜測換過去的原因,可以看出因為 open source 加上 Google Chrome 團隊有強大的技術能力下,用 open source 軟體可以對 compiler 大量客製化各種功能,另外也是因為一個 compiler 就可以吃多個平台,可以省下一些跨平台的力氣 (像是相容性語法)。

而 Visual C++ 在商業支援與文件兩方面比較好的優勢,在這個情況下就顯得不是那麼重要了...

GCC 的警告參數

在「Useful GCC warning options not enabled by -Wall -Wextra」這邊提到 GCC 如果把這些參數放入 -Wall-Wextra 裡會產生出太多的誤判,但有些參數還是很有用。

不過這邊介紹的參數蠻多都需要 GCC 6+ 甚至 GCC 7+,翻了 Ubuntu 16.04 是 GCC 5.4。


-Wduplicated-cond -Wduplicated-branches -Wlogical-op -Wrestrict -Wnull-dereference -Wold-style-cast -Wuseless-cast -Wjump-misses-init -Wdouble-promotion -Wshadow -Wformat=2

另外一個比較特別的問題是,其實愈來愈多專案搬到 clang 上,這幾年可以看出能量的消長蠻明顯的...

Webkit 推出 B3 JIT Compiler (Bare Bones Backend)

Webkit 推出了 B3 加快 optimization 的速度,取代原來 LLVM 的工作:「Introducing the B3 JIT Compiler」。

在文章後方 Performance Results 的部份可以看到最主要的差異在啟動時間:

另外也可以看到其他各種 performance benchmark 也幾乎都是小勝 LLVM。

接下來會有 ARM64 與其他平台的計畫:

B3 is not yet complete. We still need to finish porting B3 to ARM64. B3 passes all tests, but we haven’t finished optimizing performance on ARM. Once all platforms that used the FTL switch to B3, we plan to remove LLVM support from the FTL JIT.

Android NDK 宣佈向 Clang 靠攏...

Hacker News Daily 上看到 Android NDK 宣佈向 Clang 靠過去的消息:「Changelog for NDK Build 2490520」。

Android NDK 做為效能的加速手段而使用到 C 或是 C++,所以會使用對應的 compiler suite:

The NDK is a toolset that allows you to implement parts of your app using native-code languages such as C and C++. Typically, good use cases for the NDK are CPU-intensive applications such as game engines, signal processing, and physics simulation.


PSA: Everyone should be switching to Clang.


GCC in the NDK is now deprecated.

FreeBSD 10 的改變...

Zite 上看到 FreeBSD 10 的改變:「FreeBSD 10's New Technologies and Features」。

最耀眼的當然是對 GCC 的宣戰達到高潮,第一個將預設編譯器換掉的 major release。同樣的,也把 GNU 的 libstdc++ 換成 MIT license 實作的 libc++。

再來是 ISCBIND 被換掉,改用 Unbound 以及 LDNS

然後 UFS 檔案系統可以透過 growfs(8) 線上長大... XDDD

其他的改善包括了 iSCSI stack 重寫,PF 防火牆可以善用 SMP 資源,以及 ZFS 的更新。等正式出版後應該還是會等到 10.1 再上 production 吧?感覺 compiler 一換不知道會有多少雷啊 XD

NaCl (Native Client) 總算要支援 ARM 了...

OSnews 上看到 NaCl 要支援 ARM 了,在這之前的版本都只能跑在 x86 family 上面:「Native client now supports ARM」。

另外在 The Chromium Blog 上也提到這件事情:「Native Client support on ARM」。

下一個預定要完成的計畫是 Portable Native Client (PNaCl),希望用 LLVM 一統江湖... XD

FreeBSD 預設的 compiler 從 GCC 換成 clang

FreeBSD 預設的 compiler (/usr/bin/cc/usr/bin/c++/usr/bin/cpp) 從 GCC 4.2.1 換成 clang 了:「Revision 242624」。

目前只有 CURRENT 裡的 amd64 與 i386 版本換過去,如此一來,FreeBSD 10.0 會是第一個使用 clang 作為預設編輯器的正式版本 (看起來不像會 back port 回 FreeBSD 9)。接下來是 Ports 大混戰了,應該會有一卡車的 ports 用 USE_GCC=yes 來解?

從 2009 年的努力到現在三年多了 (參考「[ANNOUNCE]: clang/llvm can compile booting FreeBSD kernel on i386/amd64」這封公告信),離拔掉 GCC 4.2.1 又進了一大步...

FreeBSD 將在 10.0 時將預設編譯器從 GCC 換成 clang

FreeBSD 預定在今年十一月將 amd64 與 i386 版本的 C 與 C++ 預設編譯器從 GCC 4.2.1 換成 clang,也就是下一個 major release (10.0) 就會是預設編譯器:「Clang as default compiler November 4th」。

自從 GCC 決定要換成 GPLv3 後整個計畫才活起來,到現在走了三年,看起來明年應該有機會看到預設是使用 clang 的 FreeBSD?

接下來的工作是解決 Ports 裡面一堆用 clang 編不過的軟體,以目前「Ports and Clang」這邊列出來的數量,看起來把幾個大的傢伙解決掉就差不多了?(不過應該是不怎麼好解,不然這種大目標物應該早就解決了...)