perf: Consider something like `pow2k`

[Yawning]

Both Invert and Pow22523 repeatedly square in a loop. The overhead of repeatedly calling Square (and having to shuffling data in/out of registers) adds up to a decent chunk of execution time.

Doing something like func (v *Element) pow2k(x *Element, k uint) with the precondition that k >= 1, dramatically improves performance of the two operations like thus:

Invert-4    11.3µs ± 0%   7.1µs ± 0%  -37.33%
Pow22523-4  11.1µs ± 0%   7.0µs ± 0%  -37.32%

Numbers taken with purego, but the amd64 assembly implementation will also benefit (and can be written without having to spill to the stack at all).

[FiloSottile]

I tried out implementing it as a simple loop of the Square body, manually inlining carryPropagate, and I don't see any improvement on high-level group functions. Are we missing some useful benchmark, or is this for an application that relies specifically on Invert and Pow22523?

[Yawning]

I tried out implementing it as a simple loop of the Square body, manually inlining carryPropagate, and I don't see any improvement on high-level group functions. Are we missing some useful benchmark, or is this for an application that relies specifically on Invert and Pow22523?

Point compression/decompression involve one Invert, and 1 SqrtRatio respectively. While it's true that those things aren't repeatedly called, a lot of the actual uses do involve doing both (eg: ref10-style Ed25519 signature verification).

[Yawning]

As another concrete example of where this would be nice would be ECVRF_prove from the VRF draft.

Benchmarking my (unpublished) edwards25519 based version, Invert + Pow22523 account for ~23.5% of the function's runtime (I can reduce this by shaving off 2 decompressions by checking point canonicity on the encoded buffer, but it still will be a decent fraction).

[AlexanderYastrebov]

(and can be written without having to spill to the stack at all)

This seems to be tricky as one needs 10 registers to hold intermediate results so there is not enough registers to store element limbs: https://github.com/oasisprotocol/curve25519-voi/blob/1f23a7beb09a352354cbd7277c6b7f0170cf6d5d/internal/asm/amd64/field_u64.go#L331