Switch to a more efficient rolling Bloom filter #7113

1. 
   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.

2. laanwj added the label Feature on Nov 27, 2015
3. sipa force-pushed on Nov 27, 2015
4. 
   laanwj commented at 1:11 pm on November 27, 2015: member

   Nice! (discussion was in Replace setInventoryKnown with a rolling bloom filter. #7100 )
5. 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
6. sipa force-pushed on Nov 28, 2015
7. 
   pstratem commented at 10:17 am on November 29, 2015: contributor

   ACK
8. 
   ghost commented at 6:34 pm on November 30, 2015: none

   Yes
9. 
   laanwj commented at 12:18 pm on December 3, 2015: member

   utACK
10. laanwj merged this on Dec 3, 2015
11. laanwj closed this on Dec 3, 2015

    ---

12. laanwj referenced this in commit 54a550bef8 on Dec 3, 2015
13. codablock referenced this in commit 6662b55412 on Sep 16, 2017
14. codablock referenced this in commit bf2307791c on Sep 19, 2017
15. codablock referenced this in commit 9479f66893 on Dec 9, 2017
16. codablock referenced this in commit bf688abcee on Dec 9, 2017
17. furszy referenced this in commit c5edef052e on Feb 14, 2021
18. zkbot referenced this in commit be459619a8 on Mar 5, 2021
19. zkbot referenced this in commit 78de0cdf46 on Apr 15, 2021
20. DrahtBot locked this on Sep 8, 2021

Contributors
sipa laanwj pstratem ghost

Labels
Feature