Performance optimizations

[DemiMarie]

There are probably optimizations to be made, both in terms of micro-optimization, and in terms of the algorithms used.

[afck]

We should also add some benchmarks, similar to the ones in threshold_crypto, but maybe more deterministic ones.

[DemiMarie]

Perf is utterly useless on my system ― it records almost all of the time being spent on GMP internals with no detailed information. I suspect that parts of GMP are missing frame unwind information.

[DemiMarie]

I should probably report this as a bug in Fedora’s GMP.

[DemiMarie]

Some good news is that all but a few percent of the time is spent in GMP, and very little is spent doing memory allocation. So the performance is probably close to optimal.

[DemiMarie]

It might be possible to optimize even more by switching to low-level GMP calls. The guts of GMP are written in assembler, but the convenience functions could be ported to Rust and then inlined.

[afck]

Sounds good! Yes, I guess perf isn't that useful for now then.
I'd add benchmarks and then look at potential higher-level optimizations. (Questions like: Do we need to reduce in every step? Are there faster algorithms to compute the same proofs? Can we reduce the number of GMP calls somehow?) With benchmarks, we'll also be able to get more precise numbers if we want to try out a different bignum implementation.