Merge #13176: Improve CRollingBloomFilter performance: replace modulus with FastMod
Summary:
9aac9f90d5e56752cc6cbfac48063ad29a01143c replace modulus with FastMod (Martin Ankerl)
Pull request description:
Not sure if this is optimization is necessary, but anyway I have some spare time so here it is. This replaces the slow modulo operation with a much faster 64bit multiplication & shift. This works when the hash is uniformly distributed between 0 and 2^32-1. This speeds up the benchmark by a factor of about 1.3: ``` RollingBloom, 5, 1500000, 3.73733, 4.97569e-07, 4.99002e-07, 4.98372e-07 # before RollingBloom, 5, 1500000, 2.86842, 3.81630e-07, 3.83730e-07, 3.82473e-07 # FastMod ``` Be aware that this changes the internal data of the filter, so this should probably not be used for CBloomFilter because of interoperability problems.
Tree-SHA512: 04104f3fb09f56c9d14458a6aad919aeb0a5af944e8ee6a31f00e93c753e22004648c1cd65bf36752b6addec528d19fb665c27b955ce1666a85a928e17afa47a
Backport of Core PR13176
https://github.com/bitcoin/bitcoin/pull/13176/
Test Plan:
make check src/bench/bench_bitcoin -filter=RollingBloom
Repeat above for master and compare.
Before change:
Benchmark, evals, iterations, total, min, max, median RollingBloom, 5, 1500000, 5.16318, 6.61227e-07, 7.3991e-07, 6.70607e-07
After change:
Benchmark, evals, iterations, total, min, max, median RollingBloom, 5, 1500000, 3.73982, 4.92548e-07, 5.10237e-07, 4.95271e-07
Reviewers: deadalnix, Fabien, jasonbcox, O1 Bitcoin ABC, #bitcoin_abc
Reviewed By: deadalnix, O1 Bitcoin ABC, #bitcoin_abc
Differential Revision: https://reviews.bitcoinabc.org/D4160