Pippenger for G1 scalar_mul (single-threaded), add_mixed optimisation about algebra HOT 6 CLOSED

This is incorrect, the above discrepancies were even after the equivalent alg was implemented. In fact, our assembly montgomery mul is faster.

Anw, I'm closing, as these comments are imo based on old data and not worth digging up. If someone wants to bench carefully and find areas for improvements please do so anew.

from algebra.

All elliptic curves in Zexe already work with the pippenger-based MSM!

from algebra.

At some point the Edwards "Jubjub" curves could benefit form Pippenger too, although maybe that code should be modeled on dalek or something, not sure.

from algebra.

Hmm @jon-chuang do you know what the difference between the two algorithms was? I believe ark-ec is just using the standard EFD algorithms

from algebra.

Well certainly with w-NAF and GLV we've achieved the desired speedup for scalar mul and more. The only remaining question is for the mixed add.

Wrt your question, I don't know.

from algebra.

AFAIU, gnark has a lower finite field multiplication time than arkworks, due to the optimization to montgomery reduction they describe in this article: https://hackmd.io/@zkteam/modular_multiplication#Implementation. Their speedup was 65ns -> 50ns per multiplication, which looks roughly like the speedup for mul_assign.

(Perhaps theres a separate algorithmic speedup there as well)

from algebra.