構造体の初期化パフォーマンスの深堀り
BLAKE3をいじり始め、CrystalでSHA256と比べてどれくらい高速なのか、そして無料で改善できるかすぐに評価したくなりました。幸運なことに、公式ライブラリ をラップした、さまざまなCPU機能（SSE、AVX2、NEONなど）向けにカスタムアセンブリで高度に最適化されたシャードがあります。
驚いたことに、パフォーマンスはかなり悪かったです。この記事は、その理由を理解するための探求の記録です。技術的な詳細と、言語設計がパフォーマンスにどのように影響するかについて掘り下げる準備をしてください。
自宅でベンチマークを実行したい場合は、shard.yml があります。
name: blake3-struct-test
version: 0.1.0
dependencies:
blake3:
github: didactic-drunk/blake3.cr
commit: d7ac0b7ff8f766b528cc99170664402518dd78b4
ベンチマークしてみましょう
BLAKE3のセールスポイントの1つは、代替ハッシュダイジェストよりも桁違いに高速であることです。たとえば、作成者はSHA256の約14倍高速であると主張しています。32バイトのセッションIDをハッシュするなど、私のユースケースで通常デフォルトの選択肢であるDigest::SHA256（OpenSSLでサポート）とDigest::Blake3を比較する簡単なベンチマークを作成しました。
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は反復ごとにヒープに2.13KBのメモリを割り当てています。 BLAKE3アルゴリズムを調べると、これは設計によるものです。アルゴリズムはハッシュダイジェストを計算するためにほぼ2KBの状態を必要とします。これは大量のメモリであり、このようなベンチマークはメモリを割り当ててすぐに破棄します。ヒープの繰り返し割り当ては、GCに負担をかけるため、処理速度が低下します（定期的にメモリをマーク/スイープする必要があり、これは低速でブロッキング操作です）。
ヒープに割り当てる必要があるのは16進文字列だけです。 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バイト（16進文字列の場合）のみを割り当て、BLAKE3ははるかに高速になりました！ 14倍の主張にはほど遠いですが、ハッシュするデータは小さく、CライブラリはCPU用にSSE4.1アセンブリを選択しました。 AVX512アセンブリは高速になる可能性がありますが、私のCPUはそれをサポートしていません。
慣用的なCrystalとしてリファクタリングしましょう
パフォーマンスが戻ったので、シャードのリファクタリングを続け、C関数をstruct 内にラップして、美しく、慣用的で最適化されたCrystalを取得しました。最適な場合は、構造体を直接使用できます。たとえば、Digest::Blake3.hexdigestを1回だけ使用する場合などです。最悪の場合、ヒープに2KBを割り当てる必要があるyieldingおよびstreamingケースでクラスに埋め込みますが、ハッシュするメッセージが長いほど、初期ヒープ割り当ての影響は少なくなります。
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
そして… パフォーマンスが低下しています。
何が起こっているのでしょうか？
構造体はスタックに割り当てられるため、ヒープにはまだ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を呼び出すだけですが、Crystalでは#initializeメソッドが保護されているため、直接呼び出すことはできません。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時間がかかり、* 2回*行われているように見えますか？ パフォーマンスが低下するのも不思議ではありません。
構造体はクラスとまったく同じように初期化されます。コンストラクタメソッドを介してです。クラスは参照（1つのポインター）を返しますが、構造体は値自体を返します。これはコピーする必要があるため、コストのかかる操作になる可能性があります。これが問題の原因です。 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]または2つのポインター（128ビット）の場合、アセンブリは構造体をコピーするためにいくつかのXMMレジスタを使用し始めます。
構造体は、1つのポインターをラップする場合、（ランタイムの観点からは）無料の抽象化です。他の何かまたはより多くのデータをラップするとすぐに、いくらかのオーバーヘッドが発生します。