深入探討結構初始化效能
我開始嘗試使用 BLAKE3，並很快想評估它在 Crystal 中比 SHA256 快多少，看看是否能帶來一些免費的改進。幸運的是，有一個 shard 包裝了 官方函式庫，該函式庫針對不同的 CPU 功能（SSE、AVX2、NEON …）進行了高度優化的自訂組裝。
令我驚訝的是，效能非常糟糕。這篇文章是為了理解原因而寫下的記錄。準備好深入了解技術細節以及語言設計如何影響效能。
如果你想在家嘗試執行基準測試，這是一個 shard.yml
name: blake3-struct-test
version: 0.1.0
dependencies:
blake3:
github: didactic-drunk/blake3.cr
commit: d7ac0b7ff8f766b528cc99170664402518dd78b4
讓我們進行基準測試
BLAKE3 的賣點之一是它比其他雜湊摘要快上幾個數量級；作者聲稱比 SHA256 快將近 14 倍。我寫了一個快速的基準測試，比較 Digest::Blake3 和 Digest::SHA256 (由 OpenSSL 支援)，這通常是我用例中的預設選擇，例如雜湊一個由 32 個位元組組成的 session id。
require "benchmark"
require "blake3"
require "digest/sha256"
class Digest::Blake3 < ::Digest
# inject the class methods because the shard doesn't
extend ::Digest::ClassMethods
end
Benchmark.ips do |x|
bytes = Random::Secure.random_bytes(32)
x.report("SHA256") { Digest::SHA256.hexdigest(bytes) }
x.report("Blake3") { Digest::Blake3.hexdigest(bytes) }
end
SHA256 1.33M (753.33ns) (± 0.91%) 224B/op fastest
Blake3 1.21M (827.21ns) (± 0.79%) 2.13kB/op 1.10× slower
而贏家是… SHA256！什麼？
讓我們來調查一下
基準測試顯示 Digest::Blake3 在每個迭代中於 HEAP 中分配了 2.13KB 的記憶體。研究 BLAKE3 演算法，這是設計使然：該演算法需要將近 2KB 的狀態才能計算雜湊摘要。這佔用了大量的記憶體，而這樣的基準測試分配記憶體只是為了立即丟棄它。重複的 HEAP 分配會降低速度，因為它會對 GC 造成壓力（它需要定期標記/掃描記憶體，這是一個緩慢且阻塞的操作）。
我們只需要將十六進位字串分配到 HEAP 中。2KB 被分配並丟棄，所以也許我們可以嘗試將它們放在堆疊上並直接呼叫 C 函式？讓我們驗證一下是否能改善情況。
require "benchmark"
require "blake3"
require "digest/sha256"
def blake3_hexstring(data)
hasher = uninitialized UInt8[1912]
hashsum = uninitialized UInt8[32]
Digest::Blake3::Lib.init pointerof(hasher)
Digest::Blake3::Lib.update pointerof(hasher), data, data.bytesize
Digest::Blake3::Lib.final pointerof(hasher), hashsum.to_slice, hashsum.size
hashsum.to_slice.hexstring
end
Benchmark.ips do |x|
bytes = Random::Secure.random_bytes(32)
x.report("SHA256") { Digest::SHA256.hexstring(bytes) }
x.report("Blake3") { blake3_hexstring(bytes) }
end
SHA256 1.33M (754.01ns) (± 1.09%) 225B/op 3.40× slower
Blake3 4.51M (221.76ns) (± 2.57%) 80.0B/op fastest
我們現在每個摘要只分配 80 個位元組（用於十六進位字串），而 BLAKE3 快得多！我們遠遠沒有達到 14 倍的說法，但要雜湊的資料很小，而且 C 函式庫為我的 CPU 選擇了 SSE4.1 組裝；AVX512 組裝可能會更快，但我的 CPU 不支援它。
讓我們將其重構為慣用的 Crystal
隨著效能的回升，我繼續重構 shard，將 C 函式封裝在 struct 內，以便我們獲得一個美觀、慣用且最佳化的 Crystal。最好的情況是我們可以直接使用結構，例如在一次性使用 Digest::Blake3.hexdigest 的情況下。最壞的情況下，我會將其嵌入到類別中，用於需要分配 2KB 在 HEAP 中的 yield 和串流情況，但是要雜湊的訊息越長，初始 HEAP 分配的影響就越小。
require "benchmark"
require "blake3"
require "digest/sha256"
struct Blake3Hasher
def initialize
@hasher = uninitialized UInt8[1912]
Digest::Blake3::Lib.init(self)
end
def update(data)
Digest::Blake3::Lib.update(self, data.to_slice, data.bytesize)
end
def final(hashsum)
Digest::Blake3::Lib.final(self, hashsum, hashsum.size)
end
def to_unsafe
pointerof(@hasher)
end
end
def blake3_hexstring(data)
hasher = Blake3Hasher.new
hashsum = uninitialized UInt8[32]
hasher.update(data)
hasher.final(hashsum.to_slice)
hashsum.to_slice.hexstring
end
Benchmark.ips do |x|
bytes = Random::Secure.random_bytes(32)
x.report("SHA256") { Digest::SHA256.hexdigest(bytes) }
x.report("Blake3") { blake3_hexstring(bytes) }
end
SHA256 1.34M (744.61ns) (± 0.52%) 225B/op 1.38× slower
Blake3 1.85M (539.81ns) (± 1.22%) 80.0B/op fastest
而…效能正在急劇下降。
發生什麼事了？
我們仍然只在 HEAP 中分配 80B，因為結構分配在堆疊上，那麼到底發生什麼事了？在 Crystal 中，封裝結構不是應該是免費的抽象嗎？因為這裡顯然不是這種情況。難道 LLVM 無法內聯結構和方法呼叫，而且 BLAKE3 如此之快，以至於任何開銷都會降低效能？
這裡沒有更多的提示來理解發生了什麼。我們必須深入研究生成的程式碼才能進行進一步調查。我為上面的基準測試產生了 LLVM IR
$ crystal build --release --emit llvm-ir --no-debug bench.cr
上面的指令會在目前目錄中產生一個 bench.ll 檔案。我們在發布模式下建置，以便 LLVM 優化程式碼，並告訴 Crystal 不要產生偵錯資訊以提高可讀性。遺憾的是，我在那裡找不到任何奇怪的東西。
當我撰寫這篇部落格文章時，我注意到 LLVM IR 顯示與下面反組譯碼完全相同的問題。我不知道我怎麼沒注意到…也許我忘記了 --release 🤦
讓我們更深入地檢查我的 CPU 產生的組裝。例如，我們可以使用 objdump -d 反組譯可執行檔，而這次我立即注意到一些奇怪的事情：函式呼叫 Blake3::Hasher.new，後面跟著幾頁的 MOV 指令，而直接 C 函式呼叫的反組譯碼只是一些指令和函式呼叫。
這是緩慢 struct 案例的反組譯碼。查看其餘的反組譯碼，當初始化 @hasher 時，Blake3Hasher.new 內也發生了同樣的事情：重複的 MOV 指令太多，無法計算。
000000000003cf70 <~procProc(Nil)@bench.cr:35>:
(... snip...)
3cfa0: e8 0b 1d 00 00 callq 3ecb0 <*Blake3Hasher::new:Blake3Hasher>
3cfa5: 48 8b 84 24 10 16 00 mov 0x1610(%rsp),%rax
3cfac: 00
3cfad: 48 89 84 24 00 07 00 mov %rax,0x700(%rsp)
3cfb4: 00
3cfb5: 48 8b 84 24 08 16 00 mov 0x1608(%rsp),%rax
3cfbc: 00
(... snip: the above 2 MOV are repeated with a different index ...)
3ec3b: 4c 8d bc 24 28 07 00 lea 0x728(%rsp),%r15
3ec42: 00
3ec43: 4c 89 ff mov %r15,%rdi
3ec46: 48 8b b4 24 10 07 00 mov 0x710(%rsp),%rsi
3ec4d: 00
3ec4e: 48 8b 94 24 08 07 00 mov 0x708(%rsp),%rdx
3ec55: 00
3ec56: e8 e5 32 01 00 callq 51f40 <blake3_hasher_update>
(... snip ...)
這是發布版本的反組譯碼（LLVM 內聯了 C 呼叫）。它非常小，我不需要剪輯任何東西。它相當易讀，即使你不懂組合語言（我自己也不太懂）：它在堆疊上保留空間 (0x7b0)，儲存/還原被呼叫者儲存的暫存器並呼叫函式
000000000003cfb0 <~procProc(Nil)@bench.cr:44>:
3cfb0: 41 57 push %r15
3cfb2: 41 56 push %r14
3cfb4: 53 push %rbx
3cfb5: 48 81 ec b0 07 00 00 sub $0x7b0,%rsp
3cfbc: 48 8b 5f 08 mov 0x8(%rdi),%rbx
3cfc0: 4c 63 37 movslq (%rdi),%r14
3cfc3: 4c 8d 7c 24 38 lea 0x38(%rsp),%r15
3cfc8: 4c 89 ff mov %r15,%rdi
3cfcb: e8 20 16 01 00 callq 4e5f0 <blake3_hasher_init>
3cfd0: 4c 89 ff mov %r15,%rdi
3cfd3: 48 89 de mov %rbx,%rsi
3cfd6: 4c 89 f2 mov %r14,%rdx
3cfd9: e8 02 17 01 00 callq 4e6e0 <blake3_hasher_update>
3cfde: 48 8d 5c 24 18 lea 0x18(%rsp),%rbx
3cfe3: ba 20 00 00 00 mov $0x20,%edx
3cfe8: 4c 89 ff mov %r15,%rdi
3cfeb: 48 89 de mov %rbx,%rsi
3cfee: e8 3d 1f 01 00 callq 4ef30 <blake3_hasher_finalize>
3cff3: c7 44 24 08 20 00 00 movl $0x20,0x8(%rsp)
3cffa: 00
3cffb: c6 44 24 0c 00 movb $0x0,0xc(%rsp)
3d000: 48 89 5c 24 10 mov %rbx,0x10(%rsp)
3d005: 48 8d 7c 24 08 lea 0x8(%rsp),%rdi
3d00a: e8 41 fd ff ff callq 3cd50 <*Slice(UInt8)@Slice(T)#hexstring:String>
3d00f: 48 81 c4 b0 07 00 00 add $0x7b0,%rsp
3d016: 5b pop %rbx
3d017: 41 5e pop %r14
3d019: 41 5f pop %r15
3d01b: c3 retq
3d01c: 0f 1f 40 00 nopl 0x0(%rax)
所有 MOV 指令看起來像是我們…正在複製結構？
我嘗試將結構分配到堆疊上，然後呼叫它的 init 方法 —它僅僅呼叫 #initialize，但我們無法直接呼叫它，因為 #initialize 方法在 Crystal 中受到保護。 blake3_hexstring 方法中唯一的變更是
hasher = uninitialized Blake3Hasher
hasher.init
SHA256 944.38k ( 1.06µs) (± 0.97%) 225B/op 3.50× slower
Blake3 3.30M (302.91ns) (± 2.24%) 80.0B/op fastest
效能終於與直接呼叫 C 函式並駕齊驅。這表示 LLVM 現在正在最佳化抽象。查看反組譯碼，產生的區塊與我上面列出的直接 C 函式呼叫相同。 LLVM 在最佳化結構方面做得非常出色！
發生什麼事
結構先被初始化，然後使用太多組裝指令來計算，複製 2KB 的資料。當然，這一切都發生在堆疊上，但是複製所有這些資料需要大量的 CPU 時間，而且似乎還複製了兩次？難怪效能會被破壞。
結構的初始化方式與類別完全相同：透過建構子方法。雖然類別傳回參考（一個指標），但結構傳回必須複製的值本身，這可能是一個昂貴的操作。這是問題的根源。Crystal 程式碼產生器始終會產生一個看起來像這樣的建構子方法
struct Blake3Hasher
def self.new(*args, **kwargs) : self
value = uninitialized self
value.initialize(*args, **kwargs)
value
end
end
我們可以說問題源自 Ruby 語法。.new 建構子非常好，並且適用於類別，但是該設計不太適合 Crystal 結構，因為它鼓勵 LLVM 無法最佳化的複製操作。其他語言，例如 C、Go 或 Rust 沒有這個問題，因為它們不是物件導向的語言：你宣告一個變數（未定義），然後呼叫一個函式來初始化它（帶有指向結構的指標）。
因此，問題的關鍵在於：當我們初始化一個結構時，結構會複製到堆疊上。當它只有幾個位元組時，幾乎不會被注意到，但是一旦結構變大，就會很痛苦。LLVM 會在發布模式下將所有內容內聯到一個方法中，並且它確實最佳化了結構及其方法，但是它不會最佳化複製操作，這很令人驚訝。
我們可以修復它嗎？
Crystal 程式碼產生器可以宣告堆疊上的變數，然後呼叫 #initialize，而不是為結構產生建構子，就像我上面所做的那樣。儘管如此，說起來可能比做起來容易得多；例如，如果你的結構上有任何自訂建構子，則問題會再次出現，但是也許 Ameba 可以警告它？
額外內容
我們看到 LLVM 有時會最佳化掉複製，有時則不會。但是閾值是什麼？我進行了一些測試並閱讀反組譯碼或發布版本後，我發現
- 當 ivar 為
Pointer(64 位元) 時，結構體會完全被抽象化； - 當 ivar 為
UInt64或UInt64[1](64 位元) 時，儘管結構體與具有相同對齊方式的指標大小完全相同，組合語言會稍有變化 (多了幾個 MOV 和 LEA 指令)； - 當 ivar 為
UInt64[2]或兩個指標 (128 位元) 時，組合語言開始使用一些 XMM 暫存器來複製結構體。
當結構體包裹一個指標時，它是一個自由的抽象 (就執行時間而言)。一旦它包裹任何其他東西或更多數據，就會涉及一些額外開銷。