Tiny optimization #247

sipa commented at 6:39 PM on May 5, 2015: contributor

No description provided.

Tiny optimization a1d5ae1527

sipa force-pushed on May 5, 2015

apoelstra commented at 8:45 PM on May 5, 2015: contributor

Tested ACK

ghost commented at 9:06 PM on May 5, 2015: none

@apoelstra, can i ask what your test procedure was/if there were benchmarks you ran? i want to test this, but i'm not sure if i need to run many runs to see the performance gain (or if you just did a make check)

sipa commented at 9:43 PM on May 5, 2015: contributor

Performance improvement is very hard to measure (use bench_internal, look for group_add_affine, and make sure your cpu is locked to a single frequency), but seems to be around 0.2% (1ns) per group addition, or around 0.02% (16ns) per ECDSA signature. Seriously, performance isn't the reason - just simpler code.

apoelstra commented at 10:01 PM on May 5, 2015: contributor

@faizkhan00 I ran my usual correctness tests: make check, valgrind ./tests 1, the rust-secp256k1 unit tests. I did not expect to be able to measure a perf improvement in this case so I didn't even try :)

ghost commented at 10:23 PM on May 5, 2015: none

Ah okay, thanks for the explanation on this. I think I understand now, thanks :)

gmaxwell commented at 10:59 PM on May 5, 2015: contributor

ACK.

ghost commented at 11:39 PM on May 5, 2015: none

Tested ACK (thanks @apoelstra), but Valgrind reports several thousand errors in the default mode. I'm not seeing leaks, just reachable memory after exit:

==1162== HEAP SUMMARY:
==1162==     in use at exit: 1,344 bytes in 10 blocks
==1162==   total heap usage: 7,040 allocs, 7,030 frees, 21,556,468 bytes allocated
==1162== 
==1162== LEAK SUMMARY:
==1162==    definitely lost: 0 bytes in 0 blocks
==1162==    indirectly lost: 0 bytes in 0 blocks
==1162==      possibly lost: 0 bytes in 0 blocks
==1162==    still reachable: 1,344 bytes in 10 blocks
==1162==         suppressed: 0 bytes in 0 blocks

gmaxwell commented at 11:51 PM on May 5, 2015: contributor

but Valgrind reports several thousand errors in the default mode. I'm not seeing leaks, just reachable memory after exit:

Yea not our problem; turn off cross-checking with libcrypto in the tests. Thats OpenSSL's inadvisable construction. (turn off ENABLE_OPENSSL_TESTS and HAVE_LIBCRYPTO in the config.h).

dcousens commented at 11:52 PM on May 5, 2015: contributor

To clarify:

2 * (1 - a->infinity) results in 2 or 0 based on infinity. But the reason you haven't just side-stepped the entire process at the start was so that it is constant time?

gmaxwell commented at 11:55 PM on May 5, 2015: contributor

@dcousens Right; and "correctly computing" in the infinity case is not needed anymore after my prior change; because the cmov just overwrites the output if it was infinity instead of counting on it to be zero.

dcousens commented at 11:58 PM on May 5, 2015: contributor

@gmaxwell cheers, ACK.

ghost commented at 12:02 AM on May 6, 2015: none

@gmaxwell ah, thanks- I double checked the output of valgrind and I see those errors are all from either libcrypto or libgmp, thanks again for the clarification there.

gmaxwell commented at 12:11 AM on May 6, 2015: contributor

Hm. There shouldn't be any related to libgmp. I'm interested in that.

ghost commented at 12:30 AM on May 6, 2015: none

Ah, I should have been more specific- the actual errors were still due to the openssl construction (ie test_ecdsa_openssl), but openssl is linked against libgmp and that seems to be the starting point for some of the memory problems, for example:

==5408== Conditional jump or move depends on uninitialised value(s)
==5408==    at 0x4E862B6: __gmpn_hgcd2 (in /usr/lib/libgmp.so.10.2.0)
==5408==    by 0x4E81EFE: __gmpn_gcdext_lehmer_n (in /usr/lib/libgmp.so.10.2.0)
==5408==    by 0x4E80B16: __gmpn_gcdext (in /usr/lib/libgmp.so.10.2.0)
==5408==    by 0x406DB9: secp256k1_num_mod_inverse (num_gmp_impl.h:127)
==5408==    by 0x409A6A: secp256k1_scalar_inverse_var (scalar_impl.h:246)
==5408==    by 0x40F8C6: secp256k1_ecdsa_sig_verify.part.29 (ecdsa_impl.h:146)
==5408==    by 0x41B499: test_ecdsa_openssl (tests.c:2035)
==5408==    by 0x401134: run_ecdsa_openssl (tests.c:2050)
==5408==    by 0x401134: main (tests.c:2143)

In case you're curious here's my log: http://pastebin.com/uKtJxJF2 but basically you were spot on about openSSL/libGMP being the primary offender here&

gmaxwell commented at 1:06 AM on May 6, 2015: contributor

Ah yep. Thats expected due to the use of undefined behavior in the OpenSSL RNG. thanks!

ghost commented at 5:09 AM on May 6, 2015: none

Hehe, maybe next time we can anticipate a more exciting result..

sipa merged this on Jun 13, 2015

sipa closed this on Jun 13, 2015

sipa referenced this in commit 91eb0da155 on Jun 13, 2015