深入研究结构体初始化性能
我开始使用 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 字节组成的会话 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 在每次迭代中在堆上分配 2.13 KB 的内存。查看 BLAKE3 算法，这是设计使然：该算法需要近 2 KB 的状态来计算哈希摘要。这是相当多的内存，这样的基准测试会分配内存，只是为了立即丢弃它。重复堆分配会降低速度，因为它会给 GC 带来压力（它需要定期标记/清除内存，这是一个缓慢且阻塞的操作）。
我们只需要在堆上分配十六进制字符串。2 KB 的内存分配和丢弃，所以也许我们可以尝试将它们放在栈上并直接调用 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 的一次性使用中。最坏的情况是我会将它嵌入到类中，用于需要在堆上分配 2 KB 的生成和流式传输情况，但要散列的消息越长，初始堆分配的影响就越小。
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 在优化结构体方面做得非常出色！
发生了什么事
结构体首先被初始化，然后使用太多汇编指令无法计数的方式复制 2 KB 的内存。当然，这一切都发生在栈上，但复制所有这些数据需要大量 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 寄存器来复制结构体。
当结构体封装一个指针时，它是一个免费的抽象（在运行时方面）。一旦它封装了其他任何内容或更多数据，它就会涉及一些开销。