marcinbugaj
commented
2 years ago Benchmark code is here: https://github.com/zcash/halo2/commit/f25447b8d44f0fa58d211752c4898bbc8784b8ee
Results are:
Benchmarking msm ref/20: Warming up for 3.0000 s
Warning: Unable to complete 500 samples in 5.0s. You may wish to increase target time to 10.6s, or reduce sample count to 230.
msm ref/20 time: [21.109 ms 21.110 ms 21.112 ms]
change: [-0.8669% -0.8551% -0.8434%] (p = 0.00 < 0.05)
Change within noise threshold.
Found 6 outliers among 500 measurements (1.20%)
2 (0.40%) low mild
3 (0.60%) high mild
1 (0.20%) high severe
Benchmarking msm ref/21: Warming up for 3.0000 s
Warning: Unable to complete 500 samples in 5.0s. You may wish to increase target time to 21.1s, or reduce sample count to 110.
msm ref/21 time: [42.311 ms 42.315 ms 42.318 ms]
change: [-0.3332% -0.3237% -0.3143%] (p = 0.00 < 0.05)
Change within noise threshold.
Found 3 outliers among 500 measurements (0.60%)
3 (0.60%) low mild
Benchmarking msm ref/22: Warming up for 3.0000 s
Warning: Unable to complete 500 samples in 5.0s. You may wish to increase target time to 42.4s, or reduce sample count to 50.
msm ref/22 time: [84.773 ms 84.777 ms 84.780 ms]
change: [-0.1484% -0.1437% -0.1388%] (p = 0.00 < 0.05)
Change within noise threshold.
Found 4 outliers among 500 measurements (0.80%)
4 (0.80%) high mild
Benchmarking msm ref/23: Warming up for 3.0000 s
Warning: Unable to complete 500 samples in 5.0s. You may wish to increase target time to 84.8s, or reduce sample count to 20.
msm ref/23 time: [169.69 ms 169.70 ms 169.72 ms]
change: [-0.2118% -0.1896% -0.1670%] (p = 0.00 < 0.05)
Change within noise threshold.
Benchmarking msm ref/24: Warming up for 3.0000 s
Warning: Unable to complete 500 samples in 5.0s. You may wish to increase target time to 169.5s, or reduce sample count to 10.
msm ref/24 time: [339.21 ms 339.25 ms 339.30 ms]
change: [-0.1086% -0.0850% -0.0635%] (p = 0.00 < 0.05)
Change within noise threshold.
Found 10 outliers among 500 measurements (2.00%)
4 (0.80%) low mild
1 (0.20%) high mild
5 (1.00%) high severe
Benchmarking msm ref/25: Warming up for 3.0000 s
Warning: Unable to complete 500 samples in 5.0s. You may wish to increase target time to 339.2s, or reduce sample count to 10.
msm ref/25 time: [679.20 ms 679.27 ms 679.33 ms]
Found 7 outliers among 500 measurements (1.40%)
7 (1.40%) low mild
Benchmarking msm ref/26: Warming up for 3.0000 s
Warning: Unable to complete 500 samples in 5.0s. You may wish to increase target time to 678.4s, or reduce sample count to 10.
msm ref/26 time: [1.3604 s 1.3606 s 1.3608 s]
Found 9 outliers among 500 measurements (1.80%)
5 (1.00%) high mild
4 (0.80%) high severe
Benchmarking msm Pippenger/12: Warming up for 3.0000 s
Warning: Unable to complete 500 samples in 5.0s. You may wish to increase target time to 23.0s, or reduce sample count to 100.
msm Pippenger/12 time: [46.007 ms 46.010 ms 46.015 ms]
Found 19 outliers among 500 measurements (3.80%)
2 (0.40%) low mild
11 (2.20%) high mild
6 (1.20%) high severe
Benchmarking msm Pippenger/13: Warming up for 3.0000 s
Warning: Unable to complete 500 samples in 5.0s. You may wish to increase target time to 41.2s, or reduce sample count to 60.
msm Pippenger/13 time: [82.377 ms 82.382 ms 82.387 ms]
Found 14 outliers among 500 measurements (2.80%)
1 (0.20%) low mild
12 (2.40%) high mild
1 (0.20%) high severe
Benchmarking msm Pippenger/14: Warming up for 3.0000 s
Warning: Unable to complete 500 samples in 5.0s. You may wish to increase target time to 76.8s, or reduce sample count to 30.
msm Pippenger/14 time: [153.66 ms 153.67 ms 153.68 ms]
Found 7 outliers among 500 measurements (1.40%)
1 (0.20%) low mild
5 (1.00%) high mild
1 (0.20%) high severe
Benchmarking msm Pippenger/15: Warming up for 3.0000 s
Warning: Unable to complete 500 samples in 5.0s. You may wish to increase target time to 139.6s, or reduce sample count to 10.
msm Pippenger/15 time: [279.31 ms 279.35 ms 279.40 ms]
Found 12 outliers among 500 measurements (2.40%)
7 (1.40%) high mild
5 (1.00%) high severe
Benchmarking msm Pippenger/16: Warming up for 3.0000 s
Warning: Unable to complete 500 samples in 5.0s. You may wish to increase target time to 259.7s, or reduce sample count to 10.
msm Pippenger/16 time: [522.00 ms 522.13 ms 522.25 ms]
Found 100 outliers among 500 measurements (20.00%)
99 (19.80%) low mild
1 (0.20%) high mild
Benchmarking msm Pippenger/17: Warming up for 3.0000 s
Warning: Unable to complete 500 samples in 5.0s. You may wish to increase target time to 502.1s, or reduce sample count to 10.
msm Pippenger/17 time: [1.0032 s 1.0034 s 1.0036 s]
Found 3 outliers among 500 measurements (0.60%)
2 (0.40%) high mild
1 (0.20%) high severe
Benchmarking msm Pippenger/18: Warming up for 3.0000 s
Warning: Unable to complete 500 samples in 5.0s. You may wish to increase target time to 930.6s, or reduce sample count to 10.
msm Pippenger/18 time: [1.8686 s 1.8695 s 1.8704 s] Here criterion detailed results along with plots.
In order to compare our multi-column lookup argument with the one from Hyperplonk, current paper-pencil counts rely on a heuristic for the cost of a multi-scalar multiplication in terms of field multiplications. To have more reliable numbers (without implementing the multivariate prover) we would need a benchmark-based equivalent. Concretely, we would need:
N = 2^12. This benchmark prepares a random base point vector(G_1, ..., G_N)and scalars(s_1,..., s_n), and measures the time for Pippenger's multi-scalar in a single- threaded environment.Fof the curve. This benchmark preparesm= 2^20random field elementsa_0,....,a_{m-1}, and measures the overall time for computing recursively the producta_0 * ... * a_{m-1}by updatingb = a_0viab <- b * a_i, fori = 1, ..., m-1. Again, in a single-threaded environment.In both benchmarks the random sampling of the instances must be excluded from the timings.