Skip to Content

WWW 0x07: 為什麼薯餅要炸兩次

這裡是 WWW 第柒期,Wow Weihang Weekly 是一個毫無章法的個人週刊,出刊週期極不固定,從一週到五年都有可能。初期內容以軟體工程為主,等財富自由後會有更多雜食篇章。

Why is Rust the Most Loved Programming Language?

又到了推坑 Rust 的時間!這次,Intellij RustRust Analyzer 的作者想聊聊為什麼 Rust 值得「最受喜愛的程式語言」的稱號,節錄我覺得蠻有共鳴的點:

  • Intellij Rust:用 Kotlin 寫的 Jetbrains IDE Rust Plugin
  • Rust Analyzer:新一代的 Rust IDE language server
  • Keyword First Syntax:搜尋 foo 函式只要文字搜尋 fn foo 就解決,有利於一般人開發,更使得 IDE 的 parser 更容易開發
  • Crates:Rust 的 crate 是一個編譯單元,但並沒有 global shared namespace,取而代之的是每個 crate 都會是你的 dependant crate 的一個 property,解決了 lib 命名衝突問題
  • Eq 並非多型:以前從來沒想過這個問題,但的確不同型別的比較直接 compile error 很合理,不過代價是需要寫一堆 as usize 😂
  • Trivial Data Types:透過 #[derive(...)] 可以很快速衍生出一堆 boilerplate,不需要再像某 Gx 語言一樣複製貼上
  • String encoded in UTF-8:現在看起來是優點,未來就不一定了 😈

Understanding the power of data types

滿全面的 PostgreSQL Data Type 概觀,二十分鐘內讀完,推推。

  • 字串一律用 text、時間一律用 timestamptz
  • type 底層的 data layout,並介紹 TOAST 技術來儲存巨大 field value
  • array/jsonb/enum/range 使用時機和各種小技巧
  • 各種強大 extension e.g. PostGIS(好用)、PostBIS(生物資訊)
  • 如何自幹 data type 並整合 aggregate、function、operator

Hashbrown/SwissTable

最近在看 hashbrown 的實作(Google SwissTable 的 Rust 版),發現幾個有趣的點分享給大家:

  • 雜湊碰撞的解法有 open addressing 和 separate chaining ,open addressing 有強大的 cache hit rate。
  • open addressing 的問題在於 delete k-v pair 時,假如現在有三個 pair 碰撞在同個 slot (hash value 一樣 slot 就一樣),當 delete (29, 7) 時,index 1 的 bucket 就為空, (6, 6) 就沒辦法在線性搜尋中找到
index |  0  |  1   |  2  | 
------|-----|------|-----|
value | 5,7 | 29,7 | 6,6 |
------|-----|------|-----|
slot  |  0  |  0   |  0  | 
  • 承上,解法有兩個, 1)backshift 向前重排法 ,deleted pair 之後所有碰撞的 pair 都往前 shift,還有 2)tombstone 墓碑標記法 ,標記該 bucket 曾經死過人,線性搜尋就可以延續往後找,跳過這個墓碑
  • hashbrown/SwissTable 有做 SIMD 最佳化,可以把 SIMD 想成一個 CPU 指令下去多個 byte 同時平行處理,因此 hashbrown 每個 bucket 除了儲存 k-v pair,還會多存 control byte,是 hash value 的最大(或最小)的 8-bits,讓每個 SIMD 指令一下去,可同時比較 16 bucket (16 * 8 = 128 bits 的 register size) 的資料是否 hash value 相同,速度飛快
  • 我想不到了言盡於此,大家可以自己看文章

References