sketch_bloom.nx
buildroot/runtime/sketch_bloom.nx
about
sketch_bloom.nx -- Bloom filter v2 (sovereign-tier with typed envelope).
Burton Howard Bloom 1970. Tracks n_inserted so the FPR envelope
reflects ACTUAL load, not just design-time spec. Companion to the
older runtime/bloom.nx (which lacks the envelope + counted state +
proper FPR-by-load reporting).
FPR FORMULA (Bloom 1970):
FPR = (1 - e^(-kn/m))^k
For k = (m/n) ln(2) optimal: FPR = 0.6185^(m/n)
We can't compute exp / pow in i64-only. Conservative approach:
tabulate FPR-by-(m/n) at integer ratios assuming OPTIMAL k. If the
caller chose non-optimal k, real FPR is worse than reported -- we
document this. v2 will swap in a tighter integer approximation.
LOSSLESS-LANGUAGE DISCIPLINE (doc 20):
contains -> 1 means "probably present" with envelope FPR; 0 means
"definitely absent" with envelope FPR = 0. Both cases ship the
ApproxI64 with NX_ENV_ABS / conf_ppb = 1e9 - fpr_ppb.
Complements sketch_cuckoo.nx (which supports delete). Bloom is more
space-efficient at high FPR; Cuckoo wins below ~3% FPR with delete.
dependencies 3 imports · 2 importers
imports: syscalls.nxmurmur3.nxsketch_types.nx
imported by: sketch_bloom_test.nxsketch_cuckoo_delete_vs_bloom_bench.nx
structs
| 29 | struct BloomS { |
consts
| none |
functions
| 39 | func nx_bs_is_pow2(n: i64) -> i64 {
called by 1: nx_bloom_alloc |
| 45 | func nx_bloom_alloc(cap_bits: i64, k: i64) -> *BloomS { |
| 67 | func nx_bloom_set_bit(bf: *BloomS, bit_idx: i64) -> i64 {
called by 1: nx_bloom_insert |
| 74 | func nx_bloom_get_bit(bf: *BloomS, bit_idx: i64) -> i64 {
called by 1: nx_bloom_contains |
| 85 | func nx_bloom_insert(bf: *BloomS, key: *u8, len: i64) -> i64 { |
| 99 | func nx_bloom_contains(bf: *BloomS, key: *u8, len: i64) -> i64 { |
| 120 | func nx_bloom_fpr_ppb(bf: *BloomS) -> i64 { |
| 144 | func nx_bloom_query(bf: *BloomS, key: *u8, len: i64) -> *ApproxI64 { |
| 155 | func nx_bloom_memory_bytes(bf: *BloomS) -> i64 { |
| 159 | func nx_bloom_load_ppt(bf: *BloomS) -> i64 {
called by 1: main |