Subject: [Cfrg] Benchmarks: 384 vs 389 vs Goldilocks vs ... on Haswell

From: Mike Hamburg <[email-masked]>
Date: Mon, 29 Dec 2014 15:14:17 -0800

Hi all,

The chairs requested that I implement and benchmark 2^389 - 21, 
suggested by Ilari.

I've benchmarked several primes that have been discussed on this list.  
I used a Haswell machine running Linux test everything, including MSR 
ECCLib 1.1.  Cycle counts for mul/sqr:

MSR ECCLib (all asm, but no BMI2):
P256-mers: M = 59.2, S = 47.8.
P384-mers: M = 117.5, S = 89.8.
P512-mers: M = 199.9, S = 140.6.

My code (C with BMI2 mul+acc intrinsics):
P389: M = 112.5, S = 75.5.
Goldilocks P448: M = 118.0, S = 88.9.
Ridinghood P480: M = 118.2, S = 89.1.
NIST P521: M = 145.5, S = 110.7.

With this machine/compiler combination, 2^389 - 21 is showing at about 
8-9% faster than MSR 384-mers and Goldilocks, which are within 0.1% of 
each other.

CPU:
Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz .

Compiler:
Ubuntu clang version 3.5-1ubuntu1 (trunk) (based on LLVM 3.5)
Target: x86_64-pc-linux-gnu
Thread model: posix

Notes:

* All benchmarks computed by timing and multiplying by 3.5932GHz, since 
that's what calib() spat out.

* The P389 code is mul-after-add clean.  I did this by multiplying the 
arguments to a multiply separately by 8 and 21.  The code without this 
feature is marginally (<1%) faster.

* I haven't tested the correctness of the P389 code, nor have I built it 
into a curve.  So sue me, I'm on vacation.

* ECCLib, P389*, P448: 10^8 trials, noinline'd functions, 
32-byte-aligned stack buffers, no dependencies in the multiplications.  
TurboBoost and HyperThreading disabled. Benchmarks are stable to about 3 
significant figures.

* P480, P521, because I'm lazy: Goldilocks `make bench`, 10^8/2 trials, 
noinlined functions, 32-byte-aligned stack buffers, no dependencies.  
Almost exactly consistent when benchmarking P448.

* For MSR ECCLib I called directly into ecc384.o's functions, using the 
same benchmarking framework code as for P389.

* Earlier, offlist testing on a Haswell MacBook Air showed about a 2% 
advantage to 2^389 - 21 instead of 8%.  The code improvements to P389 
since then are not sufficient to explain the better results: they are 
apparently machine/compiler dependent.  I thought that Clang 3.5 might 
be responsible, since I've seen performance differences in arithmetic 
code with it.  But clang-3.3, 3.4 and 3.5 all give similar results for 
those primes.  GCC 4.9 gives slightly worse results for everything but 
the MSR asm code.

* The P389 code is probably less tuned than its competitors. The MS code 
is written in pure asm, but it doesn't take advantage of BMI2. The 
Goldilocks and P389 code are C with an asm multiply/accumulate 
intrinsic, but I spent more time tuning the Goldilocks code.

* The Ridinghood code is the same as the Goldilocks code with different 
shift constants.  The P-521 code is the arch_x86_64_r12 version, using 9 
limbs vector-aligned to a 12-word structure.

* I have no data about 2^389 - 21 on other platforms, but offlist 
discussions suggest that it will be OK, if perhaps annoying to 
implement, on 32-bit platforms.

Cheers,
-- Mike

---

From: "Paterson, Kenny" <[email-masked]>
Date: Wed, 31 Dec 2014 20:01:43 +0000

Hi Mike,

Thanks a lot for doing this work, especially over the holiday season -
it's much appreciated.

My take-away from your work is that there's no strong reason (in
performance terms) to prefer P389 over P384-mers or vice-versa - the 8-9%
difference is there, yes, but could easily disappear or increase with
further optimisations on either side.

Does that seem fair to you? Please feel free to give an alternative
interpretation if you like.

Regards,

Kenny 

On 29/12/2014 23:14, "Mike Hamburg" <[email-masked]> wrote:

>
>
>
>Hi all, 
>
>The chairs requested that I implement and benchmark 2^389 - 21, suggested
>by Ilari.
>
>I've benchmarked several primes that have been discussed on this list.  I
>used a Haswell machine running Linux test everything, including MSR
>* ECCLib, P389*, P448: 10^8 trials, noinline'd functions, 32-byte-aligned
>stack buffers, no dependencies in the multiplications.  TurboBoost and
>HyperThreading disabled.  Benchmarks are stable to about 3 significant
>figures.
>
>
>apparently machine/compiler dependent.  I thought
> that Clang 3.5 might be responsible, since I've seen performance
>differences in arithmetic code with it.  But clang-3.3, 3.4 and 3.5 all
>give similar results for those primes.  GCC 4.9 gives slightly worse
>results for everything but the MSR asm code.
>
>Goldilocks and P389 code are C with an asm multiply/accumulate intrinsic,
>but I spent more time tuning the Goldilocks
> code. 
>
>discussions suggest that it will be OK, if perhaps annoying to implement,
>on 32-bit platforms.
>
>Cheers, 
>-- Mike
>
>

---

From: Watson Ladd <[email-masked]>
Date: Wed, 31 Dec 2014 16:01:55 -0500

> further optimisations on either side.

Would you say the same about 2^255-19 vs 2^256-189? That also had a 8%
performance increase iirc, for very similar reasons.

 One could also try 2^382-31, which would be much more similar to the
gain at the lower security level.

Furthermore, if the faster one was more optimized, and the slower one
not as much, that would be a reasonable conclusion. But we are
comparing a C implementation written yesterday to a handwritten
assembler one, with the C outperforming the assembly. Now, with
SUPERCOP, we could measure the fastest one on each machine, across
compilers and implementations.  That unfortunately isn't going to
happen in time, and regrettably the NUMS group did not make ECClib
into a SUPERCOP submission earlier. Having screwed up plenty of
benchmarks myself through stupid things, SUPERCOP is a really good
idea to force oneself to measure the right thing.

There is a theoretical reason to think that a carryless prime will
outperform a slightly larger packed one, and that is the algorithm one
uses for packed arithmetic will work with any c that isn't bigger than
the word, so the packed implementation could be adapted for the
unpacked case.

Sincerely,
Watson Ladd

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Michael Hamburg <[email-masked]>
Date: Wed, 31 Dec 2014 14:18:25 -0800

Hi Kenny,

I think that the differences on Haswell are probably real, but I suspect that most people on this list won’t be convinced by a <10% performance difference.  On other architectures, it may depend on how unfavorable packed arithmetic is.  So on ARM scalar, the 384-bit prime is probably OK, but on ARM NEON the 389-bit one will probably be better.  It’d be kind of nice to get actual numbers on the subject, though, instead of wishy-washy speculation.

I’m still a little bit perplexed about why you asked me to do this exercise.  The argument at the WF128 level seems to be about the existing trust and deployment of Curve25519 compared to a “rigidly-generated” ed-256-mers.  At the WF192 and WF256 levels, there are no widely deployed “safe" curves, and it is between this same notion of “rigidity” vs more “efficient” curves such as Curve41417, Ed448-Goldilocks and E-521.  [Scarequoted because it’s MSR's definition of rigidity, DJB and Tanja’s safety criteria, and Trevor’s and my efficiency metric.]

Is the introduction of another efficient curve near WF192 suggested to sway the rigidity camp’s opinion about any of these proposals?  Especially with people so sick of the endless arguments that they’re cutting backroom deals?

If you think data has a chance of moving things forward, I suggest that benchmarks of the Microsoft curves’ (or at least primes’) performance on ARM scalar/NEON would be more informative, because they’d help determine whether the efficiency camp’s curves are broadly more efficient and by how much.

Cheers,
— Mike

> On Dec 31, 2014, at 12:01 PM, Paterson, Kenny <[email-masked]> wrote:
> 
> Hi Mike,
>