Neptune-Crypto / twenty-first / 36577269546

98%

Build Type

push

github

Committed by web-flow

Commit Message

Faster NTTs, polynomial arithmetic, and Tip5 hashing (#279)

Faster NTTs, polynomial arithmetic, and Tip5 hashing

Performance work driven by Triton VM's prover.
**NTT**
- Cache-blocked radix-4 transform with a tiled bit-reversal permutation:
fewer
  passes over memory.
- Scaling and zero-padding fused into the transform
(`scaled_zero_padded_ntt`,
`fast_coset_evaluate_into`), which also evaluates straight into
uninitialized
  memory.
- AVX-512 butterfly kernels, selected at runtime; scalar code everywhere
else.
- Parallel transforms of single long inputs (`par_ntt`, `par_intt`,
`par_scaled_zero_padded_ntt`).
**Polynomials**
- Quasi-linear parallel interpolation and evaluation via zerofier trees,
with
level-scheduled tree arithmetic and quasi-linear chunk-wise reduction.
- New parallel variants: `par_evaluate`, `par_scale`,
`par_fast_multiply`,
    `par_fast_coset_evaluate(_into)`, `par_fast_coset_interpolate`
`par_clean_divide`, `par_interpolate_with_zerofier_tree(_and_weights)`,
    `par_divide_and_conquer_batch_evaluate`, and more.
- `FiniteField::par_batch_inversion`; faster `XFieldElement` inversion.
  - Large polynomial buffers request transparent huge pages on Linux
    (`memory::advise_huge_pages`, `memory::vec_with_capacity`).

**Tip5**
- `hash_varlen_many` and `hash_pair_many` hash eight inputs at once with
AVX-512 (runtime-detected), using the fast MDS convolution; other
targets
  hash one input at a time as before.

**Breaking changes**
- `Tip5::round` is no longer public, but this was only ever exposed on
AVX512 builds so not relevant I think.
- `ntt::swap_indices` was removed.

Tested on Linux; clippy is clean for Linux, Windows, macOS (x86-64 and
ARM64),
and wasm32.

Coverage Stats

1276 of 1687 new or added lines in 14 files covered. (75.64%)

14 existing lines in 7 files now uncovered.

6193 of 6876 relevant lines covered (90.07%)

56848464.06 hits per line