Page MenuHomePhabricator

Merge #13176: Improve CRollingBloomFilter performance: replace modulus with FastMod
ClosedPublic

Authored by nakihito on Sep 26 2019, 20:08.

Details

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

Diff Detail

Repository
rABC Bitcoin ABC
Branch
PR13176
Lint
Lint OK
Unit
No Unit Test Coverage
Build Status
Buildable 7627
Build 13294: Bitcoin ABC Buildbot (legacy)
Build 13293: arc lint + arc unit

Event Timeline

nakihito created this revision.Sep 26 2019, 20:08
Owners added a reviewer: Restricted Owners Package.Sep 26 2019, 20:08
Herald added a reviewer: Restricted Project. · View Herald TranscriptSep 26 2019, 20:08
nakihito planned changes to this revision.Sep 26 2019, 20:08
nakihito updated this revision to Diff 13260.Sep 27 2019, 23:46

Fixed type casting method.

deadalnix requested changes to this revision.Sep 28 2019, 13:58

The test plan is not appropriate.

This revision now requires changes to proceed.Sep 28 2019, 13:58
nakihito edited the summary of this revision. (Show Details)Oct 2 2019, 03:53
nakihito edited the test plan for this revision. (Show Details)
nakihito edited the summary of this revision. (Show Details)
nakihito edited the summary of this revision. (Show Details)
nakihito requested review of this revision.Oct 2 2019, 03:56
deadalnix requested changes to this revision.Oct 2 2019, 21:09

And what was the result of the comparison?

This revision now requires changes to proceed.Oct 2 2019, 21:09
nakihito edited the test plan for this revision. (Show Details)Oct 2 2019, 21:31
nakihito requested review of this revision.Oct 2 2019, 22:04
nakihito edited the summary of this revision. (Show Details)
nakihito edited the test plan for this revision. (Show Details)

And what was the result of the comparison?

The results were in the summary. I have moved them to the test plan.

deadalnix accepted this revision.Oct 3 2019, 15:44
This revision is now accepted and ready to land.Oct 3 2019, 15:44