search

poanetwork / vdf

An implementation of Verifiable Delay Functions in Rust
Apache License 2.0
168 stars 53 forks source link

Performance optimizations #4

Open DemiMarie opened 5 years ago

DemiMarie commented 5 years ago

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

afck commented 5 years ago

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

DemiMarie commented 5 years ago

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 commented 5 years ago

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

DemiMarie commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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.