Tag: quicksort

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 了... 不過看起來沒有什麼深入的討論？

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