HomePhabricator

Switch to a more efficient rolling Bloom filter
086ee67d839bUnpublished

Unpublished Commit ยท Learn More

Repository Importing: This repository is still importing.

Description

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.

Details

Provenance
Pieter Wuille <pieter.wuille@gmail.com>Authored on Nov 27 2015, 12:20
deadalnixPushed on May 14 2017, 22:04
Parents
rABC92aa7311d64c: Merge pull request #6942
Branches
Unknown
Tags
Unknown

Event Timeline

Pieter Wuille <pieter.wuille@gmail.com> committed rABC086ee67d839b: Switch to a more efficient rolling Bloom filter (authored by Pieter Wuille <pieter.wuille@gmail.com>).Nov 28 2015, 17:53