Tag: sorting

Intel 用 AVX-512 加速 NumPy 的排序演算法被整合進主線了

Intel 用 AVX-512 加速 NumPy 排序的實做被整合進主線了：「「Intel Publishes Blazing Fast AVX-512 Sorting Library, Numpy Switching To It For 10~17x Faster Sorts」」。

GitHub 的 PR 在「ENH: Vectorize quicksort for 16-bit and 64-bit dtype using AVX512 #22315」這邊，可以看到相關的留言：

This patch adds AVX512 based 64-bit on AVX512-SKX and 16-bit sorting on AVX512-ICL. All the AVX512 sorting code has been reformatted as a separate header files and put in a separate folder. The AVX512 64-bit sorting is nearly 10x faster and AVX512 16-bit sorting is nearly 16x faster when compared to std::sort. Still working on running NumPy benchmarks to get exact benchmark numbers

16-bit int sped up by 17x and float64 by nearly 10x for random arrays. Benchmarked on a 11th Gen Tigerlake i7-1165G7.

有點「有趣」的情況是，AVX-512 在新的 Intel 消費級 CPU 被拔掉了，只有伺服器工作站的 CPU 有保留。而 AMD 的 Zen 4 則是跳下去支援 AVX-512...

另外在「Intel Publishes Fast AVX-512 Sorting Library, 10~17x Faster Sorts in NumPy (phoronix.com)」這邊當然也有人提到，如果用更廣泛的 AVX2 (寬度是 256bits) 加速的話應該也會有很大的進步才對？幾乎這十年的 CPU 都有 AVX2 了... 不過看起來沒有什麼深入的討論？

PostgreSQL 15 釋出

PostgreSQL 15 出了：「PostgreSQL 15 Released!。

先前提到過「PostgreSQL 15 將可以對透過 UNIQUE 限制 NULL 的唯一性了」，反而沒排上這次 release 的重點，翻了一下的確是排不太上 XD

第一個超大的改善是 sorting：

In this latest release, PostgreSQL improves on its in-memory and on-disk sorting algorithms, with benchmarks showing speedups of 25% - 400% based on which data types are sorted.

在「Speeding up sort performance in Postgres 15」這邊有提到四個改動，裡面很詳細的說明了改動的內容，以及 benchmark 差異。

如果以他列出來的四個進展，應該是第二個「Reduce memory consumption by using generation memory context」這個會最容易遇到，也改善最多：

另外是第三個「Add specialized sort routines for common datatypes」也會有一些：

再來是拿 PostgreSQL 當 OLAP engine 用的時候會發生的第四個「Replace polyphase merge algorithm with k-way merge」：

最開頭第一個「Improvements sorting a single column」的 SELECT col1 FROM tab ORDER BY col1; 這種 case 好像用的很少，限制 SELECT 的部份也只能出現後面 sorting 的 column，但如果遇到的話效能提昇很多：

除了 sorting 的改善以外，另外一個是 WAL 支援 LZ4 與 zstd，這對於有寫入量很大的環境應該會有幫助：

PostgreSQL 15 adds support for LZ4 and Zstandard (zstd) compression to write-ahead log (WAL) files, which can have both space and performance benefits for certain workloads.

正式版出來後，應該會有一些整體性的 benchmark 數字可以看，再來等著看...

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

JavaScript 的 sort 變成 stable

看到「Stable Array.prototype.sort」這篇在講 JavaScript 規格書裡的 sort...

本來 JavaScript 的規格書裡，各種 sort 都沒有保證 stable，而在「[Normative] Make Array.prototype.sort stable #1340」與「[Normative] Make %TypedArray%.prototype.sort stable #1433」這兩個地方則有了變化，提案在規格裡加入 stable 的要求，可以減少開發者因為不知道 unstable 而造成的問題...

Firefox 則是很久前就決定使用 Merge sort 了 (看了一下，當時還在從 Firebird 轉換名稱到 Firefox 的時期)：「Array.sort isn't a stable sort (switch to MergeSort)」。

另外這篇也剛好提到了 V8 使用 Timsort 當作 stable sorting algorithm，之前就有看到但發現沒在 blog 上提過...

Timsort 是 1993 年發明出來的演算法，與 Merge sort 的情況類似，除了 stable 外，還可以保證最差的情境下的時間複雜度是 O(n*log(n))：

Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.

這個演算法的重點是善用已經排好的子序列，藉此降低記憶體操作次數而提昇效能，符合真實環境裡常見到的資料：

The algorithm finds subsequences of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently.

除了 V8 採用這個演算法以外，其他常見的包括了 Python 與 Android 上的 Java SE：

Timsort has been Python's standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7, on the Android platform, in GNU Octave, and Google Chrome.