Unroll secp256k1_fe_(get|set)_b32 to make them much faster. #437

pull gmaxwell wants to merge 3 commits into bitcoin-core:master from gmaxwell:fe_getter_setter_speedup changing 3 files +110 −44

gmaxwell commented at 2:05 AM on January 10, 2017: contributor

fe_get_b32 was taking 7 times longer than a fe_sqr due to working two bits at a time.

Rico666 on Bitcointalk noticed this and provided a patch for 5x52, I formatted it and wrote the rest.

This is perhaps a 0.5% speedup for ecdsa_verify using 32bit field code.
sipa commented at 9:30 PM on January 18, 2017: contributor

I believe that the benchmark results are due to the entire loop being optimized out (reducing the iteration count increases the timings proportionally).
Kulme referenced this in commit 4289dcca1c on Jan 21, 2017
sipa commented at 8:56 AM on February 17, 2017: contributor

Can you adapt the benchmark so it's not optimized away?

Unroll secp256k1_fe_(get|set)_b32 for 5x52.

field_get_b32: min 0.647us / avg 0.666us / max 0.751us
field_set_b32: min 0.551us / avg 0.571us / max 0.624us

becomes

field_get_b32: min 0us / avg 0.0000000477us / max 0.000000238us
field_set_b32: min 0us / avg 0.0000000238us / max 0.000000238us

(Patch from https://bitcointalk.org/index.php?topic=1740973.0
 _get was reversed from the patch because this order appeared
 somewhat faster in testing.)

Signed-off-by: Gregory Maxwell <greg@xiph.org>

aa8499080e

Unroll secp256k1_fe_(get|set)_b32 for 10x26.

field_get_b32: min 0.890us / avg 0.905us / max 0.956us
field_set_b32: min 1.12us / avg 1.15us / max 1.19us

becomes

field_get_b32: min 0us / avg 0.000000119us / max 0.000000238us
field_set_b32: min 0.0532us / avg 0.0584us / max 0.0782us

8b7680a826

gmaxwell commented at 12:03 AM on April 24, 2017: contributor

I stripped the benchmarks out.
Fix benchmark print_number infinite loop. a2b6b1914f
sipa commented at 10:31 PM on April 25, 2017: contributor
Benchmarked bench_verify with GMP disabled on a i7-6820HQ CPU, pegged to 2.6GHz.
- master: 97.7μs (64-bit), 366μs (32-bit).
- this PR: 97.5μs (64-bit), 365μs (32-bit).
So a 0.2% (64-bit) and 0.3% improvement (32-bit).
sipa commented at 11:19 PM on April 25, 2017: contributor

utACK a2b6b19
sipa merged this on Apr 25, 2017
sipa closed this on Apr 25, 2017
sipa referenced this in commit 4cc8f52505 on Apr 25, 2017

Contributors

gmaxwell

sipa