ecmult_multi: Replace scratch space with malloc, use abcd cost model #1789

This is an implementation of the discussed changes from an in-person meeting in October. It removes usage of scratch space in batch validation and replaces it with internal malloc usage. It also adds an ABCD cost model for algorithm selection.

The API and internals follow the drafted spec from the meeting very closely: https://gist.github.com/fjahr/c2a009487dffe7a1fbf17ca1821976ca There are few minor changes that should not change the intended behavior. The test coverage may be currently a bit lower than it was previously. I am guessing an adapted form of the test_ecmult_multi test should be added back and there are some TODOs left in the test code which I am planning to address after a first round of conceptual feedback.

The second commit demonstrates the calibration tooling that I have been using though it's not exactly what has given me the results that are in the PR. I have still been struggling with the calibration code and seem to never really get a result that just works without manual tweaking. The calibration itself as well as the code added there thus is rather a work in progress. I am assuming some version of the calibration code should be added to the repo and I haven't thought much about what the best place to add it is. Putting it into the benchmark and combining it with the python script was just a convenient way for experimentation. I am very open to suggestions on how to change this.

I ran the calibration tool, and I'm getting the following results. It's very close the exisitng results, uptil PIPPENGER_8 after which the C value increases for me (this shouldn't happen right?). I'll run this a few more times.

<details> <summary>My ABCD values</summary>

static const struct secp256k1_ecmult_multi_abcd secp256k1_ecmult_multi_abcds[SECP256K1_ECMULT_MULTI_NUM_ALGOS] = {
    {0,                                     0,                                     1000,  0     },
    {SECP256K1_STRAUSS_POINT_SIZE,          0,                                     113,   143  },
    {SECP256K1_PIPPENGER_POINT_SIZE(1),  SECP256K1_PIPPENGER_FIXED_SIZE(1),  199,   303  },
    {SECP256K1_PIPPENGER_POINT_SIZE(2),  SECP256K1_PIPPENGER_FIXED_SIZE(2),  152,   460  },
    {SECP256K1_PIPPENGER_POINT_SIZE(3),  SECP256K1_PIPPENGER_FIXED_SIZE(3),  117,   782  },
    {SECP256K1_PIPPENGER_POINT_SIZE(4),  SECP256K1_PIPPENGER_FIXED_SIZE(4),  100,   1158 },
    {SECP256K1_PIPPENGER_POINT_SIZE(5),  SECP256K1_PIPPENGER_FIXED_SIZE(5),  86,    1837 },
    {SECP256K1_PIPPENGER_POINT_SIZE(6),  SECP256K1_PIPPENGER_FIXED_SIZE(6),  77,    3013 },
    {SECP256K1_PIPPENGER_POINT_SIZE(7),  SECP256K1_PIPPENGER_FIXED_SIZE(7),  72,    4845 },
    {SECP256K1_PIPPENGER_POINT_SIZE(8),  SECP256K1_PIPPENGER_FIXED_SIZE(8),  69,    8775 },
    {SECP256K1_PIPPENGER_POINT_SIZE(9),  SECP256K1_PIPPENGER_FIXED_SIZE(9),  73,    14373},
    {SECP256K1_PIPPENGER_POINT_SIZE(10), SECP256K1_PIPPENGER_FIXED_SIZE(10), 78,    26442},
    {SECP256K1_PIPPENGER_POINT_SIZE(11), SECP256K1_PIPPENGER_FIXED_SIZE(11), 80,    48783},
    {SECP256K1_PIPPENGER_POINT_SIZE(12), SECP256K1_PIPPENGER_FIXED_SIZE(12), 106,   88289},
};

</details>

I’ve visualized the benchmarks for all algorithms (see https://github.com/siv2r/secp256k1/commit/311938612268866bd3dd0cf6c1d006e418518b1d for the diagrams). I’m planning to do a deeper dive into the regression model fit to ensure they align with these results. Will share any useful findings here

I did some analysis on the linear regression model for the CD values (see https://github.com/siv2r/secp256k1/commit/b5985a60454e68c7f88bfe7a9d41b89a47f2b530). I basically ran ./bench_ecmult calib twice. Used the first run to compute the linear regression model, and the second run to test it against new benchmark values.

<details> <summary>ABCD Values</summary>

static const struct secp256k1_ecmult_multi_abcd secp256k1_ecmult_multi_abcds[SECP256K1_ECMULT_MULTI_NUM_ALGOS] = {
    {0,                                     0,                                     1000,  0     },
    {SECP256K1_STRAUSS_POINT_SIZE,          0,                                     112,   173  },
    {SECP256K1_PIPPENGER_POINT_SIZE(1),  SECP256K1_PIPPENGER_FIXED_SIZE(1),  197,   285  },
    {SECP256K1_PIPPENGER_POINT_SIZE(2),  SECP256K1_PIPPENGER_FIXED_SIZE(2),  152,   480  },
    {SECP256K1_PIPPENGER_POINT_SIZE(3),  SECP256K1_PIPPENGER_FIXED_SIZE(3),  117,   767  },
    {SECP256K1_PIPPENGER_POINT_SIZE(4),  SECP256K1_PIPPENGER_FIXED_SIZE(4),  100,   1167 },
    {SECP256K1_PIPPENGER_POINT_SIZE(5),  SECP256K1_PIPPENGER_FIXED_SIZE(5),  86,    1887 },
    {SECP256K1_PIPPENGER_POINT_SIZE(6),  SECP256K1_PIPPENGER_FIXED_SIZE(6),  78,    3023 },
    {SECP256K1_PIPPENGER_POINT_SIZE(7),  SECP256K1_PIPPENGER_FIXED_SIZE(7),  73,    4906 },
    {SECP256K1_PIPPENGER_POINT_SIZE(8),  SECP256K1_PIPPENGER_FIXED_SIZE(8),  70,    8889 },
    {SECP256K1_PIPPENGER_POINT_SIZE(9),  SECP256K1_PIPPENGER_FIXED_SIZE(9),  74,    14544},
    {SECP256K1_PIPPENGER_POINT_SIZE(10), SECP256K1_PIPPENGER_FIXED_SIZE(10), 79,    26764},
    {SECP256K1_PIPPENGER_POINT_SIZE(11), SECP256K1_PIPPENGER_FIXED_SIZE(11), 84,    49179},
    {SECP256K1_PIPPENGER_POINT_SIZE(12), SECP256K1_PIPPENGER_FIXED_SIZE(12), 106,   89518},
};

</details>

<details> <summary>Statistical analysis </summary>

Metric Definitions

Per-Algorithm Metrics

</details>

The linear fit ($R^2$) and standard error for STRAUSS is relatively worse. We can improve this by using smaller batch sizes when calibrating Strauss. I see negative intercepts (i.e., D values) for PIPPENGER_1..4, this should be positive. I think this could also be address by capping these algorithms to medium batch sizes during calibration. Otherwise, the calibrated values are excellent!

Addressed the comments on the implementation code and rebased, thanks a lot for the review @siv2r ! I need a little more time to think about the calibration again, but will comment on that asap.

@siv2r Thanks again for the review! The hint about using more narrow ranges for each of the algos in the calibration was awesome, I didn't think of this before and it pretty much fixed all the problems I ran into with the calibration results. I took these suggestions with some smaller additional tweaks, specifically with Strauss which still had quite a bit of variance. I see pretty stable calibration results between multiple runs now and the measurements between the different benchmarks are running smoother than any of my previous iterations.

These improvements have given me a lot more confidence in these changes, so taking this out of draft status too.

Randomly found #638 when looking at older PRs and found a small bug in my pippenger size calculation from comparing the overlapping code.

Addressed @siv2r 's feedback and rebased, I had kind of lost track of that, sorry.

I re-ran my old analysis on the new ABCD values. The results are very positive, and there's clear improvement in STRAUSS values, the linear fit is better now (0.983 -> 0.998).

<details> <summary>ABCD Values</summary>

static const struct secp256k1_ecmult_multi_abcd secp256k1_ecmult_multi_abcds[SECP256K1_ECMULT_MULTI_NUM_ALGOS] = {
    {0,                                     0,                                     1000,  0     },
    {SECP256K1_STRAUSS_POINT_SIZE,          0,                                     103,   274  },
    {SECP256K1_PIPPENGER_POINT_SIZE(1),  SECP256K1_PIPPENGER_FIXED_SIZE(1),  195,   417  },
    {SECP256K1_PIPPENGER_POINT_SIZE(2),  SECP256K1_PIPPENGER_FIXED_SIZE(2),  147,   602  },
    {SECP256K1_PIPPENGER_POINT_SIZE(3),  SECP256K1_PIPPENGER_FIXED_SIZE(3),  117,   888  },
    {SECP256K1_PIPPENGER_POINT_SIZE(4),  SECP256K1_PIPPENGER_FIXED_SIZE(4),  100,   1390 },
    {SECP256K1_PIPPENGER_POINT_SIZE(5),  SECP256K1_PIPPENGER_FIXED_SIZE(5),  86,    2227 },
    {SECP256K1_PIPPENGER_POINT_SIZE(6),  SECP256K1_PIPPENGER_FIXED_SIZE(6),  76,    3755 },
    {SECP256K1_PIPPENGER_POINT_SIZE(7),  SECP256K1_PIPPENGER_FIXED_SIZE(7),  67,    6626 },
    {SECP256K1_PIPPENGER_POINT_SIZE(8),  SECP256K1_PIPPENGER_FIXED_SIZE(8),  62,    10976},
    {SECP256K1_PIPPENGER_POINT_SIZE(9),  SECP256K1_PIPPENGER_FIXED_SIZE(9),  57,    19909},
    {SECP256K1_PIPPENGER_POINT_SIZE(10), SECP256K1_PIPPENGER_FIXED_SIZE(10), 54,    36574},
    {SECP256K1_PIPPENGER_POINT_SIZE(11), SECP256K1_PIPPENGER_FIXED_SIZE(11), 50,    72630},
    {SECP256K1_PIPPENGER_POINT_SIZE(12), SECP256K1_PIPPENGER_FIXED_SIZE(12), 46,    135404},
};

</details>

<details> <summary>Statistical analysis</summary>

Metric Definitions

Per-Algorithm Metrics

</details>

I was curious whether we could squeeze out better CD values by calibrating each algorithm on its most optimal batch range, instead of the broader ranges we currently use. So I ran all 14 ecmult_multi algorithms across [2, 50000] and plotted the per-point times to figure out which algorithm actually wins at each batch size (see the two toggles below for the full picture).

<details> <summary>graph comparing all 14 algorithms for speedup</summary> <img width="1200" height="800" alt="speedup_vs_individual" src="https://github.com/user-attachments/assets/229b6f11-a580-4831-ac57-f3016a2b758d" />

</details>

<details> <summary>optimal algorithm for each batch size</summary> <img width="1200" height="800" alt="winners_speedup" src="https://github.com/user-attachments/assets/3d8d38fa-de6b-4586-b178-4417f57628f5" />

Optimal Algorithm Ranges

Key Findings

• Never optimal: PIPPENGER_1, PIPPENGER_2, PIPPENGER_3, PIPPENGER_4, PIPPENGER_10 — dominated by neighbors at every batch size.
• Crossover points: STRAUSS -> PIPPENGER_5 at n~92; PIPPENGER_5 -> PIPPENGER_6 at n=140; PIPPENGER_6 -> PIPPENGER_7 at n=275; PIPPENGER_7 -> PIPPENGER_8 at n=875; PIPPENGER_8 -> PIPPENGER_9 at n=1750; PIPPENGER_9 -> PIPPENGER_11 at n=8750; PIPPENGER_11 -> PIPPENGER_12 at n=13750.

Winner at each batch size

</details>

A few things stood out. First, pippenger w=1 through w=4 are never optimal at any batch size — after strauss, ecmult_multi jumps straight to pippenger w=5. The pippenger CD values in general are already well calibrated, which makes sense since the linear fit for those is near perfect (R^2 > 0.999).

The interesting part was strauss. Strauss flatlines after about n=90. So when we calibrate using batches from [2, 500] as we currently do, we're fitting a line to data that stops being linear after 90. Including these flatline points pulls the regression intercept C upward (104 -> 109) and the slope D downward (184 -> 120) compared to what we'd get from fitting just the linear region [2, 90]. In other words, the non-linear tail inflates the C value.

Surprisingly, that inflation is actually helpful. The ecmult_multi_select picks the method that minimizes C + D/n. With the current values (C=109, D=120 for strauss, C=86, D=2187 for pippenger w=5), the crossover n works out to (2187 - 120) / (109 - 86) = 89.9. Which lines up almost perfectly with the empirical data showing pippenger w=5 becomes faster around n=92 (in the second graph above). Also, the old code switched to pippenger at n = 88.

When I tried to "fix" the linear fit by calibrating strauss only on [2, 90] where it's truly linear, I got a much better R^2 (0.9998 vs 0.983) but the crossover moved to n=110. That means ecmult_multi would keep picking strauss all the way through n=110, even though pippenger w=5 is clearly faster by n=95. Better statistical fit, worse algorithm selection.

TL;DR the current CD values are near perfect. The slightly "bad" linear fit for strauss isn't a problem. It is exactly what pushes the crossover to pippenger at the correct batch size (at n=89).

Huge thanks for the helpful review comments @siv2r , I think I have addressed them all now.