doc: make it easier to work out size of bloom filter #19130
Closed
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
Looks right, but perhaps it should go in the .h file (which has an easier approximate formula already). |
|
An alternative would be to run the code in massif and show the size of the object. 😬 |
|
To have an idea of the approximation, the formula "4.328 bits per element and per bit of fprate" is at most 0.115% off for better than 8-bit fprate (fprate < 1/256). For 10-bit, at most 0.074%. For 12-bit, at most 0.052%. For 20-bit, 0.019%. |
I agree. In general, this kind of documentation would be better in the header file. This also gets included in doxygen etc. |
|
@ajtowns did you want to follow up here and move this into the header? |
laanwj
added a commit
that referenced
this pull request
Nov 19, 2020
d9141a0 doc: clarify CRollingBloomFilter size estimate (Anthony Towns) Pull request description: Based on #19130, this change improves the comment for `CRollingBloomFilter` in `bloom.h`: - Give examples to illustrate the heuristic "1.8 bytes per element per factor 0.1 of false positive rate" - Add some Python code which can be copy/pasted for convenient filter size calculation (in an interpreter) - Reconcile the newly added code with the existing approximation ACKs for top commit: laanwj: ACK d9141a0 Tree-SHA512: e7138b3c531883a750ead06368975c750863fde7ef6f2633b137eca011079226e9205316217322014399fba05a48f294c788dd700bb7d479c58fe1f23e40419f
sidhujag
pushed a commit
to syscoin/syscoin
that referenced
this pull request
Nov 19, 2020
d9141a0 doc: clarify CRollingBloomFilter size estimate (Anthony Towns) Pull request description: Based on bitcoin#19130, this change improves the comment for `CRollingBloomFilter` in `bloom.h`: - Give examples to illustrate the heuristic "1.8 bytes per element per factor 0.1 of false positive rate" - Add some Python code which can be copy/pasted for convenient filter size calculation (in an interpreter) - Reconcile the newly added code with the existing approximation ACKs for top commit: laanwj: ACK d9141a0 Tree-SHA512: e7138b3c531883a750ead06368975c750863fde7ef6f2633b137eca011079226e9205316217322014399fba05a48f294c788dd700bb7d479c58fe1f23e40419f
|
This is really helpful. I'd love to see it merged into the header file at some point. |
|
#19968 did that, i think ? |
PastaPastaPasta
pushed a commit
to PastaPastaPasta/dash
that referenced
this pull request
Jun 27, 2021
d9141a0 doc: clarify CRollingBloomFilter size estimate (Anthony Towns) Pull request description: Based on bitcoin#19130, this change improves the comment for `CRollingBloomFilter` in `bloom.h`: - Give examples to illustrate the heuristic "1.8 bytes per element per factor 0.1 of false positive rate" - Add some Python code which can be copy/pasted for convenient filter size calculation (in an interpreter) - Reconcile the newly added code with the existing approximation ACKs for top commit: laanwj: ACK d9141a0 Tree-SHA512: e7138b3c531883a750ead06368975c750863fde7ef6f2633b137eca011079226e9205316217322014399fba05a48f294c788dd700bb7d479c58fe1f23e40419f
PastaPastaPasta
pushed a commit
to PastaPastaPasta/dash
that referenced
this pull request
Jun 28, 2021
d9141a0 doc: clarify CRollingBloomFilter size estimate (Anthony Towns) Pull request description: Based on bitcoin#19130, this change improves the comment for `CRollingBloomFilter` in `bloom.h`: - Give examples to illustrate the heuristic "1.8 bytes per element per factor 0.1 of false positive rate" - Add some Python code which can be copy/pasted for convenient filter size calculation (in an interpreter) - Reconcile the newly added code with the existing approximation ACKs for top commit: laanwj: ACK d9141a0 Tree-SHA512: e7138b3c531883a750ead06368975c750863fde7ef6f2633b137eca011079226e9205316217322014399fba05a48f294c788dd700bb7d479c58fe1f23e40419f
PastaPastaPasta
pushed a commit
to PastaPastaPasta/dash
that referenced
this pull request
Jun 29, 2021
d9141a0 doc: clarify CRollingBloomFilter size estimate (Anthony Towns) Pull request description: Based on bitcoin#19130, this change improves the comment for `CRollingBloomFilter` in `bloom.h`: - Give examples to illustrate the heuristic "1.8 bytes per element per factor 0.1 of false positive rate" - Add some Python code which can be copy/pasted for convenient filter size calculation (in an interpreter) - Reconcile the newly added code with the existing approximation ACKs for top commit: laanwj: ACK d9141a0 Tree-SHA512: e7138b3c531883a750ead06368975c750863fde7ef6f2633b137eca011079226e9205316217322014399fba05a48f294c788dd700bb7d479c58fe1f23e40419f
PastaPastaPasta
pushed a commit
to PastaPastaPasta/dash
that referenced
this pull request
Jul 1, 2021
d9141a0 doc: clarify CRollingBloomFilter size estimate (Anthony Towns) Pull request description: Based on bitcoin#19130, this change improves the comment for `CRollingBloomFilter` in `bloom.h`: - Give examples to illustrate the heuristic "1.8 bytes per element per factor 0.1 of false positive rate" - Add some Python code which can be copy/pasted for convenient filter size calculation (in an interpreter) - Reconcile the newly added code with the existing approximation ACKs for top commit: laanwj: ACK d9141a0 Tree-SHA512: e7138b3c531883a750ead06368975c750863fde7ef6f2633b137eca011079226e9205316217322014399fba05a48f294c788dd700bb7d479c58fe1f23e40419f
PastaPastaPasta
pushed a commit
to PastaPastaPasta/dash
that referenced
this pull request
Jul 1, 2021
d9141a0 doc: clarify CRollingBloomFilter size estimate (Anthony Towns) Pull request description: Based on bitcoin#19130, this change improves the comment for `CRollingBloomFilter` in `bloom.h`: - Give examples to illustrate the heuristic "1.8 bytes per element per factor 0.1 of false positive rate" - Add some Python code which can be copy/pasted for convenient filter size calculation (in an interpreter) - Reconcile the newly added code with the existing approximation ACKs for top commit: laanwj: ACK d9141a0 Tree-SHA512: e7138b3c531883a750ead06368975c750863fde7ef6f2633b137eca011079226e9205316217322014399fba05a48f294c788dd700bb7d479c58fe1f23e40419f
PastaPastaPasta
pushed a commit
to PastaPastaPasta/dash
that referenced
this pull request
Jul 15, 2021
d9141a0 doc: clarify CRollingBloomFilter size estimate (Anthony Towns) Pull request description: Based on bitcoin#19130, this change improves the comment for `CRollingBloomFilter` in `bloom.h`: - Give examples to illustrate the heuristic "1.8 bytes per element per factor 0.1 of false positive rate" - Add some Python code which can be copy/pasted for convenient filter size calculation (in an interpreter) - Reconcile the newly added code with the existing approximation ACKs for top commit: laanwj: ACK d9141a0 Tree-SHA512: e7138b3c531883a750ead06368975c750863fde7ef6f2633b137eca011079226e9205316217322014399fba05a48f294c788dd700bb7d479c58fe1f23e40419f
PastaPastaPasta
pushed a commit
to PastaPastaPasta/dash
that referenced
this pull request
Jul 15, 2021
d9141a0 doc: clarify CRollingBloomFilter size estimate (Anthony Towns) Pull request description: Based on bitcoin#19130, this change improves the comment for `CRollingBloomFilter` in `bloom.h`: - Give examples to illustrate the heuristic "1.8 bytes per element per factor 0.1 of false positive rate" - Add some Python code which can be copy/pasted for convenient filter size calculation (in an interpreter) - Reconcile the newly added code with the existing approximation ACKs for top commit: laanwj: ACK d9141a0 Tree-SHA512: e7138b3c531883a750ead06368975c750863fde7ef6f2633b137eca011079226e9205316217322014399fba05a48f294c788dd700bb7d479c58fe1f23e40419f
PastaPastaPasta
pushed a commit
to PastaPastaPasta/dash
that referenced
this pull request
Jul 16, 2021
d9141a0 doc: clarify CRollingBloomFilter size estimate (Anthony Towns) Pull request description: Based on bitcoin#19130, this change improves the comment for `CRollingBloomFilter` in `bloom.h`: - Give examples to illustrate the heuristic "1.8 bytes per element per factor 0.1 of false positive rate" - Add some Python code which can be copy/pasted for convenient filter size calculation (in an interpreter) - Reconcile the newly added code with the existing approximation ACKs for top commit: laanwj: ACK d9141a0 Tree-SHA512: e7138b3c531883a750ead06368975c750863fde7ef6f2633b137eca011079226e9205316217322014399fba05a48f294c788dd700bb7d479c58fe1f23e40419f
gabriel-bjg
pushed a commit
to gabriel-bjg/dash
that referenced
this pull request
Jul 16, 2021
d9141a0 doc: clarify CRollingBloomFilter size estimate (Anthony Towns) Pull request description: Based on bitcoin#19130, this change improves the comment for `CRollingBloomFilter` in `bloom.h`: - Give examples to illustrate the heuristic "1.8 bytes per element per factor 0.1 of false positive rate" - Add some Python code which can be copy/pasted for convenient filter size calculation (in an interpreter) - Reconcile the newly added code with the existing approximation ACKs for top commit: laanwj: ACK d9141a0 Tree-SHA512: e7138b3c531883a750ead06368975c750863fde7ef6f2633b137eca011079226e9205316217322014399fba05a48f294c788dd700bb7d479c58fe1f23e40419f
gades
pushed a commit
to cosanta/cosanta-core
that referenced
this pull request
Apr 25, 2022
d9141a0 doc: clarify CRollingBloomFilter size estimate (Anthony Towns) Pull request description: Based on bitcoin#19130, this change improves the comment for `CRollingBloomFilter` in `bloom.h`: - Give examples to illustrate the heuristic "1.8 bytes per element per factor 0.1 of false positive rate" - Add some Python code which can be copy/pasted for convenient filter size calculation (in an interpreter) - Reconcile the newly added code with the existing approximation ACKs for top commit: laanwj: ACK d9141a0 Tree-SHA512: e7138b3c531883a750ead06368975c750863fde7ef6f2633b137eca011079226e9205316217322014399fba05a48f294c788dd700bb7d479c58fe1f23e40419f
Sign up for free
to subscribe to this conversation on GitHub.
Already have an account?
Sign in.
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
I've manually traced through the bloom filter code to work out how big a filter ends up being a few times now; this just adds some python code as a comment so it's easy to do that by cutting and pasting into an interpreter instead.