Faster curve25519 implementation for ntor
Floodberry's curve25519 implementations at https://github.com/floodyberry/curve25519-donna are mostly C, and claim to be faster still than the ones we're using now, especially on intel cpus. We should evaluate them and consider switching.
Also, if we find an ed25519 implementation we like and wind up using it, we should evaluate using its component pieces to build an optimized curve25519 implementation for calculations on the base point as per http://www.imperialviolet.org/2013/05/10/fastercurve25519.html ; Adam has some example code based on one of the amd64 assembly implementations.
Activity
changed milestone to %Tor: unspecified
Trac:
Parent: N/A to #9657 (moved)
Trac:
Parent: #9657 (moved) to #9662 (moved)-
The "optimized basepoint multiply" part is now #9663 (moved). This ticket is only about "use a faster curve25519".
-
This and the #9663 (moved) changes together save 28% of the runtime for the server side of the ntor handshake when built with gcc 4.7 on my 64-bit laptop (136 vs 175 usec); 18% when built with clang (177 vs 213 usec); and 22% (155 vs 200 usec) when built with gcc 4.2-llvm. (yeah, yeah, I know, we should be using CPU counters. That's another issue.)
Note that using a recent gcc gets a pretty big performance boost in and of itself with this code.
My review of the ticket8897_9663_v2 branch at https://trac.torproject.org/projects/tor/ticket/9663#comment:4 also covers this ticket.
-
Based on profile information from #11332 (moved), maybe we should let this take a back-seat for a while.
Having a look at Andrea's results in "tor-58f4200789d0cc47ebd88f3091207cf4dd493573-profile-run.gprof.txt", I see 7956 calls to onion_skin_ntor_server_handshake vs 78824 to onion_skin_TAP_server_handshake(). But curve25519_donna accounts for less than .01% of total runtime. If we imagine that we replaced all of the TAP handhakes with ntor handshakes, that would still be only about 0.07% of runtime.
Possibly it's just not worth our time to optimize this stuff right now.
-
Sounds plausible. We in part wanted a faster ntor implementation for the future where the botnet upgraded its clients -- but that future hasn't appeared yet, and it's been a while, so hey.
Seems like if we want to optimize handling of create cells, we'd get a lot more mileage out of making #9682 (moved) happen.
-
(To be clearer, the optimization here is for the cpuworker threads, and the optimization in #9682 (moved) is for the main thread. We could process many more ntor cells if we could get them to cpuworkers more efficiently.)
Has anyone (apart from me) benchmarked this stuff recently in isolation from #9663 (moved)?
On a i5-4250U (TurboBoost etc), I get:
- Andrew M. SSE2 (
-O3 -m64 -DCURVE25519_SSE2): 203194 ticks (clang: 160530 ticks) - Andrew M. (
-O3 -m64): 125878 ticks (clang: 136594 ticks) - agl c64 (
-O3 -m64): 134442 ticks (clang: 150482 ticks)
This is compiling with gcc 5.1.0, clang 3.6.1. On x86_64 this doesn't feel worth it at all, especially considering that anyone who cares about Curve25519 performance is going to probably be hosting a high traffic HS, and should be on something modern with a 64 bit processor.
How much do we care about 32 bit performance for this sort of thing anyway?
- Andrew M. SSE2 (
-
I think I benchmarked this stuff a tiny bit, long long ago. I think 32-bit performance is mostly nice-to-have, but not critical. A performance improvement that only helps with 64 bit is fine.
The numbers you give for the
-m64cases seem like they're a 7-10% improvement in curve25519 processing time. I agree that's not necessarily low-hanging fruit for 0.2.7, but it doesn't mean we should write it off permanently. 7% here and 7% there can add up to real savings in the long run.That said, I'm not going to call this a critical optimization. :)
So, some researchers went and did an AVX2 Curve25519 implementation.
http://link.springer.com/chapter/10.1007/978-3-319-22174-8_18?no-access=true (Paywall)
Having read the paper, when they say "slight" they mean it (a few percent over djb's amd64 assembly), and their code isn't available. Their work should be applicable to AVX512 but since that's still Xeon only even with Skylake, I'm inclined to also leave this to a "if we get really desperate" sort of thing.
(Key generation gets more of a boost, but we already have faster code there.)
This also looks promising, though it's modern intel optimized.
http://csrc.nist.gov/groups/ST/ecc-workshop-2015/presentations/session6-chou-tung.pdf https://www.win.tue.nl/~tchou/sandy2x/
Public domain.
Trac:
Reviewer: N/A to N/Amentioned in issue #9662 (moved)
mentioned in issue #9663 (moved)
mentioned in issue #12464 (moved)
mentioned in issue #15463 (moved)
moved to tpo/core/tor#8897 (closed)