圖片無損壓縮下的演算法比較

Hacker News 上看到「What’s the best lossless image format? Comparing PNG, WebP, AVIF, and JPEG XL」這篇,在講圖片的無損壓縮演算法。在 Hacker News 上的討論也可以看看:「What’s the best lossless image format? (siipo.la)」。

文章有點舊 (2021 年七月),但應該還行... 另外作者看起來是以 service bandwidth 考量為主,在這種情境下,自然圖片一般都會以非無損的方式提供 (像是 JPEG),而人造圖片則是以無損的方式提供 (像是 PNG),所以在這邊討論無損的時候會以人造圖片的 dataset 來挑選,於是作者是跑去 Dribbble 上翻圖片當 dataset:

What I ended up with was downloading a set of images from Dribbble, a portfolio site for designers.

最後的結果就是:

考慮到目前各家瀏覽器的支援性,可以看到 Lossless WebP 其實是個很好的選擇,檔案算蠻小的,而且 Apple ecosystem 的支援性也已經出來了:

如果不用考慮到瀏覽器的話,JPEG XL 也可以考慮,不過本來宣稱 royalty-free 的部份蒙上了陰影:「Alarm raised after Microsoft wins data-encoding patent」,用的人反而要注意到 patent 問題...

Cloudflare 推出了讓你買 cache 空間的 Cache Reserve

這幾天 Cloudflare 推出了一大包東西,其中一個是 Cache Reserve:「Introducing Cache Reserve: massively extending Cloudflare’s cache」。

一般的使用情境是依照 LRU 演算法在決定 Cloudflare 的 cache 滿的時候要排除誰:

We do eviction based on an algorithm called “least recently used” or LRU. This means that the least-requested content can be evicted from cache first to make space for more popular content when storage space is full.

Cache Reserve 就是自己買 cache 空間,他的作法是你付 R2 的空間費用:

Cache Reserve is a large, persistent data store that is implemented on top of R2.

這樣就可以完全依照 Cache-Control 這類 HTTP header 內的時間保存了,你就不用擔心會被 purge 掉,首先價錢包括了 R2 的部份:

The Cache Reserve Plan will mimic the low cost of R2. Storage will be $0.015 per GB per month and operations will be $0.36 per million reads, and $4.50 per million writes.

另外還有還沒公告的 Cache Reserve 的部份:

(Cache Reserve pricing page will be out soon)

對於很極致想要拼 hit rate 的使用者來說是個選擇就是了,另外可以想到直播相關的協定 (像是 HLS) 好像可以這樣搞來壓低對 origin server 的壓力?

Tor 0.4.7.7 支援 congestion control

Tor 首度在協定內支援了 congestion control:「Congestion Control Arrives in Tor 0.4.7-stable!」。

這個新功能會帶來效能的提昇:

Tor has released 0.4.7.7, the first stable Tor release with support for congestion control. Congestion control will eliminate the speed limit of current Tor, as well as reduce latency by minimizing queue lengths at relays. It will result in significant performance improvements in Tor, as well as increased utilization of our network capacity.

之所以沒有辦法直接利用 packet loss 的方式讓 TCP network stack 直接判斷 congestion control,是因為這樣會產生 side channel:

Crucially, we rejected mechanisms to provide congestion control by allowing packet drops, due to the ability to introduce end-to-end side channels in the packet drop pattern.

所以 Tor 得自己實做 congestion control 演算法,選擇的演算法是結合了 Vegas 的 Tor-Vegas,可以看到在實驗中,德國與香港的 exit node 效率大幅提昇:

另外也因為 0.4.7.7 也出來一個禮拜了,也可以看到 Advertised Bandwidth (算是 Tor network 觀察到的 bandwidth) 開始成長:

另外一個重要的點是 UDP 的支援計畫,看起來在這次改善後也比較有可行性了:

The astute reader will note that we rejected datagram transports. However, this does not mean that Tor will never carry UDP traffic. On the contrary, congestion control deployment means that queue delay and latency will be much more stable and predictable. This will enable us to carry UDP without packet drops in the network, and only drop UDP at the edges, when the congestion window becomes full. We are hopeful that this new behavior will match what existing UDP protocols expect, allowing their use over Tor.

在 PostgreSQL 上直接掛 ML extension

Hacker News 首頁上看到「Show HN: PostgresML, now with analytics and project management (postgresml.org)」這個專案,可以在 PostgreSQL 上面直接掛 extension 跑 ML algorithm:「PostgresML - an end-to-end machine learning solution」,從 GitHub 上可以看到大多數是 Python 的程式碼。

從 GitHub 頁面上面可以看到這個專案還在比較早期的階段:

This project is currently a proof of concept. Some important features, which we are currently thinking about or working on, are listed below.

如果是目前要用的話,主要是方便看一些東西吧?可以想到的是掛個 replication 出來跑一些 query,這樣不會影響到 production database 的效能,應該還行...

另外看了一下支援的演算法,主要是以經典的 ML 演算法為主,而且就是套用 Python 上面的套件:XGBoostscikit-learn

這些演算法算是很好用了,而且掛到 PostgreSQL 裡面會讓使用上方便很多 (少了倒資料的動作,不過就得小心處理 dirty data 了),然後專案也附上一個 UI 界面可以看一些資料,不過我猜還是用其他生 visualization 的工具會比較豐富一點:

另外一個想法是拿來學習還不錯?老師在上課的時候拿來示範一些演算法,就不用自己再刻很多程式碼...

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

AWS KMS 與 AWS ACM 支援 post-quantum TLS ciphers

AWS 宣佈 AWS KMSAWS ACM 支援 post-quantum TLS ciphers:「AWS KMS and ACM now support the latest hybrid post-quantum TLS ciphers」。

全區支援 Kyber、BIKE 與 SIKE 這三個演算法:

The three PQC key encapsulation mechanisms (KEMs) offered are Kyber, BIKE, and SIKE. Hybrid post-quantum TLS combines a classical key agreement, such as ECDHE, with one of these KEMs. The result is that your TLS connections inherit the security properties of both the classical and post-quantum key exchanges.

Hybrid post-quantum TLS for AWS KMS and ACM is available in all public AWS Regions.

不過這是 NIST Post-Quantum Cryptography Standardization 裡 Round 3 裡面其中幾個演算法而已:

AWS Key Management Service (KMS) and AWS Certificate Manager (ACM) now support hybrid post-quantum key establishment for transport layer security (SSL/TLS) connections using the latest post-quantum ciphers from Round 3 of the NIST Post-Quantum Cryptography (PQC) selection process.

順便補一下隔壁棚 Cloudflare 的研究:「Making protocols post-quantum」。

程式競賽常用的演算法

一開始是在 Hacker News Daily 上看到「Algorithms for Modern Hardware (algorithmica.org)」這篇,原文在「Algorithms for Modern Hardware」,本來是在他們要在 2022 夏天出一本書講現代硬體架構下的演算法,但在裡面看到了「Algorithms for Competitive Programming」這個網站,列出了程式競賽常用的演算法。

裡面的演算法常常是解問題的基礎 (小積木),拿來打 Leetcode 也很好用,不過要注意裡面都未必是最佳解,像是 Kth order statistic in O(N) 這邊只提到了 Quickselect 這個時間複雜度平均是 \theta(n) 的演算法 (最壞是 \theta(n^2)),但實際上配合 Median of medians 可以確保最壞的情況下是 \theta(n)

Amazon S3 支援 MD5 以外的檢查演算法了

Amazon S3 宣佈支援 MD5 以外的檢查演算法了:「New – Additional Checksum Algorithms for Amazon S3」。

多支援了 SHA-1SHA-256 以及 CRC-32CRC-32C

In particular, you can specify the use of any one of four widely used checksum algorithms (SHA-1, SHA-256, CRC-32, and CRC-32C) when you upload each of your objects to S3.

雖然有拿 cryptographic hash function 來用,但其實是當作 checksum algorithm 在用,拿來檢查檔案正確性的,而不是防中間被竄改之類 (這個部份是靠 HTTPS),本來支援的 MD5 應該算是夠用,只是現在多了不少選擇。

然後全商用區都可以用了:

The four additional checksums are now available in all commercial AWS Regions and you can start using them today at no extra charge.

Linux Kernel 裡的 RNG 從 SHA-1 換成 BLAKE2s

Hacker News Daily 上看到的消息,Linux Kernel 裡的 RNG,裡面用到的 SHA-1 演算法換成 BLAKE2s 了:

SHA-1 已知的問題是個隱患,不過換成 BLAKE2s 應該是 maintainer 的偏好,Jason Donenfeld 在 WireGuard 裡面也是用 BLAKE2s...

Ribbon filter

RocksDB 的 blog 上看到「Ribbon Filter」這個,主要是 RocksDB 從 6.15 開始支援 Ribbon filter,取代本來的 Bloom filter 機制。

RocksDB 的 wiki 上面是說用 CPU 資源換 memory 的使用量:

A new Bloom filter alternative is available as a drop-in replacement (since version 6.15.0), saving about 30% of Bloom filter space (most importantly, memory) but using about 3-4x as much CPU on filters. Most of the additional CPU time is in the background jobs constructing the filters, and this is usually a good trade because it is common for SST filters to use ~10% of system RAM and well under 1% of CPU.

論文則是在「Ribbon filter: practically smaller than Bloom and Xor」這邊可以看到,Facebook 之前也有提到 Ribbon filter:「Ribbon filter: Practically smaller than Bloom and Xor」,在 Hacker News 上有對應的討論可以翻:「Ribbon filter: Practically smaller than Bloom and Xor (fb.com)」。

在 Ribbon filter 的資料裡面都提到了 Xor filter 當作比較,先前在「比 Bloom filter 與 Cuckoo filter 再更進一步的 Xor filter」這邊有提到 Xor filter。

用 CPU 去換記憶體,算是特化的版本...