MultiExp bench seems a bit "optimistic"

[0x0ece]

See this line:
https://github.com/ConsenSys/gnark-crypto/blob/master/ecc/bls12-377/multiexp_test.go#L209

All points are equal, so the MSM algo is doing a ton of dbl that in ExtJac are considerably faster than add.
As a result the numbers one gets running go test -bench are extremely optimistic.

I'd recommend generating a somewhat random set of points.

[gbotrel]

No the MSM is not doing a ton of dbl; the ExtJac happens on the buckets, not on the points. The bucket values are filled depending on the scalar, which are "reasonably" mixed (not random but still representative).

You can try for your self the benchmarks with randomizing the points, I doubt the result will vary. (it doesn't on my machine for the reference 2 >> 20 size).

edit: not randomizing may indeed trigger more doubling, for the first operation on each bucket index. So ~80ns * len(buckets) (* time chunks) delta, which may bias the result within a ~2% margin (eye balling) for 1 << 20 and c= 16

[0x0ece]

I did try, with random points it's almost 50%-2x slower on my mac. I run both your parallel code and a "single thread" version of the same algo.

When you add to the buckets:

• first point you add, the bucket is empty so you're doing a bucket.Set(point)
• second point you add, for every bucket, it's a dbl if all points are the same

I couldn't test on amd yet, maybe the bias is only 2% like you say, but I just thought it'd might be more fair to just use random points.

[gbotrel]

You're right, I stand corrected :-). On mac (arm) the difference is ~40%, on x86 ~33%, definitely worth it to correct that and not measure a best case scenario.

Thanks for raising the issue 👍

[0x0ece]

🙌