Make WINDOW_G configurable

real-or-random commented at 1:29 pm on March 6, 2019: contributor

This makes WINDOW_G a configurable value in the range of [2..24]. The upper limit of 24 is a defensive choice. The code is probably correct for values up to 33 but those larger values yield in huge tables (>= 256MiB), which are i) unlikely to be really beneficial in practice and ii) increasingly difficult to test.

The main point of this is not to make the window size configurable (using ./configure) but rather to use an external #define for the window size, which makes it configurable for embedded system that rely on their own build system (like in #595).

in configure.ac:159 in f207e5de30 outdated

162+AC_ARG_WITH([ecmult-window], [AS_HELP_STRING([--with-ecmult-window=SIZE],
163+[window size for ecmult precomputation for verification, specified as integer in range [2..24],]
164+[or in range [3..25] if endomorphisms optimization is used.]
165+[Larger values result in better performance at the cost of an exponentially larger precomputed table.]
166+[The table will store 2^(SIZE-2) * 64 bytes of data but can be larger in memory due]
167+[to platform-specific padding and alignment. [default=16]]

real-or-random commented at 1:36 pm on March 6, 2019:

This is a rather large text for an autoconf –help string, so this should probably go to a separate document in the future (#593). But I think for now it’s better to have it here than nowhere.

real-or-random closed this on Mar 6, 2019

real-or-random reopened this on Mar 6, 2019

in configure.ac:158 in f207e5de30 outdated

161+# Default is window size 16 (or window size 15 with endomorphism) which needs 1.375 MiB. */
162+AC_ARG_WITH([ecmult-window], [AS_HELP_STRING([--with-ecmult-window=SIZE],
163+[window size for ecmult precomputation for verification, specified as integer in range [2..24],]
164+[or in range [3..25] if endomorphisms optimization is used.]
165+[Larger values result in better performance at the cost of an exponentially larger precomputed table.]
166+[The table will store 2^(SIZE-2) * 64 bytes of data but can be larger in memory due]

jonasnick commented at 3:01 pm on March 6, 2019:

s/SIZE/ecmult-window ?

real-or-random commented at 6:07 pm on March 6, 2019:

SIZE seems more in the style of the other options if you have a look at –help. But I don’t care in the end.

in configure.ac:157 in f207e5de30 outdated

159+[assembly optimizations to use (experimental: arm) [default=auto]])],[req_asm=$withval], [req_asm=auto])
160+
161+# Default is window size 16 (or window size 15 with endomorphism) which needs 1.375 MiB. */
162+AC_ARG_WITH([ecmult-window], [AS_HELP_STRING([--with-ecmult-window=SIZE],
163+[window size for ecmult precomputation for verification, specified as integer in range [2..24],]
164+[or in range [3..25] if endomorphisms optimization is used.]

jonasnick commented at 5:32 pm on March 6, 2019:

Is there a particular reason you have two different bounds instead of just [3..24] for both? Would be simpler, but it seems to work as is from my testing.

real-or-random commented at 6:05 pm on March 6, 2019:

The logic behind that is that I wanted to make sure that the same number yields the same memory requirements, no matter if the endomorphism is enabled or not. Unfortunately this implies the offset by one. Now we could restrict it to [3, 24] for both cases but that means you can’t set the minimal value if endo is disabled, which makes a difference if you want to squeeze the last 64 bytes out… I’m not sure if it’s worth the hassle in practice. Open to suggestions.

gmaxwell commented at 8:29 pm on March 6, 2019:

The difference between 2 and 3 is pretty small. I’d probably just go with the smaller range. If you want to save another 64 bytes there are other things you can do. (e.g. replace all the various normalize functions with just the strongest constant time version. :) )

in configure.ac:151 in f207e5de30 outdated

153-[Specify scalar implementation. Default is auto])],[req_scalar=$withval], [req_scalar=auto])
154+[scalar implementation to use [default=auto]])],[req_scalar=$withval], [req_scalar=auto])
155 
156-AC_ARG_WITH([asm], [AS_HELP_STRING([--with-asm=x86_64|arm|no|auto]
157-[Specify assembly optimizations to use. Default is auto (experimental: arm)])],[req_asm=$withval], [req_asm=auto])
158+AC_ARG_WITH([asm], [AS_HELP_STRING([--with-asm=x86_64|arm|no|auto],

jonasnick commented at 5:35 pm on March 6, 2019:

If I configure --without-ecmult-window configure succeeds but compilation fails.

real-or-random commented at 5:58 pm on March 6, 2019:

Good catch

jonasnick commented at 5:37 pm on March 6, 2019: contributor

I’ve compiled and tested with multiple ecmult-window on 64 bit and 32 bit with sanitizers under clang and that seems to work. ~~As an aside I can get a 10% speedup with ecdsa verify using window 10.~~ (EDIT)

in src/ecmult_impl.h:33 in f207e5de30 outdated

37-/** Two tables for window size 15: 1.375 MiB. */
38-#define WINDOW_G 15
39-#else
40-/** One table for window size 16: 1.375 MiB. */
41-#define WINDOW_G 16
42+#  define WINDOW_A 5

gmaxwell commented at 8:31 pm on March 6, 2019:

Don’t just document how the setting changes size in the configure script, document it in the code– probably here-ish. (Someone throwing out our build system will not find the docs inside configure. :) )

gmaxwell commented at 9:09 pm on March 6, 2019: contributor

Concept ACK. With regard to the range, we probably shouldn’t set the maximum any higher than we can benchmark a speedup on something: basically don’t give a faster knob that doesn’t necessarily make it faster.

real-or-random force-pushed on Mar 7, 2019

real-or-random commented at 0:05 am on March 7, 2019: contributor

Addressed the comments but I haven’t done benchmarks yet to determine a good maximum value.

real-or-random commented at 3:11 pm on March 7, 2019: contributor

we probably shouldn’t set the maximum any higher than we can benchmark a speedup on something: basically don’t give a faster knob that doesn’t necessarily make it faster.

That’s a great idea but I’m not sure about the “on something” part. It’s a lot of work but still we’ll never cover be able to cover all platform, so we’ll then probably just end up erring on the side of too low values instead of too high values. And I’m not sure if that’s worth the hassle: some people may abuse it and just set the maximum value but that’s not makes things only slower and not unsafe.

real-or-random commented at 3:12 pm on March 7, 2019: contributor

As an aside I can get a 10% speedup with ecdsa verify using window 10.

Not for this PR but I’d like to hear people’s opinion on making this configurable at runtime. Then you could finetune your node in the config file.

gmaxwell commented at 10:32 am on March 8, 2019: contributor

I expect there is a value which not faster on any existent hardware, somewhere around the size of L3 cache on the biggest chip, if performance still increases beyond that… that would be independently interesting to me. If you don’t fee like benchmarking that’s absolutely fine to me, I’m happy to do it.

We need to have a maximum value for sanity sake. Setting it somewhere around the maximum we think anyone should use makes sense. We shouldn’t think the user is a lot more able to test it than we are, and we should also not offer a range beyond what what we’re willing to test periodically.

Ultimately, it should perhaps end up on a chart like one of the ones on the minisketch page… window vs speed for 1g+1p on a couple different cpus.

gmaxwell commented at 10:34 am on March 8, 2019: contributor

On the runtime configurable part, window_a probably has a lot more impact and device sensitivity, but its also harder to set right (narrower peak performance).

real-or-random commented at 1:26 pm on March 8, 2019: contributor

If you don’t fee like benchmarking that’s absolutely fine to me, I’m happy to do it.

I’m willing to take that offer in particular if you have a few CPUs for benchmarking. I think I have (easy) access to at most two platforms.

sipa commented at 5:59 pm on March 8, 2019: contributor

Some random googling indicates that L3 cache sizes max out at 64 MiB, but there was an Intel chip with 128 MiB L4 cache.

gmaxwell commented at 7:47 pm on March 8, 2019: contributor

[tv@glowcloud ~]$ cat /proc/cpuinfo processor : 0 vendor_id : GenuineIntel cpu family : 6 model : 70 model name : Intel(R) Core(TM) i7-4770R CPU @ 3.20GHz

The cpu you’re referring to is in my TV computer, I believe.

The power9 cpus I have 90MB of L3.

K. I’ll benchmark.

gmaxwell commented at 8:39 pm on March 8, 2019: contributor

on i7-4770r (128MB L4) for lulz I expanded the range

 0for i in `seq 3 29` ; do echo -n $i' ' ; ./configure --with-bignum=gmp --enable-endomorphism  --enable-benchmark --with-ecmult-window=$i > /dev/null ; make -j4 > /dev/null ; ./bench_verify ; done
 13 ecdsa_verify: min 67.8us / avg 67.9us / max 68.1us
 24 ecdsa_verify: min 61.4us / avg 61.5us / max 61.7us
 35 ecdsa_verify: min 57.4us / avg 57.8us / max 58.6us
 46 ecdsa_verify: min 54.7us / avg 54.9us / max 55.1us
 57 ecdsa_verify: min 53.0us / avg 53.4us / max 54.9us
 68 ecdsa_verify: min 51.5us / avg 51.6us / max 51.7us
 79 ecdsa_verify: min 50.4us / avg 50.5us / max 50.8us
 810 ecdsa_verify: min 49.6us / avg 49.7us / max 49.8us
 911 ecdsa_verify: min 48.8us / avg 49.0us / max 49.1us
1012 ecdsa_verify: min 48.2us / avg 48.3us / max 48.5us
1113 ecdsa_verify: min 47.8us / avg 47.9us / max 47.9us
1214 ecdsa_verify: min 47.4us / avg 47.5us / max 47.8us
1315 ecdsa_verify: min 46.8us / avg 47.0us / max 47.2us
1416 ecdsa_verify: min 46.7us / avg 46.9us / max 47.3us
1517 ecdsa_verify: min 46.3us / avg 46.5us / max 47.0us
1618 ecdsa_verify: min 46.4us / avg 46.5us / max 46.7us
1719 ecdsa_verify: min 46.3us / avg 46.4us / max 46.6us
1820 ecdsa_verify: min 46.4us / avg 46.5us / max 46.6us
1921 ecdsa_verify: min 46.5us / avg 46.5us / max 46.6us
2022 ecdsa_verify: min 46.1us / avg 46.1us / max 46.2us
2123 ecdsa_verify: min 45.9us / avg 46.0us / max 46.2us
2224 ecdsa_verify: min 45.8us / avg 45.9us / max 46.0us
2325 ecdsa_verify: min 45.9us / avg 46.1us / max 46.2us
2426 ecdsa_verify: min 45.7us / avg 46.0us / max 46.8us
2527 ecdsa_verify: min 45.4us / avg 45.6us / max 45.7us
2628 ecdsa_verify: min 45.5us / avg 45.7us / max 45.8us
2729 ecdsa_verify: min 45.5us / avg 45.6us / max 45.7us
28for i in `seq 3 24` ; do echo -n $i' ' ; ./configure --with-bignum=gmp   --enable-benchmark --with-ecmult-window=$i > /dev/null ; make -j4 > /dev/null ; ./bench_verify ; done
293 ecdsa_verify: min 79.7us / avg 79.8us / max 80.0us
304 ecdsa_verify: min 75.6us / avg 75.7us / max 76.0us
315 ecdsa_verify: min 73.3us / avg 73.3us / max 73.4us
326 ecdsa_verify: min 71.4us / avg 71.6us / max 71.8us
337 ecdsa_verify: min 69.9us / avg 70.1us / max 70.2us
348 ecdsa_verify: min 69.0us / avg 69.0us / max 69.1us
359 ecdsa_verify: min 67.8us / avg 68.0us / max 68.1us
3610 ecdsa_verify: min 67.3us / avg 67.4us / max 67.8us
3711 ecdsa_verify: min 66.8us / avg 66.9us / max 67.0us
3812 ecdsa_verify: min 66.2us / avg 66.3us / max 66.5us
3913 ecdsa_verify: min 65.8us / avg 65.9us / max 66.1us
4014 ecdsa_verify: min 65.5us / avg 65.6us / max 65.8us
4115 ecdsa_verify: min 65.1us / avg 65.5us / max 67.4us
4216 ecdsa_verify: min 65.0us / avg 65.1us / max 65.3us
4317 ecdsa_verify: min 64.6us / avg 64.7us / max 64.9us
4418 ecdsa_verify: min 64.6us / avg 64.8us / max 64.9us
4519 ecdsa_verify: min 64.8us / avg 64.9us / max 65.1us
4620 ecdsa_verify: min 64.6us / avg 64.8us / max 65.0us
4721 ecdsa_verify: min 64.5us / avg 64.6us / max 64.7us
4822 ecdsa_verify: min 64.4us / avg 64.5us / max 64.7us
4923 ecdsa_verify: min 64.2us / avg 64.3us / max 64.4us
5024 ecdsa_verify: min 64.2us / avg 64.3us / max 64.4us

Will test on other things soon.

gmaxwell commented at 8:57 pm on March 8, 2019: contributor

model name : Intel(R) Xeon(R) CPU E31230 @ 3.20GHz

 0$ for i in `seq 3 24` ; do echo -n $i' ' ; ./configure --with-bignum=gmp --enable-endomorphism --disable-openssl-tests  --enable-benchmark --with-ecmult-window=$i > /dev/null ; make -j4 > /dev/null ; ./bench_verify ; done
 13 ecdsa_verify: min 81.6us / avg 81.7us / max 82.0us
 24 ecdsa_verify: min 74.1us / avg 74.1us / max 74.4us
 35 ecdsa_verify: min 69.2us / avg 69.3us / max 69.5us
 46 ecdsa_verify: min 66.1us / avg 66.2us / max 66.6us
 57 ecdsa_verify: min 63.9us / avg 64.0us / max 64.2us
 68 ecdsa_verify: min 62.2us / avg 62.3us / max 62.6us
 79 ecdsa_verify: min 60.9us / avg 60.9us / max 61.1us
 810 ecdsa_verify: min 59.9us / avg 59.9us / max 60.3us
 911 ecdsa_verify: min 59.0us / avg 59.1us / max 59.4us
1012 ecdsa_verify: min 58.3us / avg 58.4us / max 58.7us
1113 ecdsa_verify: min 57.9us / avg 57.9us / max 58.2us
1214 ecdsa_verify: min 57.4us / avg 57.4us / max 57.6us
1315 ecdsa_verify: min 56.7us / avg 56.7us / max 56.8us
1416 ecdsa_verify: min 56.6us / avg 56.6us / max 56.6us
1517 ecdsa_verify: min 56.0us / avg 56.0us / max 56.0us
1618 ecdsa_verify: min 56.0us / avg 56.0us / max 56.0us
1719 ecdsa_verify: min 55.5us / avg 55.6us / max 55.7us
1820 ecdsa_verify: min 55.8us / avg 55.9us / max 56.0us
1921 ecdsa_verify: min 56.0us / avg 56.0us / max 56.0us
2022 ecdsa_verify: min 55.4us / avg 55.5us / max 55.5us
2123 ecdsa_verify: min 55.3us / avg 55.4us / max 55.9us
2224 ecdsa_verify: min 55.3us / avg 55.3us / max 55.3us
23$ for i in `seq 3 24` ; do echo -n $i' ' ; ./configure --with-bignum=gmp --disable-openssl-tests  --enable-benchmark --with-ecmult-window=$i > /dev/null ; make -j4 > /dev/null ; ./bench_verify ; done
243 ecdsa_verify: min 96.0us / avg 96.0us / max 96.3us
254 ecdsa_verify: min 91.2us / avg 91.2us / max 91.6us
265 ecdsa_verify: min 88.0us / avg 88.1us / max 88.3us
276 ecdsa_verify: min 86.1us / avg 86.1us / max 86.4us
287 ecdsa_verify: min 84.2us / avg 84.3us / max 84.6us
298 ecdsa_verify: min 83.1us / avg 83.2us / max 83.5us
309 ecdsa_verify: min 81.9us / avg 82.0us / max 82.3us
3110 ecdsa_verify: min 81.3us / avg 81.4us / max 81.7us
3211 ecdsa_verify: min 80.5us / avg 80.5us / max 81.1us
3312 ecdsa_verify: min 79.9us / avg 79.9us / max 80.2us
3413 ecdsa_verify: min 79.4us / avg 79.4us / max 79.7us
3514 ecdsa_verify: min 79.0us / avg 79.0us / max 79.1us
3615 ecdsa_verify: min 78.7us / avg 78.8us / max 78.9us
3716 ecdsa_verify: min 78.3us / avg 78.4us / max 78.5us
3817 ecdsa_verify: min 78.0us / avg 78.0us / max 78.0us
3918 ecdsa_verify: min 77.7us / avg 77.8us / max 78.4us
4019 ecdsa_verify: min 77.8us / avg 77.8us / max 77.9us
4120 ecdsa_verify: min 77.9us / avg 77.9us / max 77.9us
4221 ecdsa_verify: min 77.7us / avg 77.7us / max 77.7us
4322 ecdsa_verify: min 77.7us / avg 77.7us / max 78.0us
4423 ecdsa_verify: min 77.5us / avg 77.6us / max 77.6us
4524 ecdsa_verify: min 77.4us / avg 77.4us / max 77.4us

gmaxwell commented at 9:15 pm on March 8, 2019: contributor

model name : AMD Ryzen Threadripper 2950X 16-Core Processor

 0$ for i in `seq 3 29` ; do echo -n $i' ' ; ./configure --with-bignum=gmp --enable-endomorphism --disable-openssl-tests  --enable-benchmark --with-ecmult-window=$i > /dev/null ; make -j4 > /dev/null ; ./bench_verify ; done
 13 ecdsa_verify: min 67.5us / avg 67.7us / max 67.9us
 24 ecdsa_verify: min 61.3us / avg 61.7us / max 62.0us
 35 ecdsa_verify: min 57.1us / avg 57.2us / max 57.4us
 46 ecdsa_verify: min 54.8us / avg 54.8us / max 54.8us
 57 ecdsa_verify: min 52.8us / avg 52.9us / max 53.0us
 68 ecdsa_verify: min 51.6us / avg 51.7us / max 51.8us
 79 ecdsa_verify: min 50.7us / avg 50.7us / max 50.9us
 810 ecdsa_verify: min 49.6us / avg 49.6us / max 49.7us
 911 ecdsa_verify: min 49.1us / avg 49.1us / max 49.1us
1012 ecdsa_verify: min 48.5us / avg 48.5us / max 48.7us
1113 ecdsa_verify: min 47.8us / avg 47.8us / max 47.9us
1214 ecdsa_verify: min 47.4us / avg 47.4us / max 47.4us
1315 ecdsa_verify: min 46.9us / avg 46.9us / max 47.0us
1416 ecdsa_verify: min 47.3us / avg 47.4us / max 47.5us
1517 ecdsa_verify: min 46.0us / avg 46.1us / max 46.1us
1618 ecdsa_verify: min 46.3us / avg 46.3us / max 46.4us
1719 ecdsa_verify: min 46.2us / avg 46.2us / max 46.4us
1820 ecdsa_verify: min 47.2us / avg 47.2us / max 47.2us
1921 ecdsa_verify: min 46.7us / avg 46.8us / max 46.8us
2022 ecdsa_verify: min 46.6us / avg 46.7us / max 46.7us
2123 ecdsa_verify: min 46.8us / avg 46.8us / max 46.8us
2224 ecdsa_verify: min 46.7us / avg 46.7us / max 46.8us
2325 ecdsa_verify: min 47.0us / avg 47.0us / max 47.1us
2426 ecdsa_verify: min 46.5us / avg 46.5us / max 46.5us
2527 ecdsa_verify: min 46.5us / avg 46.6us / max 46.6us
2628 ecdsa_verify: min 46.7us / avg 46.8us / max 46.9us
2729 ecdsa_verify: min 46.6us / avg 46.7us / max 46.7us
28$ for i in `seq 3 29` ; do echo -n $i' ' ; ./configure --with-bignum=gmp  --disable-openssl-tests  --enable-benchmark --with-ecmult-window=$i > /dev/null ; make -j4 > /dev/null ; ./bench_verify ; done
293 ecdsa_verify: min 80.0us / avg 80.0us / max 80.1us
304 ecdsa_verify: min 76.4us / avg 76.6us / max 76.6us
315 ecdsa_verify: min 73.2us / avg 73.6us / max 73.7us
326 ecdsa_verify: min 71.7us / avg 71.8us / max 72.0us
337 ecdsa_verify: min 71.0us / avg 71.1us / max 71.2us
348 ecdsa_verify: min 69.7us / avg 69.8us / max 69.8us
359 ecdsa_verify: min 68.4us / avg 68.5us / max 68.5us
3610 ecdsa_verify: min 67.8us / avg 67.8us / max 67.8us
3711 ecdsa_verify: min 66.8us / avg 66.8us / max 66.9us
3812 ecdsa_verify: min 67.6us / avg 67.6us / max 67.6us
3913 ecdsa_verify: min 66.0us / avg 66.2us / max 66.3us
4014 ecdsa_verify: min 65.6us / avg 65.6us / max 65.8us
4115 ecdsa_verify: min 65.9us / avg 66.0us / max 66.0us
4216 ecdsa_verify: min 65.7us / avg 65.8us / max 65.8us
4317 ecdsa_verify: min 64.8us / avg 65.6us / max 65.9us
4418 ecdsa_verify: min 64.9us / avg 64.9us / max 65.0us
4519 ecdsa_verify: min 65.6us / avg 65.8us / max 65.9us
4620 ecdsa_verify: min 66.2us / avg 66.3us / max 66.4us
4721 ecdsa_verify: min 66.2us / avg 66.3us / max 66.4us
4822 ecdsa_verify: min 65.5us / avg 65.5us / max 65.6us
4923 ecdsa_verify: min 65.4us / avg 65.5us / max 65.5us
5024 ecdsa_verify: min 65.9us / avg 65.9us / max 65.9us
5125 ecdsa_verify: min 65.3us / avg 65.3us / max 65.4us
5226 ecdsa_verify: min 66.1us / avg 66.1us / max 66.2us
5327 ecdsa_verify: min 66.1us / avg 66.1us / max 66.1us
5428 ecdsa_verify: min 65.8us / avg 66.1us / max 67.5us
5529 ecdsa_verify: min 66.0us / avg 66.0us / max 66.1us

gmaxwell commented at 3:17 am on March 9, 2019: contributor

model name : Genuine Intel(R) CPU @ 2.40GHz (haswell xeon)

 0$ for i in `seq 3 24` ; do echo -n $i' ' ; ./configure --with-bignum=gmp --enable-endomorphism --disable-openssl-tests  --enable-benchmark --with-ecmult-window=$i > /dev/null ; make -j4 > /dev/null 2> /dev/null ; ./bench_verify ; done
 13 ecdsa_verify: min 87.2us / avg 88.6us / max 94.5us
 24 ecdsa_verify: min 79.0us / avg 79.8us / max 86.3us
 35 ecdsa_verify: min 73.9us / avg 74.7us / max 80.9us
 46 ecdsa_verify: min 70.5us / avg 71.9us / max 77.4us
 57 ecdsa_verify: min 68.3us / avg 69.2us / max 75.4us
 68 ecdsa_verify: min 66.4us / avg 67.3us / max 70.1us
 79 ecdsa_verify: min 65.0us / avg 67.0us / max 73.3us
 810 ecdsa_verify: min 63.9us / avg 65.1us / max 70.7us
 911 ecdsa_verify: min 63.0us / avg 63.5us / max 68.5us
1012 ecdsa_verify: min 62.5us / avg 63.3us / max 70.2us
1113 ecdsa_verify: min 61.6us / avg 62.4us / max 68.9us
1214 ecdsa_verify: min 61.3us / avg 61.9us / max 67.5us
1315 ecdsa_verify: min 60.8us / avg 61.5us / max 67.4us
1416 ecdsa_verify: min 60.6us / avg 61.2us / max 66.8us
1517 ecdsa_verify: min 59.8us / avg 61.5us / max 66.7us
1618 ecdsa_verify: min 60.0us / avg 61.1us / max 65.5us
1719 ecdsa_verify: min 59.4us / avg 59.9us / max 63.9us
1820 ecdsa_verify: min 59.4us / avg 60.2us / max 63.3us
1921 ecdsa_verify: min 59.4us / avg 59.7us / max 61.7us
2022 ecdsa_verify: min 58.6us / avg 59.1us / max 59.7us
2123 ecdsa_verify: min 58.9us / avg 59.2us / max 59.7us
2224 ecdsa_verify: min 59.2us / avg 59.3us / max 59.8us
23$ for i in `seq 3 24` ; do echo -n $i' ' ; ./configure --with-bignum=gmp --disable-openssl-tests  --enable-benchmark --with-ecmult-window=$i > /dev/null ; make -j4 > /dev/null 2> /dev/null ; ./bench_verify ; done
243 ecdsa_verify: min 102us / avg 103us / max 109us
254 ecdsa_verify: min 96.9us / avg 97.8us / max 104us
265 ecdsa_verify: min 93.5us / avg 94.2us / max 101us
276 ecdsa_verify: min 91.1us / avg 92.8us / max 98.5us
287 ecdsa_verify: min 89.4us / avg 91.3us / max 96.9us
298 ecdsa_verify: min 87.9us / avg 89.0us / max 95.3us
309 ecdsa_verify: min 86.9us / avg 87.6us / max 93.4us
3110 ecdsa_verify: min 85.9us / avg 86.6us / max 92.8us
3211 ecdsa_verify: min 85.3us / avg 86.0us / max 92.1us
3312 ecdsa_verify: min 84.5us / avg 86.3us / max 91.6us
3413 ecdsa_verify: min 84.1us / avg 84.9us / max 92.0us
3514 ecdsa_verify: min 83.6us / avg 86.2us / max 90.4us
3615 ecdsa_verify: min 83.5us / avg 84.3us / max 90.5us
3716 ecdsa_verify: min 83.1us / avg 84.7us / max 89.5us
3817 ecdsa_verify: min 82.9us / avg 83.7us / max 89.2us
3918 ecdsa_verify: min 82.3us / avg 83.1us / max 88.1us
4019 ecdsa_verify: min 82.2us / avg 83.0us / max 86.6us
4120 ecdsa_verify: min 82.2us / avg 84.6us / max 89.0us
4221 ecdsa_verify: min 81.9us / avg 82.6us / max 84.6us
4322 ecdsa_verify: min 205us / avg 205us / max 205us
4423 ecdsa_verify: min 81.8us / avg 85.0us / max 112us
4524 ecdsa_verify: min 82.0us / avg 82.1us / max 82.8us

gmaxwell commented at 3:52 am on March 9, 2019: contributor

The comment is wrong, overflow happens at 33 (or 31 non-endo) not 34. src/ecmult_impl.h:298:42: warning: integer overflow in expression of type ‘int’ results in ‘2147483647’ [-Woverflow] VERIFY_CHECK((n) >= -((1 « ((w)-1)) - 1)); \

model : T2P9D01 REV 1.01 (Power9)

 0$ for i in `seq 3 32` ; do echo -n $i' ' ; ./configure --disable-openssl-tests --with-bignum=gmp --enable-endomorphism  -
 1-enable-benchmark --with-ecmult-window=$i > /dev/null ; make -j4 > /dev/null ; ./bench_verify ; done
 23 ecdsa_verify: min 95.8us / avg 95.9us / max 96.6us
 34 ecdsa_verify: min 87.1us / avg 87.1us / max 87.6us
 45 ecdsa_verify: min 81.7us / avg 81.8us / max 82.8us
 56 ecdsa_verify: min 76.6us / avg 76.7us / max 77.2us
 67 ecdsa_verify: min 75.7us / avg 75.8us / max 76.4us
 78 ecdsa_verify: min 73.8us / avg 74.0us / max 74.8us
 89 ecdsa_verify: min 72.2us / avg 72.3us / max 73.0us
 910 ecdsa_verify: min 71.1us / avg 71.1us / max 71.8us
1011 ecdsa_verify: min 70.1us / avg 70.2us / max 70.9us
1112 ecdsa_verify: min 69.3us / avg 69.4us / max 70.4us
1213 ecdsa_verify: min 68.6us / avg 68.7us / max 69.3us
1314 ecdsa_verify: min 68.1us / avg 68.2us / max 68.8us
1415 ecdsa_verify: min 67.4us / avg 67.5us / max 68.0us
1516 ecdsa_verify: min 67.2us / avg 67.3us / max 67.7us
1617 ecdsa_verify: min 66.6us / avg 66.6us / max 66.9us
1718 ecdsa_verify: min 66.6us / avg 66.6us / max 66.8us
1819 ecdsa_verify: min 65.9us / avg 65.9us / max 66.0us
1920 ecdsa_verify: min 66.0us / avg 66.1us / max 66.2us
2021 ecdsa_verify: min 66.1us / avg 66.1us / max 66.2us
2122 ecdsa_verify: min 65.6us / avg 65.6us / max 65.7us
2223 ecdsa_verify: min 65.3us / avg 65.4us / max 65.6us
2324 ecdsa_verify: min 65.4us / avg 65.5us / max 65.7us
2425 ecdsa_verify: min 65.4us / avg 65.6us / max 65.8us
2526 ecdsa_verify: min 65.1us / avg 65.1us / max 65.4us
2627 ecdsa_verify: min 64.6us / avg 64.7us / max 65.0us
2728 ecdsa_verify: min 64.6us / avg 64.7us / max 64.9us
2829 ecdsa_verify: min 64.6us / avg 64.7us / max 64.9us
2930 ecdsa_verify: min 64.6us / avg 64.6us / max 64.9us
3031 ecdsa_verify: min 64.7us / avg 64.7us / max 65.1us
3132 ecdsa_verify: min 64.7us / avg 64.8us / max 65.1us
32$ for i in `seq 3 32` ; do echo -n $i' ' ; ./configure --disable-openssl-tests --with-bignum=gmp --enable-benchmark --wit
33h-ecmult-window=$i > /dev/null ; make -j4 > /dev/null ; ./bench_verify ; done
343 ecdsa_verify: min 113us / avg 114us / max 114us
354 ecdsa_verify: min 108us / avg 108us / max 109us
365 ecdsa_verify: min 105us / avg 105us / max 105us
376 ecdsa_verify: min 103us / avg 103us / max 103us
387 ecdsa_verify: min 101us / avg 101us / max 102us
398 ecdsa_verify: min 99.3us / avg 99.4us / max 100us
409 ecdsa_verify: min 98.2us / avg 98.3us / max 98.9us
4110 ecdsa_verify: min 97.3us / avg 97.4us / max 97.9us
4211 ecdsa_verify: min 96.5us / avg 96.6us / max 97.2us
4312 ecdsa_verify: min 95.8us / avg 95.9us / max 96.5us
4413 ecdsa_verify: min 95.3us / avg 95.4us / max 96.0us
4514 ecdsa_verify: min 94.9us / avg 94.9us / max 95.4us
4615 ecdsa_verify: min 94.4us / avg 94.5us / max 94.8us
4716 ecdsa_verify: min 94.1us / avg 94.2us / max 94.5us
4817 ecdsa_verify: min 93.8us / avg 93.8us / max 94.0us
4918 ecdsa_verify: min 93.4us / avg 93.4us / max 93.5us
5019 ecdsa_verify: min 93.2us / avg 93.2us / max 93.3us
5120 ecdsa_verify: min 93.2us / avg 93.3us / max 93.4us
5221 ecdsa_verify: min 93.0us / avg 93.1us / max 93.8us
5322 ecdsa_verify: min 93.0us / avg 93.1us / max 93.2us
5423 ecdsa_verify: min 92.7us / avg 92.8us / max 93.0us
5524 ecdsa_verify: min 92.8us / avg 92.8us / max 93.1us
5625 ecdsa_verify: min 92.4us / avg 92.5us / max 92.8us
5726 ecdsa_verify: min 92.4us / avg 92.4us / max 92.7us
5827 ecdsa_verify: min 92.4us / avg 92.5us / max 92.7us
5928 ecdsa_verify: min 92.0us / avg 92.1us / max 92.3us
6029 ecdsa_verify: min 91.9us / avg 92.0us / max 92.2us
6130 ecdsa_verify: min 92.0us / avg 92.0us / max 92.3us
6231 ecdsa_verify: min 91.8us / avg 91.9us / max 92.3us

sipa commented at 3:57 am on March 9, 2019: contributor

You have a nice number of computers.

gmaxwell commented at 8:02 am on March 9, 2019: contributor

model name : Intel(R) Celeron(R) CPU 1007U @ 1.50GHz

 0$ for i in `seq 3 24` ; do echo -n $i' ' ; ./configure --with-bignum=gmp --enable-endomorphism --disable-openssl-tests  --enable-benchmark --with-ecmult-window=$i > /dev/null ; make -j4 > /dev/null 2> /dev/null ; ./bench_verify ; done
 13 ecdsa_verify: min 183us / avg 187us / max 191us
 24 ecdsa_verify: min 166us / avg 167us / max 173us
 35 ecdsa_verify: min 155us / avg 156us / max 161us
 46 ecdsa_verify: min 148us / avg 150us / max 156us
 57 ecdsa_verify: min 143us / avg 145us / max 149us
 68 ecdsa_verify: min 139us / avg 141us / max 144us
 79 ecdsa_verify: min 136us / avg 137us / max 139us
 810 ecdsa_verify: min 134us / avg 136us / max 142us
 911 ecdsa_verify: min 132us / avg 133us / max 137us
1012 ecdsa_verify: min 131us / avg 132us / max 133us
1113 ecdsa_verify: min 129us / avg 132us / max 140us
1214 ecdsa_verify: min 128us / avg 129us / max 134us
1315 ecdsa_verify: min 127us / avg 129us / max 133us
1416 ecdsa_verify: min 127us / avg 128us / max 129us
1517 ecdsa_verify: min 126us / avg 127us / max 131us
1618 ecdsa_verify: min 126us / avg 127us / max 134us
1719 ecdsa_verify: min 125us / avg 125us / max 125us
1820 ecdsa_verify: min 125us / avg 127us / max 132us
1921 ecdsa_verify: min 125us / avg 125us / max 126us
2022 ecdsa_verify: min 123us / avg 123us / max 124us
2123 ecdsa_verify: min 123us / avg 125us / max 131us
2224 ecdsa_verify: min 124us / avg 124us / max 124us
23$ for i in `seq 3 24` ; do echo -n $i' ' ; ./configure --with-bignum=gmp --disable-openssl-tests  --enable-benchmark --with-ecmult-window=$i > /dev/null ; make -j4 > /dev/null 2> /dev/null ; ./bench_verify ; done
243 ecdsa_verify: min 214us / avg 216us / max 221us
254 ecdsa_verify: min 204us / avg 205us / max 210us
265 ecdsa_verify: min 198us / avg 199us / max 200us
276 ecdsa_verify: min 192us / avg 193us / max 195us
287 ecdsa_verify: min 188us / avg 189us / max 194us
298 ecdsa_verify: min 185us / avg 186us / max 186us
309 ecdsa_verify: min 184us / avg 185us / max 190us
3110 ecdsa_verify: min 182us / avg 182us / max 183us
3211 ecdsa_verify: min 180us / avg 181us / max 189us
3312 ecdsa_verify: min 179us / avg 180us / max 186us
3413 ecdsa_verify: min 177us / avg 178us / max 178us
3514 ecdsa_verify: min 177us / avg 179us / max 190us
3615 ecdsa_verify: min 176us / avg 177us / max 177us
3716 ecdsa_verify: min 176us / avg 178us / max 184us
3817 ecdsa_verify: min 175us / avg 175us / max 175us
3918 ecdsa_verify: min 175us / avg 177us / max 183us
4019 ecdsa_verify: min 174us / avg 175us / max 176us
4120 ecdsa_verify: min 175us / avg 176us / max 181us
4221 ecdsa_verify: min 174us / avg 174us / max 176us
4322 ecdsa_verify: min 174us / avg 175us / max 181us
4423 ecdsa_verify: min 172us / avg 173us / max 177us
4524 ecdsa_verify: min 173us / avg 174us / max 180us

gmaxwell commented at 8:08 am on March 9, 2019: contributor

model name : ARMv7 Processor rev 10 (v7l) [ARM Cortex-A9 (Freescale i.MX6 Quad)]

 0$ for i in `seq 3 24` ; do echo -n $i' ' ; ./configure --with-bignum=gmp --enable-endomorphism --enable-experimental --with-asm=arm --disable-openssl-tests  --enable-benchmark --with-ecmult-window=$i > /dev/null ; make -j4 > /dev/null 2> /dev/null ; ./bench_verify ; done
 13 ecdsa_verify: min 1064us / avg 1065us / max 1065us
 24 ecdsa_verify: min 960us / avg 962us / max 971us
 35 ecdsa_verify: min 901us / avg 903us / max 906us
 46 ecdsa_verify: min 860us / avg 861us / max 862us
 57 ecdsa_verify: min 829us / avg 832us / max 835us
 68 ecdsa_verify: min 810us / avg 811us / max 814us
 79 ecdsa_verify: min 790us / avg 790us / max 793us
 810 ecdsa_verify: min 777us / avg 777us / max 779us
 911 ecdsa_verify: min 766us / avg 766us / max 767us
1012 ecdsa_verify: min 760us / avg 762us / max 770us
1113 ecdsa_verify: min 754us / avg 755us / max 763us
1214 ecdsa_verify: min 745us / avg 748us / max 755us
1315 ecdsa_verify: min 741us / avg 742us / max 746us
1416 ecdsa_verify: min 737us / avg 737us / max 738us
1517 ecdsa_verify: min 732us / avg 733us / max 733us
1618 ecdsa_verify: min 732us / avg 734us / max 737us
1719 ecdsa_verify: min 724us / avg 725us / max 728us
1820 ecdsa_verify: min 720us / avg 722us / max 726us
1921 ecdsa_verify: min 722us / avg 723us / max 725us
2022 ecdsa_verify: min 712us / avg 715us / max 719us
2123 ecdsa_verify: min 712us / avg 715us / max 716us
2224 ecdsa_verify: min 715us / avg 716us / max 717us
23$ for i in `seq 3 24` ; do echo -n $i' ' ; ./configure --with-bignum=gmp --enable-experimental --with-asm=arm --disable-openssl-tests  --enable-benchmark --with-ecmult-window=$i > /dev/null ; make -j4 > /dev/null 2> /dev/null ; ./bench_verify ; done
243 ecdsa_verify: min 1265us / avg 1267us / max 1272us
254 ecdsa_verify: min 1204us / avg 1208us / max 1214us
265 ecdsa_verify: min 1163us / avg 1164us / max 1166us
276 ecdsa_verify: min 1134us / avg 1135us / max 1140us
287 ecdsa_verify: min 1116us / avg 1119us / max 1132us
298 ecdsa_verify: min 1099us / avg 1104us / max 1121us
309 ecdsa_verify: min 1081us / avg 1081us / max 1083us
3110 ecdsa_verify: min 1075us / avg 1076us / max 1078us
3211 ecdsa_verify: min 1067us / avg 1068us / max 1070us
3312 ecdsa_verify: min 1058us / avg 1074us / max 1082us
3413 ecdsa_verify: min 1048us / avg 1049us / max 1051us
3514 ecdsa_verify: min 1053us / avg 1059us / max 1065us
3615 ecdsa_verify: min 1042us / avg 1047us / max 1063us
3716 ecdsa_verify: min 1035us / avg 1035us / max 1035us
3817 ecdsa_verify: min 1037us / avg 1040us / max 1046us
3918 ecdsa_verify: min 1033us / avg 1046us / max 1098us
4019 ecdsa_verify: min 1032us / avg 1040us / max 1081us
4120 ecdsa_verify: min 1028us / avg 1029us / max 1030us
4221 ecdsa_verify: min 1023us / avg 1025us / max 1027us
4322 ecdsa_verify: min 1029us / avg 1030us / max 1031us
4423 ecdsa_verify: min 1020us / avg 1022us / max 1026us
4524 ecdsa_verify: min 1020us / avg 1023us / max 1026us

gmaxwell commented at 8:16 am on March 9, 2019: contributor

Recommendations:

Fix the comment in the code about the maximum values.

24 is a fine maximum, on power9 the absurdly large 32 was only 1.2% faster than 24, and on none of the big systems were numbers between 16 and 24 killing performance. 24 is still small enough that we can expect all developers to be able to test it, not so much for 32-ish.

Endomorphism’s peak performance on large systems is at a larger table size than non-endo. It might be worth trying out making the G split actually use one table with the endomorphism.

For non-endo the existing default is argably slightly too high even on high performance hardware. Going down one would hardly hurt performance, and might help overall performance when doing something other than verifying in a tight loop.

Maybe we should eliminate the -1 on the endomorphism and decrease the default to 15 from 16? This would also have the benefit of allowing the minimum to be 2 instead of 3. Values that small are really awful for performance so I expect that someone minimizing memory usage would still be better off larger and getting the savings SOME other way. … however, the ARM actually really likes the bigger sizes.

real-or-random commented at 9:59 am on March 9, 2019: contributor

Maybe we should eliminate the -1 on the endomorphism and decrease the default to 15 from 16? This would also have the benefit of allowing the minimum to be 2 instead of 3. Values that small are really awful for performance so I expect that someone minimizing memory usage would still be better off larger and getting the savings SOME other way. … however, the ARM actually really likes the bigger sizes.

Sounds good to me. I think it’s better to keep the property that the table size depends on the parameter only (and not on endo), so I’d rather set the default to 15 or 16 depending on whether endo is on.

real-or-random force-pushed on Mar 12, 2019

real-or-random commented at 3:40 pm on March 12, 2019: contributor

updated

real-or-random commented at 3:51 pm on March 15, 2019: contributor

This should update basic_config.h too.

real-or-random force-pushed on Mar 18, 2019

real-or-random commented at 3:28 pm on March 18, 2019: contributor

Force-pushed to add a line in base-config.h

real-or-random cross-referenced this on Apr 1, 2019 from issue Changes necessary for usage on Trezor by real-or-random

gmaxwell commented at 4:20 pm on April 5, 2019: contributor

This looks pretty good to me, any opinions @theuni or @sipa ?

in configure.ac:123 in 06473d7e3f outdated

125+    AS_HELP_STRING([--enable-endomorphism],[enable endomorphism [default=no]]),
126     [use_endomorphism=$enableval],
127     [use_endomorphism=no])
128 
129 AC_ARG_ENABLE(ecmult_static_precomputation,
130-    AS_HELP_STRING([--enable-ecmult-static-precomputation],[enable precomputed ecmult table for signing (default is yes)]),

theuni commented at 4:26 pm on April 5, 2019:

s/yes/auto/

theuni approved

theuni commented at 4:33 pm on April 5, 2019: contributor

Buildsystem changes look good to me other than the one nit. Untested, but looks correct.

No comment on the change itself.

real-or-random commented at 7:20 pm on April 5, 2019: contributor

Addressed the nit, I can squash if you want.

sipa commented at 8:03 pm on April 5, 2019: contributor

utACK after squash

gmaxwell commented at 9:49 am on April 6, 2019: contributor

squash please!

real-or-random force-pushed on Apr 6, 2019

real-or-random commented at 12:09 pm on April 6, 2019: contributor

yeah, squashed.

gmaxwell commented at 6:15 pm on April 6, 2019: contributor

See above:

The comment is wrong, overflow happens at 33 (or 31 non-endo) not 34. src/ecmult_impl.h:298:42: warning: integer overflow in expression of type ‘int’ results in ‘2147483647’ [-Woverflow] VERIFY_CHECK((n) >= -((1 « ((w)-1)) - 1)); \

real-or-random commented at 2:10 pm on April 8, 2019: contributor

Oops, I forgot that one. When changing the comment, I noticed that we run into problems earlier if size_t is 32 bits. I added a VERIFY_CHECK to check for this.

gmaxwell commented at 6:29 pm on April 21, 2019: contributor

The fixup looks okay to me.

laanwj cross-referenced this on May 7, 2019 from issue Compile secp256 in U-boot by tmagik

gmaxwell commented at 10:56 pm on May 9, 2019: contributor

Can you squash your fixup?

gmaxwell commented at 0:00 am on May 10, 2019: contributor

Also– it’s still shrinking the table sizes one lower than the configured value w/ endo… so making the auto value one smaller yet is making it two smaller.

real-or-random commented at 5:00 pm on May 10, 2019: contributor

sure I’ll squash. But I’m not sure I can parse your comment.

Somewhere above, I wrote:

I think it’s better to keep the property that the table size depends on the parameter only (and not on endo), so I’d rather set the default to 15 or 16 depending on whether endo is on.

That’s why I did it differently. So you’re asking not to do that and instead do what you originally had proposed, i.e., “eliminate the -1 on the endomorphism and decrease the default to 15 from 16”? (Fine with me of course, I just want to make sure that I understand what you’re saying.)

gmaxwell commented at 8:34 pm on May 10, 2019: contributor

no no .. okay so I thought what you did was eliminate the -1 but then make the default (‘auto’) mean 15 or 16 depending on the endomorphism setting. That is what the configure text claimed.

But what I observe is that the size of –with-ecmult-window=constant (e.g. 4) that ECMULT_TABLE_SIZE(WINDOW_G) depends on the endomorphism. I wasn’t expecting that. [And maybe I made a mistake, if you think it doesn’t work that way– I didn’t check carefully, just noticed when quickly stuffing endomorphism support in for that for-discussion PR]

I don’t actually have a really strong feeling one way or another, though my static constants patch would be slightly cleaner if ECMULT_TABLE_SIZE(WINDOW_G) depended only on with-ecmult-window and not on endomorphism, and setting endo just had the effect of there being two tables instead of one.

in src/ecmult_impl.h:45 in 2df0ded241 outdated

49+ */
50+#  ifdef USE_ENDOMORPHISM
51+#    define WINDOW_G ((ECMULT_WINDOW_SIZE)-1)
52+#  else
53+#    define WINDOW_G (ECMULT_WINDOW_SIZE)
54+#  endif

real-or-random commented at 8:54 am on May 14, 2019:

Yes, so at the moment, what I mean by “table size” here is the the size of the all tables together, and it’s an implementation detail whether there are one or two tables. But I see the point with your new PR. The complexity that I added is not really worth the hassle. We can just instead document that there will be two tables when endo is on.

real-or-random force-pushed on May 16, 2019

real-or-random commented at 9:20 pm on May 16, 2019: contributor

I squashed (see real-or-random:config-window-size-fixup for reference/easier re-review), and then updated to remove the -1.

real-or-random cross-referenced this on May 24, 2019 from issue variable sized precomputed table for signing by douglasbakkum

Make WINDOW_G configurable

This makes WINDOW_G a configurable value in the range of [2..24].
The upper limit of 24 is a defensive choice. The code is probably
correct for values up to 27 but those larger values yield in huge
tables (>= 256MiB), which are i) unlikely to be really beneficial
in practice and ii) increasingly difficult to test.

2842dc523e

Clean up ./configure help strings a61a93ff50

real-or-random force-pushed on May 24, 2019

real-or-random commented at 7:05 pm on May 24, 2019: contributor

Pushed again, I forgot to adapt some comments and the commit message.

gmaxwell commented at 10:57 am on May 25, 2019: contributor

ACK. In the long run, we may want to restrict the number of options to make testing all of them more reasonable (took me a couple hours), but I think the extra flexibility is good for now.

gmaxwell merged this on May 25, 2019

gmaxwell closed this on May 25, 2019

gmaxwell referenced this in commit 36698dcfee on May 25, 2019

real-or-random cross-referenced this on Jun 17, 2019 from issue Low-footprint mode by gmaxwell

real-or-random cross-referenced this on Jan 6, 2020 from issue General CI discussion by real-or-random

sipa cross-referenced this on Jun 9, 2020 from issue Update libsecp256k1 subtree by sipa

fanquake referenced this in commit 8c97780db8 on Jun 13, 2020

sidhujag referenced this in commit 8a3a072968 on Jun 13, 2020

ComputerCraftr referenced this in commit b98f1c6e6c on Jun 16, 2020

UdjinM6 referenced this in commit 9d36ba6570 on Aug 10, 2021

5tefan referenced this in commit 8ded2caa74 on Aug 12, 2021

gades referenced this in commit d855cc511d on May 8, 2022

Make WINDOW_G configurable #596