Tag: sort

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

檔案壓縮順序造成壓縮率的差異

Hacker News Daily 上看到「Why are tar.xz files 15x smaller when using Python's tar library compared to macOS tar?」這篇，作者問了為什麼他用 Python 的 tarfile 壓出來比起用 tar 壓出來小了 15 倍，檔案都是 JSON 檔壓成 XZ 格式：

I'm compressing ~1.3 GB folders each filled with 1440 JSON files and find that there's a 15-fold difference between using the tar command on macOS or Raspbian 10 (Buster) and using Python's built-in tarfile library.

看到 1440 個檔案應該會有直覺是一分鐘一個檔案，跑一天的量...

隔天他把原因找出來了，在裝了 GNU Tar 並且加上 --sort='name' 參數後，壓出來的大小就跟 Python 的 tarfile 差不多了：

Ok, I think I found the issue: BSD tar and GNU tar without any sort options put the files in the archive in an undefined order.

After installing GNU tar on my Mac with:

brew install gnu-tar

And then tarring the same folder, but with the --sort option:

gtar --sort='name' -cJf zsh-archive-sorted.tar.xz /Users/user/Desktop/temp/tar/2021-03-11

I get a .tar.xz archive of 1.5 MB, equal to the archive created by the Python library.

底層的原因是檔名與檔案內容有正相關的相似度 (因為裡面都是 sensor 資料)，依照檔名排序壓縮就等於把類似的 JSON 檔案放在一起壓，使得 xz 可以利用這點急遽拉高壓縮率：

My JSON files contain measurements from hundreds of sensors. Every minute I read out all sensors, but only a few of these sensors have a different value from minute to minute.

By sorting the files by name (which has the creation unixtime at the beginning of it), two subsequent files have very little different characters between them. Apparently this is very favourable for the compression efficiency.

遇到類似的情境可以當作 tuning 的一種，測試看看會不會變小很多...

第四堂：「Data Wrangling」

有陣子沒寫了，來還個債...

這個系列是從『MIT 的「The Missing Semester of Your CS Education」』這邊延伸出來的，這邊講的是「Data Wrangling」這篇。

這篇是在講 pipe 的用法，在講這些工具之前，其實有個很重要的概念應該要說明 (但沒有在這篇文章裡被提到)，也就是 Unix philosophy，這個哲學是指 unix 環境下的工具，都會設計成只做好一件事情。

而要怎麼把這些工具串起來，最常見的就是 pipe，你可以在文章裡看到 grep、sed 與 sort 這些工具的用法，以及怎麼用 pipe 串起來。

這邊剛好也可以提一下，利用 pipe 可以把不同功能打散到不同的 process 上，剛好也可以稍微利用到現在常見的多 CPU 的環境。

另外上面因為提到了 grep，文章內花了不少篇幅在講 Regular expression 這個在 CS 課程裡面也是重要的基礎。

會放這種篇幅長度，一方面是 Regular expression 的實用性很高，另外一方面，學術上與自動機理論中的 DFA 與 NFA 都有關，算是學習計算理論的起點：

然後後面就有提到 AWK 這個工具，這邊要注意的是，雖然可以用 Perl 之類的工具作到類似的事情 (而且更強大)，但 AWK 有被放到 POSIX 標準裡，所以在各種作業系統內幾乎都一定會出現，加上語法算是簡單，學起來還是很有幫助...

然後再最後面的段落冒出一個 gnuplot 畫個圖，以及示範 xargs 這種神器要怎麼用 (這邊會更建議看一下 manpage，可以配合 find 之類的工具用，並且平行化同時處理)。

然後最後示範了 binary data 怎麼處理。

Amazon Redshift 會自動在背景重新排序資料以增加效能

Amazon Redshift 的新功能，會自動在背景重新排序資料以增加效能：「Amazon Redshift introduces Automatic Table Sort, an automated alternative to Vacuum Sort」。

版本要到更新到 1.0.11118，然後預設就會打開：

This feature is available in Redshift 1.0.11118 and later.

Automatic table sort is now enabled by default on Redshift tables where a sort key is specified.

重新排序的運算會在背景處理，另外帶一些行為學習分析：

Redshift runs the sorting in the background and re-organizes the data in tables to maintain sort order and provide optimal performance. This operation does not interrupt query processing and reduces the compute resources required by operating only on frequently accessed blocks of data. It prioritizes which blocks of table to sort by analyzing query patterns using machine learning.

算是丟著讓他跑就好的東西，升級上去後可以看一下 CloudWatch 的報告，這邊沒有特別講應該是還好... XD

引用自己論文的問題...

Nature 上點出來期刊論文裡自我引用的問題 (這邊的自我引用包括了合作過的人)：「Hundreds of extreme self-citing scientists revealed in new database」。

開頭舉了一個極端的例子，Vaidyanathan 的自我引用比率高達 94%，而學界的中位數是 12.7%，感覺是有某種制度造成的行為？

Vaidyanathan, a computer scientist at the Vel Tech R&D Institute of Technology, a privately run institute, is an extreme example: he has received 94% of his citations from himself or his co-authors up to 2017, according to a study in PLoS Biology this month. He is not alone. The data set, which lists around 100,000 researchers, shows that at least 250 scientists have amassed more than 50% of their citations from themselves or their co-authors, while the median self-citation rate is 12.7%.

會想要提是因為想到當年 Google 的經典演算法 PageRank，就是在處理這個問題... 把 paper 換成 webpage 而已。

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.

對於按讚數排名的方法

前幾天看到一篇 2009 年的老文章，在討論使用者透過「喜歡」以及「不喜歡」投票後，要怎麼排名的方法：「How Not To Sort By Average Rating」。

基本的概念是當使用者投票數愈多時就會愈準確，透過統計方法可以算一個信賴區間，再用區間的下限來排... 但沒想到公式「看起來」這麼複雜 XDDD

Score = Lower bound of Wilson score confidence interval for a Bernoulli parameter

但實際的運算其實沒那麼複雜，像是 Ruby 的程式碼可以看出大多都是系統內的運算就可以算出來。其中的 z 在大多數的情況下是常數。

require 'statistics2'

def ci_lower_bound(pos, n, confidence)
    if n == 0
        return 0
    end
    z = Statistics2.pnormaldist(1-(1-confidence)/2)
    phat = 1.0*pos/n
    (phat + z*z/(2*n) - z * Math.sqrt((phat*(1-phat)+z*z/(4*n))/n))/(1+z*z/n)
end

The z-score in this function never changes, so if you don't have a statistics package handy or if performance is an issue you can always hard-code a value here for z. (Use 1.96 for a confidence level of 0.95.)

作者後來在 2012 年與 2016 年也分別給了 SQL 以及 Excel 的範例程式碼出來，裡面 hard-code 了 95% 信賴區間的部份：

SELECT widget_id, ((positive + 1.9208) / (positive + negative) - 
                   1.96 * SQRT((positive * negative) / (positive + negative) + 0.9604) / 
                          (positive + negative)) / (1 + 3.8416 / (positive + negative)) 
       AS ci_lower_bound FROM widgets WHERE positive + negative > 0 
       ORDER BY ci_lower_bound DESC;
=IFERROR((([@[Up Votes]] + 1.9208) / ([@[Up Votes]] + [@[Down Votes]]) - 1.96 * 
    SQRT(([@[Up Votes]] *  [@[Down Votes]]) / ([@[Up Votes]] +  [@[Down Votes]]) + 0.9604) / 
    ([@[Up Votes]] +  [@[Down Votes]])) / (1 + 3.8416 / ([@[Up Votes]] +  [@[Down Votes]])),0)

而更多的說明在維基百科的「Binomial proportion confidence interval」可以翻到，裡面也有其他的方法可以用。

Go 1.6 把 HTTP/2 變成預設支援的功能

在 Go 的官方公告「Go 1.6 is released」提到了把 net/http 的 HTTP/2 預設啟用了：

In Go 1.6, support for HTTP/2 is enabled by default for both servers and clients when using HTTPS, bringing the benefits of the new protocol to a wide range of Go projects, such as the popular Caddy web server.

另外值得一提的是 sort 演算法的效能改善：

The algorithm inside sort.Sort was improved to run about 10% faster, but the change may break programs that expect a specific ordering of equal but distinguishable elements.

這應該算還蠻基本常用到的東西，會改善很多程式效能...