Implement a runtime-creation-sized Bloom Filter

[matheus23]

Description

• Adds a bloom filter implementation runtime_sized::BloomFilter
• Splits out bloom filter implementations across modules
• Implements rejection sampling in HashIndexIterator (has no effect if the size is a power of two)

Link to issue

Fixes #4

Type of change

• [x] New feature (non-breaking change that adds functionality)
• [x] Refactor (non-breaking change that updates existing functionality)
• [x] Breaking change (fix or feature that would cause existing functionality to not work as expected)
• [x] This change requires a documentation update
• [x] Comments have been added/updated

Test plan (required)

• [x] Needs more tests. Consider this somewhat WIP.

[codecov[bot]]

Codecov Report

Merging #5 (9f19523) into main (ae5bda4) will increase coverage by 2.07%. The diff coverage is 73.45%.

@@            Coverage Diff             @@
##             main       #5      +/-   ##
==========================================
+ Coverage   71.42%   73.50%   +2.07%     
==========================================
  Files           2        5       +3     
  Lines          35      117      +82     
  Branches        6       15       +9     
==========================================
+ Hits           25       86      +61     
- Misses          7       21      +14     
- Partials        3       10       +7     

Files Changed	Coverage Δ
deterministic-bloom/src/lib.rs	100.00% <ø> (+28.12%)	:arrow_up:
deterministic-bloom/src/utils.rs	25.00% <0.00%> (-41.67%)	:arrow_down:
deterministic-bloom/src/const_size.rs	65.21% <65.21%> (ø)
deterministic-bloom/src/runtime_size.rs	77.77% <77.77%> (ø)
deterministic-bloom/src/common.rs	82.50% <82.50%> (ø)

[matheus23]

Argh, why does the benchmark bot have to ping Brooke? :sweat_smile:

[matheus23]

I looked a bit into what's happening with performance, and honestly I just think it's some kind of optimization not kicking in in one case vs. another.

Here's a call graph cpu cycle graph from the state in this PR:

vs. the state before the PR:

As you can see it's basically doing the same thing except in one case, to set bits in the bitvec it uses deref_mut whereas in the other case it's using set. For some reason the version with set is much faster than the version using deref_mut. Keep in mind in both cases this is using exactly the same code to set bits (the BitSlice::set method).

The thing that I mainly wanted to make sure was not the culprit are the changes in the HashIndexIterator::next function, but as you can see apparently that's using less time in the new version version before, so :man_shrugging:

[matheus23]

@appcypher Yeah, valid question. Generally I didn't need any functionality from Bytes (e.g. don't need the sharing/refcounting), so I went with the most "barebones" way that works. I actually kinda wanted to make BloomFilter { k_hashes: u32, bytes: [u8] } work, but it's difficult working with unsized types (e.g. missing a Clone implementation).