/ benchmarks / bench_powmod.nim
bench_powmod.nim
1 import 2 ../constantine/math/arithmetic, 3 ../constantine/math/io/[io_bigints, io_fields], 4 ../constantine/math/config/curves, 5 ../constantine/platforms/abstractions, 6 ../constantine/serialization/codecs, 7 ../constantine/math_arbitrary_precision/arithmetic/bigints_views, 8 ../helpers/prng_unsafe, 9 ./platforms, ./bench_blueprint 10 11 import stint, gmp 12 from bigints import nil # force qualified import to avoid conflicts on BigInt 13 14 # Benchmarks for modular exponentiation implementations: 15 # 16 # - Constantine has 2 backends 17 # - The cryptographic backend uses fixed-sized integer. 18 # Often the modulus is known at compile-time (specific elliptic curves), 19 # except for RSA. 20 # 21 # This allows reducing precomputation time, 22 # and unrolling all loops. 23 # This is significant as incrementing a loop counter messes up carry propagation. 24 # 25 # That backend requires the modulus to be prime. 26 # 27 # As cryptography only uses primes (which are odd), this is not a limitation. 28 # However it is not suitable for general-purpose 29 # 30 # - The arbitrary-sized integer backend. 31 # Some protocol like Ethereum modexp (EIP-198) require 32 # modular exponentiation on arbitrary inputs. 33 # 34 # - Stint, GMP, nim-bigints are also benchmarked 35 # for reference. GMP and nim-bigints require dynamic allocation. 36 # - For GMP, we reuse buffers to limit allocation to the first benchmark 37 # - nim-bigints doesn't allow reusing buffers 38 # 39 # Stint requires all inputs to be the same size 40 # so we use 256-bits for all. 41 # 42 # To benchmark the cryptographic backend, we use Secp256k1 (the Bitcoin curve). 43 # Note that Constantine implements it generically, 44 # due to the special form of the prime (2²⁵⁶ - 2³² - 977), 45 # even faster algorithms can be used. 46 # This gives an upper-bound 47 48 proc report(op: string, elapsedNs: int64, elapsedCycles: int64, iters: int) = 49 let ns = elapsedNs div iters 50 let cycles = elapsedCycles div iters 51 let throughput = 1e9 / float64(ns) 52 when SupportsGetTicks: 53 echo &"{op:<45} {throughput:>15.3f} ops/s {ns:>16} ns/op {cycles:>12} CPU cycles (approx)" 54 else: 55 echo &"{op:<45} {throughput:>15.3f} ops/s {ns:>16} ns/op" 56 57 const # https://gmplib.org/manual/Integer-Import-and-Export.html 58 GMP_WordLittleEndian = -1'i32 59 GMP_WordNativeEndian = 0'i32 60 GMP_WordBigEndian = 1'i32 61 62 GMP_MostSignificantWordFirst = 1'i32 63 GMP_LeastSignificantWordFirst = -1'i32 64 65 const bits = 256 66 67 type BenchDesc = object 68 # Hex strings 69 a: string 70 e: string 71 M: string 72 73 proc genBench(iters: int): seq[BenchDesc] = 74 for _ in 0 ..< iters: 75 let a = rng.random_long01Seq(BigInt[bits]) 76 let e = rng.random_long01Seq(BigInt[bits]) 77 let M = rng.random_long01Seq(BigInt[bits]) 78 result.add BenchDesc( 79 a: a.toHex(), 80 e: e.toHex(), 81 M: M.toHex()) 82 83 template bench(fnCall: untyped, ticks, ns: var int64): untyped = 84 block: 85 let startTime = getMonotime() 86 let startClock = getTicks() 87 fnCall 88 let stopClock = getTicks() 89 let stopTime = getMonotime() 90 91 ticks += stopClock - startClock 92 ns += inNanoseconds(stopTime-startTime) 93 94 proc benchAll(desc: seq[BenchDesc]) = 95 96 var perfCttArb, perfCttCrypto, perfGmp, perfStint, perfNimBigInt: int64 97 98 block: # Constantine Arbitrary-precision 99 var ticks, nanoseconds: int64 100 101 for i in 0 ..< desc.len: 102 # The implementation is view based and uses unowned-buffers (seq or arrays) 103 # but for hex parsing simplicity we reuse BigInt buffers 104 # and we directly access the array behind with .limbs 105 var r: BigInt[bits] 106 let a = BigInt[bits].fromHex(desc[i].a) 107 let M = BigInt[bits].fromHex(desc[i].M) 108 let e = array[bits div 8, byte].fromHex(desc[i].e) 109 110 bench( 111 r.limbs.powMod_varTime(a.limbs, e, M.limbs, window = 4), 112 ticks, nanoseconds) 113 114 report("Constantine (generic arbitrary-precision)", nanoseconds, ticks, desc.len) 115 perfCttArb = nanoseconds 116 117 block: # Constantine Cryptographic backend 118 var ticks, nanoseconds: int64 119 var e = newSeq[byte](bits div 8) 120 121 for i in 0 ..< desc.len: 122 var r: Fp[Secp256k1] 123 let a = Fp[Secp256k1].fromHex(desc[i].a) 124 e.paddedFromHex(desc[i].e, bigEndian) 125 126 bench( 127 (r = a; r.pow_varTime(e)), 128 ticks, nanoseconds) 129 130 report("Constantine (crypto fixed 256-bit precision)", nanoseconds, ticks, desc.len) 131 perfCttCrypto = nanoseconds 132 133 block: # GMP 134 var ticks, nanoseconds: int64 135 var a, e, M, r: mpz_t 136 mpz_init(a) 137 mpz_init(e) 138 mpz_init(M) 139 mpz_init(r) 140 141 for i in 0 ..< desc.len: 142 let aCtt = BigInt[bits].fromHex(desc[i].a) 143 a.mpz_import(aCtt.limbs.len, GMP_LeastSignificantWordFirst, sizeof(SecretWord), GMP_WordNativeEndian, 0, aCtt.limbs[0].unsafeAddr) 144 let eCtt = BigInt[bits].fromHex(desc[i].e) 145 e.mpz_import(eCtt.limbs.len, GMP_LeastSignificantWordFirst, sizeof(SecretWord), GMP_WordNativeEndian, 0, eCtt.limbs[0].unsafeAddr) 146 let mCtt = BigInt[bits].fromHex(desc[i].M) 147 M.mpz_import(mCtt.limbs.len, GMP_LeastSignificantWordFirst, sizeof(SecretWord), GMP_WordNativeEndian, 0, mCtt.limbs[0].unsafeAddr) 148 149 bench( 150 r.mpz_powm(a, e, M), 151 ticks, nanoseconds) 152 153 report("GMP", nanoseconds, ticks, desc.len) 154 perfGMP = nanoseconds 155 156 mpz_clear(r) 157 mpz_clear(M) 158 mpz_clear(e) 159 mpz_clear(a) 160 161 block: # Stint 162 var ticks, nanoseconds: int64 163 164 for i in 0 ..< desc.len: 165 let a = Stuint[bits].fromHex(desc[i].a) 166 let e = Stuint[bits].fromHex(desc[i].e) 167 let M = Stuint[bits].fromHex(desc[i].M) 168 169 bench( 170 (let r = powmod(a, e, M)), 171 ticks, nanoseconds) 172 173 report("Stint", nanoseconds, ticks, desc.len) 174 perfStint = nanoseconds 175 176 block: # Nim bigints 177 var ticks, nanoseconds: int64 178 179 for i in 0 ..< desc.len: 180 # Drop the 0x prefix 181 let a = bigints.initBigInt(desc[i].a[2..^1], base = 16) 182 let e = bigints.initBigInt(desc[i].e[2..^1], base = 16) 183 let M = bigints.initBigInt(desc[i].M[2..^1], base = 16) 184 185 bench( 186 (let r = bigints.powmod(a, e, M)), 187 ticks, nanoseconds) 188 189 report("nim-bigints", nanoseconds, ticks, desc.len) 190 perfNimBigInt = nanoseconds 191 192 let ratioCrypto = float64(perfCttCrypto) / float64(perfCttArb) 193 let ratioGMP = float64(perfGMP) / float64(perfCttArb) 194 let ratioStint = float64(perfStint) / float64(perfCttArb) 195 let ratioNimBigInt = float64(perfNimBigInt) / float64(perfCttArb) 196 197 echo "" 198 echo &"Perf ratio Constantine generic vs crypto fixed precision: {ratioCrypto:>8.3f}x" 199 echo &"Perf ratio Constantine generic vs GMP: {ratioGMP:>8.3f}x" 200 echo &"Perf ratio Constantine generic vs Stint: {ratioStint:>8.3f}x" 201 echo &"Perf ratio Constantine generic vs nim-bigints: {ratioNimBigInt:>8.3f}x" 202 203 204 when isMainModule: 205 let benchDesc = genBench(100) 206 benchDesc.benchAll()