Better implementation of Num::add_assign. - Githubissues

matter-labs-archive / sapling-crypto

Zcash "Sapling" cryptography gadgets along with additions. Uses our Ethereum compatible bellman under the hood

Other

15 stars 9 forks source link

Better implementation of Num::add_assign. #13

Open alex-ozdemir opened 4 years ago

alex-ozdemir commented 4 years ago

The original implementation of Num::add_assign had a few inefficiencies:

It instantiated the standard hashmap with small keys.
It put a bunch of items into an empty hashmap, without setting the intial hashmap capacity.
It used multiple hash lookups in an insert-or-modify pattern.

This commit:

Uses the Fnv hash function instead of the default: SipHash.
Initializes the hashmap with appropriate capacity.
Uses the entry API.

In my microbenchmarks, this sped up Poseidon evaluation by 1.7x.