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).