Achieve competitive performance on x86_64

[mkannwischer]

We strive for competitive performance. For x86_64 a baseline is the Dilithium team's AVX2 implementation available at https://github.com/pq-crystals/dilithium/tree/master/avx2
We should match that performance.

Here are some benchmarks of that implementation:
CPU: Intel Sapphire Rapids Xeon Platinum 8488C (AWS EC2, c7i.metal-24xl)
SMT: Disabled (echo off | sudo tee /sys/devices/system/cpu/smt/control )
TurboBoost: Disabled (echo 1 | sudo tee /sys/devices/system/cpu/intel_pstate/no_turbo)
Compiler: gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Compilation flags: -march=native -mtune=native -O3

Benchmarking code: https://github.com/pq-crystals/dilithium/blob/master/ref/test/test_speed.c
Iterations: 10000 (#define NTESTS 10000)

Below are the keygen/sign/verify benchmarks. For the full benchmarks see the attached files

Dilithium2

Keypair:
median: 73596 cycles/ticks
average: 74205 cycles/ticks

Sign:
median: 172068 cycles/ticks
average: 214186 cycles/ticks

Verify:
median: 75666 cycles/ticks
average: 78043 cycles/ticks

Dilithium3

Keypair:
median: 127448 cycles/ticks
average: 129274 cycles/ticks

Sign:
median: 289940 cycles/ticks
average: 348492 cycles/ticks

Verify:
median: 125406 cycles/ticks
average: 125750 cycles/ticks

Dilithium5

Keypair:
median: 200636 cycles/ticks
average: 204270 cycles/ticks

Sign:
median: 366312 cycles/ticks
average: 426632 cycles/ticks

Verify:
median: 198418 cycles/ticks
average: 200015 cycles/ticks

speed2.txt
speed3.txt
speed5.txt

[mkannwischer]

Here is our current performance (including native Keccak from #302, and adjusted bencharking from #307).
Same platform and configuration (in particular NTESTS=1, NWARMUP=0, NITERATIONS=10000)

./scripts/tests bench -c PMU --cflags "-march=native -mtune=native -O3

ML-DSA-44

INFO  > Benchmark          ML-DSA-44   (native opt):     make run_bench_44
INFO  > Benchmark          ML-DSA-44   (native opt):     test/build/mldsa44/bin/bench_mldsa44
   keypair cycles = 102580
      sign cycles = 366215
    verify cycles = 99831

ML-DSA-65

INFO  > Benchmark          ML-DSA-65   (native opt):     make run_bench_65
INFO  > Benchmark          ML-DSA-65   (native opt):     test/build/mldsa65/bin/bench_mldsa65
   keypair cycles = 224941
      sign cycles = 610618
    verify cycles = 162640

ML-DSA-87

INFO  > Benchmark          ML-DSA-87   (native opt):     make run_bench_87
INFO  > Benchmark          ML-DSA-87   (native opt):     test/build/mldsa87/bin/bench_mldsa87
   keypair cycles = 252407
      sign cycles = 728542
    verify cycles = 240790

[mkannwischer]

For reference I also benchmarked the reference implementation on the same platform:

Dilithium2

Keypair:
median: 688550 cycles/ticks
average: 692142 cycles/ticks

Sign:
median: 1871416 cycles/ticks
average: 2238790 cycles/ticks

Verify:
median: 718710 cycles/ticks
average: 722444 cycles/ticks

Dilithium3

Keypair:
median: 450440 cycles/ticks
average: 452423 cycles/ticks

Sign:
median: 1367060 cycles/ticks
average: 1700027 cycles/ticks

Verify:
median: 417340 cycles/ticks
average: 418736 cycles/ticks

Dilithium5

Keypair:
median: 253638 cycles/ticks
average: 254408 cycles/ticks

Sign:
median: 898486 cycles/ticks
average: 1170765 cycles/ticks

Verify:
median: 278030 cycles/ticks
average: 278784 cycles/ticks

speed2_ref.txt
speed3_ref.txt
speed5_ref.txt

Full benchmark files attached

[mkannwischer]

The following functions have native implementations in the Dilithium AVX2 code:

AVX2 assembly:

• poly_ntt
• poly_invntt_tomont
• poly_pointwise_montgomery
• polyvecl_pointwise_acc_montgomery

AVX2 intrinsics:

• poly_reduce
• poly_caddq
• poly_add
• poly_sub
• poly_shiftl
• poly_power2round
• poly_decompose
• poly_make_hint
• poly_use_hint
• poly_chknorm
• rej_uniform
• rej_eta
• polyz_unpack
• polyw1_pack

[mkannwischer]

I ran the benchmarks again in #483 (which also includes #414):

with

#define NWARMUP 3
#define NITERATIONS 5
#define NTESTS 10000

./scripts/tests bench -c PMU --cflags "-march=native -mtune=native -O3" --opt opt
INFO  > Benchmark          Compile     (native opt):     CFLAGS=-march=native -mtune=native -O3 make bench OPT=1 AUTO=1 CYCLES=PMU -j48
INFO  > Benchmark          ML-DSA-44   (native opt):     make run_bench_44
INFO  > Benchmark          ML-DSA-44   (native opt):     test/build/mldsa44/bin/bench_mldsa44
   keypair cycles (avg) = 58448
      sign cycles (avg) = 241159
    verify cycles (avg) = 69016

           percentile      1     10     20     30     40     50     60     70     80     90     99
   keypair percentiles:  57016  58067  58210  58283  58341  58396  58454  58522  58622  59174  59993
      sign percentiles: 102827 103280 104281 141549 150261 187338 225772 270696 343870 443941 812172
    verify percentiles:  68324  68517  68620  68704  68782  68865  68963  69084  69293  69735  70748

INFO  > Benchmark          ML-DSA-65   (native opt):     make run_bench_65
INFO  > Benchmark          ML-DSA-65   (native opt):     test/build/mldsa65/bin/bench_mldsa65
   keypair cycles (avg) = 104007
      sign cycles (avg) = 386748
    verify cycles (avg) = 111596

           percentile      1     10     20     30     40     50     60     70     80     90     99
   keypair percentiles: 103184 103453 103569 103658 103741 103824 103920 104065 104384 104862 105618
      sign percentiles: 157302 157991 206450 218572 267696 317445 368362 438729 537682 7207641351397
    verify percentiles: 110755 110998 111112 111208 111298 111398 111526 111723 112070 112494 113312

INFO  > Benchmark          ML-DSA-87   (native opt):     make run_bench_87
INFO  > Benchmark          ML-DSA-87   (native opt):     test/build/mldsa87/bin/bench_mldsa87
   keypair cycles (avg) = 158938
      sign cycles (avg) = 454589
    verify cycles (avg) = 166152

           percentile      1     10     20     30     40     50     60     70     80     90     99
   keypair percentiles: 157038 157866 158436 158602 158734 158858 159011 159242 159596 159971 160808
      sign percentiles: 232772 233792 234702 301685 317580 384751 437168 501354 618844 7869631413879
    verify percentiles: 165135 165383 165514 165628 165752 165910 166140 166438 166706 167043 169299

All good!

Algorithm	Operation	mldsa-native	pqcrystals	Improvement
ML-DSA-44/Dilithium2	Keypair	58,448	74,205	21.2% faster
ML-DSA-44/Dilithium2	Sign	241,159	214,186	-12.6% slower
ML-DSA-44/Dilithium2	Verify	69,016	78,043	11.6% faster
ML-DSA-65/Dilithium3	Keypair	104,007	129,274	19.5% faster
ML-DSA-65/Dilithium3	Sign	386,748	348,492	-11.0% slower
ML-DSA-65/Dilithium3	Verify	111,596	125,750	11.3% faster
ML-DSA-87/Dilithium5	Keypair	158,938	204,270	22.2% faster
ML-DSA-87/Dilithium5	Sign	454,589	426,632	-6.6% slower
ML-DSA-87/Dilithium5	Verify	166,152	200,015	16.9% faster

There is still a 7 - 13% gap for signing.

[jammychiou1]

Here's the benchmark results on my laptop.

Machine spec

CPU: 13th Gen Intel(R) Core(TM) i5-1340P
SMT: Disabled
TurboBoost: Disabled
Compiler: gcc (GCC) 15.2.1 20250808 (Red Hat 15.2.1-1)

mldsa-native

Configuration: Same as #303 (comment)

$ ./scripts/tests bench -c PMU --cflags "-march=native -mtune=native -O3" --opt OPT
INFO  > Benchmark          Compile     (native opt):     CFLAGS=-march=native -mtune=native -O3 make bench OPT=1 AUTO=1 CYCLES=PMU -j12
INFO  > Benchmark          ML-DSA-44   (native opt):     make run_bench_44
INFO  > Benchmark          ML-DSA-44   (native opt):     test/build/mldsa44/bin/bench_mldsa44
   keypair cycles (avg) = 91993
      sign cycles (avg) = 316105
    verify cycles (avg) = 100939

           percentile      1     10     20     30     40     50     60     70     80     90     99
   keypair percentiles:  89071  91100  91318  91444  91537  91623  91707  91826  92541  93482  94267
      sign percentiles: 145882 146351 148133 196293 243577 256421 305244 363660 422898 5502651041976
    verify percentiles:  99927 100167 100277 100379 100466 100572 100692 100910 102001 102417 103225

INFO  > Benchmark          ML-DSA-65   (native opt):     make run_bench_65
INFO  > Benchmark          ML-DSA-65   (native opt):     test/build/mldsa65/bin/bench_mldsa65
   keypair cycles (avg) = 161035
      sign cycles (avg) = 520667
    verify cycles (avg) = 163981

           percentile      1     10     20     30     40     50     60     70     80     90     99
   keypair percentiles: 159275 159628 159780 159905 160067 160244 160486 161389 161770 162264 164741
      sign percentiles: 224440 226316 288336 304088 367187 430349 495941 585052 713990 9776201682641
    verify percentiles: 162468 162766 162963 163132 163278 163498 163916 164604 164982 165394 167050

INFO  > Benchmark          ML-DSA-87   (native opt):     make run_bench_87
INFO  > Benchmark          ML-DSA-87   (native opt):     test/build/mldsa87/bin/bench_mldsa87
   keypair cycles (avg) = 266011
      sign cycles (avg) = 661006
    verify cycles (avg) = 267497

           percentile      1     10     20     30     40     50     60     70     80     90     99
   keypair percentiles: 261299 263727 264445 264880 265363 265874 266331 266735 267132 267867 272178
      sign percentiles: 353716 355851 357217 445476 465340 554171 643822 734489 86546011351212042290
    verify percentiles: 264869 265626 266028 266497 266987 267389 267679 268012 268395 268988 272547

All good!

pqcrystals

Configuration: Same as #303 (comment)

$ make CFLAGS="-march=native -mtune=native -O3" speed; for i in 2 3 5; do echo Dilithium $i; ./test/test_speed$i | tee speed$i.txt | tail -n 12; done;
make: Nothing to be done for 'speed'.
Dilithium 2
Keypair:
median: 94399 cycles/ticks
average: 94889 cycles/ticks

Sign:
median: 212642 cycles/ticks
average: 266172 cycles/ticks

Verify:
median: 94992 cycles/ticks
average: 95702 cycles/ticks

Dilithium 3
Keypair:
median: 165288 cycles/ticks
average: 166029 cycles/ticks

Sign:
median: 354443 cycles/ticks
average: 421564 cycles/ticks

Verify:
median: 160564 cycles/ticks
average: 161080 cycles/ticks

Dilithium 5
Keypair:
median: 265048 cycles/ticks
average: 265949 cycles/ticks

Sign:
median: 461687 cycles/ticks
average: 534053 cycles/ticks

Verify:
median: 257702 cycles/ticks
average: 258886 cycles/ticks

speed2.txt
speed3.txt
speed5.txt

Comparison

Algorithm	Operation	mldsa-native	pqcrystals	Improvement
ML-DSA-44/Dilithium2	Keypair	91993	94889	3.1% faster
ML-DSA-44/Dilithium2	Sign	316105	266172	-18.8% slower
ML-DSA-44/Dilithium2	Verify	100939	95702	-5.5% slower
ML-DSA-65/Dilithium3	Keypair	161035	166029	3.0% faster
ML-DSA-65/Dilithium3	Sign	520667	421564	-23.5% slower
ML-DSA-65/Dilithium3	Verify	163981	161080	-1.8% slower
ML-DSA-87/Dilithium5	Keypair	266011	265949	-0.0% slower
ML-DSA-87/Dilithium5	Sign	661006	534053	-23.8% slower
ML-DSA-87/Dilithium5	Verify	267497	258886	-3.3% slower

The gaps for signing are considerably larger.