Skip to content

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

Merged
laanwj merged 2 commits intobitcoin:masterfrom
promag:2019-05-rollingbloomfilter-reset
May 22, 2019
Merged

refactor: Improve CRollingBloomFilter::reset by using std::fill#16073
laanwj merged 2 commits intobitcoin:masterfrom
promag:2019-05-rollingbloomfilter-reset

Conversation

@promag
Copy link
Contributor

@promag promag commented May 21, 2019 •
edited
Loading

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
Copy link
Contributor Author

promag commented May 21, 2019

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

@gmaxwell
Copy link
Contributor

gmaxwell commented May 21, 2019

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
Copy link
Member

maflcko commented May 21, 2019

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

@promag
Copy link
Contributor Author

promag commented May 22, 2019

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

@jonasschnelli
Copy link
Contributor

jonasschnelli commented May 22, 2019

Well spotted!
Concept ACK

@promag
Copy link
Contributor Author

promag commented May 22, 2019

Updated OP with benchmark result.

Profiling before and after this change:

Screenshot 2019-05-22 at 00 11 14

Screenshot 2019-05-22 at 00 10 12

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

promag commented May 22, 2019

@MarcoFalke benchmark added.

@laanwj
Copy link
Member

laanwj commented May 22, 2019

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
Copy link
Contributor Author

promag commented May 22, 2019

but maybe an area for bigger improvement

@gmaxwell maybe open an issue and throw some suggestions?

jamesob
jamesob approved these changes May 22, 2019
View reviewed changes
Copy link
Contributor

@jamesob jamesob left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

utACK a47b560

Nice find.

@maflcko
Copy link
Member

maflcko commented May 22, 2019 •
edited
Loading

What compiler and hardware are you using?

utACK 8d774bbbe8454119161446225451210c23fe56d3

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

Show signature and timestamp

Signature:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

utACK 8d774bbbe8454119161446225451210c23fe56d3

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

iQGzBAEBCgAdFiEE+rVPoUahrI9sLGYTzit1aX5ppUgFAlwqrYAACgkQzit1aX5p
pUiX4gwAsi8srAjhAkRx0STvjJ75oiaU5ADUonn7zrstBc17F2kNONLedb+vR9J/
elm5lUmqrucGVItm1UlFgaOB/yq100B688xovcaOez2RKuSTT51y26Aur1Amrtyk
CDiP1dYabzImeSUPbaKEP33Hx0fNbzp77NAqbUW/ufJUYqAlmbh5QJsKP/baMKyo
f+1Jt5n/fDA9B9YNIWckb5qLAqlLDQE07RrMLRROcIHW3+ipsxdHEpug49QEzlTE
15lQAjzTXOfVzAX78dxdFc0lRzVr1MmPyAWlA26xhqe+4Lo4ObW7OMeSWHhMlISL
fntaqw2K8iYz8rBo218A+nY4BjcJSMEcjOAP2n1p+kU2rSm/NbyIjwZaHOv4xIWT
S/Y5DbZIZdPmIcEM/CXsGUzGENjIUeCyCa77+Rt6O0swC2OKaW3cJ02u+Iksq9iY
UnVv029AZdjRz+RGDHk2ubosddk/hczXTUju9+lUDoRpH0FKu0T5efn7Co1yT3gR
gwypjCZu
=k0jH
-----END PGP SIGNATURE-----

Timestamp of file with hash 0afe9d4d13b7b6fae0b5c6625b924bdb707bd6bf085d76618e964707100296a0 -

@promag
Copy link
Contributor Author

promag commented May 22, 2019

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

maflcko
maflcko reviewed May 22, 2019
View reviewed changes
@maflcko
Copy link
Member

maflcko commented May 22, 2019

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

@laanwj
Copy link
Member

laanwj commented May 22, 2019

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 promag force-pushed the 2019-05-rollingbloomfilter-reset branch from 8d774bb to df9e15f Compare May 22, 2019 14:59
@promag
Copy link
Contributor Author

promag commented May 22, 2019

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

@maflcko
Copy link
Member

maflcko commented May 22, 2019

re-utACK df9e15f

Show signature and timestamp

Signature:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

re-utACK df9e15f092
-----BEGIN PGP SIGNATURE-----

iQGzBAEBCgAdFiEE+rVPoUahrI9sLGYTzit1aX5ppUgFAlwqrYAACgkQzit1aX5p
pUipzwwAha/6gluoBoDmrtyN06+eiKHYnCrPhkDCFXmUptsHMMkCLnxpzWslG9zX
CXO6RZq48KQj6ZSx0TjdVFZuq5JEICqbiSk3u9McQxl2sILJx7x0fdz7yS/elu5m
RvT+cFIxav/eb7Bgnm6Zoz9EdRHFqyvglN3xBKowF5M2AHXbDq9trhM8oL9sgSFZ
dtHpaAern/L6s1UWF5zgVpDIqVB6Xr0mp0HodjMo8UurMTzB4nzZR6PAABJOeXPG
CGA7Xfkqj/gC/MP4gUKndS1aRlsY0uERPWclMd4NDF6fEX1mSAQHzJ7GO8pDBM5D
RwDpmV99ZdYUiD0Uv0IM2LfQQjWMSXNgoYm4CNf3R9FTLMUmM15xU8BcXTAXwLh2
0baT6VIdDhy12BtpcDm9cxrIoKtU5OBFxjBLRY7ZkyMs8LlEjBxadlSBBOlDEUsm
6uAj8b2Mek26y5fRJ+eBFok9B/up9G7ci5GuCmMhVf4syA1bSr+q/sIBr2U0Phea
TPfT5e04
=joN1
-----END PGP SIGNATURE-----

Timestamp of file with hash 156b97ccbe8a8aa40230d38498141d8b529ac9c16533d56aa09c7bd632f6c12c -

@jamesob
Copy link
Contributor

jamesob commented May 22, 2019

re-utACK df9e15f

@practicalswift
Copy link
Contributor

practicalswift commented May 22, 2019

utACK d2dbc7d

1 similar comment
@sipa
Copy link
Member

sipa commented May 22, 2019

utACK d2dbc7d

@laanwj laanwj merged commit df9e15f into bitcoin:master May 22, 2019
laanwj added a commit that referenced this pull request May 22, 2019
@laanwj
Merge #16073: refactor: Improve CRollingBloomFilter::reset by using s…
fdc951a 
…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
@promag promag deleted the 2019-05-rollingbloomfilter-reset branch May 22, 2019 19:12
@maflcko
Copy link
Member

maflcko commented May 22, 2019

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

@promag
Copy link
Contributor Author

promag commented May 22, 2019

Sort by date FTW.

@practicalswift
Copy link
Contributor

practicalswift commented May 22, 2019

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

deadalnix pushed a commit to Bitcoin-ABC/bitcoin-abc that referenced this pull request Jun 9, 2020
@laanwj @jasonbcox
Merge #16073: refactor: Improve CRollingBloomFilter::reset by using s…
910e126 
…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
ftrader pushed a commit to bitcoin-cash-node/bitcoin-cash-node that referenced this pull request Aug 17, 2020
@laanwj @ftrader
Merge #16073: refactor: Improve CRollingBloomFilter::reset by using s…
4d055e0 
…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
@str4d str4d mentioned this pull request Mar 5, 2021
Merged
zkbot added a commit to zcash/zcash that referenced this pull request Mar 5, 2021
@zkbot
Auto merge of #5026 - str4d:bloom-filter-backports, r=<try>
be45961 
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
zkbot added a commit to zcash/zcash that referenced this pull request Apr 15, 2021
@zkbot
Auto merge of #5026 - str4d:bloom-filter-backports, r=str4d
78de0cd 
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
PastaPastaPasta pushed a commit to PastaPastaPasta/dash that referenced this pull request Jul 1, 2021
@laanwj @PastaPastaPasta
Merge bitcoin#16073: refactor: Improve CRollingBloomFilter::reset by …
8ac49d7 
…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
@pravblockc pravblockc mentioned this pull request Sep 27, 2021
Merged
pravblockc pushed a commit to pravblockc/dash that referenced this pull request Sep 29, 2021
@laanwj @pravblockc
Merge bitcoin#16073: refactor: Improve CRollingBloomFilter::reset by …
b5316a8 
…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
PastaPastaPasta added a commit to dashpay/dash that referenced this pull request Sep 30, 2021
@PastaPastaPasta
Merge pull request #4469 from pravblockc/backports-v0.19-pr2
2f845d8 
Backports bitcoin#15853 bitcoin#15463 and bitcoin#16073
@bitcoin bitcoin locked as resolved and limited conversation to collaborators Dec 16, 2021
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Reviewers

2 more reviewers

@maflcko maflcko maflcko left review comments

@jamesob jamesob jamesob approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

Refactoring

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

9 participants

@promag @gmaxwell @maflcko @jonasschnelli @laanwj @jamesob @practicalswift @sipa @DrahtBot