Performance Improvements #65

• Setup: width 3 (2 inputs), release, native arm64.
• Measured shape: sol_poseidon (construct hasher, then hash_bytes_be).
• Baseline: main, 11.77 us.
• Projected: items 1-5 together, ~4.91 us: 3.1x faster than v0.4.0
• Note the benchmark setup is dirty but should be directionally correct.

Proposed Improvements

Improvements

1. Zero heap allocations

   • PoC: PR perf: zero-heap-allocation Poseidon hash path #64, perf/zero-alloc-poseidon
   • Gain: 11.77 -> 8.91 us (-24%). Allocations per hash: 80 -> 0.
   • What changes:
     • Parameters are static arrays. Each constant is converted to Montgomery
       form at compile time instead of on every hasher construction.
     • The permutation state is a fixed-size stack array instead of a Vec
       rebuilt every round.
     • Byte inputs and outputs are converted directly, without intermediate
       big integers or vectors.
   • Why it is safe:
     • The constants have the same values. Only the time of their Montgomery
       conversion moves, from runtime to compile time, via the same reduction.
     • The permutation performs the same operations; only the containers
       change.
     • Hash outputs match vectors frozen from main across all widths and
       both endiannesses.
     • The signatures solana-poseidon uses are unchanged.

2. Sparse MDS for partial rounds

   • PoC: worktree-poseidon-perf-followups (82e88a1, 6a285aa)
   • Gain: width 3 8.91 -> 6.73 us (-24%), width 13 123.76 -> 34.64 us (-72%).
     A partial round costs 2W - 1 multiplications instead of W^2.
   • Why it is safe:
     • The rewrite is two exact identities over the field: M = M_sparse * M',
       where M' commutes with the partial-round S-box, and round-constant
       folding.
     • The sparse constants are derived from the existing parameters and
       checked against the matrix identities.
     • Tested equal to the dense path across all widths.
     • The public API is unchanged. Custom parameters keep the old path.
   • References:
     • Same factorization as Filecoin's neptune
       (https://github.com/filecoin-project/neptune) and circomlib's
       optimized Poseidon, which uses precomputed S/P matrices
       (https://github.com/iden3/circomlib/blob/master/circuits/poseidon.circom).
     • Round numbers are from the Poseidon paper,
       https://eprint.iacr.org/2019/458.

3. Const-generic width ([F; W] instead of runtime-width slices)

   • PoC: exp/poseidon-perf 622b4cf (bench only)
   • Gain: 6.82 -> 5.70 us (-16.5%), from fewer bounds checks and unrolled
     loops.
   • Why it is safe: mechanical. The algorithm and the order of operations
     stay the same; only the container type changes. The public API keeps its
     runtime width.

4. sum_of_products for MDS rows

   • PoC: exp/poseidon-perf 622b4cf
   • Gain: -10.6% on sparse rows, -2.3% on full MDS rows.
   • Why it is safe: arkworks' sum_of_products computes the same dot product
     mod p with fewer modular reductions. Reduction does not change the field
     element. BN254 qualifies for the fast path. Requires fixed-size arrays,
     so it depends on item 3.
   • References:
     • Adapted from zkcrypto/bls12_381 PR #84 by str4d
       (Use interleaving to improve performance of G2 arithmetic and pairings zkcrypto/bls12_381#84).
     • gnark's no-carry Montgomery multiplication,
       https://hackmd.io/@gnark/modular_multiplication.

5. Final round computes lane 0 only

   • PoC: exp/poseidon-perf 622b4cf
   • Gain: -0.9%.
   • Why it is safe: mechanical. The hash returns state[0], so the final
     round's MDS output for lanes 1..W is discarded.

6. Concretely-compiled BN254 permutation, selected by TypeId

   • PoC: worktree-poseidon-perf-followups 335b3c2 (src/bn254.rs)
   • Gain: width 3, 5.58 -> 5.07 us (-9%) on top of items 3-5. Byte-identical
     code measures 5.60 us generic against 4.90 us concrete, so the
     genericity itself costs ~12% of a hash.
   • Why it is needed: rustc's MIR inliner runs before monomorphization, so
     <F as Field>::square through a type parameter is not inlinable.
     LLVM's cost model then keeps the wide Montgomery bodies as outline
     calls, and the state round-trips through memory between them. Concrete
     Fr code inlines everything (~2800 instructions, no calls).
   • Why it is safe:
     • Selection is TypeId equality, which is a compile-time constant for
       a concrete caller; any other field takes the generic path, unchanged.
     • The concrete core is the same algorithm statement for statement. A
       unit test runs every bundled width through both cores, with and
       without the sparse factorization, and requires agreement.
     • The public API is unchanged.
   • Caveat: the concrete core duplicates the generic one. If the
     permutation changes, both copies change; the parity test covers this.

7. ark-ff asm feature on x86_64

   • PoC: none. It cannot be measured on arm64.
   • Expected: 5-15% on field multiplication. Validators run x86_64.
   • Why it is safe: an arkworks feature flag with the same arithmetic.

8. arkworks 0.5 -> 0.6 (optional)

   • PoC: chore/arkworks-0.6 720adb0
   • Gain: -0.5% to -1.3%.
   • Why it is safe: no source change; outputs unchanged.
   • Caveat: semver-breaking. arkworks types are in the public API, so
     solana-poseidon and Agave must bump in the same step. Only tested
     stacked on item 2, not on main directly.