Add ecmult_gen, ecmult_const and ecmult to benchmark #662

jonasnick commented at 7:03 PM on September 5, 2019: contributor

I was trying to determine the impact of ecmult_gen in schnorrsig signing and noticed that there is no way to bench this right now. The new benchmarks look like this:

$ ./bench_ecmult
ecmult_gen: min 20.9us / avg 21.2us / max 21.7us
ecmult_const: min 63.9us / avg 64.3us / max 64.8us
ecmult 1: min 49.4us / avg 49.7us / max 50.3us
ecmult 1g: min 39.8us / avg 40.0us / max 40.3us
ecmult 2g: min 27.2us / avg 27.3us / max 27.8us
ecmult_multi 1g: min 39.8us / avg 40.0us / max 40.2us
ecmult_multi 2g: min 27.2us / avg 27.4us / max 27.7us
ecmult_multi 3g: min 22.8us / avg 22.9us / max 23.1us
ecmult_multi 4g: min 20.6us / avg 20.8us / max 21.1us
ecmult_multi 5g: min 19.3us / avg 19.5us / max 19.7us

(Turns out ecmult_gen is 37% of the 55.8us that schnorrsig sign takes)

real-or-random commented at 7:34 PM on September 5, 2019: contributor

Approach ACK

in src/bench_ecmult.c:63 in 34712f1384 outdated

  47 |  
  48 | -static int bench_callback(secp256k1_scalar* sc, secp256k1_ge* ge, size_t idx, void* arg) {
  49 | +/* Hashes x into [0, POINTS) twice and store the result in offset1 and offset2. */
  50 | +static void hash_into_offset(bench_data* data, size_t x) {
  51 | +    data->offset1 = (x * 0x537b7f6f + 0x8f66a481) % POINTS;
  52 | +    data->offset2 = (x * 0x7f6f537b + 0x6a1a8f49) % POINTS;

elichai commented at 8:28 PM on September 27, 2019:

where's this thing from? I see it's also in bench_ecmult_setup but can't find the source of this

jonasnick commented at 1:04 PM on September 28, 2019:

I think is this is just a standard integer hash function (akin to https://en.wikipedia.org/wiki/Universal_hashing#Hashing_integers) whose parameters sipa selected. But looking at it now it may be give poor results because POINTS is not prime.

gmaxwell commented at 12:03 PM on October 15, 2019:

I don't think points needs to be prime, so long as the multipliers are coprime to it.

jonasnick commented at 12:36 PM on October 15, 2019:

fwiw they're all coprime to POINTS.

in src/bench_ecmult.c:128 in 34712f1384 outdated

 125 | +static void bench_ecmult_1_teardown(void* arg) {
 126 | +    bench_data* data = (bench_data*)arg;
 127 | +    bench_ecmult_teardown_helper(data, &data->offset1, &data->offset2, NULL);
 128 | +}
 129 | +
 130 | +static void bench_ecmult_1g(void* arg) {

real-or-random commented at 2:09 PM on October 28, 2019:

static void bench_ecmult_0g(void* arg) {

in src/bench_ecmult.c:139 in 34712f1384 outdated

 136 | +    for (iter = 0; iter < ITERS; ++iter) {
 137 | +        secp256k1_ecmult(&data->ctx->ecmult_ctx, &data->output[iter], NULL, &zero, &data->scalars[(data->offset1+iter) % POINTS]);
 138 | +    }
 139 | +}
 140 | +
 141 | +static void bench_ecmult_1g_teardown(void* arg) {

real-or-random commented at 2:09 PM on October 28, 2019:

static void bench_ecmult_0g_teardown(void* arg) {

and so on..

in src/bench_ecmult.c:144 in 34712f1384 outdated

 141 | +static void bench_ecmult_1g_teardown(void* arg) {
 142 | +    bench_data* data = (bench_data*)arg;
 143 | +    bench_ecmult_teardown_helper(data, NULL, NULL, &data->offset1);
 144 | +}
 145 | +
 146 | +static void bench_ecmult_2g(void* arg) {

real-or-random commented at 2:10 PM on October 28, 2019:

1g

real-or-random commented at 2:10 PM on October 28, 2019: contributor

Looks good otherwise

jonasnick commented at 4:59 PM on October 28, 2019: contributor

@real-or-random I don't think so (unless we change it for ecmult_multi) but it took me a while to figure this out again. I added a commit that printfs an explanation. It's not pretty, but less confusing.

real-or-random commented at 5:21 PM on October 28, 2019: contributor

@real-or-random I don't think so (unless we change it for ecmult_multi) but it took me a while to figure this out again. I added a commit that printfs and explanation. It's not pretty, but less confusing.

Certainly pretty enough for a benchmark. Can you squash?

jonasnick force-pushed on Oct 28, 2019

jonasnick commented at 6:39 PM on October 28, 2019: contributor

squashed

in src/bench_ecmult.c:250 in 6a5673fe67 outdated

 247 | +    run_benchmark(str, bench_ecmult_multi, bench_ecmult_multi_setup, bench_ecmult_multi_teardown, data, 10, count * (1 + ITERS / count));
 248 | +}
 249 | +
 250 | +static void generate_scalar(uint32_t num, secp256k1_scalar* scalar) {
 251 | +    secp256k1_sha256 sha256;
 252 | +    unsigned char c[11] = {'e', 'c', 'm', 'u', 'l', 't', 0, 0, 0, 0};

real-or-random commented at 7:53 AM on October 29, 2019:

I know it's just code you move around but this annoys me every time I see it...

    unsigned char c[10] = {'e', 'c', 'm', 'u', 'l', 't', 0, 0, 0, 0};

It's not a bug because c[10] will be initialized to 0 automatically. But it's a code smell and it can't be wrong to fix it.

ACK for the rest.

jonasnick commented at 8:18 AM on October 29, 2019:

Added commit with fix

real-or-random commented at 8:38 AM on October 29, 2019: contributor

ACK a419f3dddfc96b0c7454985a913b932b77b94b0b I read the code and tried it

jonasnick force-pushed on Apr 30, 2020

jonasnick commented at 2:06 PM on April 30, 2020: contributor

Rebased and added a --help command instead of printing an explanation of the output every time this is run.

in src/bench_ecmult.c:297 in 82a5911d73 outdated

 303 | -            secp256k1_scratch_space_destroy(data.ctx, data.scratch);
 304 | -            data.scratch = NULL;
 305 |          } else {
 306 |              fprintf(stderr, "%s: unrecognized argument '%s'.\n", argv[0], argv[1]);
 307 | -            fprintf(stderr, "Use 'pippenger_wnaf', 'strauss_wnaf', 'simple' or no argument to benchmark a combined algorithm.\n");
 308 | +            fprintf(stderr, "Use '--help', 'pippenger_wnaf', 'strauss_wnaf', 'simple' or no argument to benchmark a combined algorithm.\n");

real-or-random commented at 3:08 PM on May 1, 2020:

simply call help here?

jonasnick commented at 8:45 PM on May 1, 2020:

okay

real-or-random commented at 8:17 PM on May 31, 2021:

Ah sorry, my suggestion was just to replace the entire else branch with help(), not to replace the --help by help. Feel free to change back, or to ignore.

jonasnick commented at 8:44 PM on May 31, 2021:

Fixed

in src/bench_ecmult.c:158 in 82a5911d73 outdated

 299 |          } else if(have_flag(argc, argv, "simple")) {
 300 | -            printf("Using simple algorithm:\n");
 301 | +            printf("Using simple combined algorithm:\n");
 302 |              data.ecmult_multi = secp256k1_ecmult_multi_var;
 303 | -            secp256k1_scratch_space_destroy(data.ctx, data.scratch);
 304 | -            data.scratch = NULL;

real-or-random commented at 3:23 PM on May 1, 2020:

That line got lost, and this was what made the difference between simple and combined? I see you merged this into "simple combined" in the printfs. Was this change on purpose?

jonasnick commented at 8:45 PM on May 1, 2020:

Good catch. I also forgot what the simple algorithm actually does. I fixed this and added an explanation to the help().

jonasnick force-pushed on May 1, 2020

jonasnick commented at 5:42 PM on May 28, 2021: contributor

@real-or-random care to reACK :) ?

real-or-random commented at 8:37 PM on May 31, 2021: contributor

ACK ee83dbf267b34bb4a01c872cd02bf1c8065e3166

jonasnick force-pushed on May 31, 2021

Clean up ecmult_bench to make space for more benchmarks 593e6bad9c

Add ecmult_gen, ecmult_const and ecmult to benchmark 2fe1b50df1

Fix array size in bench_ecmult 8f879c2887

jonasnick commented at 8:56 PM on May 31, 2021: contributor

Rebased to let CI do its thing

sipa commented at 9:18 PM on May 31, 2021: contributor

While we're at it: are no-g variants not interesting?

jonasnick commented at 3:29 PM on June 2, 2021: contributor

Hm with-g seems more interesting (schnorrsig batch verify, taproot tweaks, pedersen commitments,...) but we could add a flag or something for no-g (preferably in a separate PR imho).

real-or-random commented at 3:58 PM on June 5, 2021: contributor

ACK 8f879c2887e166da2ec959ce78078f7b84ebfdf9

elichai commented at 11:38 AM on June 6, 2021: contributor

tACK 8f879c2887e166da2ec959ce78078f7b84ebfdf9

nit, It is a little confusing that the first 5 benchmarks are unrelated to the flag being passed (Maybe we want to move the "Using XXX algorithm" print to just before the relevant benchmarks?)

real-or-random commented at 11:57 AM on June 6, 2021: contributor

nit, It is a little confusing that the first 5 benchmarks are unrelated to the flag being passed (Maybe we want to move the "Using XXX algorithm" print to just before the relevant benchmarks?)

Indeed but this can be done in a separate PR, too.

Let me take the opportunity to merge this PR now that we have two ACKs.

real-or-random merged this on Jun 6, 2021

real-or-random closed this on Jun 6, 2021

jonasnick cross-referenced this on Jun 14, 2021 from issue Upstream PRs 831, 907, 903, 889, 918, 906, 928, 922, 933, Merge bitcoin-core/secp256k1#936: Fix gen_context/ASM build on ARM, 925, 937, 926, Merge bitcoin-core/secp256k1#940: contrib: Explain explicit header guards, 850, 930, 941, 846, 947, 662, 950 by jonasnick