Based on #19130, this change improves the comment for CRollingBloomFilter in bloom.h:
107 | + logfp = math.log(fprate) 108 | + nhash = max(1, min(round(logfp/math.log(0.5)), 50)) 109 | + nfilbits = math.ceil(-1.0*nhash*(3*int((nel+1)/2)) / math.log(1.0 - math.exp(logfp / nhash))) 110 | + return (nfilbits+63)/64*2*8 111 | + 112 | + * If we make these assumptions:
Nit: I found these next 6 lines added complexity to something that was very clear thus far. Do you think the simpler formula makes it easier to reason about the size of the bloom filter?
How does this render on doxygen? If it is markdown style you'd likely want to quote an inline script using triple-backquotes.
TBH I'm not sure the python script adds much in the first place. Sometimes a simple but good-enough approximation is better for documentation purposes. Is this level of precision necessary?
(edit: whoops, didn't mean to click the resolve conversation button)
See my comment: #19130 (comment)
Given how accurate the formula is in all reasonable cases (at most 0.115% off, and usually much less), I don't think it's worth including the code.
The rest of the PR seems useful, though.
Thanks for the input! Agreed that the extra complexity from the Python script is not worthwhile for the small accuracy gain; I'll update.
Ooh, didn't know about doxygen use before, thanks for the reminder! The formatting should be reasonable now:
<img width="807" alt="Doxygen" src="https://user-images.githubusercontent.com/4276679/94890948-9a186580-0435-11eb-808e-4902ae092b69.png">
93 | @@ -94,7 +94,26 @@ class CBloomFilter 94 | * insert()'ed ... but may also return true for items that were not inserted. 95 | * 96 | * It needs around 1.8 bytes per element per factor 0.1 of false positive rate. 97 | - * (More accurately: 3/(log(256)*log(2)) * log(1/fpRate) * nElements bytes) 98 | + * e.g. for 1000 elements, we'd need:
Nit: Maybe add "Lower tolerance for false positives increases the size of the bloom filter manifesting a trade-off between memory and compute (in the case of a false positive)."
ACK 01d14f2
I tested this by being new to bitcoin and having only a high-level understanding of bloom filters. The commit made the trade-off between the acceptable false positive rate and memory footprint easy to understand. A couple optional nits below.
ACK d9141a0002bb508b2e94e206a1bd28ef8f97ffde