bug: MultiExp splits the msm when splitting cannot add parallelism

[4waan]

Description

MultiExp decides whether to recursively split the msm in half by comparing costPreSplit
against costPostSplit. The comment above that branch states the contract:

splitting the msm will add operations, but if it allows to use more CPU, it might be worth it.

Found while working on #875, which reworks the window cost model feeding this comparison. That
PR fixes two defects in costFunction and narrows the damage, but the structural problem
survives it, so it is filed separately here.

Expected Behavior

The msm splits only when splitting can fill cores that a single msm would leave idle, that is
when nbChunks < nbCpus. Otherwise it runs unsplit.

Actual Behavior

It splits in a regime where splitting is provably a loss.

Splitting only helps by filling idle cores. The unsplit msm launches
nbChunks = ceil(fr.Bits/c) chunk goroutines, and with c <= 16 that is at least 16 for a
254-bit fr, at least 24 for BW6. So any host with NumCPU <= 16 has no idle capacity to
fill, ever.

Splitting is meanwhile strictly more work:

cost(c, n)        = K * (bucketAddCost(c)*n + 2^c) / c
2 * cost(c, n/2)  = K * (bucketAddCost(c)*n + 2^(c+1)) / c
                  = cost(c, n) + K * 2^c / c

Measured on BLS12-381 G1, Apple M2 (8 cores), MultiExp against the same call with the split
branch forced off, min-of-N, interleaved:

n	NbTasks	split	forced no-split
300	32	1.268ms	1.139ms	+11.4%
700	16	2.492ms	2.281ms	+9.2%
1536	8	4.676ms	3.947ms	+18.5%
1540	8	4.783ms	3.945ms	+21.3%
12358	16	21.553ms	19.376ms	+11.2%
100000	16	124.137ms	117.566ms	+5.6%
200000	16	255.415ms	240.573ms	+6.2%

Every split that fired lost. None won.

#875 removes most of these, mainly by fixing nbCpus, which was being handed config.NbTasks
(default NumCPU*2) and so was inventing parallelism that does not exist. Post-#875 the firing
band on 8 cores narrows to n in [96904, 740066], which still contains the last two rows.

Possible Fix

The branch should be gated, not deleted. When nbChunks < nbCpus there is real idle capacity:
at NumCPU = 64, C = 16 gives 16 chunks on 64 cores, and splitting to 34 chunks still fits in
one wave for a genuine near-2x. The model predicts ratio = 0.51 there and that one is real.

1. Gate the split on the only condition that can make it profitable: nbChunks < nbCpus. Cheap,
   provably safe, and it removes the entire misfiring regime on the machines most people run on.
2. Replace the wave model with a makespan estimate that bills a partial wave in proportion
   rather than in full, and that charges the split arm for the work it actually adds (the second
   set of bucket reductions and the second msmReduceChunk).
3. If 2 is done, consider splitting into ceil(nbCpus/nbChunks) parts rather than always 2. The
   current recursion reaches other factors only by splitting again, and each level re-pays the
   reduction.

Root cause

costFunction models a barrier-synchronised wave scheduler. It charges
ceil(nbTasks/nbCpus) waves, each a full costPerTask, so a partially filled last wave costs
exactly as much as a full one. That rounding is the entire source of the split verdict.

8 cores, n = 110652, BN254 G1: C = 13, 20 chunks, so 3 waves (8 + 8 + 4). Split gives
cPostSplit = 13 and 40 chunks, so 5 waves, but each chunk carries about half the points.
5 * 0.5 < 3 * 1, so the model buys the split from the 4-chunk wave being billed as 8.

_innerMsm has no waves to round. The semaphore is only allocated when
config.NbTasks < runtime.NumCPU(), and NbTasks defaults to NumCPU*2, so at the default it
is nil and all nbChunks goroutines are launched at once for the Go scheduler to run over
GOMAXPROCS, with no barrier anywhere. Splitting halves NbTasks to NumCPU, which is still
not < NumCPU, so it stays nil and both halves launch their full chunk sets concurrently.
The model and the implementation disagree about the scheduler.

Steps to Reproduce

The firing bands are pure functions of the generated cost model, so they can be enumerated
without benchmarking.

1. Add a test in ecc/bn254 that replays the costFunction block from MultiExp, calling the
   generated bestCG1, computeNbChunks and msmChunkCost.

2. Sweep n and a simulated NumCPU, with NbTasks = 2*NumCPU as the default sets it, and
   record where costPostSplit < costPreSplit.

3. For BN254 G1 this reports:

   numcpu=  4  fires in [672973, 740066]
   numcpu=  8  fires in [96904, 740066]
   numcpu= 12  fires in [1237, 8388603]
   numcpu= 16  fires in [12365, 740066]
   numcpu= 32  fires in [483, 8388603]
   numcpu= 64  fires in [1237, 8388603]
   

   Every row up to 16 cores is in the regime where nbChunks >= nbCpus, so every one of those
   splits is a loss.

4. To confirm on the clock, benchmark MultiExp at an n inside the band against a build with
   the if costPostSplit < costPreSplit branch forced to false.

Environment

• gnark-crypto version used: master at v0.21.0, and the branch for perf(ecc): price the batch-affine chunk processor in the MultiExp cost model #875
• go version: 1.25.7 darwin/arm64
• OS and version: macOS 26.5.1, Apple M2, 8 cores

[4waan]

ran the enumeration exhaustively rather than sampled, over every curve in the repo. The result
is sharper than what I claimed above, and it corrects two numbers in the description.

Setup. All 11 curves, 18 curve and group pairs, nbPoints from 2 to 2^24 with no sampling,
9 core counts times 3 NbTasks policies (2*NumCPU, NumCPU, NumCPU/2). 486 rows, 8.1
billion decisions, driven by the generated bestC / msmChunkCost / computeNbChunks rather
than a reimplementation. Each decision is scored against an oracle that is the same wave model
with a partial wave billed pro rata instead of in full, which is the fluid limit _innerMsm
actually runs at when the semaphore is nil.

Two more invariants held across the whole sweep:

• Splitting strictly increased total work at every single firing. Zero exceptions in 8.1e9.
• The decision depends only on nbCpus = min(NbTasks, NumCPU). The NumCPU/2 rows at 2k
  cores reproduce the default rows at k cores exactly, so a 24 core host with NbTasks = 12
  misfires identically to a 12 core host at the default.

Some core counts are worse than the description suggests. These are not bounded bands:

nbCpus	curve, group	fires over	sizes hit	worst modeled slowdown
4	BN254 G1	[672962, 740071]	67k	1.085
8	BN254 G1	[96896, 740071]	643k	1.137
8	BW6-633 G1	[3992, 2^24]	16.6M	1.200
12	BN254 G1	[1225, 2^24]	16.1M, 96% of the range	1.213
16	BN254 G1	[12358, 740071]	728k	1.234
16	secp256k1 G1	[12358, 2^24]	16.8M	1.234
16	BW6-761 G1	[7303, 2^24]	16.7M	1.333
32	BW6-761 G1	[1225, 114486]	111k	1.475

On a 12 core host, BN254, BLS12-381, BLS24-315/317, grumpkin and stark-curve split harmfully at
all but 4% of sizes above 1225 points, two levels of recursion deep. Every curve in the repo is
affected at some core count, and G2 behaves identically to G1 throughout.