Killing the Last 20 Nanoseconds

We ported a SHA-256 Merkle tree from a real trading codebase to SuperJ, benchmarked it against C on an isolated CPU, and found a 20-nanosecond-per-leaf gap. This is the story of the four fixes that closed it — and the one design decision that made SuperJ 10% faster than C.

The task

Port a production MerkleTree from Java to SuperJ. The Java source uses a ByteBlockList (a list of fixed-size byte blocks) to store leaf hashes and internal node hashes in a flat array. The algorithm is the standard Bitcoin-style Merkle tree: hash each leaf with SHA-256, then pairwise-hash adjacent hashes up the tree, duplicating the last node when a level has an odd count. The root is the single hash at the top.

The Java implementation is clean and arena-friendly. The port to SuperJ was straightforward: replace ByteBlockList with a flat byte[] + offset arithmetic, use the existing Hash.sha256 for hashing, and wire up the tree reduction logic.

The unit tests passed on the first try — all 24 of them, ported from the Java test suite. Roots matched Python hashlib exactly. The implementation was correct.

Then we benchmarked it.

The first measurement: 111 vs 91 ns

We ran on an AMD Ryzen 9 9950X3D, pinned to isolated core 10 (taskset -c 10) for clean, interference-free results. Three C references:

Implementation	addData (ns/leaf)	compute (ns/leaf)	total (ns/leaf)
C (OpenSSL)	148	156	304
C (same SHA-256 runtime)	37	56	93
SuperJ --sdk-source	46	65	111

SuperJ was 3.6× faster than OpenSSL C (111 vs 304) — the hardware-accelerated SHA-256 (x86 SHA-NI sha256rnds2, ~53 ns/hash) crushes OpenSSL's software path. But against C using the same SHA-256 runtime, SuperJ was 20 ns/leaf slower (111 vs 93). That's a 1.22× gap. Close, but not parity.

Fix 1: eliminate the intermediate copy (111 → 107 ns)

The native binding sj_Hash_sha256 copies the hash to a stack buffer, then copies it again to the output array:

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;
}

Two 32-byte memcpys per call. The hash[32] buffer exists to prevent aliasing — if the input and output overlap, writing directly to the output would corrupt the input mid-hash. But for a Merkle tree, the input (leaf data or pairBuf) and output (the hashes array) are always different buffers.

We added sha256Into — a native binding that writes directly to the output, no intermediate. We also eliminated the tmp buffer in addData: instead of Hash.sha256(data, …, tmp); addHash(tmp, 0), we write directly into the hashes array.

Lesson: every copy is a tax. The intermediate buffer was defensive — but in a hot loop, defensive copies compound. The Merkle tree adds 1M leaves; 2M extra memcpys of 32 bytes each is 64 MB of unnecessary memory traffic.

Fix 2: literal constants in hot paths (no change)

SuperJ has a trap: static final int constants in one class compile to runtime global loads when accessed from another class. MerkleTree.HASH_SIZE = 32 reads as a load i32, ptr @sj_MerkleTree_HASH_SIZE in the IR — a memory access instead of an immediate.

We replaced all MerkleTree.HASH_SIZE references in hot paths with the literal 32. The IR went from mul i32 %t13, %t14 (where %t14 is a global load) to mul i32 %t13, 32 (immediate). clang -O3 folds the immediate multiply at link time.

This didn't move the needle on the benchmark — -O3 was already folding the constant global load. But it's the right thing to do: don't rely on the optimizer to fix what you can fix at the source.

Fix 3: the resize that cost 14 ns/leaf (107 → 93 ns)

The benchmark created a new MerkleTree(n) with a pre-sized constructor. But the constructor sized the hashes array for expectedKeys leaves — not for the total tree nodes. A Merkle tree with 1M leaves has (pow2 - 1) * 2 + 1 = 2,097,151 total nodes (leaves + internal). The pre-sized array held 1,048,576 slots. When compute() tried to write internal nodes at offset pow2, it triggered ensureCapacity — which allocated a new 64 MB array and copied 32 MB of leaf hashes.

We caught this by measuring compute() in isolation with different pre-sizes:

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

The 14 ns/leaf difference was the resize: 10 ms to allocate + copy, spread across 1M leaves. The fix: the constructor now computes totalNodes = (pow2 - 1) * 2 + 1 and sizes the array for that.

Lesson: pre-size for the final size, not the input size. A Merkle tree's internal nodes outnumber its leaves. The ensureCapacity branch was never taken during addData (the leaves fit), but it fired once during compute() — and that single resize cost 10 ms.

Fix 4: the batch native (93 → 84 ns — and SuperJ beats C)

After fixes 1–3, SuperJ was at 93 ns/leaf — matching C with the same SHA-256 runtime. But the gap was still there: 46 vs 37 ns on addData, 47 vs 46 ns on compute. The remaining overhead was the per-leaf SuperJ→C transition: each sha256Into call crosses the language boundary, going through the SJArray struct (input->data + offset * input->elem_size) instead of a raw pointer.

We moved the entire loop into C. runtime/merkle.c defines two native functions that do the full batch in one call — all the leaf hashing in one C function, all the tree reduction in another. One SuperJ→C transition for the entire batch. Inside C, sj_sha256 is called C-to-C — no SJArray indirection, no boundary crossing.

The result:

Implementation	addData (ns/leaf)	compute (ns/leaf)	total (ns/leaf)
C (same SHA-256 runtime)	37	56	93
SuperJ --sdk-source	32	51	84

SuperJ is 10% faster than C (84 vs 93 ns/leaf). The batch native eliminated all per-leaf boundary overhead. The remaining work — SHA-256 hashing + tree reduction — runs identically in both, because both call the same sj_sha256 function. SuperJ wins because the batch function call has less overhead than C's per-leaf function calls (the C benchmark calls sj_sha256 in a loop from main, which has function-call overhead per iteration; the SuperJ batch native calls it from within C, where the compiler can optimize the loop).

The verification

Every result was verified against a Python hashlib reference:

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

For n=3: 57c18f197eec50ca58d6a40b85c7833da638f394689ad4fd8e86319f8aa507a8 — C, SuperJ, and Python all agree. For n=1M: 1350da2b010d0554709bf6ce93e3fcf4d0a8110da71cb20ff128aba237cd4e55 — all three agree.

The C benchmark had a tree layout bug in the first version (the parentOffset update was wrong, causing the duplicate-leaf copy to overwrite the parent area). Python caught it. We fixed the C code, re-verified, and then the SuperJ roots matched.

Lesson: always verify the output, not just the timing. A fast wrong answer is still wrong. The Python reference was the oracle — if C and SuperJ didn't match it, the benchmark was broken, not the implementation.

What we learned

1. Measure on an isolated CPU. The first numbers on a shared, noisy machine showed a 7 ns gap. On the isolated core, the gap was 20 ns. The shared machine was hiding the real overhead behind noise.
2. Every copy is a tax. The intermediate hash[32] buffer, the tmp array, the ensureCapacity resize — each was a copy that compounded in the hot loop. Eliminating copies is the single highest-ROI optimization.
3. Pre-size for the final size. A Merkle tree's internal nodes outnumber its leaves. Sizing for the input (leaves) instead of the output (total nodes) turns a zero-cost operation into a 10 ms resize.
4. Batch the boundary crossings. N individual SuperJ→C calls cost N × (SJArray indirection + function-call overhead). One batch call costs 1 × (SJArray indirection) + N × (raw C loop). For 1M leaves, that's 20 ns/leaf saved.
5. The batch native is the SuperJ pattern for hot loops. When the hot path is N iterations of (native call + small work), move the loop into C. The SuperJ code calls the batch, the batch calls sj_sha256 C-to-C, and the boundary is crossed once.

The numbers

AMD Ryzen 9 9950X3D, isolated core 10, 1M leaves, best of 3:

	addData	compute	total
C (OpenSSL)	148 ns	156 ns	304 ns
C (same SHA-256 runtime)	37 ns	56 ns	93 ns
SuperJ	32 ns	51 ns	84 ns

SuperJ is 3.6× faster than OpenSSL C and 10% faster than C using the same SHA-256 runtime. The Merkle tree — a blockchain primitive, a core data structure for state-root verification — runs faster in SuperJ than in C.

That's parity. And then some.