Optimization status: firedancer parity, what we tried, and what is left

[unsafePtr]

Reference for future performance work: which pipeline stages firedancer vectorises, which we do, and everything we have already tried and rejected. Recorded so the rejected ideas are not re-attempted from scratch.

Stage-by-stage: firedancer vs us

Firedancer from src/ballet/base58/fd_base58_tmpl.c, ours from this repo.

Pipeline stage	Firedancer	Us	Verdict
Count leading zeros	AVX (wuc_ldu + count_leading_zeros_32)	Vector256	parity
Bytes -> uint32 limbs	scalar (fd_uint_bswap(fd_uint_load_4(...)))	scalar (ReadUInt32BigEndian loop)	parity, and they chose scalar too
Encode matmul (axpy)	scalar	Vector256/Vector128 + MultiplyWidening32	we go beyond firedancer
Decode matmul (dot)	scalar	Vector256/Vector128 + MultiplyWidening32	we go beyond firedancer
Base-58^5 reduction	scalar	scalar	parity; inherently serial carry chain
Digit extraction (intermediate_to_raw)	AVX	scalar, 45/90 constant divisions	GAP
Compaction (ten_per_slot_down)	AVX	n/a, we write densely with no gap stage	n/a
Alphabet map (raw_to_base58)	AVX	scalar (EncodeState.EmitForward)	GAP

Both remaining gaps are on the output side, and the digit-extraction division chain is the measured critical path of the fast paths.

Rejected: limb-read and bounds-check work

All measured end to end on the real encode path, on Zen 4 (AVX-512) and Raptor Lake (AVX2), with --launchCount 3.

Attempt	Codegen signal	Measured	Outcome
Vector128 limb read, consume-and-advance	120 -> 22 instrs	27-33% slower	rejected; SysV runs out of callee-saved registers and spills all four span fields per iteration
Vector128 limb read, index-and-slice	no spill	~0% at 32B	rejected
MemoryMarshal.Cast + BinaryPrimitives.ReverseEndianness	one call, no inline	~0%	rejected; an apparent 9% win turned out to be a noisy scalar baseline
Vector256, inline mask, hoisted bound	96 -> 3 instrs	0% at 32B, ~4% at 64B	rejected as not worth the complexity
Const-length slice to fold bounds checks	-30% code, 8 -> 3 checks	0% / -2.7%	kept for code size only, comment says perf-neutral
Portable x * y instead of Avx2.Multiply	8 instrs vs 1 on AVX2	n/a	rejected
Runtime narrowness check instead of Debug.Assert	134 bytes vs 20	n/a	rejected; RyuJIT has no known-bits analysis for SIMD lanes, so the proof buys nothing
AVX-512 special case using vpmullq	1 instr either way	vpmullq is 3 uops / ~15c vs vpmuludq 1 uop / ~5c	rejected; vpmuludq is optimal on AVX-512 too

Rejected: earlier attempts on this branch and before

Attempt	Outcome
IndexOfAnyExcept for CountLeadingZeros	rejected, ~27% regression; benchmark kept as evidence
TensorPrimitives.Dot / .MultiplyAdd	rejected, hand-rolled kernels win and drop the System.Numerics.Tensors dependency
Jagged -> transposed column-major decode tables	kept
Loop restructure, i-outer/j-inner decode	rejected, replaced register accumulation with 288 array read-modify-writes
uzp1 + umull on arm64	superseded by xtn + umull
Vector<T> width-agnostic kernels	rejected, Vector<T>.Count does not fold so accumulators stay live and spill
Vector256.ShuffleNative	rejected, 31 test failures because it indexes globally rather than per 128-bit lane
Safe consume-and-advance in TensorDot (the .NET 11 idiom)	rejected, 13-33% slower on x64 at our lengths, parity on arm64; see dotnet/runtime#127506 and EgorBot/Benchmarks#401
SIMD decode-intermediate build	rejected, the stride-5 layout defeats it

What the pattern says

Everything that succeeded was algorithmic and changed what work happens: vectorising both matmuls, and the widening 32x32 multiply (8 instructions down to 1). Everything that failed tried to make the same work cheaper in instruction count.

Instruction count and code size turned out to be decoupled from latency in this code in five separate, independently measured cases. The strongest example: removing ~50 bounds checks and 30% of the machine code from ComputeBitcoin32FastRaw produced exactly zero measurable change, because never-taken forward branches are perfectly predicted and issue in spare slots on a wide out-of-order core, while the real critical path is the serial division chain in digit extraction.

Firedancer's own choices corroborate this: they left the limb load scalar and spent their AVX budget on digit extraction and the alphabet map, which are exactly the two stages we still do scalar.

Remaining opportunities, in order of expected value

1. Generic path: 34 bytes costs 11x more than 32 bytes (1085 ns vs 95 ns) because ComputeGenericDigits walks one input byte at a time into base-58 byte digits with a DivRem per digit. Switching to base-58^5 limbs in uint with ulong intermediates, consuming 4 input bytes at a time, cuts inner iterations roughly 9x for 34-byte input. This affects Bitcoin addresses (25B) and IPFS hashes (34B), arguably the most common real inputs. Largest single item by a wide margin.
2. Vectorise digit extraction, firedancer's intermediate_to_raw: replace the 45/90 constant divisions with lane-wise reciprocal multiplication. This is the measured critical path of the fast paths.
3. Vectorise the alphabet map, firedancer's raw_to_base58: a shuffle-based lookup, complicated by the 58-entry table exceeding the 16-byte shuffle window, so it needs a multi-table blend or a range-based computed mapping.
4. arm64 umlal: both kernels have the shape acc + (x * y), so MultiplyWideningLowerAndAdd would fuse multiply and accumulate, 4 vector instructions down to 3. API verified to exist. Small, arm64 only.

Benchmarking methodology notes

Learned the hard way this session, worth keeping:

• Always pass --launchCount 3 or higher. The default is 1, so BenchmarkDotNet runs each case in a single process and never samples process-level variance. This produced error bars of +/-0.4 ns while two runs of the same benchmark disagreed by 6.4 ns, which manufactured a phantom 9% win.
• Verify that the A/B arms actually differ in codegen before trusting any result. One benchmark here sliced a span whose length never reached the code being guarded, so both arms compiled identically and the comparison measured nothing.
• Use untouched cases as controls. In the good runs, the generic-path rows matched to 0.02% between builds, which is what made a 2.7% difference credible.
• Inline vector masks constant-fold, static readonly ones may not. Vector256.Shuffle with a literal mask becomes one vpshufb; with a field it became roughly nine instructions of cross-lane emulation, which caused 256-bit width to be wrongly written off.
• --runOncePerIteration cannot measure a ~100 ns function: the harness overhead was 20x the operation, and BenchmarkDotNet warns about it.