name: Spdupverifypow
about: Speed up all 5 PoW verification functions about 5x
title: Speed up PoW verify
labels:
assignees:
Profiling an initial header sync found about 20% of time was spent in cuckaroo::verify
The old code for all 5 verify functions was quadratic in cycle length, taking on average 42/2 iterations of an inner loop to find the next edge in the cycle.
The new code uses 2 or 3 extra arrays of length O(proof_size) that allows the next edge in the cycle to be found in O(1) iterations on average.
name: Spdupverifypow about: Speed up all 5 PoW verification functions about 5x title: Speed up PoW verify labels: assignees:
Profiling an initial header sync found about 20% of time was spent in cuckaroo::verify The old code for all 5 verify functions was quadratic in cycle length, taking on average 42/2 iterations of an inner loop to find the next edge in the cycle. The new code uses 2 or 3 extra arrays of length O(proof_size) that allows the next edge in the cycle to be found in O(1) iterations on average.
Tested with a full sync from scratch on mainnet.