Improve rolling bloom filter performance and benchmark #7934

1. 
   sipa commented at 5:01 pm on April 24, 2016: member

   Added a benchmark for the rolling bloom filter (with parameters corresponding to the tx rejection cache), which showed that on average, adding+checking one item takes around 2.1us, but the refresh action that wipes all old generation items every 60000 iterations takes 65ms, which is very significant.

   Thus, this patch also changes the implementation from one that stores 16 2-bit integers in uint32_t’s, to one that stores the first bit of 64 2-bit integers in one uint64_t and the second bit in another. This allows for 450x faster refreshing (0.14ms) and 2.2x faster average adding+checking (0.93us).

   All benchmarks done on an Intel Core i7-4800MQ CPU, running at 2.6 GHz, with binaries compiled with GCC 5.3.1.

2. sipa force-pushed on Apr 24, 2016
3. sipa force-pushed on Apr 24, 2016
4. laanwj added the label Resource usage on Apr 25, 2016
5. in src/bloom.cpp: in 67d44f8fd0 outdated

   276-        uint32_t h = Hash(n, vKey);
   277-        put(h, nGeneration);
   278+        uint32_t h = RollingBloomHash(n, nTweak, vKey);
   279+        int bit = h & 0x3F;
   280+        uint32_t pos = (h >> 6) % data.size();
   281+        /* The lowest bit of pos is ignored, and set to zero first the first bit, and to one for the second. */
   

   ---

   ---

   

   dcousens commented at 1:32 am on April 26, 2016:

   set to zero for first the first bit

6. in src/bloom.cpp: in 67d44f8fd0 outdated

   286@@ -276,8 +287,11 @@ void CRollingBloomFilter::insert(const uint256& hash)
   287 bool CRollingBloomFilter::contains(const std::vector<unsigned char>& vKey) const
   288 {
   289     for (int n = 0; n < nHashFuncs; n++) {
   290-        uint32_t h = Hash(n, vKey);
   291-        if (get(h) == 0) {
   292+        uint32_t h = RollingBloomHash(n, nTweak, vKey);
   293+        int bit = h & 0x3F;
   294+        uint32_t pos = (h >> 6) % data.size();
   295+        /* Check whether either the relevant bit is set in data[pos & ~1] or data[pos | 1] */
   

   ---

   ---

   

   dcousens commented at 3:21 am on April 26, 2016:

   Check whether either the relevant bit is not set in either data[pos & ~1] or data[pos | 1]

   or

   If the relevant bit is not set in either data[pos & ~1] or data[pos | 1], the filter does not contain vKey

7. in src/bloom.cpp: in 67d44f8fd0 outdated

   265-            }
   266+        for (uint32_t p = 0; p < data.size(); p += 2) {
   267+            uint64_t p1 = data[p], p2 = data[p + 1];
   268+            uint64_t mask = (p1 ^ nGenerationMask1) | (p2 ^ nGenerationMask2);
   269+            data[p] = p1 & mask;
   270+            data[p + 1] = p2 & mask;
   

   ---

   ---

   

   dcousens commented at 3:24 am on April 26, 2016:

   Nice branch removal :)
8. 
   dcousens commented at 3:26 am on April 26, 2016: contributor

   light utACK 67d44f8, didn’t verify masking operations
9. Benchmark rolling bloom filter aa62b68745
10. More efficient bitsliced rolling Bloom filter

    This patch changes the implementation from one that stores 16 2-bit integers
    in one uint32_t's, to one that stores the first bit of 64 2-bit integers in
    one uint64_t and the second bit in another. This allows for 450x faster
    refreshing and 2.2x faster average speed.

    1953c40aa9
11. sipa force-pushed on Apr 28, 2016
12. 
    sipa commented at 12:56 pm on April 28, 2016: member

    Addressed @dcousens’s nits.
13. 
    gmaxwell commented at 4:02 pm on April 28, 2016: contributor

    utACK.
14. 
    dcousens commented at 4:40 am on April 30, 2016: contributor

    utACK 1953c40
15. 
    gmaxwell commented at 11:17 am on May 5, 2016: contributor

    ACK. (appears to work.)
16. laanwj merged this on May 9, 2016
17. laanwj closed this on May 9, 2016

    ---

18. laanwj referenced this in commit f17032f703 on May 9, 2016
19. 
    laanwj commented at 6:53 am on May 9, 2016: member

    utACK 1953c40
20. 
    rebroad commented at 2:03 am on December 21, 2016: contributor

    I’d like to understand this code - where do I start?
21. in src/bloom.cpp: in 1953c40aa9

    274 
    275     for (int n = 0; n < nHashFuncs; n++) {
    276-        uint32_t h = Hash(n, vKey);
    277-        put(h, nGeneration);
    278+        uint32_t h = RollingBloomHash(n, nTweak, vKey);
    279+        int bit = h & 0x3F;
    

    ---

    ---

    

    dcousens commented at 2:09 am on December 21, 2016:

    I wonder if it is confusing alternating between 0x3f and 63 a few times in this code…
22. 
    laanwj commented at 8:49 am on December 21, 2016: member

    I’d like to understand this code - where do I start?

    In this case it is the theory that is important to understand. With that, the code is pretty straightforward. Google “bloom filters”. Most notably the wikipedia page about Bloom filters has a lot of references to CS literature about various kinds of bloom filters, and the article itself may give basic understanding.

23. codablock referenced this in commit a536d807cf on Sep 16, 2017
24. codablock referenced this in commit eaa3e4e9a2 on Sep 19, 2017
25. codablock referenced this in commit 93be53e34e on Dec 21, 2017
26. zkbot referenced this in commit aa225ebb0b on Jan 24, 2020
27. zkbot referenced this in commit 74ff73abab on Jan 24, 2020
28. zkbot referenced this in commit be459619a8 on Mar 5, 2021
29. zkbot referenced this in commit 78de0cdf46 on Apr 15, 2021
30. MarcoFalke locked this on Sep 8, 2021

Contributors
sipa dcousens gmaxwell laanwj rebroad

Labels
Resource usage