Switch to a more efficient rolling Bloom filter #7113

pull sipa wants to merge 1 commits into bitcoin:master from sipa:betterrolling changing 3 files +75 −30

sipa commented at 12:25 PM on November 27, 2015: member
For each 'bit' in the filter we really maintain 2 bits, which store either:
- 0: not set
- 1-3: set in generation N
After (nElements / 2) insertions, we switch to a new generation, and wipe entries which already had the new generation number, effectively switching from the last 1.5 * nElements set to the last 1.0 * nElements set.

This is 25% more space efficient than the previous implementation, and can (at peak) store 1.5 times the requested amount of history (though only 1.0 times the requested history is guaranteed).

The existing unit tests should be sufficient.
laanwj added the label Feature on Nov 27, 2015
sipa force-pushed on Nov 27, 2015
laanwj commented at 1:11 PM on November 27, 2015: member

Nice! (discussion was in Replace setInventoryKnown with a rolling bloom filter. #7100 )
sipa cross-referenced this on Nov 27, 2015 from issue Replace setInventoryKnown with a rolling bloom filter. by gmaxwell

Switch to a more efficient rolling Bloom filter

For each 'bit' in the filter we really maintain 2 bits, which store either:
0: not set
1-3: set in generation N

After (nElements / 2) insertions, we switch to a new generation, and wipe
entries which already had the new generation number, effectively switching
from the last 1.5 * nElements set to the last 1.0 * nElements set.

This is 25% more space efficient than the previous implementation, and can
(at peak) store 1.5 times the requested amount of history (though only
1.0 times the requested history is guaranteed).

The existing unit tests should be sufficient.

086ee67d83

sipa force-pushed on Nov 28, 2015
pstratem commented at 10:17 AM on November 29, 2015: contributor

ACK
ghost commented at 6:34 PM on November 30, 2015: none

Yes
laanwj commented at 12:18 PM on December 3, 2015: member

utACK
laanwj merged this on Dec 3, 2015
laanwj closed this on Dec 3, 2015
laanwj referenced this in commit 54a550bef8 on Dec 3, 2015
dgenr8 cross-referenced this on Dec 29, 2015 from issue Further work on thin blocks by dagurval
codablock referenced this in commit 6662b55412 on Sep 16, 2017
codablock referenced this in commit bf2307791c on Sep 19, 2017
codablock referenced this in commit 9479f66893 on Dec 9, 2017
codablock referenced this in commit bf688abcee on Dec 9, 2017
sickpig cross-referenced this on May 31, 2018 from issue [PORT] Rolling Bloom Filter new implementation. by sickpig
laanwj cross-referenced this on Apr 15, 2019 from issue Add tests for (or remove) untested unused methods by practicalswift
random-zebra cross-referenced this on Feb 5, 2021 from issue [Core] More efficient rolling Bloom filter by random-zebra
furszy referenced this in commit c5edef052e on Feb 14, 2021
str4d cross-referenced this on Mar 5, 2021 from issue Backport bloom filter improvements by str4d
zkbot referenced this in commit be459619a8 on Mar 5, 2021
zkbot referenced this in commit 78de0cdf46 on Apr 15, 2021
bitcoin locked this on Sep 8, 2021

Contributors

Labels

Linked (view graph)

#7100 Replace setInventoryKnown with a rolling bloom filter.#15814 Add tests for (or remove) untested unused methods