refactor: Improve CRollingBloomFilter::reset by using std::fill #16073

promag · 2019-05-21T23:13:01Z

Cleaner code. Also improves performance with --enable-debug (which is meaningless to non-developers).

Before:

# Benchmark, evals, iterations, total, min, max, median
RollingBloomReset, 5, 150, 19.3008, 0.0254917, 0.0259195, 0.0257395

After:

# Benchmark, evals, iterations, total, min, max, median
RollingBloomReset, 5, 150, 5.43269, 0.00720651, 0.00729697, 0.00724854

promag · 2019-05-21T23:16:14Z

I was going to use memset but I think std::fill is much nicer and probably as fast as memset.

gmaxwell · 2019-05-21T23:18:16Z

Seems okay to me, but why are we resetting a big rolling bloom filter this often?

It may be better to use a generation counter. (this isn't a reason not to take this improvement, but maybe an area for bigger improvement).

maflcko · 2019-05-21T23:30:57Z

Any intuition why this is faster? Could add a trivial benchmark as first commit?

promag · 2019-05-22T06:51:15Z

@MarcoFalke one reason may be a specialized version of fill for uint64_t. Will add the benchmark.

jonasschnelli · 2019-05-22T09:21:10Z

Well spotted!
Concept ACK

promag · 2019-05-22T13:46:53Z

Updated OP with benchmark result.

Profiling before and after this change:

promag · 2019-05-22T13:51:21Z

@MarcoFalke benchmark added.

laanwj · 2019-05-22T13:51:28Z

Any intuition why this is faster? Could add a trivial benchmark as first commit?

IIRC std::fill tends to be optimized to a memset, which uses arch-specific instructions for the fastest filling of memory, whereas a loop is not

promag · 2019-05-22T13:54:35Z

but maybe an area for bigger improvement

@gmaxwell maybe open an issue and throw some suggestions?

jamesob

utACK a47b560

Nice find.

maflcko · 2019-05-22T14:12:25Z

What compiler and hardware are you using?

utACK 8d774bb

Couldn't find a performance difference on my system, but the code looks cleaner.

Show signature and timestamp

Signature:

Timestamp of file with hash 0afe9d4d13b7b6fae0b5c6625b924bdb707bd6bf085d76618e964707100296a0 -

promag · 2019-05-22T14:24:25Z

@MarcoFalke Apple LLVM version 10.0.1 (clang-1001.0.46.4) with --enable-debug --with-sanitizers=thread.

src/bench/rollingbloom.cpp

maflcko · 2019-05-22T14:46:24Z

Please mention that in the OP. Performance improvements when run with a sanitizer are completely meaningless to non-developers.

laanwj · 2019-05-22T14:49:48Z

Also, always benchmark in release mode. --enable-debug dials down the optimization level. It's very possible that you'll see no difference without that.

promag · 2019-05-22T15:02:03Z

After all in release mode I have the same result as @MarcoFalke. Updated OP.

maflcko · 2019-05-22T15:22:56Z

re-utACK df9e15f

Show signature and timestamp

Signature:

Timestamp of file with hash 156b97ccbe8a8aa40230d38498141d8b529ac9c16533d56aa09c7bd632f6c12c -

jamesob · 2019-05-22T15:26:58Z

re-utACK df9e15f

practicalswift · 2019-05-22T15:47:57Z

utACK d2dbc7d

sipa · 2019-05-22T18:31:05Z

utACK d2dbc7d

…td::fill df9e15f refactor: Improve CRollingBloomFilter::reset by using std::fill (João Barbosa) d2dbc7d bench: Add benchmark for CRollingBloomFilter::reset (João Barbosa) Pull request description: Cleaner code. Also improves performance with `--enable-debug` (which is meaningless to non-developers). Before: ``` # Benchmark, evals, iterations, total, min, max, median RollingBloomReset, 5, 150, 19.3008, 0.0254917, 0.0259195, 0.0257395 ``` After: ``` # Benchmark, evals, iterations, total, min, max, median RollingBloomReset, 5, 150, 5.43269, 0.00720651, 0.00729697, 0.00724854 ``` ACKs for commit df9e15: MarcoFalke: re-utACK df9e15f jamesob: re-utACK df9e15f Tree-SHA512: 22038411dfd41afad77b17a3da9ee04476ffbd4d215dcf47bdd9f14588759bc328a55d958dcebc2036b52ce4c56f79b1284eae11e56ddfaf21f0b2ee1c6a914a

maflcko · 2019-05-22T20:38:52Z

@sipa, @practicalswift Just FYI, you reviewed an incorrect commit and your ACKs haven't been recorded in the merge.

promag · 2019-05-22T20:42:24Z

Sort by date FTW.

practicalswift · 2019-05-22T20:56:38Z

@MarcoFalke Oh sorry about that and thanks for the notification!

…td::fill Summary: df9e15f092c18a8047f09307576c2b77b9c8d01c refactor: Improve CRollingBloomFilter::reset by using std::fill (João Barbosa) d2dbc7da26e1ca40200521c05a0b1ca75578acd2 bench: Add benchmark for CRollingBloomFilter::reset (João Barbosa) Pull request description: Cleaner code. Also improves performance with `--enable-debug` (which is meaningless to non-developers). Before: ``` # Benchmark, evals, iterations, total, min, max, median RollingBloomReset, 5, 150, 19.3008, 0.0254917, 0.0259195, 0.0257395 ``` After: ``` # Benchmark, evals, iterations, total, min, max, median RollingBloomReset, 5, 150, 5.43269, 0.00720651, 0.00729697, 0.00724854 ``` ACKs for commit df9e15: MarcoFalke: re-utACK df9e15f092 jamesob: re-utACK bitcoin/bitcoin@df9e15f Tree-SHA512: 22038411dfd41afad77b17a3da9ee04476ffbd4d215dcf47bdd9f14588759bc328a55d958dcebc2036b52ce4c56f79b1284eae11e56ddfaf21f0b2ee1c6a914a Backport of Core [[bitcoin/bitcoin#16073 | PR16073]] Test Plan: `ninja check bench-bitcoin` Reviewers: #bitcoin_abc, majcosta Reviewed By: #bitcoin_abc, majcosta Differential Revision: https://reviews.bitcoinabc.org/D6485

Backport bloom filter improvements Cherry-picked from the following upstream PRs: - bitcoin/bitcoin#7113 - bitcoin/bitcoin#7818 - Only the second commit (to resolve conflicts). - bitcoin/bitcoin#7934 - bitcoin/bitcoin#8655 - Partial backport to help resolve conflicts. - bitcoin/bitcoin#9060 - bitcoin/bitcoin#9223 - bitcoin/bitcoin#9644 - Partial backport to help resolve conflicts. - bitcoin/bitcoin#9916 - bitcoin/bitcoin#9750 - bitcoin/bitcoin#13176 - bitcoin/bitcoin#13948 - bitcoin/bitcoin#16073 - bitcoin/bitcoin#18670 - bitcoin/bitcoin#18806 - Reveals upstream's covert fix for CVE-2013-5700. - bitcoin/bitcoin#19968

…using std::fill df9e15f refactor: Improve CRollingBloomFilter::reset by using std::fill (João Barbosa) d2dbc7d bench: Add benchmark for CRollingBloomFilter::reset (João Barbosa) Pull request description: Cleaner code. Also improves performance with `--enable-debug` (which is meaningless to non-developers). Before: ``` # Benchmark, evals, iterations, total, min, max, median RollingBloomReset, 5, 150, 19.3008, 0.0254917, 0.0259195, 0.0257395 ``` After: ``` # Benchmark, evals, iterations, total, min, max, median RollingBloomReset, 5, 150, 5.43269, 0.00720651, 0.00729697, 0.00724854 ``` ACKs for commit df9e15: MarcoFalke: re-utACK df9e15f jamesob: re-utACK bitcoin@df9e15f Tree-SHA512: 22038411dfd41afad77b17a3da9ee04476ffbd4d215dcf47bdd9f14588759bc328a55d958dcebc2036b52ce4c56f79b1284eae11e56ddfaf21f0b2ee1c6a914a

Backports bitcoin#15853 bitcoin#15463 and bitcoin#16073

…using std::fill df9e15f refactor: Improve CRollingBloomFilter::reset by using std::fill (João Barbosa) d2dbc7d bench: Add benchmark for CRollingBloomFilter::reset (João Barbosa) Pull request description: Cleaner code. Also improves performance with `--enable-debug` (which is meaningless to non-developers). Before: ``` # Benchmark, evals, iterations, total, min, max, median RollingBloomReset, 5, 150, 19.3008, 0.0254917, 0.0259195, 0.0257395 ``` After: ``` # Benchmark, evals, iterations, total, min, max, median RollingBloomReset, 5, 150, 5.43269, 0.00720651, 0.00729697, 0.00724854 ``` ACKs for commit df9e15: MarcoFalke: re-utACK df9e15f jamesob: re-utACK bitcoin@df9e15f Tree-SHA512: 22038411dfd41afad77b17a3da9ee04476ffbd4d215dcf47bdd9f14588759bc328a55d958dcebc2036b52ce4c56f79b1284eae11e56ddfaf21f0b2ee1c6a914a

DrahtBot added the Refactoring label May 21, 2019

promag force-pushed the 2019-05-rollingbloomfilter-reset branch from 49f3560 to 8d774bb Compare May 22, 2019 13:49

jamesob approved these changes May 22, 2019

View reviewed changes

maflcko reviewed May 22, 2019

View reviewed changes

src/bench/rollingbloom.cpp Outdated Show resolved Hide resolved

promag added 2 commits May 22, 2019 15:55

bench: Add benchmark for CRollingBloomFilter::reset

d2dbc7d

refactor: Improve CRollingBloomFilter::reset by using std::fill

df9e15f

promag force-pushed the 2019-05-rollingbloomfilter-reset branch from 8d774bb to df9e15f Compare May 22, 2019 14:59

laanwj merged commit df9e15f into bitcoin:master May 22, 2019

promag deleted the 2019-05-rollingbloomfilter-reset branch May 22, 2019 19:12

str4d mentioned this pull request Mar 5, 2021

Backport bloom filter improvements zcash/zcash#5026

Merged

pravblockc mentioned this pull request Sep 27, 2021

Backports #15853 #15463 and #16073 dashpay/dash#4469

Merged

PastaPastaPasta added a commit to dashpay/dash that referenced this pull request Sep 30, 2021

Merge pull request #4469 from pravblockc/backports-v0.19-pr2

2f845d8

Backports bitcoin#15853 bitcoin#15463 and bitcoin#16073

bitcoin locked as resolved and limited conversation to collaborators Dec 16, 2021

refactor: Improve CRollingBloomFilter::reset by using std::fill #16073

refactor: Improve CRollingBloomFilter::reset by using std::fill #16073

Uh oh!

Conversation

promag commented May 21, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

promag commented May 21, 2019

Uh oh!

gmaxwell commented May 21, 2019

Uh oh!

maflcko commented May 21, 2019

Uh oh!

promag commented May 22, 2019

Uh oh!

jonasschnelli commented May 22, 2019

Uh oh!

promag commented May 22, 2019

Uh oh!

promag commented May 22, 2019

Uh oh!

laanwj commented May 22, 2019

Uh oh!

promag commented May 22, 2019

Uh oh!

jamesob left a comment

Choose a reason for hiding this comment

Uh oh!

maflcko commented May 22, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

promag commented May 22, 2019

Uh oh!

Uh oh!

maflcko commented May 22, 2019

Uh oh!

laanwj commented May 22, 2019

Uh oh!

promag commented May 22, 2019

Uh oh!

maflcko commented May 22, 2019

Uh oh!

jamesob commented May 22, 2019

Uh oh!

practicalswift commented May 22, 2019

Uh oh!

sipa commented May 22, 2019

Uh oh!

maflcko commented May 22, 2019

Uh oh!

promag commented May 22, 2019

Uh oh!

practicalswift commented May 22, 2019

Uh oh!

Uh oh!

promag commented May 21, 2019 •

edited

Loading

maflcko commented May 22, 2019 •

edited

Loading