Skip to content

Latest commit

 

History

History
155 lines (124 loc) · 25.1 KB

BENCHMARKS.md

File metadata and controls

155 lines (124 loc) · 25.1 KB
Raw

The math in gf256 is very close to the hardware, and for each algorithm, there is usually more than one way to do things.

To make things more complicated, the best implementation depends on a number of things, such as what hardware is available (ie carry-less multiplication ), memory, and constant-time requirements.

To help with this, gf256 uses highly-configurable proc_macros to let users choose the best implementation for their purpose. More information about these macros can be found in README.md.

In order to choose a good default strategy for each algorithm, gf256 has a set of rudimentary benchmarks using Criterion. This lets us easily compare different implementation strategies on different hardware configurations.

It's important to note, these aren't the the most exhaustive benchmarks, and they haven't been ran on the most exhaustive set of hardware. Fortunately, even with rudimentary benchmarking, there's usually a pretty clear winner for each configuration. At least of the options available in gf256.

Feel free to run these benchmarks locally, to find the most performant implementation on your machine:

$ make bench

The following are the most recent results (which are probably already out-of-date). Bold results indicate the fastest implementation in their category.

Carry-less multiplication

AMD Ryzen-3975WX @ 6.3 GHz AMD Ryzen-3975WX @ 6.3 GHz (no-xmul) AMD FX-6300 @ 3.5 GHz AMD FX-6300 @ 3.5 GHz (no-xmul) Arm A72 @ 1.8 GHz Arm A72 @ 1.8 GHz (no-xmul) Arm A53 @ 1.4 GHz Arm A53 @ 1.4 GHz (no-xmul)
xmul/naive_xmul 16.406 ns 16.139 ns 37.017 ns 37.921 ns 97.731 ns 97.753 ns 229.35 ns 228.79 ns
xmul/hardware_xmul 999.84 ps 16.156 ns 3.4420 ns 36.596 ns 4.7512 ns 97.766 ns 9.3101 ns 228.76 ns

Galois-field multiplication

AMD Ryzen-3975WX @ 6.3 GHz AMD Ryzen-3975WX @ 6.3 GHz (no-xmul) AMD FX-6300 @ 3.5 GHz AMD FX-6300 @ 3.5 GHz (no-xmul) Arm A72 @ 1.8 GHz Arm A72 @ 1.8 GHz (no-xmul) Arm A53 @ 1.4 GHz Arm A53 @ 1.4 GHz (no-xmul)
gfmul/gf256_naive_mul 11.129 ns 16.953 ns 21.706 ns 26.184 ns 33.356 ns 36.286 ns 33.851 ns 56.792 ns
gfmul/gf256_table_mul 983.50 ps 1.0578 ns 2.2841 ns 2.3177 ns 3.6110 ns 3.6088 ns 14.381 ns 14.419 ns
gfmul/gf256_rem_table_mul 984.46 ps 5.0971 ns 2.6204 ns 11.826 ns 5.4644 ns 11.723 ns 11.588 ns 33.700 ns
gfmul/gf256_small_rem_table_mul 6.2360 ns 10.970 ns 18.028 ns 21.038 ns 18.862 ns 26.444 ns 41.849 ns 70.230 ns
gfmul/gf256_barret_mul 2.2866 ns 9.3038 ns 12.056 ns 18.456 ns 10.515 ns 23.392 ns 15.152 ns 49.276 ns
AMD Ryzen-3975WX @ 6.3 GHz AMD Ryzen-3975WX @ 6.3 GHz (no-xmul) AMD FX-6300 @ 3.5 GHz AMD FX-6300 @ 3.5 GHz (no-xmul) Arm A72 @ 1.8 GHz Arm A72 @ 1.8 GHz (no-xmul) Arm A53 @ 1.4 GHz Arm A53 @ 1.4 GHz (no-xmul)
gfmul/gf16_naive_mul 7.5132 ns 12.575 ns 13.817 ns 21.909 ns 24.037 ns 27.576 ns 22.778 ns 45.215 ns
gfmul/gf16_table_mul 1.8285 ns 1.8217 ns 3.8362 ns 3.8429 ns 7.1143 ns 7.1034 ns 14.892 ns 14.897 ns
gfmul/gf16_rem_table_mul 1.0802 ns 2.8074 ns 3.1999 ns 5.8933 ns 5.7304 ns 7.8272 ns 13.700 ns 17.189 ns
gfmul/gf16_small_rem_table_mul 6.4772 ns 9.4698 ns 18.378 ns 18.310 ns 20.017 ns 20.058 ns 43.369 ns 52.566 ns
gfmul/gf16_barret_mul 2.3745 ns 1.9874 ns 9.4158 ns 3.3668 ns 13.102 ns 21.160 ns 18.690 ns 23.715 ns
AMD Ryzen-3975WX @ 6.3 GHz AMD Ryzen-3975WX @ 6.3 GHz (no-xmul) AMD FX-6300 @ 3.5 GHz AMD FX-6300 @ 3.5 GHz (no-xmul) Arm A72 @ 1.8 GHz Arm A72 @ 1.8 GHz (no-xmul) Arm A53 @ 1.4 GHz Arm A53 @ 1.4 GHz (no-xmul)
gfmul/gf2p16_naive_mul 15.953 ns 26.443 ns 27.075 ns 41.326 ns 40.831 ns 57.402 ns 50.381 ns 99.296 ns
gfmul/gf2p16_rem_table_mul 6.7126 ns 14.743 ns 12.718 ns 29.823 ns 18.087 ns 34.586 ns 36.750 ns 83.857 ns
gfmul/gf2p16_small_rem_table_mul 10.013 ns 17.645 ns 24.320 ns 38.890 ns 35.569 ns 50.127 ns 69.866 ns 119.24 ns
gfmul/gf2p16_barret_mul 2.2937 ns 13.455 ns 8.9820 ns 31.893 ns 9.8849 ns 53.460 ns 15.426 ns 108.54 ns
AMD Ryzen-3975WX @ 6.3 GHz AMD Ryzen-3975WX @ 6.3 GHz (no-xmul) AMD FX-6300 @ 3.5 GHz AMD FX-6300 @ 3.5 GHz (no-xmul) Arm A72 @ 1.8 GHz Arm A72 @ 1.8 GHz (no-xmul) Arm A53 @ 1.4 GHz Arm A53 @ 1.4 GHz (no-xmul)
gfmul/gf2p32_naive_mul 24.942 ns 35.281 ns 41.008 ns 53.034 ns 58.916 ns 101.61 ns 63.794 ns 119.28 ns
gfmul/gf2p32_rem_table_mul 10.687 ns 14.406 ns 21.535 ns 34.929 ns 26.756 ns 79.501 ns 59.424 ns 193.97 ns
gfmul/gf2p32_small_rem_table_mul 18.864 ns 19.921 ns 37.345 ns 49.648 ns 54.087 ns 99.291 ns 112.18 ns 208.58 ns
gfmul/gf2p32_barret_mul 2.2320 ns 17.901 ns 9.0284 ns 33.821 ns 9.6186 ns 90.596 ns 15.807 ns 194.67 ns
AMD Ryzen-3975WX @ 6.3 GHz AMD Ryzen-3975WX @ 6.3 GHz (no-xmul) AMD FX-6300 @ 3.5 GHz AMD FX-6300 @ 3.5 GHz (no-xmul) Arm A72 @ 1.8 GHz Arm A72 @ 1.8 GHz (no-xmul) Arm A53 @ 1.4 GHz Arm A53 @ 1.4 GHz (no-xmul)
gfmul/gf2p64_naive_mul 83.672 ns 110.04 ns 129.96 ns 214.52 ns 221.70 ns 418.54 ns 283.20 ns 667.17 ns
gfmul/gf2p64_rem_table_mul 20.533 ns 35.096 ns 34.605 ns 124.94 ns 48.117 ns 249.24 ns 109.16 ns 506.18 ns
gfmul/gf2p64_small_rem_table_mul 36.280 ns 50.096 ns 61.355 ns 152.01 ns 102.13 ns 298.31 ns 213.93 ns 613.42 ns
gfmul/gf2p64_barret_mul 1.8085 ns 45.276 ns 6.9333 ns 120.59 ns 9.2153 ns 313.76 ns 15.890 ns 618.90 ns

Galois-field division

AMD Ryzen-3975WX @ 6.3 GHz AMD Ryzen-3975WX @ 6.3 GHz (no-xmul) AMD FX-6300 @ 3.5 GHz AMD FX-6300 @ 3.5 GHz (no-xmul) Arm A72 @ 1.8 GHz Arm A72 @ 1.8 GHz (no-xmul) Arm A53 @ 1.4 GHz Arm A53 @ 1.4 GHz (no-xmul)
gfdiv/gf256_naive_div 118.69 ns 154.64 ns 271.21 ns 324.45 ns 397.56 ns 446.31 ns 440.14 ns 752.00 ns
gfdiv/gf256_table_div 972.08 ps 957.69 ps 2.3997 ns 2.6109 ns 4.1131 ns 4.1154 ns 15.102 ns 15.128 ns
gfdiv/gf256_rem_table_div 19.690 ns 82.690 ns 59.391 ns 146.69 ns 95.588 ns 190.76 ns 117.64 ns 365.01 ns
gfdiv/gf256_small_rem_table_div 73.855 ns 138.28 ns 178.03 ns 272.30 ns 238.57 ns 334.75 ns 461.02 ns 849.28 ns
gfdiv/gf256_barret_div 61.260 ns 112.78 ns 221.96 ns 230.49 ns 244.08 ns 340.33 ns 182.47 ns 738.94 ns
AMD Ryzen-3975WX @ 6.3 GHz AMD Ryzen-3975WX @ 6.3 GHz (no-xmul) AMD FX-6300 @ 3.5 GHz AMD FX-6300 @ 3.5 GHz (no-xmul) Arm A72 @ 1.8 GHz Arm A72 @ 1.8 GHz (no-xmul) Arm A53 @ 1.4 GHz Arm A53 @ 1.4 GHz (no-xmul)
gfdiv/gf16_naive_div 31.564 ns 47.578 ns 69.057 ns 96.437 ns 110.71 ns 140.21 ns 120.36 ns 282.55 ns
gfdiv/gf16_table_div 2.1055 ns 2.0982 ns 3.8425 ns 4.1275 ns 6.6130 ns 6.6105 ns 14.999 ns 14.952 ns
gfdiv/gf16_rem_table_div 10.205 ns 18.079 ns 33.548 ns 33.175 ns 52.817 ns 44.515 ns 77.164 ns 102.05 ns
gfdiv/gf16_small_rem_table_div 36.017 ns 47.200 ns 92.921 ns 82.143 ns 122.92 ns 106.78 ns 233.20 ns 266.85 ns
gfdiv/gf16_barret_div 27.939 ns 35.534 ns 111.64 ns 67.928 ns 124.02 ns 117.35 ns 107.55 ns 223.28 ns
AMD Ryzen-3975WX @ 6.3 GHz AMD Ryzen-3975WX @ 6.3 GHz (no-xmul) AMD FX-6300 @ 3.5 GHz AMD FX-6300 @ 3.5 GHz (no-xmul) Arm A72 @ 1.8 GHz Arm A72 @ 1.8 GHz (no-xmul) Arm A53 @ 1.4 GHz Arm A53 @ 1.4 GHz (no-xmul)
gfdiv/gf2p16_naive_div 432.36 ns 757.89 ns 728.90 ns 1.3381 us 1.0561 us 1.5762 us 1.2732 us 2.8786 us
gfdiv/gf2p16_rem_table_div 160.22 ns 406.33 ns 364.29 ns 884.03 ns 592.46 ns 1.1292 us 1.0873 us 2.6141 us
gfdiv/gf2p16_small_rem_table_div 375.07 ns 550.93 ns 585.41 ns 1.0450 us 1.0087 us 1.5059 us 1.8075 us 3.2385 us
gfdiv/gf2p16_barret_div 149.24 ns 432.70 ns 440.55 ns 954.82 ns 517.61 ns 1.6336 us 452.15 ns 3.0219 us
AMD Ryzen-3975WX @ 6.3 GHz AMD Ryzen-3975WX @ 6.3 GHz (no-xmul) AMD FX-6300 @ 3.5 GHz AMD FX-6300 @ 3.5 GHz (no-xmul) Arm A72 @ 1.8 GHz Arm A72 @ 1.8 GHz (no-xmul) Arm A53 @ 1.4 GHz Arm A53 @ 1.4 GHz (no-xmul)
gfdiv/gf2p32_naive_div 1.3246 us 1.9433 us 2.1068 us 2.8985 us 3.0042 us 5.5931 us 3.2607 us 6.6853 us
gfdiv/gf2p32_rem_table_div 587.34 ns 895.70 ns 1.2291 us 2.1905 us 1.6276 us 4.4786 us 3.2995 us 9.9253 us
gfdiv/gf2p32_small_rem_table_div 1.1231 us 1.5014 us 2.1185 us 3.2455 us 3.3309 us 6.6975 us 6.3128 us 14.666 us
gfdiv/gf2p32_barret_div 275.00 ns 1.2688 us 917.81 ns 2.5065 us 1.0120 us 5.7242 us 848.13 ns 12.123 us
AMD Ryzen-3975WX @ 6.3 GHz AMD Ryzen-3975WX @ 6.3 GHz (no-xmul) AMD FX-6300 @ 3.5 GHz AMD FX-6300 @ 3.5 GHz (no-xmul) Arm A72 @ 1.8 GHz Arm A72 @ 1.8 GHz (no-xmul) Arm A53 @ 1.4 GHz Arm A53 @ 1.4 GHz (no-xmul)
gfdiv/gf2p64_naive_div 8.0257 us 11.473 us 13.535 us 25.363 us 21.452 us 50.114 us 27.224 us 78.147 us
gfdiv/gf2p64_rem_table_div 2.2686 us 4.9446 us 4.0306 us 16.621 us 6.0299 us 34.536 us 13.017 us 64.879 us
gfdiv/gf2p64_small_rem_table_div 4.7742 us 6.9519 us 7.6062 us 19.217 us 14.480 us 41.218 us 25.220 us 77.527 us
gfdiv/gf2p64_barret_div 395.02 ns 5.9427 us 1.2398 us 15.405 us 1.9941 us 43.758 us 1.5969 us 82.216 us

LFSRs

AMD Ryzen-3975WX @ 6.3 GHz AMD Ryzen-3975WX @ 6.3 GHz (no-xmul) AMD FX-6300 @ 3.5 GHz AMD FX-6300 @ 3.5 GHz (no-xmul) Arm A72 @ 1.8 GHz Arm A72 @ 1.8 GHz (no-xmul) Arm A53 @ 1.4 GHz Arm A53 @ 1.4 GHz (no-xmul)
lfsr/lfsr64_naive 127.34 MiB/s 126.65 MiB/s 95.677 MiB/s 89.662 MiB/s 71.481 MiB/s 71.480 MiB/s 52.768 MiB/s 52.676 MiB/s
lfsr/lfsr64_divrem 49.718 MiB/s 50.553 MiB/s 27.616 MiB/s 27.371 MiB/s 17.307 MiB/s 17.302 MiB/s 12.324 MiB/s 12.312 MiB/s
lfsr/lfsr64_table 540.48 MiB/s 540.38 MiB/s 414.77 MiB/s 404.96 MiB/s 240.76 MiB/s 240.76 MiB/s 167.68 MiB/s 167.88 MiB/s
lfsr/lfsr64_small_table 269.88 MiB/s 267.43 MiB/s 244.64 MiB/s 242.61 MiB/s 121.45 MiB/s 121.45 MiB/s 86.121 MiB/s 86.094 MiB/s
lfsr/lfsr64_barret 79.492 MiB/s 69.227 MiB/s 45.364 MiB/s 40.412 MiB/s 30.900 MiB/s 20.358 MiB/s 21.647 MiB/s 11.715 MiB/s
lfsr/lfsr64_table_barret 155.21 MiB/s 43.711 MiB/s 49.520 MiB/s 21.622 MiB/s 46.972 MiB/s 7.3621 MiB/s 36.694 MiB/s 3.1524 MiB/s
lfsr/lfsr64_small_table_barret 77.618 MiB/s 21.981 MiB/s 25.389 MiB/s 11.254 MiB/s 23.147 MiB/s 3.6297 MiB/s 16.867 MiB/s 1.5732 MiB/s
AMD Ryzen-3975WX @ 6.3 GHz AMD Ryzen-3975WX @ 6.3 GHz (no-xmul) AMD FX-6300 @ 3.5 GHz AMD FX-6300 @ 3.5 GHz (no-xmul) Arm A72 @ 1.8 GHz Arm A72 @ 1.8 GHz (no-xmul) Arm A53 @ 1.4 GHz Arm A53 @ 1.4 GHz (no-xmul)
lfsr/xorshift64 4.9006 GiB/s 4.9463 GiB/s 2.9912 GiB/s 2.9687 GiB/s 2.2308 GiB/s 2.2316 GiB/s 1.7497 GiB/s 1.7466 GiB/s

CRCs

AMD Ryzen-3975WX @ 6.3 GHz AMD Ryzen-3975WX @ 6.3 GHz (no-xmul) AMD FX-6300 @ 3.5 GHz AMD FX-6300 @ 3.5 GHz (no-xmul) Arm A72 @ 1.8 GHz Arm A72 @ 1.8 GHz (no-xmul) Arm A53 @ 1.4 GHz Arm A53 @ 1.4 GHz (no-xmul)
crc/naive_crc 70.162 MiB/s 72.168 MiB/s 50.933 MiB/s 51.872 MiB/s 37.713 MiB/s 37.731 MiB/s 27.545 MiB/s 27.569 MiB/s
crc/less_naive_crc 76.072 MiB/s 77.650 MiB/s 50.547 MiB/s 50.812 MiB/s 39.730 MiB/s 39.721 MiB/s 26.656 MiB/s 26.766 MiB/s
crc/word_less_naive_crc 143.77 MiB/s 144.38 MiB/s 91.878 MiB/s 103.83 MiB/s 73.326 MiB/s 73.330 MiB/s 61.919 MiB/s 61.920 MiB/s
crc/table_crc 476.43 MiB/s 475.45 MiB/s 412.85 MiB/s 444.69 MiB/s 213.55 MiB/s 213.32 MiB/s 148.11 MiB/s 147.55 MiB/s
crc/small_table_crc 213.63 MiB/s 215.92 MiB/s 186.30 MiB/s 199.50 MiB/s 95.077 MiB/s 95.093 MiB/s 80.944 MiB/s 81.181 MiB/s
crc/barret_crc 147.86 MiB/s 50.603 MiB/s 45.476 MiB/s 27.352 MiB/s 44.161 MiB/s 16.026 MiB/s 34.457 MiB/s 6.8674 MiB/s
crc/word_barret_crc 664.75 MiB/s 209.72 MiB/s 208.67 MiB/s 108.86 MiB/s 213.85 MiB/s 67.776 MiB/s 362.81 MiB/s 27.877 MiB/s
crc/reversed_barret_crc 127.57 MiB/s 50.016 MiB/s 39.038 MiB/s 24.993 MiB/s 38.342 MiB/s 12.993 MiB/s 24.023 MiB/s 5.6548 MiB/s
crc/word_reversed_barret_crc 592.13 MiB/s 214.57 MiB/s 194.16 MiB/s 110.00 MiB/s 191.32 MiB/s 56.501 MiB/s 166.23 MiB/s 22.548 MiB/s