HomePhabricator

Merge #13176: Improve CRollingBloomFilter performance: replace modulus with…

Authored by Wladimir J. van der Laan <laanwj@gmail.com> on May 18 2018, 16:39.

Description

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

Details

Committed
Nico Guiton <nico@bitframe.org>Thu, Oct 3, 17:16
Pushed
nakihitoThu, Oct 3, 20:47
Reviewer
Restricted Owners Package
Differential Revision
D4160: Merge #13176: Improve CRollingBloomFilter performance: replace modulus with FastMod
Parents
rSTAGING290f3a73f004: Add native support for serializing char arrays without FLATDATA
Branches
Unknown
Tags
Unknown