Skip to content

perf: faster Fp.add/sub with branchless reduction #60

Description

@MatteoMer

Problem

Fp.add at 4.6-5.7ns vs arkworks' 3-4ns (~40% gap). The conditional modular reduction likely causes branch misprediction overhead.

Approach

Replace conditional branch with branchless reduction:

  • x86 ASM using sbb to generate mask + cmov chain for conditional subtraction
  • Or: always subtract modulus, use carry flag to select result (sbb + cmov)
  • Ensure no unnecessary loads/stores around the operation

Impact

Add/sub are called even more frequently than mul (every field operation involves adds for Karatsuba cross-terms, point coordinate updates, etc.). A 30% improvement compounds significantly.

Files

  • src/field/mod.zigMontgomeryField.add(), .sub(), .addNoReduce(), .reduce()

Benchmark baseline

  • Fp.add: 4.6-5.7 ns/op
  • Target: 3-4 ns/op

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions