Cloudflare Workers 支援 Python (是 open beta)

Cloudflare 宣佈 Cloudflare Workers 支援 Python:「Bringing Python to Workers using Pyodide and WebAssembly」。

不過比較特別的是,並不是原生支援 Python 環境,而是透過轉譯成 WebAssembly 丟進 V8 engine 執行,就如同文章標題提到的。

另外是套件的部分,照這個文字的說明,應該不是所有的套件都可以丟進去用 (can import a subnet of popular Python packages),支援的套件看起來是預先 compile 好:

All bindings, including bindings to Vectorize, Workers AI, R2, Durable Objects, and more are supported on day one. Python Workers can import a subset of popular Python packages including FastAPI, Langchain, Numpy and more. There are no extra build steps or external toolchains.

看起來是打算全部都用 javascript 當作基礎?

UI Event 的順序

othree 寫了一篇「UI Event Order」在講滑鼠 (或是更廣廣義的 pointer 類) 以及鍵盤 (包括輸入法) 在瀏覽器上會產生的 event。

裡面有些是歷史 (提到 IE 上的實作方式),現在都不太會碰到了,可以直接看目前的幾份標準就好,然後蠻多標準都還是在 draft 階段,各家瀏覽器更新的速度不一樣,所以會有不同的行為冒出來。

我決定先把文章保留起來,等遇到的時候再回來看 XD

Google 的 HyperLogLog++

算是接續昨天寫的「Redis 對 HyperLogLog 省空間的實作」,在 RedisHyperLogLog 實作有提到 Google 在 2013 年的論文「HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm」,裡面提出了 HyperLogLog++ (HLL++)。

論文中 Google 提出來的改進主要有三個,第一個是用了 64-bit hash function:

5.1 Using a 64 Bit Hash Function

原因也有提到,當需要處理超過十億筆資料時,32-bit hash 的 4B 上限就有點不太夠用:

To fulfill the requirement of being able to estimate multisets of cardinalities beyond 1 billion, we use a 64 bit hash function.

這點也簡化了原始論文中當 cardinality 接近 232 時的 count 估算修正,因為實務上不太可能遇到 264 上限?

It would be possible to introduce a similar correction if the cardinality
approaches 264, but it seems unlikely that such cardinalities are encountered in practice.

第二個是改善 cardinality 比較低時的 count 估算公式:

5.2 Estimating Small Cardinalities

第三個則是提出了 sparse representation 的概念,在 cardinality 比較低的時候不需要直接用完整的 HLL 資料結構儲存:

5.3 Sparse Representation

另外也是一路往回讀的關係,查資料才了解 (ε, δ)-model 的用法,在「A Quick Introduction to Data Stream Algorithmics」這邊投影片的 Page 17 可以看到指的是,有多少正確性 (randomized) 是給出 ε 內的誤差 (approximation),像是 Page 18 的範例:

Example: Actual answer is within 5 ± 1 with prob ≥ 0.9

Java 21 的 ZGC 在 Netflix 的效果

Hacker News 上看到連結「Bending pause times to your will with Generational ZGC (netflixtechblog.com)」,發現這篇還沒整理:「Bending pause times to your will with Generational ZGC」,裡面講的東西都有圖有數字 (i.e. Y 軸),作者是 Danny Thomas

在這之前他們就已經知道 GC pause 是延遲的重要來源,會導致 timeout & retry:

In both our GRPC and DGS Framework services, GC pauses are a significant source of tail latencies.

That’s particularly true of our GRPC clients and servers, where request cancellations due to timeouts interact with reliability features such as retries, hedging and fallbacks.

第一張圖拉出來的資料是 error rate,白色是上個禮拜的資料,紫色是這個禮拜的資料,而從 G1GC 切到 ZGC 是在 2023/11/16 發生的:

可以看到很明顯的 error rate 改變:尖峰從 2k 下降到大約 0.3k,大約是原來的 1/6 到 1/7 的下降。

第二張圖是 GC 的時間:

可以看到 G1GC 還是偶而會撞到 2 秒,發生時平均值也都還是會 >100ms,切到 ZGC 後直接降到個位數 ms 等級了。

第三張圖是 memory overhead 的部分:

從圖上可以看到上週與本週的對比,導入 ZGC 後記憶體的使用量下降了,不過文裡面倒是沒解釋這點,反而提到 ZGC 比起 G1GC 有個固定的 3% overhead:

ZGC has a fixed overhead 3% of the heap size, requiring more native memory than G1. Except in a couple of cases, there’s been no need to lower the maximum heap size to allow for more headroom, and those were services with greater than average native memory needs.

第四張則是 Huge Pages 的差異,這邊要注意這張圖的 Y 軸不是從 0 計算:

可以看到在開 Huge Pages 後,在 RPS (request per second) 不變的情況下 CPU 使用率是有下降的,大約從 50% 降到 45% 左右,不過這張圖的時間跨度有點少,應該是要拉長一點的圖... 不過既然被提出來了,就假設 Netflix 內看起來應該是有這個趨勢,只是抓圖的時候懶了點?

整體算是大成功?

tf-idf 與 BM25

tf–idfBM25 是兩個在資訊檢索 (IR) 裡面的經典演算法,也常被用在搜尋引擎技術上。

前陣子在練 Go,剛好找個主題來練,tf-idf 已經很熟了,但 BM25 沒有實際寫過,而自己的 blog 也累積了七千多篇,這個數量還算好用,不用自己另外 dump 維基百科的文章跑... (而且量太大)

第一步是拆成 token,我這邊就拿 bigram 拆了,但英文的部分把一整個詞當作一個單位,而非一個字母一個字母拆。

btw,這邊 tf-idf 與 BM25 的公式就請大家自己去維基百科上翻了...

tf-idf 概念上很簡單,而也沒有什麼 magic number 在公式裡面。

如果把 tf-idf 當一個 function 來看的話會是 score = tfidf(w, d, D),表示一個字 w 在一份文件 d 裡面的分數 (而 D 是所有文件)。

而 tf 只跟文件本身有關,可以預先算好放著,df 在後續文件新增刪除時都可以 incremental update,不需要重頭算,是個對於平行化運算很友善的演算法。

接著是看 BM25,如果把 BM25 當作一個 function 來看的話,會是 array = bm25(Q, D),針對 query words Q 與所有文章 D 傳回一個排序結果 array,裡面會是排序過的 document id,通常會包括分數。

而從公式可以看到 BM25 其實就是把 Q 裡面的每個字丟進 tf-idf 後加起來的變形,只是多考慮到文件大小對分數的影響,另外裡面引入了一些花招,像是 k1 與 b 這兩個常數項。

所以我就寫了兩個版本,一個是單純用 tf-idf 相加 (這樣長文章分數應該會比較高),另外一個是用 BM25 的公式跑... 算是趣味趣味的寫法。

算是清掉了之前一直放著的項目...

各家首頁 JavaScript 的大小

看到「JavaScript Bloat in 2024 (tonsky.me)」這篇在講各家首頁 JavaScript 的大小,原文在「JavaScript Bloat in 2024」這邊。

作者 Nikita Prokopov 創造了很多 open source project,我比較有印象的是 Fira Code,這篇比較像是他在抱怨現在的網站...

裡面站台一堆都是 10MB+ 的 JavaScript 在跑的,突然提到 P 站只有 1.4MB 的時候笑了出來 (在 Hacker News 的 comment 裡面也有人提到這個):

Compare it to people who really care about performance — Pornhub, 1.4 MB:

另外 Jira 也被拿出來鞭:

Here, Jira, a task management software. Almost 50 MB!

但趨勢看起來不可逆?現在開發網站一堆都搞前後端分離,用 JavaScript 產生出所有頁面,然後再想辦法補 SEO...

Go 的 net/http 在 1.22 的 routing 新功能

Gonet/http 在 1.22 引入了更方便的 pattern matching:「Routing Enhancements for Go 1.22」。

用官方的範例,現在可以處理路徑裡的參數了:

http.Handle("GET /posts/{id}", handlePost2)

後續可以透過 PathValue() 取出來:

idString := req.PathValue("id")

而優先順序則是依照吻合度定義:

The precedence rule is simple: the most specific pattern wins. This rule matches our intuition that posts/latests should be preferred to posts/{id}, and /users/{u}/posts/latest should be preferred to /users/{u}/posts/{id}. It also makes sense for methods. For example, GET /posts/{id} takes precedence over /posts/{id} because the first only matches GET and HEAD requests, while the second matches requests with any method.

但是當有重疊卻無法判斷相對吻合度的 rule 被加進去時,會直接 panic()

What if two patterns overlap but neither is more specific? For example, /posts/{id} and /{resource}/latest both match /posts/latest. There is no obvious answer to which takes precedence, so we consider these patterns to conflict with each other. Registering both of them (in either order!) will panic.

這的確是種方法啦... 而且留有之後處理的空間,真的有好的方法就可以把 panic() 的邏輯改成新的共識。

uv:用 Rust 寫的 Python Packaging 替代方案

社群好幾個地方都有提到的「uv: Python packaging in Rust」這個,文章開頭的說明有快速說明目標是 pip 的 drop-in replacement:

TL;DR: uv is an extremely fast Python package installer and resolver, written in Rust, and designed as a drop-in replacement for pip and pip-tools workflows.

這跟「Ruff:用 Rust 寫的 Python Linter」都是 Astral 下的專案,主打用 Rust 改善速度的專案。

馬上想到的是 package resolver,這指的是依照每個套件指定的相依條件,找出符合所有條件的版本組合。

這在各個語言的套件系統上都是痛點,而在「Dependency hell is NP-complete」這篇就有指出這是 NP-complete

這是因為 3SAT 問題可以 PTIME 轉成 package resolver 問題 (於是就 NP-hard 了),再加上有 PTIME 的驗證,就變成 NP-complete 了。

但看說明應該是不只這個部分,包括了一些 i/o 類操作的改善。

除了速度以外,uv 也提供了讓測試更方便的功能,像是在計算相容版本時,預設的演算法是儘量都裝最新版,但你可以指定要儘量裝最舊的版本,這樣對於相容性測試頗有用的:

But by passing --resolution=lowest, library authors can test their packages against the lowest-compatible version of their dependencies. (This is similar to Go's Minimal version selection.)

這個工具的出現也是頗有幫助,我記得寫 Python 專案時隨便引入個 Django,再多拉幾個套件,跑起 package resolver 就要花不少時間了,可以想像中大型專案在這塊的痛點...

另外剛剛回去看了 ruff,從去年四月 500+ 條規則增加到 700+ 條了,在發表受到注目後應該補了不少社群常用到的規則,說不定新專案可以無痛跳進去了,去年的時候試著用,有發現常見的規則還沒有支援...

PHP 8.3 相比於 PHP 8.2 的效能提升

找資料的時候意外發現 PHP 8.3 相對於 PHP 8.2 的效能提升好像不算小?目前看到這兩個地方有提到:

前面那篇的 benchmark 數據可以看出來愈大愈複雜的框架,提升的效能就愈多:

  • 乾淨的 WordPress 從 158 rps 成長到 169 rps,大約 7% 的增加。
  • 如果是 WooCommerce 的話從 49 rps 到 58 rps,大約是 18.4%。
  • 接著 Laravel 則是從 670 rps 到 925 rps,提升了 38.1%。
  • Drupal 則是 941 rps 到 1432 rps,提升了 52.2%。

在「Make your app faster with PHP 8.3」這邊提到了 PHP 8.3 改善了很多關於效能的項目。

首先提到的是 JIT 的改善:

The Just-In-Time (JIT) compiler has been further optimized for better efficiency. The execution of scripts is faster and consumes less CPU time. This is especially beneficial for resource-intensive tasks.

然後是 opcode 這邊的改善:

PHP has refined how it handles opcodes (the instructions in the PHP bytecode). Version 8.3 uses more efficient ways to interpret and execute these opcodes. This reduces the execution time of scripts.

然後 GC 機制也改善了:

PHP 8.3 enhances the garbage collection mechanism, which is responsible for freeing memory occupied by unused objects. This results in more efficient memory usage and can significantly improve performance for memory-intensive applications.

array 的改善:

Other improvements include optimizations for handling arrays and an enhanced type system.

對於複雜的應用就很容易都受惠,然後就有頗大的提升...

展開所有 GitHub comment 的 Bookmarklet

看到 Eric Meyer 弄了一個可以展開 GitHub comment 的 bookmarklet:「Bookmarklet: Load All GitHub Comments」。

分析他的程式碼,稍微手動排一下,可以看出來邏輯蠻簡單的,就是去找出對應的 button,然後模擬按下去的 event:

javascript:function start() {
  let buttons = document.querySelectorAll('button');
  let loaders = [];
  for (let i = 0; i < buttons.length; i += 1) {
    if (buttons[i].textContent.trim() == 'Load more%E2%80%A6') {
      loaders.push(buttons[i]);
      buttons[i].dispatchEvent(new MouseEvent('click', {
        view: window,
        bubbles: false
      }))
    }
  }
  if (loaders.length > 0) {
    setTimeout(start, 5000)
  }
}
setTimeout(start, 500);
void(20240130);

意外可以看到一些應該是作者以前寫習慣的寫法 (畢竟 Eric Meyer 這個名字二十年前就聽過了?),現在 for 拿來當 iteration 應該會用 of 的語法了,另外是 letconst 的差異...

還好這邊還是用 querySelectorAll(),而不是直接看到 getElementsByTagName(),不然就更有考古感了...

拿「Quadratic time internal base conversions #90716」這個測了一下還行,不過我不是那麼常用到,大概不會掛到 bookmark bar 上面...

作者有提到考慮過寫成 userscript,不過看起來是懶 XD