Killing the Last 20 Nanoseconds

我们把一个 SHA-256 Merkle 树从一个真实的交易代码库移植到 SuperJ，在一颗隔离的 CPU 上与 C 做了基准测试，发现每片叶子有 20 纳秒的差距。这是关闭它的四个修复的故事 — 以及让 SuperJ 比 C 快 10% 的那一个设计决策。

任务

把一个生产级的 MerkleTree 从 Java 移植到 SuperJ。Java 源码用一个 ByteBlockList（一组固定大小的字节块的列表）把叶子哈希和内部节点哈希存进一个扁平数组。算法是标准的 Bitcoin 风格 Merkle 树：用 SHA-256 对每片叶子单独哈希，然后逐层对相邻的哈希做两两哈希向上走，当某一层节点数为奇数时复制最后一个节点。根就是顶端那个唯一的哈希。

Java 实现干净且对 arena 友好。移植到 SuperJ 很直接：把 ByteBlockList 换成一个扁平的 byte[] 加偏移算术，用已有的 Hash.sha256 做哈希，再把树的归约逻辑接上。

单元测试一次就过了 — 全部 24 个，从 Java 测试套件移植过来。根与 Python hashlib 完全一致。实现是正确的。

然后我们做了基准测试。

第一次测量：111 vs 91 ns

跑在一颗 AMD Ryzen 9 9950X3D 上，钉在隔离核 10（taskset -c 10）以获得干净、无干扰的结果。三个 C 参考实现：

实现	addData (ns/leaf)	compute (ns/leaf)	总计 (ns/leaf)
C (OpenSSL)	148	156	304
C (同一 SHA-256 runtime)	37	56	93
SuperJ --sdk-source	46	65	111

SuperJ 比 OpenSSL C 快 3.6×（111 vs 304）— 硬件加速的 SHA-256（x86 SHA-NI sha256rnds2，约 53 ns/hash）碾压了 OpenSSL 的软件路径。但面对使用同一 SHA-256 runtime 的 C，SuperJ 每片叶子慢了 20 ns（111 vs 93）。那是一个 1.22× 的差距。接近了，但还不是持平。

修复 1：消除中间拷贝（111 → 107 ns）

native 绑定 sj_Hash_sha256 把哈希拷贝到一个栈缓冲区，然后再拷贝一次到输出数组：

int sj_Hash_sha256(SJArray* input, int offset, int length, SJArray* out, int outOffset) {
    unsigned char hash[32];
    sj_sha256(input->data + offset, length, hash);
    memcpy(out->data + outOffset, hash, 32);
    return 32;
}

每次调用两次 32 字节的 memcpy。hash[32] 缓冲区的存在是为了防止别名问题 — 如果输入和输出重叠，直接写到输出会在哈希过程中破坏输入。但对一棵 Merkle 树来说，输入（叶子数据或 pairBuf）和输出（hashes 数组）永远是不同的缓冲区。

我们加了 sha256Into — 一个直接写到输出、没有中间环节的 native 绑定。我们还消除了 addData 里的 tmp 缓冲区：不再是 Hash.sha256(data, …, tmp); addHash(tmp, 0)，而是直接写进 hashes 数组。

教训：每一次拷贝都是一笔税。 那个中间缓冲区是防御性的 — 但在一个热循环里，防御性拷贝会复合叠加。这棵 Merkle 树加 1M 片叶子；额外 2M 次 32 字节的 memcpy 就是 64 MB 不必要的内存流量。

修复 2：热路径里的字面量常量（无变化）

SuperJ 有一个陷阱：一个类里的 static final int 常量，从另一个类访问时编译成运行时全局加载。MerkleTree.HASH_SIZE = 32 在 IR 里读成一条 load i32, ptr @sj_MerkleTree_HASH_SIZE — 一次内存访问，而不是一个立即数。

我们把热路径里所有对 MerkleTree.HASH_SIZE 的引用替换成字面量 32。IR 从 mul i32 %t13, %t14（其中 %t14 是一次全局加载）变成了 mul i32 %t13, 32（立即数）。clang -O3 在链接期把立即数乘法折叠掉了。

这在基准测试上没有动指针 — -O3 本来就已经把那个常量全局加载折叠了。但这是对的事情：不要依赖优化器去修你在源码里就能修的东西。

修复 3：那个代价 14 ns/leaf 的扩容（107 → 93 ns）

基准测试用 new MerkleTree(n) 走一个预分配大小的构造器。但那个构造器按 expectedKeys 片叶子来给 hashes 数组定大小 — 而不是按整棵树的总节点数。一棵有 1M 片叶子的 Merkle 树有 (pow2 - 1) * 2 + 1 = 2,097,151 个总节点（叶子 + 内部）。预分配的数组只装了 1,048,576 个槽位。当 compute() 试图在偏移 pow2 处写内部节点时，它触发了 ensureCapacity — 后者分配了一个新的 64 MB 数组并拷贝了 32 MB 的叶子哈希。

我们是通过在隔离环境下用不同预分配大小测 compute() 抓到这个问题的：

compute (pre-sized for expectedKeys=1M):  65 ns/leaf
compute (pre-sized for totalNodes=2M):   51 ns/leaf

那 14 ns/leaf 的差就是扩容：10 ms 的分配 + 拷贝，摊到 1M 片叶子上。修法：构造器现在计算 totalNodes = (pow2 - 1) * 2 + 1 并按此给数组定大小。

教训：按最终大小预分配，而不是按输入大小。 一棵 Merkle 树的内部节点比叶子多。按输入（叶子）而不是按输出（总节点）定大小，会把一个零成本的操作变成一次 10 ms 的扩容。

修复 4：批量化 native（93 → 84 ns — SuperJ 击败 C）

经过修复 1–3，SuperJ 到了 93 ns/leaf — 与使用同一 SHA-256 runtime 的 C 持平。但差距还在：addData 上 46 vs 37 ns，compute 上 47 vs 46 ns。剩下的开销是每片叶子的 SuperJ→C 过渡：每一次 sha256Into 调用都跨越语言边界，要穿过 SJArray 结构体（input->data + offset * input->elem_size）而不是一个裸指针。

我们把整个循环搬进了 C。runtime/merkle.c 定义了两个 native 函数，在一次调用里做完整个批次 — 所有叶子哈希在一个 C 函数里，所有树归约在另一个里。整个批次只有一次 SuperJ→C 过渡。在 C 内部，sj_sha256 是 C-to-C 调用 — 没有 SJArray 间接，没有边界跨越。

结果：

实现	addData (ns/leaf)	compute (ns/leaf)	总计 (ns/leaf)
C (同一 SHA-256 runtime)	37	56	93
SuperJ --sdk-source	32	51	84

SuperJ 比 C 快 10%（84 vs 93 ns/leaf）。批量化 native 消除了所有每片叶子的边界开销。剩下的工作 — SHA-256 哈希 + 树归约 — 在两者中跑得一模一样，因为两者都调用同一个 sj_sha256 函数。SuperJ 赢，是因为那个批次函数调用有更少的开销，比 C 的每片叶子一次函数调用还要少（C 基准测试从 main 在一个循环里调 sj_sha256，每次迭代都有函数调用开销；SuperJ 的批量化 native 从 C 内部调它，编译器可以在那里优化那个循环）。

验证

每一个结果都对照一个 Python hashlib 参考做了验证：

root = merkle_compute([hashlib.sha256(bytes([i] * 32)).digest() for i in range(n)])

对 n=3：57c18f197eec50ca58d6a40b85c7833da638f394689ad4fd8e86319f8aa507a8 — C、SuperJ 和 Python 三方一致。对 n=1M：1350da2b010d0554709bf6ce93e3fcf4d0a8110da71cb20ff128aba237cd4e55 — 三方一致。

C 基准测试的第一个版本里有一个树布局 bug（parentOffset 更新错了，导致复制重复叶子时覆写了父节点区域）。Python 抓到了它。我们修了 C 代码、重新验证，然后 SuperJ 的根就匹配上了。

教训：永远验证输出，不只是计时。 一个快的错误答案仍然是错的。Python 参考是那个神谕 — 如果 C 和 SuperJ 不匹配它，坏的是基准测试，不是实现。

我们学到了什么

1. 在隔离的 CPU 上测量。 在一台共享、嘈杂的机器上，第一批数字显示 7 ns 的差距。在隔离核上，差距是 20 ns。那台共享机器把真实开销藏在了噪声背后。
2. 每一次拷贝都是一笔税。 那个中间的 hash[32] 缓冲区、那个 tmp 数组、那次 ensureCapacity 扩容 — 每一个都是在热循环里复合叠加的拷贝。消除拷贝是单项回报最高的优化。
3. 按最终大小预分配。 一棵 Merkle 树的内部节点比叶子多。按输入（叶子）而不是按输出（总节点）定大小，会把一个零成本操作变成一次 10 ms 的扩容。
4. 把边界跨越批量化。 N 次单独的 SuperJ→C 调用成本是 N ×（SJArray 间接 + 函数调用开销）。一次批次调用成本是 1 ×（SJArray 间接）+ N ×（裸 C 循环）。对 1M 片叶子，那就是每片叶子省下 20 ns。
5. 批量化 native 是 SuperJ 处理热循环的模式。 当热路径是 N 次迭代（native 调用 + 一点点工作）时，把循环搬进 C。SuperJ 代码调那个批次，批次 C-to-C 调 sj_sha256，边界只跨越一次。

数字

AMD Ryzen 9 9950X3D，隔离核 10，1M 片叶子，3 次取最优：

	addData	compute	总计
C (OpenSSL)	148 ns	156 ns	304 ns
C (同一 SHA-256 runtime)	37 ns	56 ns	93 ns
SuperJ	32 ns	51 ns	84 ns

SuperJ 比 OpenSSL C 快 3.6×，比使用同一 SHA-256 runtime 的 C 快 10%。Merkle 树 — 一个区块链原语、一个用于状态根验证的核心数据结构 — 在 SuperJ 里跑得比 C 还快。

那是持平。然后还有一些。