cairo-lang icon indicating copy to clipboard operation
cairo-lang copied to clipboard

perf: faster poseidon hades permutation

Open feltroidprime opened this issue 1 year ago • 1 comments

This gives ~7x improvement by not using numpy for vectors/matrices, using native python pow function, and using the mds matrix directly instead of matrix multiplication, taking advantage of the small constants.

This would allow faster trace generation when using cairo-run for programs that uses intensively the Poseidon builtin since the permutation is used in the builtin runner.

Quite a few interesting programs could benefit from it. :)

For ~100k hashes on a i7-12700h (one core), it takes around 13 seconds instead of 90. The only counterpart is that it is removing generality over the Mds Matrix, but it's not really a problem in our context.


This change is Reviewable

feltroidprime avatar Sep 08 '23 19:09 feltroidprime

Fyi a slightly different version of this will be in 0.13.1. Thanks for the contrib

0xLucqs avatar Feb 05 '24 10:02 0xLucqs