Make WINDOW_G configurable #596

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 12: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

for 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
3 ecdsa_verify: min 67.8us / avg 67.9us / max 68.1us
4 ecdsa_verify: min 61.4us / avg 61.5us / max 61.7us
5 ecdsa_verify: min 57.4us / avg 57.8us / max 58.6us
6 ecdsa_verify: min 54.7us / avg 54.9us / max 55.1us
7 ecdsa_verify: min 53.0us / avg 53.4us / max 54.9us
8 ecdsa_verify: min 51.5us / avg 51.6us / max 51.7us
9 ecdsa_verify: min 50.4us / avg 50.5us / max 50.8us
10 ecdsa_verify: min 49.6us / avg 49.7us / max 49.8us
11 ecdsa_verify: min 48.8us / avg 49.0us / max 49.1us
12 ecdsa_verify: min 48.2us / avg 48.3us / max 48.5us
13 ecdsa_verify: min 47.8us / avg 47.9us / max 47.9us
14 ecdsa_verify: min 47.4us / avg 47.5us / max 47.8us
15 ecdsa_verify: min 46.8us / avg 47.0us / max 47.2us
16 ecdsa_verify: min 46.7us / avg 46.9us / max 47.3us
17 ecdsa_verify: min 46.3us / avg 46.5us / max 47.0us
18 ecdsa_verify: min 46.4us / avg 46.5us / max 46.7us
19 ecdsa_verify: min 46.3us / avg 46.4us / max 46.6us
20 ecdsa_verify: min 46.4us / avg 46.5us / max 46.6us
21 ecdsa_verify: min 46.5us / avg 46.5us / max 46.6us
22 ecdsa_verify: min 46.1us / avg 46.1us / max 46.2us
23 ecdsa_verify: min 45.9us / avg 46.0us / max 46.2us
24 ecdsa_verify: min 45.8us / avg 45.9us / max 46.0us
25 ecdsa_verify: min 45.9us / avg 46.1us / max 46.2us
26 ecdsa_verify: min 45.7us / avg 46.0us / max 46.8us
27 ecdsa_verify: min 45.4us / avg 45.6us / max 45.7us
28 ecdsa_verify: min 45.5us / avg 45.7us / max 45.8us
29 ecdsa_verify: min 45.5us / avg 45.6us / max 45.7us
for 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
3 ecdsa_verify: min 79.7us / avg 79.8us / max 80.0us
4 ecdsa_verify: min 75.6us / avg 75.7us / max 76.0us
5 ecdsa_verify: min 73.3us / avg 73.3us / max 73.4us
6 ecdsa_verify: min 71.4us / avg 71.6us / max 71.8us
7 ecdsa_verify: min 69.9us / avg 70.1us / max 70.2us
8 ecdsa_verify: min 69.0us / avg 69.0us / max 69.1us
9 ecdsa_verify: min 67.8us / avg 68.0us / max 68.1us
10 ecdsa_verify: min 67.3us / avg 67.4us / max 67.8us
11 ecdsa_verify: min 66.8us / avg 66.9us / max 67.0us
12 ecdsa_verify: min 66.2us / avg 66.3us / max 66.5us
13 ecdsa_verify: min 65.8us / avg 65.9us / max 66.1us
14 ecdsa_verify: min 65.5us / avg 65.6us / max 65.8us
15 ecdsa_verify: min 65.1us / avg 65.5us / max 67.4us
16 ecdsa_verify: min 65.0us / avg 65.1us / max 65.3us
17 ecdsa_verify: min 64.6us / avg 64.7us / max 64.9us
18 ecdsa_verify: min 64.6us / avg 64.8us / max 64.9us
19 ecdsa_verify: min 64.8us / avg 64.9us / max 65.1us
20 ecdsa_verify: min 64.6us / avg 64.8us / max 65.0us
21 ecdsa_verify: min 64.5us / avg 64.6us / max 64.7us
22 ecdsa_verify: min 64.4us / avg 64.5us / max 64.7us
23 ecdsa_verify: min 64.2us / avg 64.3us / max 64.4us
24 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

$ 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
3 ecdsa_verify: min 81.6us / avg 81.7us / max 82.0us
4 ecdsa_verify: min 74.1us / avg 74.1us / max 74.4us
5 ecdsa_verify: min 69.2us / avg 69.3us / max 69.5us
6 ecdsa_verify: min 66.1us / avg 66.2us / max 66.6us
7 ecdsa_verify: min 63.9us / avg 64.0us / max 64.2us
8 ecdsa_verify: min 62.2us / avg 62.3us / max 62.6us
9 ecdsa_verify: min 60.9us / avg 60.9us / max 61.1us
10 ecdsa_verify: min 59.9us / avg 59.9us / max 60.3us
11 ecdsa_verify: min 59.0us / avg 59.1us / max 59.4us
12 ecdsa_verify: min 58.3us / avg 58.4us / max 58.7us
13 ecdsa_verify: min 57.9us / avg 57.9us / max 58.2us
14 ecdsa_verify: min 57.4us / avg 57.4us / max 57.6us
15 ecdsa_verify: min 56.7us / avg 56.7us / max 56.8us
16 ecdsa_verify: min 56.6us / avg 56.6us / max 56.6us
17 ecdsa_verify: min 56.0us / avg 56.0us / max 56.0us
18 ecdsa_verify: min 56.0us / avg 56.0us / max 56.0us
19 ecdsa_verify: min 55.5us / avg 55.6us / max 55.7us
20 ecdsa_verify: min 55.8us / avg 55.9us / max 56.0us
21 ecdsa_verify: min 56.0us / avg 56.0us / max 56.0us
22 ecdsa_verify: min 55.4us / avg 55.5us / max 55.5us
23 ecdsa_verify: min 55.3us / avg 55.4us / max 55.9us
24 ecdsa_verify: min 55.3us / avg 55.3us / max 55.3us
$ 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
3 ecdsa_verify: min 96.0us / avg 96.0us / max 96.3us
4 ecdsa_verify: min 91.2us / avg 91.2us / max 91.6us
5 ecdsa_verify: min 88.0us / avg 88.1us / max 88.3us
6 ecdsa_verify: min 86.1us / avg 86.1us / max 86.4us
7 ecdsa_verify: min 84.2us / avg 84.3us / max 84.6us
8 ecdsa_verify: min 83.1us / avg 83.2us / max 83.5us
9 ecdsa_verify: min 81.9us / avg 82.0us / max 82.3us
10 ecdsa_verify: min 81.3us / avg 81.4us / max 81.7us
11 ecdsa_verify: min 80.5us / avg 80.5us / max 81.1us
12 ecdsa_verify: min 79.9us / avg 79.9us / max 80.2us
13 ecdsa_verify: min 79.4us / avg 79.4us / max 79.7us
14 ecdsa_verify: min 79.0us / avg 79.0us / max 79.1us
15 ecdsa_verify: min 78.7us / avg 78.8us / max 78.9us
16 ecdsa_verify: min 78.3us / avg 78.4us / max 78.5us
17 ecdsa_verify: min 78.0us / avg 78.0us / max 78.0us
18 ecdsa_verify: min 77.7us / avg 77.8us / max 78.4us
19 ecdsa_verify: min 77.8us / avg 77.8us / max 77.9us
20 ecdsa_verify: min 77.9us / avg 77.9us / max 77.9us
21 ecdsa_verify: min 77.7us / avg 77.7us / max 77.7us
22 ecdsa_verify: min 77.7us / avg 77.7us / max 78.0us
23 ecdsa_verify: min 77.5us / avg 77.6us / max 77.6us
24 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

$ 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
3 ecdsa_verify: min 67.5us / avg 67.7us / max 67.9us
4 ecdsa_verify: min 61.3us / avg 61.7us / max 62.0us
5 ecdsa_verify: min 57.1us / avg 57.2us / max 57.4us
6 ecdsa_verify: min 54.8us / avg 54.8us / max 54.8us
7 ecdsa_verify: min 52.8us / avg 52.9us / max 53.0us
8 ecdsa_verify: min 51.6us / avg 51.7us / max 51.8us
9 ecdsa_verify: min 50.7us / avg 50.7us / max 50.9us
10 ecdsa_verify: min 49.6us / avg 49.6us / max 49.7us
11 ecdsa_verify: min 49.1us / avg 49.1us / max 49.1us
12 ecdsa_verify: min 48.5us / avg 48.5us / max 48.7us
13 ecdsa_verify: min 47.8us / avg 47.8us / max 47.9us
14 ecdsa_verify: min 47.4us / avg 47.4us / max 47.4us
15 ecdsa_verify: min 46.9us / avg 46.9us / max 47.0us
16 ecdsa_verify: min 47.3us / avg 47.4us / max 47.5us
17 ecdsa_verify: min 46.0us / avg 46.1us / max 46.1us
18 ecdsa_verify: min 46.3us / avg 46.3us / max 46.4us
19 ecdsa_verify: min 46.2us / avg 46.2us / max 46.4us
20 ecdsa_verify: min 47.2us / avg 47.2us / max 47.2us
21 ecdsa_verify: min 46.7us / avg 46.8us / max 46.8us
22 ecdsa_verify: min 46.6us / avg 46.7us / max 46.7us
23 ecdsa_verify: min 46.8us / avg 46.8us / max 46.8us
24 ecdsa_verify: min 46.7us / avg 46.7us / max 46.8us
25 ecdsa_verify: min 47.0us / avg 47.0us / max 47.1us
26 ecdsa_verify: min 46.5us / avg 46.5us / max 46.5us
27 ecdsa_verify: min 46.5us / avg 46.6us / max 46.6us
28 ecdsa_verify: min 46.7us / avg 46.8us / max 46.9us
29 ecdsa_verify: min 46.6us / avg 46.7us / max 46.7us
$ 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
3 ecdsa_verify: min 80.0us / avg 80.0us / max 80.1us
4 ecdsa_verify: min 76.4us / avg 76.6us / max 76.6us
5 ecdsa_verify: min 73.2us / avg 73.6us / max 73.7us
6 ecdsa_verify: min 71.7us / avg 71.8us / max 72.0us
7 ecdsa_verify: min 71.0us / avg 71.1us / max 71.2us
8 ecdsa_verify: min 69.7us / avg 69.8us / max 69.8us
9 ecdsa_verify: min 68.4us / avg 68.5us / max 68.5us
10 ecdsa_verify: min 67.8us / avg 67.8us / max 67.8us
11 ecdsa_verify: min 66.8us / avg 66.8us / max 66.9us
12 ecdsa_verify: min 67.6us / avg 67.6us / max 67.6us
13 ecdsa_verify: min 66.0us / avg 66.2us / max 66.3us
14 ecdsa_verify: min 65.6us / avg 65.6us / max 65.8us
15 ecdsa_verify: min 65.9us / avg 66.0us / max 66.0us
16 ecdsa_verify: min 65.7us / avg 65.8us / max 65.8us
17 ecdsa_verify: min 64.8us / avg 65.6us / max 65.9us
18 ecdsa_verify: min 64.9us / avg 64.9us / max 65.0us
19 ecdsa_verify: min 65.6us / avg 65.8us / max 65.9us
20 ecdsa_verify: min 66.2us / avg 66.3us / max 66.4us
21 ecdsa_verify: min 66.2us / avg 66.3us / max 66.4us
22 ecdsa_verify: min 65.5us / avg 65.5us / max 65.6us
23 ecdsa_verify: min 65.4us / avg 65.5us / max 65.5us
24 ecdsa_verify: min 65.9us / avg 65.9us / max 65.9us
25 ecdsa_verify: min 65.3us / avg 65.3us / max 65.4us
26 ecdsa_verify: min 66.1us / avg 66.1us / max 66.2us
27 ecdsa_verify: min 66.1us / avg 66.1us / max 66.1us
28 ecdsa_verify: min 65.8us / avg 66.1us / max 67.5us
29 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)

$ 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
3 ecdsa_verify: min 87.2us / avg 88.6us / max 94.5us
4 ecdsa_verify: min 79.0us / avg 79.8us / max 86.3us
5 ecdsa_verify: min 73.9us / avg 74.7us / max 80.9us
6 ecdsa_verify: min 70.5us / avg 71.9us / max 77.4us
7 ecdsa_verify: min 68.3us / avg 69.2us / max 75.4us
8 ecdsa_verify: min 66.4us / avg 67.3us / max 70.1us
9 ecdsa_verify: min 65.0us / avg 67.0us / max 73.3us
10 ecdsa_verify: min 63.9us / avg 65.1us / max 70.7us
11 ecdsa_verify: min 63.0us / avg 63.5us / max 68.5us
12 ecdsa_verify: min 62.5us / avg 63.3us / max 70.2us
13 ecdsa_verify: min 61.6us / avg 62.4us / max 68.9us
14 ecdsa_verify: min 61.3us / avg 61.9us / max 67.5us
15 ecdsa_verify: min 60.8us / avg 61.5us / max 67.4us
16 ecdsa_verify: min 60.6us / avg 61.2us / max 66.8us
17 ecdsa_verify: min 59.8us / avg 61.5us / max 66.7us
18 ecdsa_verify: min 60.0us / avg 61.1us / max 65.5us
19 ecdsa_verify: min 59.4us / avg 59.9us / max 63.9us
20 ecdsa_verify: min 59.4us / avg 60.2us / max 63.3us
21 ecdsa_verify: min 59.4us / avg 59.7us / max 61.7us
22 ecdsa_verify: min 58.6us / avg 59.1us / max 59.7us
23 ecdsa_verify: min 58.9us / avg 59.2us / max 59.7us
24 ecdsa_verify: min 59.2us / avg 59.3us / max 59.8us
$ 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
3 ecdsa_verify: min 102us / avg 103us / max 109us
4 ecdsa_verify: min 96.9us / avg 97.8us / max 104us
5 ecdsa_verify: min 93.5us / avg 94.2us / max 101us
6 ecdsa_verify: min 91.1us / avg 92.8us / max 98.5us
7 ecdsa_verify: min 89.4us / avg 91.3us / max 96.9us
8 ecdsa_verify: min 87.9us / avg 89.0us / max 95.3us
9 ecdsa_verify: min 86.9us / avg 87.6us / max 93.4us
10 ecdsa_verify: min 85.9us / avg 86.6us / max 92.8us
11 ecdsa_verify: min 85.3us / avg 86.0us / max 92.1us
12 ecdsa_verify: min 84.5us / avg 86.3us / max 91.6us
13 ecdsa_verify: min 84.1us / avg 84.9us / max 92.0us
14 ecdsa_verify: min 83.6us / avg 86.2us / max 90.4us
15 ecdsa_verify: min 83.5us / avg 84.3us / max 90.5us
16 ecdsa_verify: min 83.1us / avg 84.7us / max 89.5us
17 ecdsa_verify: min 82.9us / avg 83.7us / max 89.2us
18 ecdsa_verify: min 82.3us / avg 83.1us / max 88.1us
19 ecdsa_verify: min 82.2us / avg 83.0us / max 86.6us
20 ecdsa_verify: min 82.2us / avg 84.6us / max 89.0us
21 ecdsa_verify: min 81.9us / avg 82.6us / max 84.6us
22 ecdsa_verify: min 205us / avg 205us / max 205us
23 ecdsa_verify: min 81.8us / avg 85.0us / max 112us
24 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)

$ for i in `seq 3 32` ; do echo -n $i' ' ; ./configure --disable-openssl-tests --with-bignum=gmp --enable-endomorphism  -
-enable-benchmark --with-ecmult-window=$i > /dev/null ; make -j4 > /dev/null ; ./bench_verify ; done
3 ecdsa_verify: min 95.8us / avg 95.9us / max 96.6us
4 ecdsa_verify: min 87.1us / avg 87.1us / max 87.6us
5 ecdsa_verify: min 81.7us / avg 81.8us / max 82.8us
6 ecdsa_verify: min 76.6us / avg 76.7us / max 77.2us
7 ecdsa_verify: min 75.7us / avg 75.8us / max 76.4us
8 ecdsa_verify: min 73.8us / avg 74.0us / max 74.8us
9 ecdsa_verify: min 72.2us / avg 72.3us / max 73.0us
10 ecdsa_verify: min 71.1us / avg 71.1us / max 71.8us
11 ecdsa_verify: min 70.1us / avg 70.2us / max 70.9us
12 ecdsa_verify: min 69.3us / avg 69.4us / max 70.4us
13 ecdsa_verify: min 68.6us / avg 68.7us / max 69.3us
14 ecdsa_verify: min 68.1us / avg 68.2us / max 68.8us
15 ecdsa_verify: min 67.4us / avg 67.5us / max 68.0us
16 ecdsa_verify: min 67.2us / avg 67.3us / max 67.7us
17 ecdsa_verify: min 66.6us / avg 66.6us / max 66.9us
18 ecdsa_verify: min 66.6us / avg 66.6us / max 66.8us
19 ecdsa_verify: min 65.9us / avg 65.9us / max 66.0us
20 ecdsa_verify: min 66.0us / avg 66.1us / max 66.2us
21 ecdsa_verify: min 66.1us / avg 66.1us / max 66.2us
22 ecdsa_verify: min 65.6us / avg 65.6us / max 65.7us
23 ecdsa_verify: min 65.3us / avg 65.4us / max 65.6us
24 ecdsa_verify: min 65.4us / avg 65.5us / max 65.7us
25 ecdsa_verify: min 65.4us / avg 65.6us / max 65.8us
26 ecdsa_verify: min 65.1us / avg 65.1us / max 65.4us
27 ecdsa_verify: min 64.6us / avg 64.7us / max 65.0us
28 ecdsa_verify: min 64.6us / avg 64.7us / max 64.9us
29 ecdsa_verify: min 64.6us / avg 64.7us / max 64.9us
30 ecdsa_verify: min 64.6us / avg 64.6us / max 64.9us
31 ecdsa_verify: min 64.7us / avg 64.7us / max 65.1us
32 ecdsa_verify: min 64.7us / avg 64.8us / max 65.1us
$ for i in `seq 3 32` ; do echo -n $i' ' ; ./configure --disable-openssl-tests --with-bignum=gmp --enable-benchmark --wit
h-ecmult-window=$i > /dev/null ; make -j4 > /dev/null ; ./bench_verify ; done
3 ecdsa_verify: min 113us / avg 114us / max 114us
4 ecdsa_verify: min 108us / avg 108us / max 109us
5 ecdsa_verify: min 105us / avg 105us / max 105us
6 ecdsa_verify: min 103us / avg 103us / max 103us
7 ecdsa_verify: min 101us / avg 101us / max 102us
8 ecdsa_verify: min 99.3us / avg 99.4us / max 100us
9 ecdsa_verify: min 98.2us / avg 98.3us / max 98.9us
10 ecdsa_verify: min 97.3us / avg 97.4us / max 97.9us
11 ecdsa_verify: min 96.5us / avg 96.6us / max 97.2us
12 ecdsa_verify: min 95.8us / avg 95.9us / max 96.5us
13 ecdsa_verify: min 95.3us / avg 95.4us / max 96.0us
14 ecdsa_verify: min 94.9us / avg 94.9us / max 95.4us
15 ecdsa_verify: min 94.4us / avg 94.5us / max 94.8us
16 ecdsa_verify: min 94.1us / avg 94.2us / max 94.5us
17 ecdsa_verify: min 93.8us / avg 93.8us / max 94.0us
18 ecdsa_verify: min 93.4us / avg 93.4us / max 93.5us
19 ecdsa_verify: min 93.2us / avg 93.2us / max 93.3us
20 ecdsa_verify: min 93.2us / avg 93.3us / max 93.4us
21 ecdsa_verify: min 93.0us / avg 93.1us / max 93.8us
22 ecdsa_verify: min 93.0us / avg 93.1us / max 93.2us
23 ecdsa_verify: min 92.7us / avg 92.8us / max 93.0us
24 ecdsa_verify: min 92.8us / avg 92.8us / max 93.1us
25 ecdsa_verify: min 92.4us / avg 92.5us / max 92.8us
26 ecdsa_verify: min 92.4us / avg 92.4us / max 92.7us
27 ecdsa_verify: min 92.4us / avg 92.5us / max 92.7us
28 ecdsa_verify: min 92.0us / avg 92.1us / max 92.3us
29 ecdsa_verify: min 91.9us / avg 92.0us / max 92.2us
30 ecdsa_verify: min 92.0us / avg 92.0us / max 92.3us
31 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

$ 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
3 ecdsa_verify: min 183us / avg 187us / max 191us
4 ecdsa_verify: min 166us / avg 167us / max 173us
5 ecdsa_verify: min 155us / avg 156us / max 161us
6 ecdsa_verify: min 148us / avg 150us / max 156us
7 ecdsa_verify: min 143us / avg 145us / max 149us
8 ecdsa_verify: min 139us / avg 141us / max 144us
9 ecdsa_verify: min 136us / avg 137us / max 139us
10 ecdsa_verify: min 134us / avg 136us / max 142us
11 ecdsa_verify: min 132us / avg 133us / max 137us
12 ecdsa_verify: min 131us / avg 132us / max 133us
13 ecdsa_verify: min 129us / avg 132us / max 140us
14 ecdsa_verify: min 128us / avg 129us / max 134us
15 ecdsa_verify: min 127us / avg 129us / max 133us
16 ecdsa_verify: min 127us / avg 128us / max 129us
17 ecdsa_verify: min 126us / avg 127us / max 131us
18 ecdsa_verify: min 126us / avg 127us / max 134us
19 ecdsa_verify: min 125us / avg 125us / max 125us
20 ecdsa_verify: min 125us / avg 127us / max 132us
21 ecdsa_verify: min 125us / avg 125us / max 126us
22 ecdsa_verify: min 123us / avg 123us / max 124us
23 ecdsa_verify: min 123us / avg 125us / max 131us
24 ecdsa_verify: min 124us / avg 124us / max 124us
$ 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
3 ecdsa_verify: min 214us / avg 216us / max 221us
4 ecdsa_verify: min 204us / avg 205us / max 210us
5 ecdsa_verify: min 198us / avg 199us / max 200us
6 ecdsa_verify: min 192us / avg 193us / max 195us
7 ecdsa_verify: min 188us / avg 189us / max 194us
8 ecdsa_verify: min 185us / avg 186us / max 186us
9 ecdsa_verify: min 184us / avg 185us / max 190us
10 ecdsa_verify: min 182us / avg 182us / max 183us
11 ecdsa_verify: min 180us / avg 181us / max 189us
12 ecdsa_verify: min 179us / avg 180us / max 186us
13 ecdsa_verify: min 177us / avg 178us / max 178us
14 ecdsa_verify: min 177us / avg 179us / max 190us
15 ecdsa_verify: min 176us / avg 177us / max 177us
16 ecdsa_verify: min 176us / avg 178us / max 184us
17 ecdsa_verify: min 175us / avg 175us / max 175us
18 ecdsa_verify: min 175us / avg 177us / max 183us
19 ecdsa_verify: min 174us / avg 175us / max 176us
20 ecdsa_verify: min 175us / avg 176us / max 181us
21 ecdsa_verify: min 174us / avg 174us / max 176us
22 ecdsa_verify: min 174us / avg 175us / max 181us
23 ecdsa_verify: min 172us / avg 173us / max 177us
24 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)]

$ 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
3 ecdsa_verify: min 1064us / avg 1065us / max 1065us
4 ecdsa_verify: min 960us / avg 962us / max 971us
5 ecdsa_verify: min 901us / avg 903us / max 906us
6 ecdsa_verify: min 860us / avg 861us / max 862us
7 ecdsa_verify: min 829us / avg 832us / max 835us
8 ecdsa_verify: min 810us / avg 811us / max 814us
9 ecdsa_verify: min 790us / avg 790us / max 793us
10 ecdsa_verify: min 777us / avg 777us / max 779us
11 ecdsa_verify: min 766us / avg 766us / max 767us
12 ecdsa_verify: min 760us / avg 762us / max 770us
13 ecdsa_verify: min 754us / avg 755us / max 763us
14 ecdsa_verify: min 745us / avg 748us / max 755us
15 ecdsa_verify: min 741us / avg 742us / max 746us
16 ecdsa_verify: min 737us / avg 737us / max 738us
17 ecdsa_verify: min 732us / avg 733us / max 733us
18 ecdsa_verify: min 732us / avg 734us / max 737us
19 ecdsa_verify: min 724us / avg 725us / max 728us
20 ecdsa_verify: min 720us / avg 722us / max 726us
21 ecdsa_verify: min 722us / avg 723us / max 725us
22 ecdsa_verify: min 712us / avg 715us / max 719us
23 ecdsa_verify: min 712us / avg 715us / max 716us
24 ecdsa_verify: min 715us / avg 716us / max 717us
$ 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
3 ecdsa_verify: min 1265us / avg 1267us / max 1272us
4 ecdsa_verify: min 1204us / avg 1208us / max 1214us
5 ecdsa_verify: min 1163us / avg 1164us / max 1166us
6 ecdsa_verify: min 1134us / avg 1135us / max 1140us
7 ecdsa_verify: min 1116us / avg 1119us / max 1132us
8 ecdsa_verify: min 1099us / avg 1104us / max 1121us
9 ecdsa_verify: min 1081us / avg 1081us / max 1083us
10 ecdsa_verify: min 1075us / avg 1076us / max 1078us
11 ecdsa_verify: min 1067us / avg 1068us / max 1070us
12 ecdsa_verify: min 1058us / avg 1074us / max 1082us
13 ecdsa_verify: min 1048us / avg 1049us / max 1051us
14 ecdsa_verify: min 1053us / avg 1059us / max 1065us
15 ecdsa_verify: min 1042us / avg 1047us / max 1063us
16 ecdsa_verify: min 1035us / avg 1035us / max 1035us
17 ecdsa_verify: min 1037us / avg 1040us / max 1046us
18 ecdsa_verify: min 1033us / avg 1046us / max 1098us
19 ecdsa_verify: min 1032us / avg 1040us / max 1081us
20 ecdsa_verify: min 1028us / avg 1029us / max 1030us
21 ecdsa_verify: min 1023us / avg 1025us / max 1027us
22 ecdsa_verify: min 1029us / avg 1030us / max 1031us
23 ecdsa_verify: min 1020us / avg 1022us / max 1026us
24 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 12: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